This is general knowledge or an external-engine reference, not an Apollo architecture or implementation claim. See Apollo's architecture status for target terminology and verified implementation boundaries.
Q52: How to design a pathfinding system?
Core Conclusion
A pathfinding system is not finished once you "pick an A* algorithm." What it really has to solve is:
- How to represent walkable space
- How to find an acceptable path in a dynamic environment
- How to control the cost of many units pathing at the same time
The algorithm is only one link. Map representation, dynamic obstacles, path smoothing, and request scheduling matter just as much.
1. What the pathfinding system is actually responsible for
It has to handle at least three things:
- Find a feasible path from start to goal
- Let the character move stably along the path
- Replan or steer around when the environment changes
So "searching a path" and "moving along the path" are not the same thing.
2. First choose the map representation
Common options include:
- Grid
- Navigation mesh
- Waypoint graph
1. Grid
Straightforward to implement, suits regular maps, but the cost is high when there are many nodes.
2. Navigation mesh
Better suited to real 3D scenes and irregular terrain. Many games end up adopting this approach.
3. Waypoint graph
Suits scenes with relatively stable structure and clearly defined path points, but flexibility is limited.
The pathfinding experience is largely determined by the map representation, not just by the algorithm's name.
3. A* is common, but it is not the whole answer
A* is popular because it usually finds a good path at an acceptable cost.
But when actually landing it, you still have to consider:
- The heuristic function
- Node scale
- Dynamic obstacles
- Large numbers of concurrent requests
In other words, A* is the core searcher, not a complete pathfinding system.
4. Dynamic obstacles are harder than static maps
Real game scenes often have:
- Players and monsters blocking each other
- Temporary mechanisms
- Obstacle areas generated by skills
These obstacles usually cannot be handled by fully rebaking the map every time.
A more common approach is:
- The static map is described by a navigation mesh or static graph
- Dynamic obstacles are handled through local avoidance, local replanning, or blocking markers
5. When many units path at once, scheduling matters more than the algorithm
If hundreds or thousands of units all launch a full path search at the same moment, the system is easily overwhelmed.
So common engineering approaches include:
- Queuing pathfinding requests
- Reusing results for identical paths
- Segmented planning over long distances
- Lowering the update frequency for low-priority units
This is often more effective than continuing to optimize a single search.
6. The pathfinding result is not the final movement effect
After a character gets a path, it still needs:
- Path smoothing
- Steering control
- Local avoidance
- Arrival detection
Otherwise, even if the path is theoretically correct, the character's movement will look very stiff.
7. Server and client responsibilities must be separated
In online games it is usually:
- The server is responsible for authoritative position and legal path constraints
- The client is responsible for presentation-layer smoothing and local display
Do not let the client decide final reachability and position results on its own, or it will be exploited.
8. A more reliable engineering design
A common approach is:
- Build static walkable space in advance
- Schedule pathfinding requests centrally
- Handle dynamic obstacles with local avoidance and local recalculation
- Do frequency reduction and layered processing for large group movement
Only this way can you balance precision, performance, and experience.
9. Common misconceptions
1. Picking A* means pathfinding is done
No. Map representation, dynamic obstacles, and request scheduling are equally critical.
2. Every unit needs a real-time exact shortest path
Unrealistic. Many units only need an acceptable path, not the mathematically optimal one.
3. Pathfinding and movement can be merged into one module
Not recommended. Search and motion control have different concerns.
References
- Public materials on A*, navigation meshes, and group movement
