Finding the Way
Every NPC in every game needs to navigate from point A to point B while avoiding obstacles. The A* algorithm, published by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968, remains the gold standard for pathfinding over 50 years later. It combines the guaranteed optimality of Dijkstra's algorithm with a heuristic that dramatically reduces the search space — making it fast enough for real-time games with hundreds of AI agents.
The A* Algorithm
A* works by maintaining two lists: open (nodes to explore) and closed (nodes already explored). Each node stores g (actual cost from start), h (estimated cost to goal), and f = g + h. The algorithm always expands the node with the lowest f score. When the heuristic h is admissible (never overestimates), A* is guaranteed to find the shortest path. The heuristic weight slider in this simulator lets you trade optimality for speed.
From Grids to Navigation Meshes
Grid-based pathfinding works well for 2D games but scales poorly to 3D environments. Navigation meshes (navmeshes) solve this by decomposing walkable surfaces into convex polygons. Pathfinding operates on the polygon graph rather than individual cells, reducing the search space by orders of magnitude. Unity and Unreal Engine both include built-in navmesh generation and A* pathfinding, making it accessible to all game developers.
Heuristic Weight: The Speed-Quality Tradeoff
The heuristic weight parameter controls the balance between exploration thoroughness and speed. At weight 0, A* becomes Dijkstra's algorithm — optimal but slow, exploring outward like a flood fill. At weight 1, standard A* finds optimal paths efficiently. Above 1, weighted A* becomes greedy — finding paths very quickly but potentially suboptimal. Games with many simultaneous agents often use weight > 1 because 'good enough' paths at 60fps matter more than perfect paths at 10fps.