A* Pathfinding, path not showing up

Question

I have this code, in script (p5.js), I am running it and works as expected, but the moment I include the path code, that helps in finding the previous parents to form a path to the end goal, the browser crushes, as the images show. It fist colors the 3 cells then crashes. Here is the code.

    var col = 12, row = 12, grid = new Array(col), openSet = [], closeSet = [], start, end, w, h, path = [];

function removefromArray(array_, element){
    for(var i = array_.length - 1; i >= 0; i--){
        if(array_[i] == element){
            array_.splice(i, 1);
        }
    }
}

function heuristic(a, b){
    var distance = abs(a.i - b.i) + abs(a.j - b.j);
    return distance;
}

function Spot(i, j){
    this.i = i;
    this.j = j;
    this.f = 0;
    this.g = 0;
    this.h = 0;
    this.neighbor = [];
    this.parent = undefined;
    this.wall = false;
    

    this.show = function (color){
        
        fill(color);
        if(this.wall){
            fill(0);
        }
        noStroke();
        rect(this.i * w, this.j * h, w - 1, h - 1);
    }

    this.addNeighbor = function(grid){
        var i = this.i, j = this.j;
        if(i < col - 1){
            this.neighbor.push(grid[i+1] [j]);
        }
        if(i > 0){
            this.neighbor.push(grid[i-1] [j]);
        }
        if(j < row-1){
            this.neighbor.push(grid[i] [j+1]);
        }
        if(j > 0){
            this.neighbor.push(grid[i] [j-1]);
        }
    }

}

function setup(){
    createCanvas(500,500);
    console.log("A*");

    w = width / col;
    h = height / row;
    for( var i = 0; i< col; i++){
        grid[i] = new Array(row);
    }
    //Adding a spot
    for( var i = 0; i< col; i++){
        for( var j = 0; j< row; j++){
            grid[i][j] = new Spot(i,j); 
        }
    }
    //Adding a neighbor
    for( var i = 0; i< col; i++){
        for( var j = 0; j< row; j++){
            grid[i][j].addNeighbor(grid);  
        }
    }
    start = grid[0][0];
    end = grid[col - 1][row - 1];

    openSet.push(start);
}
function draw(){
    var winner = 0;
    if(openSet.length > 0){
        for( var i = 0; i< openSet.length; i++){
            if(openSet[i].f < openSet[winner].f){
                winner = i; 
            }
        }
        var current = openSet[winner]; 
        if(current === end){
            noLoop();
            console.log("Done!");
        }

        removefromArray(openSet, current);
        closeSet.push(current);

        var neighbors = current.neighbor;
        for(var i = 0; i < neighbors.length; i++){
            var the_neighbor = neighbors[i];

            if(!closeSet.includes(the_neighbor)){
                var tempG  = current.g + 1;
            }
            if(openSet.includes(the_neighbor)){
                if(tempG < the_neighbor.g){
                    the_neighbor.g = tempG;
                }
            }
            else{
                the_neighbor.g = tempG;
                openSet.push(the_neighbor);
            }
            the_neighbor.h = heuristic(the_neighbor, end);
            the_neighbor.f = the_neighbor.g + the_neighbor.h;
            the_neighbor.parent = current; // the previous node
        }
    }
    else{
        // no solution
    }

    background(0)
    for( var i = 0; i< col; i++){
        for( var j = 0; j< row; j++){
            grid[i][j].show(color(255)); 
        }
    }

    for( var i = 0; i< openSet.length; i++){
        openSet[i].show(color("green"));
    }

    for( var i = 0; i< closeSet.length; i++){
        closeSet[i].show(color("red"));
    }

    // path = [];
    // var temp = current;
    // path.push(temp);
    // while(temp.parent){
    //     path.push(temp.parent);
    //     temp = temp.parent;
    // }

    // for(var i = 0; i < path.length; i++){
    //     path[i].show(color(0,0,255));
    // }
    
}

If I try to remove the comments slash for this last part, the system will run for about 5secs then crashes. Someone with the solution, I will highly appreciate.

Result when the path part is uncommented

user_229247 · Answer

You are generating a cycle somehow in the chain of parents (i.e. Spot A has parent Spot B and Spot B has parent Spot A), which is causing an infinite loop. I'm not sure exactly where/why this is happening. Your code is a bit hard to read. You should avoid nondescript one letter variable & property names.

Also there are several scoping issues that may be causing unexpected behavior. The keyword var is the worst element of any programming language since goto and it should be scoured from the face of the internet with the fire of 1000 suns. Please use let. See the comments below for more explanation.

var col = 12,
  row = 12,
  grid = new Array(col),
  openSet = [],
  closeSet = [],
  start, end, w, h, path = [];

function removefromArray(array_, element) {
  for (let i = array_.length - 1; i >= 0; i--) {
    if (array_[i] == element) {
      array_.splice(i, 1);
    }
  }
}

