Understanding the A* Pathfinding Algorithm Using a Maze Game

Ready to begin? Let's start with a fun maze game:

1. Your task is to find a path from the start (blue) to the goal (green) within a grid map.
2. Rules:
   • The blue square indicates your current position.
   • White cells are traversable spaces.
   • Black cells are walls that you cannot pass through.
3. Goal: Reach the goal in the fewest steps possible.

Try to find the shortest path to advance to the next level!

Found the path? How many steps did it take? Now let's examine how the A* algorithm solves this problem.

Introduction

In game development, navigation systems, and robotic path planning, we often need to find an optimal path from a starting point to a goal. A* (A-Star) is a highly efficient and widely used pathfinding algorithm for such tasks.

For beginners, simply reading the algorithm's theory isn't enough. You need to understand how A* operates in practice. This article uses a specific maze level (level1) as an example to delve into the A* implementation. We'll explain the data structures, algorithm steps, key code snippets, and guide you with visualizations to help you get started easily.

Why Choose A*?

A* combines the precision of Dijkstra's algorithm with the heuristic guidance of a best-first search. It evaluates nodes using three metrics:

• g-score: The actual cost spent so far along the path (distance, time, etc.).
• h-score (heuristic): An estimated cost from the current node to the goal node. Common heuristics include Manhattan distance.
• f-score = g-score + h-score: The total estimated cost, used to decide which node to explore next.

By using the f-score, A* can prioritize exploring paths that are more likely to lead toward the goal, thus reducing unnecessary searches.

Example Level Explanation

Below is the level1 maze data, an 8x8 grid. Each cell type is represented as follows:

• Blue square: Your current position
• Green square: The goal
• Black square: A wall (impassable)
• White square: Traversable space

Data Structures and Algorithm Flow

To implement A*, you need two lists:

1. Open List: Contains nodes that are candidates to be processed.
2. Closed List: Contains nodes that have been processed to avoid revisiting them.

Nodes: In a grid maze, each traversable cell can be considered a node. Each node stores at least the following information:

• Position (x, y) coordinates
• g-score (cost from the start node to this node)
• h-score (estimated cost from this node to the goal)
• f-score (g + h)
• from (which node it came from, used for reconstructing the final path)

Steps of the A* Algorithm

1. Initialization:

   • Add the start node to the open list.
   • For the start node, g=0 (no cost yet), h is the Manhattan distance to the goal, and f=g+h.
   • All other nodes have their g and f initialized to -1 (unknown).

2. Selecting the Current Node:

   • Choose the node in the open list with the lowest f-score as the current node.
   • Initially, only the start node is in the open list, so that's your current node.

3. Check if Goal Reached:

   • If the current node is the goal, you've found the optimal path. Exit the loop.

4. Expanding Neighboring Nodes:

   • For each traversable neighbor (up, down, left, right) of the current node:
     • Calculate the new g-score (current.g + 1).
     • If the neighbor is not in the open list, or this path is better than a previously found one (lower g-score), update the neighbor's g, h, f, and from fields to record the best path so far.

5. Updating Lists:

   • Remove the current node from the open list and add it to the closed list.
   • Continue choosing the next node with the lowest f-score from the open list as the current node. Repeat until the goal is found or the open list is empty.

Heuristic Function

In a grid map, we use the Manhattan distance as the heuristic:

h = |x1 - x2| + |y1 - y2|

Where (x1, y1) is the current node position and (x2, y2) is the goal position. This gives a quick estimate of the minimum steps needed to reach the goal (ignoring obstacles).

Example Code (TypeScript)

Below is a simplified A* code example, with comments to help beginners understand each step of the logic.

interface Node {
  x: number;
  y: number;
  g: number;
  h: number;
  f: number;
  from?: Node;
  isWall: boolean;
}

function heuristic(a: Node, b: Node): number {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

function aStar(start: Node, goal: Node, grid: Node[][]): Node[] | null {
  const openList: Node[] = [];
  const closed: boolean[][] = Array.from({ length: grid.length }, () =>
    Array(grid[0].length).fill(false),
  );

  start.g = 0;
  start.h = heuristic(start, goal);
  start.f = start.g + start.h;

  openList.push(start);

  while (openList.length > 0) {
    // 1. Find the node with the lowest f-score as the current node
    let current = openList[0];
    let currentIndex = 0;
    for (let i = 1; i < openList.length; i++) {
      if (openList[i].f < current.f) {
        current = openList[i];
        currentIndex = i;
      }
    }

    // If we’ve reached the goal, reconstruct the path
    if (current.x === goal.x && current.y === goal.y) {
      return reconstructPath(current);
    }

    // Move current node from open list to closed list
    openList.splice(currentIndex, 1);
    closed[current.y][current.x] = true;

    // Get neighbors (up, down, left, right)
    const neighbors = getNeighbors(current, grid);
    for (const neighbor of neighbors) {
      if (neighbor.isWall || closed[neighbor.y][neighbor.x]) continue;

      const tentativeG = current.g + 1;
      const inOpen = openList.includes(neighbor);

      // If the neighbor is not in openList or this path is better
      if (!inOpen || tentativeG < neighbor.g) {
        neighbor.from = current;
        neighbor.g = tentativeG;
        neighbor.h = heuristic(neighbor, goal);
        neighbor.f = neighbor.g + neighbor.h;
        if (!inOpen) openList.push(neighbor);
      }
    }
  }

  return null; // No path found
}

function reconstructPath(node: Node): Node[] {
  const path: Node[] = [];
  let current: Node | undefined = node;
  while (current) {
    path.push(current);
    current = current.from;
  }
  return path.reverse();
}

function getNeighbors(node: Node, grid: Node[][]): Node[] {
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const neighbors: Node[] = [];
  for (const [dx, dy] of dirs) {
    const nx = node.x + dx;
    const ny = node.y + dy;
    if (ny >= 0 && ny < grid.length && nx >= 0 && nx < grid[0].length) {
      neighbors.push(grid[ny][nx]);
    }
  }
  return neighbors;
}

In the maze challenge's debug mode, you can observe the algorithm's execution process in a visualized interface:

• Yellow nodes: Candidates in the open list (waiting to be explored)
• Blue nodes: Visited and placed into the closed list
• Hovering over a node allows you to view its g, h, f values and its origin node.

By stepping through the algorithm, you'll see how it continuously selects the node with the lowest f-score, navigates around walls, and eventually finds the optimal path to the goal.

Optimization and Beyond

In this example, we used a simple array for the open list, which requires linear searches to find the lowest f-score node. While fine for small grids, for larger maps you can consider:

• Using a priority queue or binary heap to improve performance in selecting the next node.
• Trying different heuristics (like Euclidean distance or custom heuristics) to suit different scenarios.
• Employing memory optimization techniques (such as multi-level map partitioning or precomputed heuristic values) in large-scale environments.

After mastering these basics, you'll be well-equipped to apply A* to more complex projects.

Conclusion

Through this article and the provided level example, you've learned how the A* algorithm operates and how to implement it. Now, why not try coding it yourself and deepen your understanding of A*?