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.