function heuristic(a, b) {
  var distance = abs(a.i - b.i) + abs(a.j - b.j);
  return distance;
}

function Spot(i, j) {
  this.i = i;
  this.j = j;
  this.f = 0;
  this.g = 0;
  this.h = 0;
  this.neighbor = [];
  this.parent = undefined;
  this.wall = false;

  this.show = function(color) {

    fill(color);
    if (this.wall) {
      fill(0);
    }
    noStroke();
    rect(this.i * w, this.j * h, w - 1, h - 1);
  }

  this.addNeighbor = function(grid) {
    let i = this.i,
      j = this.j;
    if (i < col - 1) {
      this.neighbor.push(grid[i + 1][j]);
    }
    if (i > 0) {
      this.neighbor.push(grid[i - 1][j]);
    }
    if (j < row - 1) {
      this.neighbor.push(grid[i][j + 1]);
    }
    if (j > 0) {
      this.neighbor.push(grid[i][j - 1]);
    }
  }

}

function setup() {
  createCanvas(500, 500);
  console.log("A*");

  w = width / col;
  h = height / row;
  for (let i = 0; i < col; i++) {
    grid[i] = new Array(row);
  }
  //Adding a spot
  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      grid[i][j] = new Spot(i, j);
    }
  }
  //Adding a neighbor
  for (let i = 0; i < col; i++) {
    for (let j = 0; j < row; j++) {
      grid[i][j].addNeighbor(grid);
    }
  }
  start = grid[0][0];
  end = grid[col - 1][row - 1];

  openSet.push(start);
}

function draw() {
  let winner = 0;
  let current
  if (openSet.length > 0) {
    for (let i = 0; i < openSet.length; i++) {
      if (openSet[i].f < openSet[winner].f) {
        winner = i;
      }
    }
    current = openSet[winner];
    if (current === end) {
      noLoop();
      console.log("Done!");
    }

    removefromArray(openSet, current);
    closeSet.push(current);

    var neighbors = current.neighbor;
    for (let i = 0; i < neighbors.length; i++) {
      var the_neighbor = neighbors[i];

      // The use of var here results in very weird behavior
      // where tempG's value is preserved from the previous 
      // iteration of this loop even when it is not assigned
      // a value. If that is desired you should declare this
      // variable outside of the for loop.
      //
      // If you always use let isntead of var you will get
      // errors instead of bizarre behavior. That will help
      // you be deliberate about your variable scoping.
      if (!closeSet.includes(the_neighbor)) {
        var tempG = current.g + 1;
      } else {
        print('tempG not set');
      }
      if (openSet.includes(the_neighbor)) {
        if (tempG < the_neighbor.g) {
          the_neighbor.g = tempG;
        }
      } else {
        print(`tempG: ${tempG}`);
        the_neighbor.g = tempG;
        openSet.push(the_neighbor);
        print(`openSet: ${openSet.length}`);
      }
      the_neighbor.h = heuristic(the_neighbor, end);
      the_neighbor.f = the_neighbor.g + the_neighbor.h;
      the_neighbor.parent = current; // the previous node
    }
  } else {
    // no solution
  }

  background(0)
  for (let i = 0; i < col; i++) {
    for (var j = 0; j < row; j++) {
      grid[i][j].show(color(255));
    }
  }

  for (let i = 0; i < openSet.length; i++) {
    openSet[i].show(color("green"));
  }

  for (let i = 0; i < closeSet.length; i++) {
    closeSet[i].show(color("red"));
  }

  path = [];
  let temp = current;
  path.push(temp);
  while (temp.parent) {
    if (path.includes(temp.parent)) {
      print('Cycle detected!');
      console.log({ current: { i: temp.i, j: temp.j }, parent: { i: temp.parent.i, j: temp.parent.j } });
      break;
    }
    path.push(temp.parent);
    temp = temp.parent;
  }

  for (let i = 0; i < path.length; i++) {
    path[i].show(color(0, 0, 255));
  }

}

Update: Infinite Loop Fix

The part of your code that updates neighbors deviates from the definition of A* pretty substantially. Here's what I came up with (single letter variable names replaces with meaningful names):

let tentativePathScore = current.shortestPathScore + 1;
if (the_neighbor.heuristicScore === undefined) {
  the_neighbor.heuristicScore = heuristic(the_neighbor, end);
}

if (the_neighbor.combinedScore === undefined ||
    tentativePathScore + the_neighbor.heuristicScore < the_neighbor.combinedScore) {
  
  // Update the path score and combined score for this neighbor.
  the_neighbor.shortestPathScore = tentativePathScore;
  the_neighbor.combinedScore = the_neighbor.shortestPathScore + the_neighbor.heuristicScore;
  the_neighbor.parent = current; // the previous node
  
  if (!openSet.includes(the_neighbor)) {
    openSet.push(the_neighbor);
  }
}

