Pathfinding and Funnel

[Charles Clark]

Hey Mikko,

I have a question about NavMeshTesterTool::recalc().  I've been using it to generate paths and after doing some performance analysis I'm finding the following figures on a fairly long path in a mesh of around 70k polys:

• findPath() takes 0.515 ms.
  
• the smoothing process detailed below takes 7.16 ms.

As you can imagine, optimizing smoothing became my #1 priority and thus my first step is understanding the code.  I have a high level understanding of what the code flow is, but my question for you is why.  I'm used to seeing a pathfind, then a funnel implementation, however in the case of Recast I'm seeing a lot more code.  fixupShortcuts() looks pretty self explanatory, but I'm very confused with the purpose of steps 2.2, 3 and 4.  What is this code doing?  It just seems to walk along a polygon, tiny distances at a time, returning path waypoints at each.  My end result path for a path that is only a few meters long (for example) has dozens of waypoints when I'd have expected only 2 or 3 in a typical use case.

Below is my high level analysis of this code?  Is my understanding correct?  What is the concept behind the below code?  What is it trying to do and what problems was the small iterations looking to solve?  This work to me seems unnecessary, so I'd love some background on why the complexity was added.

Thanks and I look forward to hearing back from you soon.

My high level understanding of what the pathfind code path does:

1. Calls nav query findPath() to return an unsmoothed path of each polygon along the path.
2. It then goes through each poly and calls getSteerTarget().
1. This calls findStraightPath() (i.e., the funnel algorithm) to return to me what appears to be the first iteration along the funnel algorithm.
2. The results of this are iterated through and we stop as soon as we find something that's SLOP away.  (question, why stop here?)
3. This position is returned as the target.
3. This target position is then turned into a movement delta via STEP_SIZE / len where len equals the distance to the target pos.  (question, why do we limit the target position in this way?)
4. We compute a tiny move target from this and call moveAlongSurface().  (question, why moveAlongSurface instead of raycast?)
1. moveAlongSurface() then checks a distance half way out and selects it if it's valid, or finds the wall and calculates distance as needed. (question, why only half way, why not move all the way to the target if we can?)
5. We then call fixupCorridor() which is unclear but might be splicing in polygons that the smoothing visited?
6. We then call fixupShortcuts() which as the comment suggests, finds shortcuts if able.
7. This whole thing continues until we have reached the end of our path.

[Mikko Mononen]

The loop here:

https://github.com/memononen/recastnavigation/blob/master/RecastDemo/Source/NavMeshTesterTool.cpp#L731

Simulates what you should call at each update of your agent. So the code simulates an agent taking small steps until it roughly reaches the target. TOOLMODE_PATHFIND_STRAIGHT is the version which just calculates the path.

Arriving at exact location in destination is generally a pretty hard problem to solve, and depends how the agent is actually moved (i.e. some fake physics, animations, etc). For that reason, the iteration stops, when close enough. I chose that implementation in the example since users have had problems when trying to use exact target.

MoveAlongSurface handles stuff like sliding against a wall, or shortcutting corner. If you used raycast it would get stuck on corners and all kinds of cases along edges.

Here's the full story on move along surface:

http://digestingduck.blogspot.fi/2009/12/constrained-movement-along-path.html

http://digestingduck.blogspot.fi/2010/05/constrained-movement-along-navmesh-pt-2.html

http://digestingduck.blogspot.fi/2010/07/constrained-movement-along-navmesh-pt-3.html

And path corridor optimizations:

http://digestingduck.blogspot.fi/2010/11/path-corridor-optimizations.html 

And path following in general:

http://digestingduck.blogspot.fi/2010/07/my-paris-game-ai-conference.html

http://digestingduck.blogspot.fi/2010/09/on-navigation-robustness.html

--mikko

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Charles Clark]

Thank you Mikko!  This is a tremendous help!  :)