Typical Workflow

There are two main phases: the generation phase and the runtime phase.

Generation Phase

The generation phase is intended to be performed once before any pathfinding queries are made. This phase is broken down into two steps: game object processing, called "BVH generation", and map processing. BVH generation should always happen first. After BVH generation, each map should be generated individually.

For both BVH generation and map generation, an arbitrary number of worker threads may be used. The workers will coordinate with one another for optimal loading and sharing of data as well as compute task delegation. This highly parallel implementation has provided an order of magnitude improvement in compute time compared to the status quo.

Runtime Phase

The runtime phase is when pathfind queries are performed. This phase shall not begin until the generation phase successfully completes.

The game divides maps into tiles called ADTs. namigator further divides the ADTs into smaller tiles. Currently neither Recast and Detour, nor namigator, support any form of hierarchical path finding. Therefore there is no generic solution to determining if sufficient tiles have been loaded to find a reasonable path between two points. It is therefore strongly suggested, and may occasionally be assumed, that the entire map has been loaded into memory.

For more information on hierarchical path finding in Recast and Detour, see this blog post by the original author: http://digestingduck.blogspot.com/2010/03/sketch-for-hierarchical-pathfinding.html.