Segfault in dtNavMeshQuery::findPath about recastnavigation HOT 15 CLOSED

I've had a similar problem with segfaults in findPath (see #113). Are you using off mesh connections?

from recastnavigation.

No we are using only the autogenerated meshes currently. As far as im aware that shouldnt add any off mesh connections

from recastnavigation.

Are you swapping the tiles in/out during the path finds?
Detour is definitely not thread safe, so if you are doing that you are bound to eventually run into problems. For example, if you remove a neighbor tile during the path find, the links connecting from the original tile to the neighbor are removed. This will make changes in the links array. There are made similar changes when adding neighbor tiles, and these changes are not meant to run in parallel with queries and such on the nav mesh.

from recastnavigation.

no the navigation mesh is locked while swapping tiles. there is only ever one thread that can access the navmesh(query) at a time.

from recastnavigation.

I see, that's a lot more interesting then. The fact that the error is not reproducible with the same state would indicate that at least some changes have been made, though.

What is the exact line the crash occurs on? findPath does not traverse the links of the parent tile (parentTile is merely used for the filter), so I am a bit confused on where exactly the parentTile->links[parentPoly->firstLink] access is done.

from recastnavigation.

Oh seems that wasnt that clear then. The code there is not the access fault. The access fault happens in line 1009 dtPolyRef neighbourRef = bestTile->links[i].ref;. But parentTile->links[parentPoly->firstLink] is the link the code has followed to reach the invalid bestTile, bestPoly combo. bestPoly->firstLink points to a link way outside of bestTile->links usually something around 2^31. Which is to be expected since the polyId from parentTile->links[parentPoly->firstLink].ref is also outside of bestTile->polys but usually not that far only around 2-4 indices.

from recastnavigation.

Alright, that clears it up. So we have narrowed it down to being parentTile->links[parentPoly->firstLink].ref that is wrong, as this poly ref does not exist in the mesh. Assuming this ref is bestRef in your example (so bestRef = 2295592910861), the salt is 2; however, bestTile->salt is only 1. So it's not a problem with a link not being removed properly (if that were the case the salt would be outdated, but it is ahead of the current tile's salt). That means it's not related to #113.

Can you dump the parentTile and parentTile->header as well? That should help clearing up which link exactly this is.

from recastnavigation.

(gdb) p *parentTile
$3 = {salt = 1, linksFreeList = 18, header = 0x531cf000, polys = 0x531cf170,
  verts = 0x531cf074, links = 0x531cf270, detailMeshes = 0x531cf560,
  detailVerts = 0x531cf5c0,
  detailTris = 0x531cfa04 "\027\003\004\005\004\005O\001\005\006T\001\006\a\"\001\a", bvTree = 0x531cfcc8, offMeshCons = 0x531cfdc8, offMeshSeg = 0x531cfdc8,
  data = 0x531cf000 "VAND\a", dataSize = 3544, flags = 0, next = 0x0,
  clusters = 0x531cfdc8, polyClusters = 0x0, dynamicLinksO = {m_data = 0x0,
m_size = 0, m_cap = 0}, dynamicFreeListO = 4294967295, dynamicLinksC = {
m_data = 0x0, m_size = 0, m_cap = 0}, dynamicFreeListC = 4294967295}
(gdb) p *parentTile->header
$4 = {magic = 1145979222, version = 7, x = 24, y = 27, layer = 0, userId = 0,
  polyCount = 8, vertCount = 21, maxLinkCount = 47, detailMeshCount = 8,
  detailVertCount = 91, detailTriCount = 177, bvNodeCount = 16,
  offMeshConCount = 0, offMeshSegConCount = 0, offMeshBase = 8,
  offMeshSegPolyBase = 8, offMeshSegVertBase = 21, walkableHeight = 55,
  walkableRadius = 18, walkableClimb = 18, bmin = {-10123.2969, -10357.3135,
1860.67969}, bmax = {-8723.29688, 7801.13477, 3260.67969},
  bvQuantFactor = 0.142857149, clusterCount = 0}

from recastnavigation.

Thanks, I will try to take a closer look in the following days (or after Christmas, worst case). At the moment I'm very confused since the poly ref's salt is larger than the tile salt! It's really a matter of tracking down how this is happening - only case I can think of is the tile having been removed and then readded in this split second. You can try dumping m_tiles[1439] - it should be the same as bestTile.

from recastnavigation.

(gdb) p &m_nav->m_tiles[1439]
$6 = (dtMeshTile *) 0x12982968
(gdb) p bestTile
$7 = (const dtMeshTile *) 0x12982968

we swap tiles with this function:

void DNav::Query::SwapTile(DNav::Tile *tile)
{
    // Noop if there is no tile at the given position.
    m_navMesh->removeTile(m_navMesh->getTileRefAt(tile->GetTx(), tile->GetTy(), 0), nullptr, nullptr);

    // Do not add empty tiles.
    if (tile->GetDataSize())
    {
        m_navMesh->addTile(tile->GetData(), tile->GetDataSize(), 0, 0, nullptr);
    }
}

So as long as the tile is not empty it will always swap in a new one directly

from recastnavigation.

In our latest build we replaced all calls to getTileAndPolyByRefUnsafe with calls to getTileAndPolyByRef to avoid crashes by invalid poly ids. As it stands now the server doesnt crash at all with this change. But of course pathFinding often needs to be aborted because refs are invalid. The only point where we get an invalid ref though is m_nav->getTileAndPolyByRefUnsafe(neighbourRef, &neighbourTile, &neighbourPoly); in line 1019

from recastnavigation.

Yes, that should at least avoid the crashes.
Can you try recording a sort of "replay log" of the modifications being made to the navmesh up until the invalid link appears? Tiles being removed/readded, changes made to polygons (if you make any), that sort of thing.
Also, are you using the tile cache?

from recastnavigation.

We actually found the problem now. We were assuming that the NavMesh would not modify the tiles but as it turns out the links are stored inside the tiles and updated each time you swap them in. Since we were reusing tiles across multiple map instances this ofc would lead to problems. So we prolly need to rewrite the links bit because this way it uses up way to much memory

from recastnavigation.

Ok, good to hear. I have opened issue #149 to explicitly document this.

from recastnavigation.

We may also be able to allow sharing of the tile data once #129 is implemented, if we implement the link pool appropriately. That might use slightly more memory than currently, if the tiles are not shared, however. Will need to do some measuring for that.

from recastnavigation.