Infinite loop in dtNavMesh raycast in conjunction with off mesh connections

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Choose Tile Mesh sample
2. Choose nav_test.obj input mesh
3. Build mesh
4. Create an off-mesh link in the location specified in the attached
screenshot (start on the high tile, end on the low tile)
5. Build mesh
6. Perform a raycast from the poly containing the start of the off-mesh
connection to the tile containing the end of the off mesh connection.

At this point the demo hangs due to an infinite loop in dtNavMesh::raycast.

It appears to be hitting this code which doesn't advance curRef:

// If the link is internal, just return the ref.
if (link->side == 0xff)
{
    nextRef = link->ref;
    break;
}

Sorry about the screenshot fading out, Win7 does that to crashed
applications :)

Original issue reported on code.google.com by cameron....@gmail.com on 14 Apr 2010 at 6:05

Attachments:

• recast_raycast_crash.png

[GoogleCodeExporter]

On further inspection the raycast checks the next tile, then finds the link 
back to
the previous tile and checks that, bouncing between the two indefinitly. It 
would be
solved by always excluding off mesh links I guess.

Is it valid to raycast over an off mesh connection?

Original comment by cameron....@gmail.com on 14 Apr 2010 at 6:21

[GoogleCodeExporter]

Thanks for the report. My earlier tests did not capture this, but I'm able to 
repro it.

Raycast should not follow off-mesh connections.

Efficient solution did not seem to be a simple one.

Original comment by memono...@gmail.com on 14 Apr 2010 at 6:51

• Changed state: Accepted
• Added labels: Priority-High
• Removed labels: Priority-Medium

[GoogleCodeExporter]

Could you not always treat jump links as walls on this line?

if (!nextRef || !passFilter(filter, getPolyFlags(nextRef)))

Original comment by cameron....@gmail.com on 14 Apr 2010 at 11:22

[GoogleCodeExporter]

Ah I see, the flags are specified by the app rather than Detour itself.

Original comment by cameron....@gmail.com on 14 Apr 2010 at 11:24

[GoogleCodeExporter]

I think I have a fix. 

In dtNavMesh::raycast() Replace:

if (!nextRef || !passFilter(filter, getPolyFlags(nextRef)))

With:

const dtPoly* nextPoly = nextRef ? getPolyByRef(nextRef) : 0;
if (!nextPoly || nextPoly->type == DT_POLYTYPE_OFFMESH_CONNECTION ||
!passFilter(filter, nextPoly->flags))

This worked OK for me, although raycast ends up recalculating the current poly a
couple of times in the loop which is a bit wasteful.

Original comment by cameron....@gmail.com on 15 Apr 2010 at 12:11

[GoogleCodeExporter]

That does not work correctly, it should never follow the link to that off-mesh
connection.

Original comment by memono...@gmail.com on 15 Apr 2010 at 6:56

[GoogleCodeExporter]

Fixed in R157.

Original comment by memono...@gmail.com on 15 Apr 2010 at 7:23

• Changed state: Fixed