find path enters an infinite loop.

[betterdenger]

Hi,

My test input as bellow,

float start[3] = { -22.636648178101, 12.46023273468, -123.88012695313 };
float end[3] = { -12.93, 12.08, -110.27 };
float speed = 0.77999997138978;

And the target test navmesh binary as bellow,

all_tiles_navmesh.zip

If i am trying find a smooth path use these data, i will enter an infinite loop from a iteration. From smooth_path_count_ = 17, the loop keeps give me bad point (-14.4847, 12.4086, -113.422).

Is there any hints for me?

Thanks

[robinxb]

same problem

[jakobbotsch]

I have been unable to get your navmesh file to load correctly, it seems like it is corrupt in some way. When loading it fails to load any tiles because all tile-refs are 0.

[MINIONBOTS]

I can also confirm I had this several times, very rare though. It happens for me when I set the additional HScale value of the pathfind algorightm too high. I was unable to completely fix it on my end, added a hacky failsafe, but afaik it happens because the node weights are using not only the 'already traveled distance' as costs but in addition such a HScale value. This kinda made the pathfinding rotate between a few nodes until you run out of available nodes...

[jackpoz]

I have the same issue, with detour entering an infinite loop in getPathToNode() looping through nodes with circular reference (A -> B -> C -> A) https://github.com/recastnavigation/recastnavigation/blob/master/Detour/Source/DetourNavMeshQuery.cpp#L1212

dtNavMeshQuery::getPathToNode (this=0x7ffefeeebce0, endNode=0x7ffefe5688a0, path=0x7ffefdbe1810, pathCount=0x7fff029fae10, maxPath=71) at /dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp:1212
dtNavMeshQuery::findPath (this=0x7ffefeeebce0, startRef=13510831094374714, endRef=13510831094374726, startPos=0x7fff029fae14, endPos=0x7fff029fb3f0, filter=0x7ffefdbe1ac0, path=0x7ffefdbe1810, pathCount=0x7fff029fae10, maxPath=71) at /dep/recastnavigation/Detour/Source/DetourNavMeshQuery.cpp:1193

Some guard check should be added, either max number of iterations, a hashset checking for pidx or some check in the m_nodePool so that there is no circular reference.

I will try to setup a case in recastdemo.

[cyberium]

Are the recast team able to reproduce the infinite loop or at least identify the degenerated triangle generation case?

Because the actual workaround is not really enough as the polygon at those places looks abnormally strange and so the path generated.

[jackpoz]

I was able to identify the issue in my project:
Line https://github.com/recastnavigation/recastnavigation/blob/master/Recast/Source/RecastRasterization.cpp#L133 gives priority to area types with higher id, making ground with very shallow water be handled as water.
This is how area types are defined:

NAV_EMPTY   = 0x00,
NAV_GROUND  = 0x01,
NAV_MAGMA   = 0x02,
NAV_SLIME   = 0x04,
NAV_WATER   = 0x08,

In a particular region we have terrain data from 2 different sources, one has ground and one has liquid. The way the overlap made recast mark some parts as ground and some part as liquid, creating a lot of small polys

If I change the way the flags are prioritized, making ground win against water, I get a clean result.

This is also why I couldn't reproduce the issue in RecastDemo as the .obj file doesn't have any area flag data.
This issue wasn't spotted before it didn't cause any issue as noticeable as the recent infinite loop.

[memononen]

I think it is very possible that one voxel wide ideas inside another area collapses into a degenerate polygon. Should be avoided, but sometimes tricky.

These sliver areas tend to create heaps of other problems too, even if well behaving with triangulation. Like weird paths because very uneven tesselation.

Some of the degenerate problems are caused by contour simplification. Especially at the tip of an area. One solution would be to disallow two turns in same direction. So a straight segment would need to be staircase like.

I once experimented using filtering to solve these issues and it works some times too. There's area median filter to try out.

[jackpoz]

