Pathfinding is a fundamental concept in game development and artificial intelligence, helping agents navigate through obstacles efficiently. One of the most widely used algorithms for pathfinding is the A* (A-star) algorithm. In this article, we will break down the getPath function, which implements A* search to find the shortest path between a start node and a destination node.
What is A* Pathfinding?
A* is an informed search algorithm that finds the shortest path from a start node to a destination node using a combination of:
- g-score ( ): The cost to reach the current node from the start node.
- h-score ( ): The heuristic estimate of the cost from the current node to the destination.
- f-score ( ): The total estimated cost (i.e.,
f = g + h).
The algorithm prioritizes exploring nodes with the lowest f value, ensuring an efficient and optimal path to the goal.
Breaking Down the getPath Function
Step 1: Initialize the Algorithm
this.path = []; this.openSet = [start]; this.closedSet = [];
Here, the algorithm initializes:
this.path: An array to store the final path.this.openSet: A list of nodes to be evaluated (starting with thestartnode).this.closedSet: A list of nodes that have already been evaluated.
Step 2: Set Up the Starting Node
start.g = 0; start.h = Grid.heuristic(start, destination); start.f = start.g + start.h;
- The
g-scoreof the start node is set to0(no movement cost yet). - The
h-scoreis calculated using a heuristic function (Grid.heuristic), estimating the distance from the start node to the destination. - The
f-scoreis computed asg + hto prioritize nodes.
Step 3: Begin the Main Loop
while (this.openSet.length > 0) {The algorithm iterates as long as there are nodes left in openSet (meaning there are still nodes to explore).
Step 4: Find the Node with the Lowest f-score
let current = this.openSet[0];
for (let node of this.openSet) {
if (node.f < current.f) {
current = node;
}
}- The algorithm searches
openSetto find the node with the smallestfvalue, prioritizing nodes that are expected to reach the goal faster.
Step 5: Check If Destination is Reached
if (current === destination) {
this.path = [];
while (current) {
this.path.push(current);
current = current.previous;
}
this.path.reverse();
return this.path;
}- If the current node is the destination, the algorithm reconstructs the path by tracing back through the
previousreferences and returns it. - The path is reversed to present it in the correct order (from start to destination).
Step 6: Move Current Node from openSet to closedSet
this.openSet = this.openSet.filter(s => s !== current); this.closedSet.push(current);
- The
currentnode is removed fromopenSet, as it has been processed. - The
currentnode is added toclosedSet, preventing it from being re-evaluated.
Step 7: Process Neighbors
for (let neighbor of current.neighbours) {
if (!this.closedSet.includes(neighbor) && !neighbor.wall && !neighbor.agent) {- The algorithm loops through
current‘s neighbors, filtering out nodes that are:- Already in
closedSet(processed nodes). - Walls (obstacles).
- Agents (other entities that may block movement).
- Already in
Step 8: Calculate g-score and Update Neighbor
let tempG = current.g + 1;
if (!this.openSet.includes(neighbor) || tempG < neighbor.g) {
neighbor.previous = current;
neighbor.g = tempG;
neighbor.h = Grid.heuristic(neighbor, destination);
neighbor.f = neighbor.g + neighbor.h;- The
g-scoreis updated for the neighbor (tempG = current.g + 1, assuming uniform cost movement). - If the neighbor is not in
openSetor itsg-scoreimproves, it is updated with:previousset tocurrent(for path reconstruction later).- Recomputed
handfscores.
Step 9: Add Neighbor to openSet if Necessary
if (!this.openSet.includes(neighbor)) {
this.openSet.push(neighbor);
}- If the neighbor was not already in
openSet, it is added so it can be considered in future iterations.
Step 10: Return Empty Path if No Solution Found
return [];
- If the loop exits without finding the destination, no valid path exists, and an empty array is returned.
Summary
This implementation of A* pathfinding efficiently finds the shortest path in a grid-based environment by:
- Initializing the starting node and setting up
openSet. - Iteratively choosing the node with the lowest
f-score. - Checking if the goal is reached.
- Moving nodes from
openSettoclosedSetto prevent re-evaluation. - Updating neighbors’ scores and paths dynamically.
- Returning the optimal path or an empty array if no path exists.
This method is particularly useful in game AI, robotics, and navigation systems, ensuring intelligent movement across a map while avoiding obstacles efficiently.
Example: https://run.ancientbrain.com/run.php?world=5488323698
Full Code
getPath(start, destination) {
this.path = [];
this.openSet = [start];
this.closedSet = [];
start.g = 0;
start.h = Grid.heuristic(start, destination);
start.f = start.g + start.h;
while (this.openSet.length > 0) {
// Finds the node in openSet with the lowest f-score (estimated total cost)
let current = this.openSet[0]; // Assume the first element has the lowest f-score
for (let node of this.openSet) {
if (node.f < current.f) {
current = node; // Update current if a node with a lower f-score is found
}
}
if (current === destination) {
this.path = [];
while (current) {
this.path.push(current);
current = current.previous;
}
this.path.reverse();
return this.path;
}
this.openSet = this.openSet.filter(s => s !== current);
this.closedSet.push(current);
for (let neighbor of current.neighbours) {
if (!this.closedSet.includes(neighbor) && !neighbor.wall && !neighbor.agent) {
let tempG = current.g + 1;
if (!this.openSet.includes(neighbor) || tempG < neighbor.g) {
neighbor.previous = current;
neighbor.g = tempG;
neighbor.h = Grid.heuristic(neighbor, destination);
neighbor.f = neighbor.g + neighbor.h;
if (!this.openSet.includes(neighbor)) {
this.openSet.push(neighbor);
}
}
}
}
}
return [];
}Credits: TheCodingTrain & AncientBrain
