Detour Navmesh Data and Queries Separated

I just checked in code (SVN R194) which separates the navmesh data from the queries. In the process I also cleaned up how the data is accessed via dtNavMesh.

API Changes

In a nutshell this means that instead of using dtNavMesh, you use dtNavMeshQuery, except when you initialize the data of course. That is pretty much the only change if you are using Detour in single threaded system.

All the query methods have been moved to dtNavMeshQuery. The dtNavMesh class now only has methods to add, remove or change the data.

I removed bunch of getters. Now the right way to access the data pointed by dtPolyRef is:

bool getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;

It takes polygon ref as input, and stores pointer to tile and polygon as output. The function returns false if the poly ref is not valid.

Parallel Stuff

The new change allows you to better control the memory access of Detour for multi-threaded systems. The navigation mesh data stored in dtNavMesh is considered read-only by the dtNavMeshQuery. This also allows multiple dtNavMeshQueries to work on the same data. If you organize your data modifications and queries right, there is no need for locks.

The basic outline of multi-threaded use of Detour is as outline by Bjoern in [1]:

1. Update the navigation mesh (set flags, add or remove tiles)
2. Collect new pathfinding requests or pathfinding-change requests. Requests are deferred and not processed when posting them.
3. Process all pathfinding requests.
4. Make pathfinding results available.
5. Clear out all closed pathfinding requests and prepare for the next main loop cycle.
6. Back to stage 1.

I recommend reading Bjoern's post if you are interested in parallelizing your path finder. Also, any feedback is welcome. I will not be providing task scheduler, though, no point asking for it :)

So this is the first step towards more parallel Detour. The big task yet to tackle is to make all the queries to finish in more predictable time. The findPath() is really unpredictable in its' current form.

There are two options to improve that: 1) slice it, 2) add hierarchy. The final choice might be both.

Slicing means that only a set number of nodes are visited by the A* every update. It is simple to implement, but since the data can change between the updates, there needs to be much more bookkeeping in the process. Also, slicing means that the dtNavMeshQuery will store an intermediate state. That is, it would not be possible to run other query methods between the path find iterations, as they might mess up the open and closed lists.

I think in the long run the hierarchy is the way to go, but it needs new data structures and all sorts of things to be prototyped before it is ready to go in.

As an intermediate step, I'm probably going to implement iterative findPath() at some point.

__

[1] Parallel Detour navigation mesh