Pathfinding: A* and NavMesh

Цели урока

• Implement A* on a grid with a Manhattan heuristic
• Understand when Dijkstra is preferable to A* and vice versa
• Use NavMeshAgent in Unity for NPC movement
• Build a Flow Field for simultaneous pathfinding of thousands of units

An NPC must get from point A to point B while avoiding walls, enemies, and cliffs. How can this be done quickly for hundreds of characters simultaneously without destroying the frame rate? Pathfinding is one of the central problems in game AI.

• **RPG/Shooter NPCs:** A* on NavMesh - the standard in Unity and Unreal Engine
• **RTS games (StarCraft, Age of Empires):** Flow Fields - thousands of units without FPS drops
• **Pac-Man ghosts:** simple BFS - 1980, the same principles apply today
• **Cities: Skylines:** hierarchical pathfinding across roads of different levels

The A* Algorithm

A character stands at cell A and needs to reach cell B while avoiding walls. Naive BFS explores every reachable cell in all directions - wasting time on cells moving away from the goal. **A*** is smarter: it scores each cell as the sum of "how far from the start" and "how far to the goal", always expanding the cell with the lowest score.

The scoring formula is `f(n) = g(n) + h(n)`, where `g(n)` is the real cost from the start to n, and `h(n)` is the **heuristic** - an estimate of the remaining distance to the goal. As long as h(n) never overestimates the real distance (admissible heuristic), A* is guaranteed to find the shortest path.

**Heuristics by grid type:** Manhattan distance for 4-directional grids, Euclidean distance for 8-directional grids, zero heuristic (h=0) turns A* into Dijkstra's algorithm.

Dijkstra vs A*

Dijkstra always finds the shortest path but explores the graph evenly in all directions, like an expanding wave. A* adds direction: the heuristic steers the search toward the goal. On open terrain A* visits far fewer nodes. When is Dijkstra the better choice?

Dijkstra wins when **single-source shortest paths to all destinations** are needed. For example in an RTS: compute the cost from the base to every map cell once. A* is optimal for finding **one specific path** from A to B.

**Bidirectional A*:** run the search simultaneously from start and from goal toward each other. Meeting in the middle roughly halves the explored space - important for large open maps.

NavMesh in Unity/Unreal

A 3D game world is not a grid of cells. Characters walk across uneven terrain, navigate around buildings, and climb stairs. A **NavMesh (Navigation Mesh)** is a polygonal mesh covering only the walkable surfaces. A* runs on this mesh rather than on a voxel grid of the whole level.

Unity bakes the NavMesh in the Editor: static geometry is marked Navigation Static, and the NavMesh Surface component specifies agent radius, height, and step height. The result is a polygonal mesh of accessible zones, stored as an asset.

**Funnel algorithm (SSFA):** after A* finds the polygon sequence, the raw path contains one point per polygon boundary crossing. The funnel algorithm smooths the path by replacing those points with straight line segments wherever the character can walk directly, removing unnecessary turns.

Flow Fields for RTS

In an RTS, thousands of units move toward the same goal simultaneously. Running A* for each unit every frame is not feasible. A **Flow Field** solves this: run Dijkstra once from the goal, store the best movement direction for every cell. Units simply look up their direction in O(1).

**Rebuilding the flow field:** a rebuild is only needed when the goal changes or the map changes (a building is destroyed). For an RTS with a fixed player base, rebuilds are rare and can be amortized over several frames.

Pathfinding in Games

• A*: f(n)=g(n)+h(n), guaranteed shortest path with an admissible heuristic
• Dijkstra = A* with h=0; optimal for single-source all-targets problems
• NavMesh: polygonal walkable surface mesh that works with any 3D geometry
• The funnel algorithm smooths paths through NavMesh polygons
• Flow Fields: one Dijkstra from the goal, N units use O(1) lookup

Related Topics

Pathfinding is part of a broader game AI toolkit.

• Steering Behaviors — The flow field sets direction; steering controls speed and local avoidance
• Behavior Trees — The behavior tree decides when and where to go; A* decides how to get there
• Procedural Generation — Procedurally generated levels require dynamic NavMesh baking

Вопросы для размышления

• Why does an inadmissible heuristic make A* faster while potentially returning a suboptimal path?
• How does the NavMesh agent radius affect available paths, and what happens at narrow passages?
• In what situations must the Flow Field be rebuilt, and how can rebuild frequency be minimized?

Связанные уроки

• alg-13-dfs