Detour Sliced Path Find

Well, while I was in teh mood, I though I'd give it a go.

I just checked in (SVN R196) some extra methods for dtNavMeshQuery which implements sliced path finding. It works as follows:

// Request
m_pathFindState = m_navQuery->initSlicedFindPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter);

...

// On update
if (m_pathFindState == DT_QUERY_RUNNING)
    m_pathFindState = m_navQuery->updateSlicedFindPath(maxIter);

if (m_pathFindState == DT_QUERY_READY)
    m_npolys = m_navQuery->finalizeSlicedFindPath(m_polys, MAX_POLYS);

There is new tool called "Pathfind Sliced" which allows you to see it in action. The tool advances the search one node at a time so you can see how the closed list is update in realtime.

The actual path find is a tiny little slower than the findPath() because it does more validation. It should catch the case that some of the data is being removed while the query is in flight, and if the update encounters invalid data it will return DT_QUERY_FAILED.

If the removed data was already in the closed list of the search, the path result will contain invalid data. The rest of the API can handle that, but I recommend restarting all currently running path requests after you have added or removed a tile.

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

Some Recast & Detour Projects

The image is composed of a screen shot from the game Kingdoms of Amalur: Reckonin, GSoC10 projects for CrystalSpace and Blender.

Recast & Detour has seen quite nice adaptation during the past year. During the Paris Game AI Conference I run out of fingers to count the AAA projects currently in production which are using some part of Recast and Detour. In addition to that looks like there are countless indie, open source or hobby projects which I'm totally unaware of too.

Some projects have ported the code to different platforms, some have made quite heavy modifications to add features needed specifically for their game, and some are just using some parts of the code. It's awesome that Recast and Detour are being put in use! This also means that quite a few bugs have been reported and fixed too.

Here's some recent projects I'd like to highlight (if you like to share yours, drop me a line or comment below):

Kingdoms of Amalur: Reckoning
I'm glad that I'm allowed to share that up coming game Kingdoms of Amalur: Reckoning by Big Huge Games is using Recast and Detour.

Google Summer of Code 2010
Thanks to Nick and Leonardo, Blender Game Engine and CrystalSpace both leveled up on pathfinding this summer.

I'm thankful to all the people who have sent bug reports, fixes, improvements, suggestions or challenged me. It has made the toolkit so much better!

Heads Up, API Changes Coming Soon

I try to get two API breaking changes done this week.

1) Recast Context: This change will add additional parameter to most of the recast calls. I have yet to decide if the parameter will be the first or last. The idea behind this change is to remove platform dependancy of error/warning logging, timer and profiling code from Recast. See:

• Issue 67
• Issue 77

2) dtNavMesh & dtNavMeshQuery: This change will allow multiple simultaneous navmesh queries to happen at the same time. Basically it will strip dtNavMesh to just the data management, and add new class which has all the query functions. This makes Detour more concurrency friendly. See:

• Issue 99
• Parallel Detour navigation mesh queries

I will make separate posts describing the changes once I get things checked in.

Some More Movement Progress

Since last time, I implemented smooth steering, drunken movement style and sampled velocity obstacles.

The features are coming together, but the code is still huge pile of mess. I checked in first version (R193) so that the change list does not become too big.

When using tiled navmeshes and many agents, I got quite a bit of problems with agents trying to move backwards to catch up with their path. This happens mostly around the vertices which are at tile corners.

For the time being, I added that raycast trick which tries to optimize the path corridor by checking if there is line of sight from the current location to the corner after the next corner. If so, then the beginning of the path is patched to use the results from the raycast.

The performance is still realtime (it chokes when you have large group next to each other), but I bet it is actually really horrible. Once I get the structure of the code better, I'll start looking at the optimizations.

Oh, it moves!

The first test of a couple of agents moving around in a test level, yay!

I have implemented the navigation-loop stuff, simple steering, simple dynamic constraint, and simple collision handling. I need to rethink the way stuff is organized so that it is easier to grab the necessary code to your own projects.

It's always so amazing when it works the first time, even if it just barely does.

Detour Agent Movement Progress

I'm moving forward with the agent movement code for Detour. Today I added a couple of functions to Detour help me realize the goal. Check NavMeshTesterTool.cpp how to use the new functionality.

• dtNavMesh.moveAlongSurface() - This function tries to move an agent from start position to target position along the navigation mesh and constraints the position to be inside the navigation mesh at all times. The function is Detour implementation of the algorithm I explained in a previous post. In the process I removed the old moveAlongPathCorridor(), which supported only subset of the functionality anyways.

• dtNavMesh.findLocalNeighbourhood() - This function finds non-overlapping (in 2D) neighbourhood around a specified point. It is useful for local navigation. I have explained the algorithm earlier too.

• dtNavMesh.getPolyWallSegments() - This functions returns wall segments of a specified navmesh polygon. In conjunction with findLocalNeighbourhood() it can be used to generate 2D collision segments for local obstacle avoidance.

The image at the top of the post shows local neighbourhood segments queried using the new functions.

All the above functions assume that they operate on really small set of polygons. To achieve a bit better cache coherence, I added another tiny node pool, which currently only contains 64 nodes. The aim was to improve cache coherence. The node pool uses hash table to lookup nodes based on ID. When dealing with small number of nodes this actually slows things down because of the random access through the hash table.

Additionally, instead of using priority queue, the above functions use fixed size small stack and breath first search. The random access of the navmesh polygons is quite cache pooper already, but the above gives around 30-50% speed up compared to using the existing p-queue and larger node pool.

I'm planning to spend some more time this week in the agent movement stuff. The above functions are bound to change as I try to find my way through the implementation details.