Pathfinding (A*)
Artificial Intelligence in action. Draw walls and watch the algorithm find the most efficient route.
The A* Search Algorithm
A* (A-star) is the gold standard for shortest path finding, combining Dijkstra�s algorithm with a heuristic. The evaluation function is f(n) = g(n) + h(n), where g(n) is the actual cost from the start node, and h(n) is the estimated cost to the goal. The heuristic guides the search towards the goal, dramatically reducing the number of nodes explored compared to uninformed search.
How A* Works Step by Step
1) Start at the initial node. 2) Expand the node with the lowest f(n) from the open set. 3) For each neighbour, calculate g(n) and h(n). 4) Add unexplored neighbours to the open set. 5) Repeat until the goal is reached or the open set is empty. The algorithm guarantees the shortest path if the heuristic is admissible (never overestimates the true cost).
Heuristic Functions
Manhattan distance (|x1-x2|+|y1-y2|) is optimal for grid movements restricted to four directions. Euclidean distance (v((x1-x2)�+(y1-y2)�)) works for any-angle pathfinding. Setting h=0 degrades A* to Dijkstra�s algorithm (exhaustive but slow). Overestimating the heuristic makes A* greedy (fast but potentially suboptimal).
Pathfinding in the Real World
GPS navigation (Google Maps, Waze), video game AI, robot navigation, network packet routing, and logistics and delivery optimisation all rely on pathfinding algorithms. A* was developed by Peter Hart, Nils Nilsson, and Bertram Raphael at Stanford Research Institute in 1968 � originally for navigating the Shakey robot.
Experiments to Try
- Compare A* vs Dijkstra � watch how many nodes each explores
- Create a maze and observe the search pattern
- Move the goal to different positions and see how the search adapts
- Test Manhattan vs Euclidean heuristic on the same map
A* Algorithm
A* (A-star) selects the next node to explore by minimising f(n) = g(n) + h(n), where g(n) is the exact cost from start to node n, and h(n) is a heuristic estimate of cost from n to the goal. With an admissible heuristic (never overestimates), A* is guaranteed to find the shortest path. Common heuristics: Manhattan distance (grids), Euclidean distance (continuous space).
Dijkstra vs A*
Dijkstra’s algorithm is A* with h(n) = 0 it expands in all directions equally, guaranteed to find the shortest path on weighted graphs. A* focuses the search towards the goal using the heuristic, exploring far fewer nodes on typical maps. On unweighted grids, BFS (breadth-first search) finds the shortest path and is simpler; DFS finds a path but not necessarily shortest.
Time & Space Complexity
In the worst case, A* has time and space complexity of O(bd), where b is the branching factor and d is the solution depth exponential in the worst case. In practice, with a good heuristic, A* dramatically reduces explored nodes. Dijkstra is O((V+E) log V) with a priority queue. BFS and DFS are O(V+E) on graphs.
Real-World Applications
Pathfinding algorithms power GPS navigation (Google Maps uses Dijkstra/A*), game AI (character navigation), robotics (autonomous path planning), and network packet routing. The D* (Dynamic A*) algorithm handles changing environments by replanning efficiently used in Mars rovers. Hierarchical pathfinding (HPA*) handles large maps by pre-computing paths between zones.
Algorithm Comparison
| Algorithm | Optimal? | Complete? | Time | Space | Notes |
|---|---|---|---|---|---|
| BFS | Yes (unweighted) | Yes | O(V+E) | O(V) | Explores level by level |
| DFS | No | No (cyclic) | O(V+E) | O(V) | Depth-first; not shortest path |
| Dijkstra | Yes (weighted) | Yes | O((V+E) log V) | O(V) | A* with h=0 |
| Greedy Best-First | No | No | O(bm) | O(bm) | Fast but not optimal |
| A* | Yes (admissible h) | Yes | O(bd) | O(bd) | Best practical choice |
Curriculum Relevance
| Level | Topic | Relevance |
|---|---|---|
| GCSE / A-Level CS | Algorithms & data structures | Graphs, trees, BFS, DFS, shortest path |
| IB / AP Computer Science | Algorithm design | Graph traversal, tree search, complexity analysis |
| Undergraduate Year 1-2 | Algorithms & AI | Heuristic search, informed vs uninformed search |
| Undergraduate Year 3+ | AI, robotics, operations | Planning, motion planning, dynamic programming |
| Postgraduate | Advanced algorithms | Approximation algorithms, anytime search, real-time A* |
🔒 Unlock All 32 Simulations
Get unlimited access to all 32 simulations — including A* Pathfinding, Neural Network, Sorting and more with MySimulator Premium.
Upgrade to PremiumDiscussion and comments (Premium)
Premium members can discuss use-cases and ask questions inside this page.
Video tutorial (Premium)
A short guided walkthrough is available for premium users.
Unlock Tutorial ->Downloadable worksheet (Premium)
Printable worksheet with tasks and reflection questions.
Unlock Worksheet ->Share this simulation
Send this page to students or colleagues.
Related simulations
Continue with similar experiments.
📖 Recommended Reading
Deepen your understanding with our in-depth articles.