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.
Mikko, one of the ideas I've been toying with for my game is to bake in cover selection by taking the outer edges of the navmesh and generating cover points along the edges by doing a sweep test in the cover directions. Am I right in thinking that getPolyWallSegments will basically give you the edges that have no other polygons on the other side of the edge? Because thats pretty much what I need.
ReplyDeleteAnyway, looking forward to playing with the new movement code, I really could use it right now (string pulling in a dense city definitely leads to a lot of similar paths that tend to converge agents pretty quickly).
Phil, yes getPolyWallSegments() does that, it returns the edges which do not lead to other polys.
ReplyDeleteI was also thinking about sampling the voxels instead of the sweep tests, but some collision queries should work too just fine.
I the Dice guys were using the edges to generate covers and I think Fallout3 does something similar too.
I'm going to add some kind of hash lookup which can be used to map polyId to an index this week. That together with findPolysAroundCircle() should give you good starting point to find nearby covers.
This comment has been removed by the author.
ReplyDeleteYeah, I've done that in the past too. You need to filter out the cover points in the middle of walls too.
ReplyDelete