A* Pathfinding Algorithm

How A* Pathfinding Works

1. Initialize

Start by adding the start node to the open set. Set the gScore of the start node to 0 and calculate its heuristic (hScore) to the end node.

💡 Pro Tip: The open set contains nodes to be evaluated. The start node is the first node in the open set.

2. Select Node with Lowest f(n)

From the open set, pick the node with the lowest f(n) = g(n) + h(n). This is the most promising node to explore next.

💡 Pro Tip: The node with the lowest f(n) is highlighted and expanded.

3. Check for Goal

If the current node is the end node, reconstruct the path by following the previous nodes.

💡 Pro Tip: If the end node is reached, the shortest path is traced back.

4. Explore Neighbors

For each neighbor of the current node, calculate tentative gScore. If this path is better, update the neighbor’s scores and set its previous node.

💡 Pro Tip: Neighbors are checked and updated if a better path is found.

5. Repeat

Continue the process until the open set is empty or the end node is reached.

💡 Pro Tip: The algorithm repeats until the shortest path is found or no path exists.

Key Concepts

f(n) = g(n) + h(n)

The core formula A* uses to find the most promising path to explore next.

g(n)

The exact cost of the path from the start node to node n.

h(n)

Heuristic function that estimates the cost from node n to the goal.

Optimality

A* is guaranteed to find the shortest path if the heuristic is admissible (never overestimates the true cost). "Manhattan distance" is used here.

Legend

Start Node

Click and drag to move

End Node

Click and drag to move

Wall

Click to add/remove

Visited Nodes

Shortest Path

How to Use

1. Create Your Maze

Click or drag on the grid to add or remove walls

2. Position Start & End

Drag the green and red nodes to set start and end points

3. Visualize

Click "Visualize A*" to find the shortest path

4. Experiment

Try different mazes and see how A* finds the path

About A*

A* is a popular pathfinding algorithm that finds the shortest path between two points efficiently.

âš¡

Optimal

Always finds the shortest path

🧠

Smart

Uses heuristics to be efficient

🎯

Versatile

Works with different grid layouts