Skip to content

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

Released under the MIT License