Adding rcMedianFilterWalkableArea() gave some interesting results (but ofc it's not a panacea)
Code without rcMedianFilterWalkableArea():

Code with 1 rcMedianFilterWalkableArea() call (after rcErodeWalkableArea(), before rcBuildDistanceField() and rcBuildRegions())

Code with 2 rcMedianFilterWalkableArea() (because why not :) )

Thanks for the tip 👍 now just some tries/tuning to go :)

[jackpoz]

@jakobbotsch did you have any idea about how to deal with dtClosestHeightPointTriangle() having denom = 0 ?
In that case dtClosestHeightPointTriangle() will return true but assign nan(ind) to "h". Should "h" be checked for std::isfinite() at 3a619d7#diff-bfede56e0b8a23a1d49e7ce910195ee6R709 ?

[jakobbotsch]

No, dtClosestHeightPointTriangle should change to handle degenerate triangles.
My previous idea was to interpolate along the line segments in this case, but there can be multiple choices of line segments, so that does not really make sense. It should maybe just return false. @memononen what do you think?

[memononen]

dtNavMesh::closestPointOnPoly should always return a value of the poly ID is valid. So it definitely should deal with degenerate triangles, but dtClosestHeightPointTriangle might not need to.

The epsilon is there because the closest might not be over any detail triangle because of floating point accuracy. The floating point accuracy starts to be an issues when coordinates are > 1000. The problem should only happen at the triangles at polygon edges, but I have vague memory of having problems within the poly too.

Potential solutions:

1. go over all detail triangle edges, if no hit were found using dtClosestHeightPointTriangle
2. take max (or min) height of faces and edges (in which case remove the epsilon from dtClosestHeightPointTriangle.

Pt 2 could be something like this:

bool dtClosestHeightPointSeg(const float* pt, const float* p, const float* q, float size, float& h)
{
	float t;
	float d = dtDistancePtSegSqr2D(pt, p, q, t);
	if (d > size*size)
		return false;
	h = p[1]+(q[1]-p[1])*t;
	return true;
}

...

float edgeSize = walkableRadius * 0.1f;  // Size of the edge 
float maxh = -FLT_MAX;
float h;

if (dtClosestHeightPointTriangle(closest, v[0], v[1], v[2], h))
	maxh = dtMax(maxh, h);
if (dtClosestHeightPointSeg(closest, v[0], v[1], edgeSize, h))
	maxh = dtMax(maxh, h);
if (dtClosestHeightPointSeg(closest, v[1], v[2], edgeSize, h))
	maxh = dtMax(maxh, h);
if (dtClosestHeightPointSeg(closest, v[2], v[0], edgeSize, h))
	maxh = dtMax(maxh, h);

if (maxh > -FLT_MAX)
{
	closest[1] = h;
	break;
}

Pt 1 could traverse all edges, pick nearest edges first and then calculate height. That way you would not need edges size, which makes things nicer.

Bonus points for figuring out how to traverse the detail mesh edges only once :)

[jakobbotsch]