And here's a working snippet with walls added:

let col = 12,
    row = 12,
    grid = new Array(col),
    openSet = [],
    closeSet = [],
    start, end, w, h, path = [];

function removefromArray(array_, element) {
    for (let i = array_.length - 1; i >= 0; i--) {
        if (array_[i] == element) {
            array_.splice(i, 1);
        }
    }
}

function heuristic(a, b) {
    if (a.wall) {
        return Infinity;
    }
    
    return abs(a.i - b.i) + abs(a.j - b.j);
}

function Spot(i, j) {
    this.i = i;
    this.j = j;
    this.combinedScore = undefined;
    this.shortestPathScore = undefined;
    this.heuristicScore = undefined;
    this.neighbor = [];
    this.parent = undefined;
    this.wall = false;

    this.show = function(color) {
        fill(color);
        if (this.wall) {
            fill(0);
        }
        noStroke();
        rect(this.i * w, this.j * h, w - 1, h - 1);
    }

    this.addNeighbor = function(grid) {
        let i = this.i,
            j = this.j;
        if (i < col - 1) {
            this.neighbor.push(grid[i + 1][j]);
        }
        if (i > 0) {
            this.neighbor.push(grid[i - 1][j]);
        }
        if (j < row - 1) {
            this.neighbor.push(grid[i][j + 1]);
        }
        if (j > 0) {
            this.neighbor.push(grid[i][j - 1]);
        }
    }

}

function setup() {
    createCanvas(500, 500);
    console.log("A*");

    w = width / col;
    h = height / row;
    for (let i = 0; i < col; i++) {
        grid[i] = new Array(row);
    }
    //Adding a spot
    for (let i = 0; i < col; i++) {
        for (let j = 0; j < row; j++) {
            grid[i][j] = new Spot(i, j);
        }
    }
    //Adding a neighbor
    for (let i = 0; i < col; i++) {
        for (let j = 0; j < row; j++) {
            grid[i][j].addNeighbor(grid);
        }
    }
    // make walls
    for (let i = 0; i < col; i++) {
        for (let j = 0; j < row; j++) {
            if ((i > 1 || j > 1) && (i < col - 2 || j < row - 2) && random() < 0.2) {
                grid[i][j].wall = true;
            }
        }
    }
    
    start = grid[0][0];
    end = grid[col - 1][row - 1];
    
    start.shortestPathScore = 0;
    start.heuristicScore = heuristic(start, end);
    start.combinedScore = start.shortestPathScore + start.heuristicScore;

    openSet.push(start);
}

function draw() {
    let winner = 0;
    let current;
    if (openSet.length > 0) {
        for (let i = 0; i < openSet.length; i++) {
            if (openSet[i].combinedScore < openSet[winner].combinedScore) {
                winner = i;
            }
        }
        current = openSet[winner];
        if (current === end) {
            noLoop();
            console.log("Done!");
        }

        removefromArray(openSet, current);
        closeSet.push(current);

        var neighbors = current.neighbor;
        for (let i = 0; i < neighbors.length; i++) {
            var the_neighbor = neighbors[i];

            let tentativePathScore = current.shortestPathScore + 1;
            if (the_neighbor.heuristicScore === undefined) {
                the_neighbor.heuristicScore = heuristic(the_neighbor, end);
            }
            
            if (the_neighbor.combinedScore === undefined ||
                    tentativePathScore + the_neighbor.heuristicScore < the_neighbor.combinedScore) {
                
                // Update the path score and combined score for this neighbor.
                the_neighbor.shortestPathScore = tentativePathScore;
                the_neighbor.combinedScore = the_neighbor.shortestPathScore + the_neighbor.heuristicScore;
                the_neighbor.parent = current; // the previous node
                
                if (!openSet.includes(the_neighbor)) {
                    openSet.push(the_neighbor);
                }
            }
        }
    } else {
        // no solution
    }

    background(0)
    for (let i = 0; i < col; i++) {
        for (let j = 0; j < row; j++) {
            grid[i][j].show(color(255));
        }
    }

    for (let i = 0; i < openSet.length; i++) {
        openSet[i].show(color("green"));
    }

    for (let i = 0; i < closeSet.length; i++) {
        closeSet[i].show(color("red"));
    }

    path = [];
    let temp = current;
    path.push(temp);
    while (temp.parent) {
        if (path.includes(temp.parent)) {
            print('Cycle detected!');
            break;
        }
        path.push(temp.parent);
        temp = temp.parent;
    }

    for (let i = 0; i < path.length; i++) {
        path[i].show(color(0, 0, 255));
    }

}

A* Pathfinding, path not showing up

1 Answers

Update: Infinite Loop Fix