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:
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:
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?
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.