Hierarchical Pathfinding in CrystalSpace

The navigation meshes are created using the Recast toolset.

In CrystalSpace, maps are divided into sectors (in this example each room is a sector). Each sector has it's own navigation mesh, and we have a high level graph connecting the sectors (actually, each node in this graph represents a portal, which is the area of transition between sectors).

In order to find a path, we first find a high level path in the graph, to determine which portals the path will cross. Then, sections of the path are calculated for each sector, using the Detour toolset.

Note that because of the way sectors are rendered, only the navigation mesh and path for the sector the camera is currently at are visible at a given time.

Category:

Science & Technology

Tags:

• pathfinding
• a*
• navigation