Stepping into dtNavMeshQuery::queryPolygonsInTile, at the point in the function where I start to see duplicates added, adjacent nodes in the bvTree have the same i value being or’d into the TileRef.
`const bool isLeafNode = node->i >= 0;
if (isLeafNode && overlap)
{
dtPolyRef ref = base | (dtPolyRef)node->i;
if (filter->passFilter(ref, tile, &tile->polys[node->i]) && passLinkFilter(tile, node->i))
{
if (n < maxPolys)
polys[n++] = ref;
}
}
if (overlap || isLeafNode)
node++;`They aren’t distinguished from one another (node->i == 0 on both), so they yield the same dtPolyRef value.
We have not modified any of the recast/detour code
Steps to Reproduce
Calling dtNavMeshQuery::queryPolygons, even on a modest area (3000 units squre) will add duplicate dtPolyRefs. Usually you see pairs of the same id about 50% of the time. I’m calling this with a default constructed dtQueryFilter declared on the stack.
My sincerest apologies for the delay in responding. When you see the duplicate dtPolyRefs, are the multiple refs the same underlying poly or do multiple polys have the same handle? If it is multiple polys with the same handle, are the polys from separate tiles?
From the top level call (dtNavMeshQuery::queryPolygons), I’m seeing multiple refs with the exact same dtPolyRef value (uint64 value). Stepping into dtNavMeshQuery::queryPolygonsInTile, it is returning duplicate poly values when exploring the tile’s bvTree.
I have been looking into this and can reproduce having multiple dtPolyRefs inside of queryPolygonsInTile. This seems to be caused by multiple bvTreeNodes that point to the same poly, and Detour does not check for any duplicate entries. From my testing, all polys were accounted for with ~1 poly being duplicated per tile. It is possible to alter the function to check for duplicates, but it comes at a runtime cost. The other option is to remove duplicates that have been returned in your own code.
Could you elaborate more on the problem you are experiencing from the duplicate poly refs?
I wound up deduplicating the polys from our code. I was using this API to collect polys that I used to compute islands of contiguous pathable space as well as their combined surface areas.
I certainly see the usefulness of it, but I also think the team will be reluctant to add this. It has not historically been an issue, but it may certainly be worth adding a comment in the code that duplicates can be returned by the function.