P5 Pathfinding Function Crashes Sketch


#1

I’m trying to write an A* pathfinding function to see how well it does in a snake game I’m programming based on The Coding Train’s coding challenge here: (https://www.youtube.com/watch?v=OMoVcohRgZA), but for some reason it goes in an infinite loop and crashes the sketch. From what I can tell, it shouldn’t do that. I’m basing my algorithm on this Wikipedia article: https://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm
I know it isn’t just because it’s taking a while to go through the entire grid array, because it will go until something like queue position 11000 while my width is 14 and height is 8, and it definitely should have found the snake’s head before that many queue positions.

(In the grid array air is 0, snake is 1, and food is 2)

Here’s the pathfinding function:

function pathfind() {
  
  let goal = food; // The food position (food is a PVector)
  
  // The head of the snake (snake.body.length-1 IS the head, I checked)
  let head = createVector( snake.body[ snake.body.length - 1 ].x, snake.body[ snake.body.length - 1 ].y );
  
  let queue = [ [ goal, 0 ] ];
  
  let selected = 0;
  
  function doPathfind() {
    let x = queue[selected][0].x;
    let y = queue[selected][0].y;
    let qCount = queue[selected][1];
    let aCells = [ // List of adjacent cells
      top    = [ createVector( x    , y - 1 ), qCount + 1 ],
      left   = [ createVector( x - 1, y     ), qCount + 1 ],
      bottom = [ createVector( x + 1, y     ), qCount + 1 ],
      right  = [ createVector( x    , y + 1 ), qCount + 1 ]
    ];
    
    for (i = 0; i < aCells; i++) {
      let cx = aCells[i][0].x;
      let cy = aCells[i][0].y;
      if ( cx == head.x && cy == head.y ) {
        aCells = [aCells[i],2];
        break;
      } else {
        if ( grid[cx][cy] == 1 ) {
          aCells[i] = -1;
        } else {
          for (j = 0; j < queue; j++) {
            if ( aCells[i][0] == queue[j][0] && queue[j][1] <= aCells[i][1] ) {
              aCells[i] = -1;
            }
          }
        }
      }
    }
    for (i = 0; i < aCells.length; i++) {
      if ( aCells[i] !== -1 || aCells[i] !== 2) {
        queue.push( aCells[i] );
      }
    }
    if ( aCells[1] == 2 ) {
      return queue;
    } else {
      selected++;
    }
  }
  
  if (height > width) {
    for (i = 0; i < 2 * height; i++) {
      doPathfind();
    }
  } else {
    for (i = 0; i < 2 * width; i++) {
      doPathfind();
    }
  }
}

Here’s the code for the function that sets up the grid as well, in case that will help solve it:

// Identify all the grid squares as either air (0), snake (1), or food (2)
function updateGrid() {
  for (i = 0; i < grid.length; i++) {
    for (j = 0; j < height; j++) {
      // Go through every element of the snake's body and set the grid position there to 1
      for (s = 0; s < snake.body.length; s++) {
        if (i == snake.body[s].x && j == snake.body[s].y) {
          grid[i][j] = 1;
        }
      }
      if (grid[i][j] !== 1) {
        if (i == food.x && j == food.y) {
          grid[i][j] = 2;
        } else {
          grid[i][j] = 0;
        }
      }
    }
  }
}

I’m sure it’s something simple like not checking for the head correctly, but I appreciate any help! :smiley:


#2

In the future, if you are asking a question similar to this, please provide enough code to reproduce your error.

That being said, on your first for loop, did you intend to use ACells.length?

 for (i = 0; i < aCells; i++)

#3

Thank you for the advice, I’ll try to follow that on any future questions I post here. And yes, I did intend to use that, but now an error pops up. “Cannot read property ‘-0.43366638673146873’ of undefined (main: line 113)”
Before, the error read “Cannot read property ‘2’ of undefined”

Here’s the full code, stripped down to what reproduces the problem:
https://editor.p5js.org/OrangeC7/sketches/H1v9CPuuX


#4

This is telling you to look at line 113:

      if ( grid[cx][cy] == 1 )

The console errors usually gives very specific information about what went wrong. In this case, it looks like you were trying to use a float as an index for an array. In fact, I inserted some debug code right above that line:

   db("cx: " + cx);
   db("cy: " + cy);

and it showed me that cx and cy are not integers:

cx: 3.3832958893000367 
cy: 0.6848371079120508

That being said, I highly encourage you to start learning how to interpret the console errors. Being able to debug your own code is a skill that will help you in the long run.