A-Star Pathfinding for Games

Step 1: Represent Your World as a Graph

A* operates on graphs, which means your game world needs to be represented as a set of nodes connected by edges before the algorithm can search it. The choice of graph representation depends on your game type and has major implications for both path quality and performance.

Tile grids are the simplest representation. Each tile in a 2D grid is a node, and adjacent tiles are connected by edges. Tiles can be marked as walkable or blocked, and edge costs can vary to represent different terrain types (roads are faster than mud, mud is faster than swamp). Tile grids work well for top-down 2D games, strategy games, and roguelikes. The main limitation is resolution: fine grids have many nodes (a 1000x1000 map has one million nodes), while coarse grids produce blocky, unnatural paths.

Waypoint networks place nodes at strategic positions in the level, typically at corners, doorways, intersections, and other navigation-relevant locations. Edges connect waypoints that have clear line-of-sight between them. Waypoint networks have far fewer nodes than grids, which makes pathfinding fast, but they produce paths that follow the waypoint network rather than the actual shortest route. NPCs move from waypoint to waypoint, which can look mechanical unless additional smoothing is applied.

Navigation meshes are the standard for 3D games. A NavMesh covers every walkable surface with convex polygons. Each polygon is a node, and polygons that share an edge are connected. Because each polygon is convex, the NPC can move freely within it without obstruction, so pathfinding only needs to find the sequence of polygons from start to goal. NavMesh generation is typically automated by the game engine, which analyzes the level geometry, determines which surfaces are walkable (based on slope angle and height clearance), and tessellates them into a polygon mesh.

Step 2: Implement the A* Algorithm

A* maintains two data structures during its search: an open set containing nodes that have been discovered but not yet fully evaluated, and a closed set containing nodes that have been fully evaluated. The algorithm also tracks three values for each node: g-cost (the actual cost from the start node to this node), h-cost (the heuristic estimate from this node to the goal), and f-cost (g + h, the estimated total cost of the path through this node).

The algorithm proceeds as follows. Add the start node to the open set. While the open set is not empty, remove the node with the lowest f-cost (this is where a priority queue pays for itself in performance). If this node is the goal, reconstruct the path by following parent pointers back to the start. Otherwise, add this node to the closed set and examine each of its neighbors. For each neighbor, if it is in the closed set, skip it. If it is not in the open set, calculate its g-cost, h-cost, and f-cost, set its parent to the current node, and add it to the open set. If it is already in the open set, check whether the path through the current node offers a lower g-cost. If so, update the neighbor's g-cost, f-cost, and parent.

The priority queue implementation matters significantly for performance. A binary heap is the standard choice, providing O(log n) insertion and removal. For games that frequently update priorities (because finding a better path to an existing node changes its f-cost), a Fibonacci heap or pairing heap offers better amortized performance, though the constant factors are larger. In practice, binary heaps with lazy deletion are sufficient for most game pathfinding scenarios.

Step 3: Choose the Right Heuristic

The heuristic function estimates the remaining distance from any node to the goal. A* guarantees finding the optimal path only if the heuristic is admissible, meaning it never overestimates the true distance. Choosing the right heuristic for your movement model is critical for both correctness and performance.

Manhattan distance (sum of absolute differences in x and y coordinates) is the correct heuristic for grids where movement is restricted to four directions (up, down, left, right). It exactly matches the minimum possible cost to traverse axis-aligned segments.

Chebyshev distance (the maximum of the absolute differences in x and y) is appropriate for grids that allow eight-directional movement where diagonal moves cost the same as cardinal moves. If diagonal moves cost more (typically the square root of 2 times the cardinal cost), use the Octile distance variant, which accounts for the different costs of diagonal and cardinal steps.

Euclidean distance (straight-line distance) works for NavMesh pathfinding and any graph where movement is not restricted to a grid. Euclidean distance is always admissible because the straight line is always the shortest possible path, but it can be a loose estimate on grid graphs, which causes A* to explore more nodes than necessary.

A heuristic that underestimates heavily causes A* to explore more nodes, approaching Dijkstra's algorithm (which uses a heuristic of zero). A heuristic that overestimates can find paths faster but may miss the optimal path. For games where path optimality matters less than speed, a slightly inadmissible heuristic (one that overestimates by a small factor) can dramatically reduce the search space. This variant is called Weighted A* or WA*, and it produces paths that are at most (1 + epsilon) times longer than optimal.

