javascriptpath-findinga-star

Doubts about A* (Astar) pathfinding algorithm


First of all, I am new with pathfinding algorithms.

I am trying to make a simple pathfinding program using A* algorithm. It can move diagonally and uses euclidean distance to calculate heuristic (closest path). By the way, I am using p5.js.

The program is finished and it seems like working. But when I compare it with other programs available on internet, I can not get the same results as you can see below: enter image description here

The image above is the result of program that I made. Here is the colors explanation:

Here is the most important part of code:

// Neighbors
let directions = [];
// East
directions[0] = createVector(currentNode.pos.x + 1, currentNode.pos.y);
// West
directions[1] = createVector(currentNode.pos.x - 1, currentNode.pos.y);
// North
directions[2] = createVector(currentNode.pos.x, currentNode.pos.y - 1);
// South
directions[3] = createVector(currentNode.pos.x, currentNode.pos.y + 1);
// Southeast
directions[4] = createVector(currentNode.pos.x + 1, currentNode.pos.y + 1);
// Southwest
directions[5] = createVector(currentNode.pos.x - 1, currentNode.pos.y + 1);
// Northeast
directions[6] = createVector(currentNode.pos.x - 1, currentNode.pos.y + 1);
// Nortwest
directions[7] = createVector(currentNode.pos.x - 1, currentNode.pos.y - 1);

for(let i = 0; i < directions.length; i++) {
  // Is not wall and is not in closed list
  if (isValid(directions[i])) {
    // Cost from initial point
    const g = currentNode.g + 1;
    // Cost till destination point
    const h = euclideanDistance(directions[i]);
    // Make new node based on current square
    const newNode = new Node(currentNode, directions[i], g, h);
    
    // If it is inside open list, get index
    const index = openListContainsNode(newNode);
    if (!index) {
      // If it is not inside open list add it
      openList.push(newNode);
    } else if(index && openList[index].f < newNode.f) { // f is the best estimated cost until destination
      // If there is a better path until destination, remove it from open list and add it again (but this time, with closer parent node)
      openList.push(newNode);
      openList.splice(index, 1);
    }
  }
};

When I test the result on others programs available on internet, I get a different result, as you can see at image below:

enter image description here

Source: https://qiao.github.io/PathFinding.js/visual/

This is my code available in p5js editor: https://editor.p5js.org/italoricardogeske/sketches/7H8Q9iIVl

In my program, I get a lot of holes in closed list (blue squares), while in others programs there is no holes. Any ideas of what cause that problem?


Solution

  • After some research I could find out why I was getting holes in my blue squares. I thought it was negative values being returned from euclideanDistance(), but I was wrong.

    The problem was the "else if" condition

    It had to be

    openList[index].f > newNode.f

    The newNode.f had to be less than actual node.

    enter image description here