A* in Javascript (with p5.js) not working

Question

I'm writing a pathfinding algorithm for a player located in a 2d array of squares. I want to find the shortest path from a to b and do it efficiently. I was working in java (Processing) before, and my function was working just fine.

boolean findPath(PVector down, PVector up, Square[][] board) {
  PVector start = up;
  PVector goal = down;

  ArrayList<Square> closedSet = new ArrayList<Square>();
  ArrayList<Square> openSet = new ArrayList<Square>();

  HashMap<Square, Square> cameFrom = new HashMap<Square, Square>((int)Math.pow(squares, 2));
  HashMap<Square, Float> gScore = new HashMap<Square, Float>((int)Math.pow(squares, 2));
  HashMap<Square, Float> fScore = new HashMap<Square, Float>((int)Math.pow(squares, 2));

  for (int i = 0; i<dungeon.floors.get(currentFloor).numSquares; i++) {
    for (int j = 0; j<dungeon.floors.get(currentFloor).numSquares; j++) {
      gScore.put(board[i][j], 1000.0);
    }
  }

  gScore.put(board[(int)start.x][(int)start.y], 0.0);
  fScore.put(board[(int)start.x][(int)start.y], heuristic(start, goal));

  openSet.add(board[(int)start.x][(int)start.y]);

  while (!openSet.isEmpty()) {
    Square current = board[(int)start.x][(int)start.y];
    float lowest = 1000;
    for (Square s : openSet) {
      if (fScore.get(s)<lowest) {
        lowest = fScore.get(s);
        current = s;
      }
    }
    if (current.locX == goal.x && current.locY == goal.y) {
      while (cameFrom.containsKey(current)) {
        current = cameFrom.get(current);
      }
      board[(int)start.x][(int)start.y].squareType = -3;
      return true;
    }
    openSet.remove(current);
    closedSet.add(current);
    //neighbors() returns an ArrayList of valid neighbors
    for (Square s : current.neighbors(board)) {
      if (closedSet.contains(s)) {
      } else {

        float tempG = gScore.get(current) + 1;
        if (!openSet.contains(s)) {
          openSet.add(s);
        } 
        if (tempG < gScore.get(s)) {

          cameFrom.put(s, current);
          gScore.put(s, tempG);
          fScore.put(s, gScore.get(s) + heuristic(new PVector(s.locX, s.locY), goal));
        }
      }
    }
  }

  return false;
}

float heuristic(PVector start, PVector goal) {
  return dist(start.x, start.y, goal.x, goal.y);
}

But I'm moving the game to Javascript, and I cannot tell where my code is going wrong. It is getting stuck on a square and adding it to the closedSet forever (hundreds of thousands of times). Here is my Javascript code -

this.findPath = function(f, _start, _goal) {
      var start = _start;
      var goal = _goal;

      var closedSet = [];
      var openSet = [];

      var squareScores = [];
      var startSquare = (start.x * numSquares) + start.y;

      for (var i = 0; i < numSquares; i++) {
         for (var j = 0; j < numSquares; j++) {
            squareScores.push(new MapSquare(dungeon.floors[f].board[i][j], 10000, 10000));
         }
      }

      squareScores[startSquare].gScore = 0;
      squareScores[startSquare].fScore = this.heuristic(start, goal);
      openSet.push(squareScores[startSquare]);

      while (openSet.length > 0) {
         var current = squareScores[startSquare];
         var lowest = 9999;
         for (var s = 0; s < squareScores.length; s++) {
            if (squareScores[s].fScore < lowest) {
               lowest = squareScores[s].fScore;
               current = squareScores[s];
            }
         }
         if (current.square.x == goal.x && current.square.y == goal.y) {
             return true;
         }

         openSet.splice(openSet.indexOf(current.square));  
         closedSet.push(current.square);

         var currentNeighbors = current.square.neighbors(dungeon.floors[f].board);
         for (var i = 0; i < currentNeighbors.length; i++) {
            var skip = false;
            for (let c of closedSet) {
               if (c.x == currentNeighbors[i].x && c.y == currentNeighbors[i].y) {
                  skip = true;
               }
            }
            if (skip) {
               continue;
            }
            else {
               var tempG = current.gScore + 1;

               var dontAdd = false;
               for (let o of openSet) {
                  if (o.x == currentNeighbors[i].x && o.y == currentNeighbors[i].y) {
                     dontAdd = true;
                  }
               }
               if (!dontAdd) {
                  openSet.push(currentNeighbors[i]);
               }
               var index = (currentNeighbors[i].x * numSquares) + currentNeighbors[i].y;
               if (tempG < squareScores[index].gScore) {
                  //cameFrom.push(gScore[i]);
                  console.log("update");

                  squareScores[index].gScore = tempG;
                  squareScores[index].fScore = squareScores[index].gScore + this.heuristic(squareScores[index].square.x, squareScores[index].square.y, goal.x, goal.y);
               }
            }
         }
      }
      return false;
   };

   //dist from player to goal
   this.heuristic = function(_x1, _y1, _x2, _y2) {
      return dist(_x1, _y1, _x2, _y2);
   };

My Javascript code looks a bit different because I have been trying to fix this for a few days, but I can't figure it out. What am I doing wrong? If the code needs clarification, please ask.

Answer 1

You're going to have to debug your code. That link is about debugging in Processing, but the same ideas apply to JavaScript and P5.js.

Specifically, you need to figure out exactly when the code's execution differs from what you expected it to do.

You can do this by adding console.log() statements to figure out the value of variables, which functions are called in what order, whether if statements are entered, how many times a loop iterates, etc.

If that doesn't work, you can also step through your code with a debugger. Every browser comes with a JavaScript debugger, which allows you to step through the code and examine the value of every variable. Again, the goal is to figure out exactly when the code does something different from what you expected it to do.

When you get it narrowed down to a few lines, if you still can't figure out how to fix it, then you can create an MCVE that isolates the problem without all the extra code around it. At that point it'll be much easier to help you. Good luck.