Tuesday, August 17, 2010

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.


  1. This is something I've been asked to add in Golaem Path, while it's quite simple do implement, I still have a problem that gives me headache :
    What's the best way to find the right value for 'maxIter'
    Do you have some insights ?

  2. I don't think there is good way to automatically guess it. You need to know your data and measure the performance. Probably the best way would be to give a certain time budget to one update step, then just do a lot of tests and try to find a good value which satisfies the time constraint.

  3. Mikko, you are a machine! I will have to look at this soon, it is too cool not to :)

    I've been involved in sliced path-finding before (road networks) and found that in worst case scenarios (depending on the distance & network to be travelled) checking the open/closed lists for validity on return could often blow out time-wise. Have you had a chance to see how much "slower" the new algorithm is proportionally?

  4. Currently I'm only checking the validity of the new polygons I advance to. So the polygons in the closed list may be invalid as well as the returned path.

    At some point I need to investigate more on how to improve the validation.

    I'm currently assuming that any data can be invalid at any time. The Detour API is able to handle invalid polygon references just fine. My demos do not have proper recovery yet, though. And I think I will need to add some more helpers to make it more practical.