Wednesday, July 21, 2010

Finding Navmesh Polygons Touching a Convex Shape

I added new query method to dtNavMesh to find polygons which touch a convex shape, findPolysAroundShape().

The function is similar to findPolysAround(), but with different boundary condition. As a matter of fact, I also renamed the findPolysAround() to findPolysAroundCircle() to make it less confusing. The function can be useful for creating some gameplay features such as doors.

The new method is somewhat slower than findPolysAroundCircle() because it uses polygon-segment intersection test to see if an edge should be visited.

Available in R186.


  1. Just wanted to say, thanks for your blog. It has been very useful so far for me.

    Keep up the good work !

  2. Hey, sorry for being off topic, but I'm using Detour and experiencing the following:
    I can't get a full path from start to end, I can however add some waypoints in between, say a and b, and then I can get a path from start -> a -> b -> end. I have the same set of tiles loaded at each of these pathfinds.
    Any idea why that could be?

  3. Coriolan, how long path are you trying to search? If it is really long you can try to increase the dtNavMeshParams.maxNodes (note that the max is 65536).

  4. Hah, I thought I had tried this before... okay, it's working now. Thanks for that blazing fast response and I love R&D :)

    I guess 65536 will work for now, but I'll see if I can adapt it to go beyond, basically because memory is not a premium for my use case.

  5. Coriolan, I think if you change the m_first and m_next in dtNodePool from "unsigned short" to "unsigned int" you should be able to get beyond that 65536 limit (up to 30 bits).