Understanding A* Pathfinding: Breaking Down the getPath Function

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 the start node).
• 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-score of the start node is set to 0 (no movement cost yet).
• The h-score is calculated using a heuristic function (Grid.heuristic), estimating the distance from the start node to the destination.
• The f-score is computed as g + h to 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 openSet to find the node with the smallest f value, 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 previous references 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 current node is removed from openSet, as it has been processed.
• The current node is added to closedSet, 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).

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-score is updated for the neighbor (tempG = current.g + 1, assuming uniform cost movement).
• If the neighbor is not in openSetor its g-score improves, it is updated with:
  • previous set to current (for path reconstruction later).
  • Recomputed h and f scores.

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:

1. Initializing the starting node and setting up openSet.
2. Iteratively choosing the node with the lowest f-score.
3. Checking if the goal is reached.
4. Moving nodes from openSet to closedSet to prevent re-evaluation.
5. Updating neighbors’ scores and paths dynamically.
6. 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