Pathfinding

Don't get stuck

Search Space Representation

Pathfinding directly over the level data is to expansive so simpler data structure is used that describe where in the world it is possible to move. The data structure is called the search space and the common ones are Grid, Point and Navmesh. Each search space contains some form of node that represent a position or area in the world and they are connected with each other with links. When picking a search space for a game one need to look at the following characteristics that affect the choice. The search itself is done with a graph search algorithm.

Dynamic

How well can the search space handle Dynamic obstacles that modify the search space at run-time.

Localization:

What is to cost to take a position in the world and convert it to the search space position.

Memory Usage:

How much memory does the search space take to represent an area in the world.

Planning

Cost of finding a path in the search space. Fewer nodes is better when searching for a path.

Smoothing

How easy it is to improve a path returned by the search space. Paths are often returned as the 'best path' and it might contain sharp turns or detours. It might be the fastest path or whatever 'best' is set as but it would not be the way a human walks for example.

  • Crowd
    • Hierarchical pathfinding

Reference