Number 2 is essentially what I wanted to do initially, but it can be done inside dtClosestHeightPointTriangle (then we don't need to make changes in multiple places).

The problem we have right now is that dtClosestHeightPointTriangle returns true for degenerate triangles and assigns a height of NaN. But I think making it just return false in this case should be ok -- if there is a degenerate triangle in a poly then the poly should have a non-degenerate triangle where the point will succeed (because of how they are triangulated).

EDIT: Unless the entire poly is a single degenerate triangle, but I don't think it was the case in this scenario.

[memononen]

IIRC there's only one call to dtClosestHeightPointTriangle so the change is very contained anyway.

I'm suggesting to following:

1. remove epsilon tricks and check for zero denom in dtClosestHeightPointTriangle:

bool dtClosestHeightPointTriangle(const float* p, const float* a, const float* b, const float* c, float& h)
{
	const float EPS = 1e-6f;
	float v0[3], v1[3], v2[3];

	dtVsub(v0, c,a);
	dtVsub(v1, b,a);
	dtVsub(v2, p,a);

	// Compute scaled barycentric coordinates
	float denom = v0[0] * v1[2] - v0[2] * v1[0];
	if (fabsf(denom) < EPS)
		return false;

	float u = v1[2] * v2[0] - v1[0] * v2[2];
	float v = v0[0] * v2[2] - v0[2] * v2[0];

	if (denom < 0) {
		denom = -denom;
		u = -u;
		v = -v;
	}

	// If point lies inside the triangle, return interpolated y-coord.
	if (u >= 0.0f && v >= 0.0f && (u+v) <= denom) {
		h = a[1] + (v0[1]*u + v1[1]*v) / denom;
		return true;
	}

	return false;
}

2. track nearest edge height and use it in case raycasts fail in dtNavMeshQuery::closestPointOnPoly()

float dtLerp(float a, float b, float t)
{
	return a + (b - a) * t;
} 

...

	// Find height at the location.
	float dmin = FLT_MAX, d, t;
	float safeHeight = closest[1];

	for (int j = 0; j < pd->triCount; ++j)
	{
		const unsigned char* t = &tile->detailTris[(pd->triBase+j)*4];
		const float* v[3];
		for (int k = 0; k < 3; ++k)
		{
			if (t[k] < poly->vertCount)
				v[k] = &tile->verts[poly->verts[t[k]]*3];
			else
				v[k] = &tile->detailVerts[(pd->vertBase+(t[k]-poly->vertCount))*3];
		}
		float h;
		if (dtClosestHeightPointTriangle(closest, v[0], v[1], v[2], h))
		{
			closest[1] = h;
			break;
		}

		// Track nearest extrapolated height in case we fail raycast.
		d = dtDistancePtSegSqr2D(closest, v[0], v[1], t);
		if (d < dmin)
		{
			dmin = d;
			safeHeight = dtLerp(v[0][1], v[1][1], t);
		}
		d = dtDistancePtSegSqr2D(closest, v[1], v[2], t);
		if (d < dmin)
		{
			dmin = d;
			safeHeight = dtLerp(v[1][1], v[2][1], t);
		}
		d = dtDistancePtSegSqr2D(closest, v[2], v[0], t);
		if (d < dmin)
		{
			dmin = d;
			safeHeight = dtLerp(v[2][1], v[0][1], t);
		}
	}

	// We failed to recast any of the detail triangles, use extrapolated value of nearest edge instead.
	closest[1] = safeHeight;
...

[memononen]

And one more thing:

1. as long as the polyref is valid, dtNavMeshQuery::closestPointOnPoly() should return "nearest" height to the polygon. I think you could fail also with bad input if pos is not finite.
2. detail mesh can have all kinds of nasty triangles, the triangulation algorithm is not very robust

[jakobbotsch]

Thank you, that is pretty clear. What I'm wondering is whether it is possible for an internal point in the polygons to fail all the dtClosestHeightPointTriangle tests? Internal as in a point that was not interpolated along the (non-detail) edges of the polygon.

What I mean is: can we replace this part with just finding the nearest edge for all detail triangles, and then keep the loop the same when dtDistancePtPolyEdgesSqr succeeds?

[jakobbotsch]

Also I am a little perplexed at what the difference between closestPointOnPoly and getPolyHeight is supposed to be. I would have thought the first was 3D, but it does not seem to be the case with how dtClosestHeightPointTriangle is implemented?

[memononen]

@jakobbotsch

I think I have seen the raycast (that is, dtClosestHeightPointTriangle) fail on internal edges on far away coordinates. In addition I think it is possible to have T-junction like cases if there is a degenerate triangle.

I think closestPointOnPoly initially used the nav polygons (not detail mesh), and 3D distance (not raycast down). And getPolyHeight was essentially raycast down to detail mesh. Little by little, one issue at time, they converged into essentially the same thing.

[jakobbotsch]

I believe this was fixed by #381.