There’s a special kind of frustration that comes from watching your carefully crafted enemy soldier get stuck on a doorframe, shuffling back and forth like they’re doing some bizarre dance. Pathfinding issues are among the most visible AI failures in games players notice immediately when characters can’t navigate believably. I’ve spent more hours than I’d like to admit tracking down why a character decided the optimal path involved walking through a table or getting trapped behind a staircase.
Pathfinding is the system that calculates how AI characters move from their current position to a target destination while avoiding obstacles. Sounds simple enough, right? In practice, it’s one of the most computationally expensive and temperamental parts of game AI.
The Foundation: How Pathfinding Actually Works
At its core, pathfinding needs two things: a representation of where characters can walk (the navigation data), and an algorithm to find routes through that data.
Navigation meshes or navmeshes are the industry standard for representing walkable space. Instead of treating the world as a grid, a navmesh is a collection of polygons that define where characters can go. Flat floors become large polygons, ramps connect different heights, and obstacles create gaps in the mesh. This approach is far more memory-efficient than grids and handles complex 3D environments better.
I remember working on a game where we initially used a grid-based system because it seemed simpler. Once we had multi-story buildings, ramps, and bridges, maintaining that grid became a nightmare. Switching to navmeshes cut memory usage by about 80% and actually simplified the code despite the more complex data structure.
Most modern engines (Unity, Unreal, Godot) include navmesh generation tools that analyze your level geometry and automatically create navigation data. They work surprisingly well out of the box, though you’ll inevitably need to tweak settings or manually mark certain areas.
The Algorithm Everyone Uses: A*
A* (A-star) is the pathfinding algorithm you’ll find in probably 90% of games. It’s a refined version of Dijkstra’s algorithm that uses heuristics to search more efficiently toward the goal rather than expanding in all directions equally.
Here’s the basic concept: A* maintains a list of nodes to explore, always expanding the most promising one first. “Most promising” means lowest total cost, which is the actual distance traveled so far plus an estimated distance remaining to the goal. This heuristic usually straight-line distance guides the search toward the target.
The beauty of A* is that it’s guaranteed to find the shortest path (given certain heuristic requirements), and it’s reasonably fast. The problem is it’s still expensive when running for dozens of characters simultaneously on large, complex maps.
I’ve optimized A* implementations more times than I can count. Common tricks include:
- Caching paths and reusing them when start/goal positions are similar
- Running pathfinding asynchronously over multiple frames
- Using hierarchical pathfinding for long distances
- Simplifying paths by removing unnecessary waypoints
That last one is bigger than it sounds. A* gives you a path that hits every navmesh polygon edge along the route. A character following this literally looks like they’re walking a zigzag pattern. You need a smoothing pass funnel algorithm is common that turns the jagged path into natural curves.
Performance: The Constant Battle
On a typical frame budget of 16.6ms for 60fps, you might allocate 2-3ms to AI total. Pathfinding can easily blow through that if you’re not careful.
The cost of A* depends on how far the search has to expand before finding the goal. A short path in an open area? Fast. A long path through cluttered environment? Expensive. Worst case is when there’s NO valid path the algorithm has to search a huge portion of the navmesh before determining the target is unreachable.
Async pathfinding is essential for any game with multiple AI characters. Instead of calculating paths immediately, characters submit requests to a pathfinding service that processes them over multiple frames. Maybe you limit yourself to 5 path calculations per frame. High-priority requests (player’s direct sight, combat-active enemies) get processed first, background characters wait their turn.
The challenge is characters need to do something reasonable while waiting for their path. Usually they continue their current behavior or at least face toward the goal. I’ve seen games where characters freeze in place waiting for paths it looks terrible.
Hierarchical pathfinding helps with long distances. You divide the world into regions and precompute connections between them. A character pathfinding across the map first calculates a high-level path through regions, then only runs detailed A* within each region as they reach it. This can be 10-20x faster for long paths.
Dynamic Environments and Moving Obstacles
Static pathfinding is the easy case. The real world has doors that open and close, destructible objects, moving platforms, and other characters blocking paths.
For dynamic obstacles, the navmesh needs to update at runtime. Most engines support this to some degree, but it’s expensive. You don’t want to regenerate entire navmeshes every frame. Instead, you mark specific areas as temporarily unwalkable.
I worked on a game with destructible walls that created new paths through levels. We used a system where destroying a wall triggered a localized navmesh rebuild just for that area, then characters with paths passing through that region would recalculate. It worked, but we had to carefully limit how many simultaneous destructions could happen.
Other characters as obstacles gets messy. If you treat every moving character as a navmesh obstacle, you’re constantly updating navigation data and invalidating paths. Most games use local collision avoidance instead characters have valid paths through static obstacles, then use steering behaviors to avoid each other dynamically.
RVO (Reciprocal Velocity Obstacles) is a common algorithm for multi-agent collision avoidance. Characters predict where others will be and adjust their velocity to avoid collisions. It works pretty well for crowds but can look jittery in confined spaces.
Failure Cases and Edge Cases
Pathfinding bugs are insidious because they’re often intermittent and environment-specific. Here are the ones I’ve battled repeatedly:
Off-mesh links connect areas that aren’t directly walkable jumping across gaps, climbing ladders, vaulting over obstacles. These require special handling because characters need to trigger specific animations. Get the positioning slightly wrong and characters teleport, slide, or get stuck mid-animation.
Sloped surfaces confuse many navmesh generators. Is this ramp walkable or too steep? The answer often depends on your character size and movement capabilities. I’ve had “walkable” areas that were fine for humanoids but trapped quadrupedal characters.
Narrow passages cause congestion when multiple characters try to path through simultaneously. Without careful handling, characters bunch up and push each other around. Some games use reservation systems where characters “claim” narrow passages and others wait, but this requires significant additional logic.
Navmesh boundaries are where characters can fall off edges if their collision radius isn’t properly accounted for. Edge-case scenario: character successfully paths along a ledge, but their collision radius hangs over the edge, physics kicks in, and they fall. Fun times debugging that one.
Modern Approaches and Tools
The industry has largely standardized on navmesh + A* as the baseline, but there are interesting developments.
Recast & Detour is the open-source library that most engines use under the hood (including Unity). If you’re working in a custom engine or need more control than engine defaults provide, it’s the go-to solution. Well-maintained, well-documented, battle-tested.
Flow fields are gaining popularity for large numbers of units, especially in RTS games. Instead of calculating individual paths, you generate a vector field showing the best direction to move from any position toward a goal. Every unit just looks up their current position in the field and moves in that direction. Calculating the field is expensive, but supporting thousands of units following it is cheap. Blizzard used this approach in StarCraft II.
Some games are experimenting with machine learning for pathfinding, training networks to navigate environments. Interesting research area, but I haven’t seen it replace traditional pathfinding in shipped games yet. The unpredictability and edge cases make it risky.
Practical Advice from the Trenches
Start with engine defaults. Unity’s NavMeshAgent and Unreal’s navigation system are solid. Customize only when you have specific needs they don’t address.
Build debugging tools early. Visualizing navmeshes, showing calculated paths, displaying why a path failed this stuff is essential. I’ve spent days debugging pathfinding issues that would’ve taken minutes with proper visualization.
Test with minimum spec hardware. Pathfinding performance varies dramatically between high-end PCs and low-end or mobile hardware. What runs fine in editor might chug on actual target platforms.
Design levels with pathfinding in mind. Narrow, cluttered environments with lots of small obstacles are pathfinding hell. Open spaces with larger obstacles are much friendlier. Work with your level designers to create AI-friendly spaces.
Don’t expect perfection. Even AAA games occasionally have pathfinding glitches. The goal is to make characters navigate believably 95% of the time and fail gracefully the other 5%.
Wrapping Up
Pathfinding is one of those systems that you take for granted when it works and curse loudly when it doesn’t. The fundamentals navmeshes and A* have been refined over decades and work remarkably well for most games.
The challenges come from performance constraints, dynamic environments, and the massive variety of edge cases real game worlds present. Every game I’ve worked on had its own unique pathfinding headaches that required custom solutions.
But when you finally ship and watch AI characters smoothly navigate your complex environments, avoiding each other and obstacles naturally? That’s a good feeling.
Frequently Asked Questions
What pathfinding algorithm do most games use?
A* (A-star) on navigation meshes is the industry standard, used in the vast majority of modern games due to its balance of accuracy, performance, and reliability.
Why do game characters sometimes get stuck or path weirdly?
Usually from navmesh issues (geometry not properly marked walkable), characters treating each other as static obstacles, edge cases the pathfinding didn’t anticipate, or bugs in path smoothing/following logic.
How expensive is pathfinding performance-wise?
Highly variable. Simple paths might take 0.1ms, complex long-distance paths can take 5-10ms or more. Most games run pathfinding asynchronously and limit requests per frame to manage cost.
Can I do pathfinding for flying or swimming characters?
Yes, though it’s more complex. You need 3D navigation volumes instead of 2D navmeshes. Most engines support this but with higher memory and performance costs.