Step 4: Build or Generate a Navigation Mesh

For any game with 3D environments or complex 2D layouts, a navigation mesh is the preferred graph representation. Most game engines generate NavMeshes automatically, but understanding the generation process helps you troubleshoot navigation issues and optimize for your specific level designs.

NavMesh generation starts by voxelizing the level geometry: converting all surfaces into a 3D grid of small cubes. The voxelizer marks each cell as solid or empty based on whether geometry exists there. Next, the system identifies walkable surfaces by checking which cells have solid ground below and sufficient vertical clearance above (based on the agent's height and radius). Connected walkable cells are grouped into regions, and each region is simplified into a set of convex polygons.

Agent dimensions matter. A NavMesh built for a standard humanoid character will not work for a large boss enemy because doorways and narrow passages that the humanoid can fit through may be too small for the boss. Most engines support multiple NavMesh layers or agent types, each generated with different radius and height parameters. This allows different NPC types to navigate the same level with appropriate constraints.

Off-mesh links connect navigation regions that are physically separated but logically traversable. A ledge that an NPC can jump from, a ladder, a teleporter, or a door that can be opened all require off-mesh links because the NavMesh polygons on either side are not geometrically adjacent. Place these links manually at jump points, ladder tops and bottoms, and doorways, then associate each link with the appropriate traversal animation.

Step 5: Smooth and Optimize the Path

Raw A* output on a grid produces zigzag paths that follow cell boundaries. On a NavMesh, the raw path is a sequence of polygon centroids or edge midpoints, which also looks unnatural. Path smoothing transforms these raw paths into curves that NPCs can follow believably.

Line-of-sight smoothing is the simplest approach. Walk along the path and check line-of-sight from the current waypoint to each subsequent waypoint. Remove any intermediate waypoints that have clear line-of-sight, leaving only the waypoints where direction changes are necessary. This eliminates most unnecessary zigzags and produces reasonably direct paths.

The funnel algorithm (also called string pulling) is the standard for NavMesh paths. Given a corridor of polygons from A* and the start and end positions, the funnel algorithm finds the shortest path through the corridor by maintaining a funnel shape that narrows as it progresses through each portal (shared edge between polygons). When the funnel closes to a point, a turn waypoint is placed. This produces the true shortest path through the polygon corridor, not just an approximation.

Catmull-Rom splines or similar curve-fitting can be applied after waypoint reduction to produce smooth turning arcs rather than sharp direction changes. This is especially important for vehicles or large creatures whose turning radius prevents them from making instant direction changes. The spline smoothing must be validated against the level geometry to ensure the smoothed curve does not cut through obstacles.

Step 6: Handle Dynamic Obstacles and Performance

Static pathfinding assumes the world does not change, but real games have doors that open and close, destructible walls, moving platforms, and other NPCs that occupy space. Handling these dynamic elements requires additional systems on top of basic A*.

Local obstacle avoidance handles moving obstacles that the static NavMesh does not represent. The most common approach is Reciprocal Velocity Obstacles (RVO), which gives each agent a velocity space that excludes velocities likely to cause collisions with nearby agents. Each agent independently selects a velocity from its allowed space, and the reciprocal nature of the algorithm ensures that agents cooperate to avoid each other without explicit communication. Unity's NavMesh system includes RVO-based avoidance, and Unreal Engine's crowd manager provides similar functionality.

Time-sliced pathfinding spreads expensive path queries across multiple frames. A single A* search on a large NavMesh might visit thousands of nodes, which could cause a frame rate spike if done all at once. Time-slicing runs the A* loop for a fixed number of iterations per frame and continues on the next frame until the path is complete. The NPC either waits for the path (with a brief idle animation) or starts moving toward the goal using a straight-line estimate while the full path computes in the background.

Hierarchical pathfinding divides the world into regions and performs A* at two levels. The high-level search finds a sequence of regions from start to goal. The low-level search then computes detailed paths within each region as the NPC reaches it. This dramatically reduces the search space for long-distance paths and is essential for large open-world games where NPCs might need to navigate across the entire map.

Flow fields offer an alternative for scenarios where many NPCs share the same destination. Instead of running individual A* queries, a flow field computes a direction vector at every cell in the grid pointing toward the goal. Any NPC can then navigate simply by reading the direction at its current position. Flow fields are ideal for RTS games where hundreds or thousands of units move to a selected location simultaneously.