Extra long paths flat terrains with no edge

Troubleshooting ai
1

I have one minor unwanted feature left to overcome for AI. This is unrelated to my last AI question.

When you have terrain with flat edges and a small number of objects or minimal terrain variation at the center, the navMesh pathfinding algorithm will on occasion pick the vertex point at the edge as part of the path. The main culprit seems to be the long triangle.

[Album] imgur.com

This can lead to an abnormally long path where the spatial runs to the vertex point at the edge of the long triangle, only to backtrack to the next point in the path as is indicated by the yellow arrow in the image, rather than the desired next vertex point indicated by the red circle.

Any suggestions on how to remedy this?

1 Like
2

Well in your image that is the point where the larger triangles are closest together (see theres other triangles between them at all other points). Maybe thats a reason for that behavior (not saying that it is the correct behavior in all cases though).

1 Like
3

I think it may have something to do with the way the isLineOfSight method in the NavMesh.java file calculates which points are visible to each other.

Heres a better example image demonstrating the path taken,

http://imgur.com/a/GplVS

This image is the same path but reversed.

[Album] imgur.com

I also discovered an infinite loop situation in the isLineOfSight method that I am currently trying to resolve.

boolean isInLineOfSight(Cell StartCell, Vector3f StartPos, Vector3f EndPos, DebugInfo debugInfo) {
        Line2D MotionPath = new Line2D(new Vector2f(StartPos.x, StartPos.z),
                new Vector2f(EndPos.x, EndPos.z));

        Cell testCell = StartCell;
        Cell.ClassifyResult result = testCell.classifyPathToCell(MotionPath);
        Cell.ClassifyResult prevResult = result;

        while (result.result == Cell.PathResult.ExitingCell) {
            if (result.cell == null)// hit a wall, so the point is not visible
            {
                if (debugInfo != null) {
                    debugInfo.setFailedCell(prevResult.cell);
                }
                return false;
            }
            if (debugInfo != null) {
                debugInfo.addPassedCell(prevResult.cell);
            }
            prevResult = result;
            result = result.cell.classifyPathToCell(MotionPath);
        }
        if (debugInfo != null) {
            debugInfo.setEndingCell(prevResult.cell);
        }
        return (result.result == Cell.PathResult.EndingCell || result.result == Cell.PathResult.ExitingCell); //This is messing up the result, I think because of shared borders
    }

On occasion the classifyPathToCell() line in the while() loop,

prevResult = result;
result = result.cell.classifyPathToCell(MotionPath);

will constantly bounce back and forth between the prevResult and result even when there are more points in the Path left to be processed. This leads to the classifyPathToCell(MotionPath) always returning result.ExitingCell and never returning result.EndingCell, which means it never exits the loop.

It happens when you have 2 cells where one cell is behind the other in location, for instance two hills where one hill is in front of the other and you click on the hill cell furthest away. Once you find a location that does this you can always find it after restart, ie the exact same cell cause the problem.

2 Likes
4

In NavMeshGenerator setting

clipLedges = false

helps with the infinite loop but Im not sure if its just moving the problem somewhere else yet.

With

clipLedges = true

theres two infinite loops on certain cells as mentioned above. When clicking the cell at a distance the infinite loop above shows up.

The other infinite loop occurs in buildNavigationPath in NavMeshPathfinder.java. when you are directly next to the cell and click it and not at a distance as in the above mentioned situation.

Edit: If you can visually see the cell or cells this infinite loop happens, you don’t have to be standing next to it. The other infinite loop is from a distance and I think findClosetCell chooses the cell.

while (currCell != null && currCell != endCell) {

inside the case statement
case SegmentsIntersect:

this statement is the problem.

 } else {
     // cannot fit directly.
     // try to find point where we can
     if (d1 < d2) {
         intersectionPoint.interpolateLocal(wall.getPointA(), wall.getPointB(), distBlend);
         newWayPoint = new Vector3f(intersectionPoint.x, 0, intersectionPoint.y);
      } else {
          intersectionPoint.interpolateLocal(wall.getPointB(), wall.getPointA(), distBlend);
          newWayPoint = new Vector3f(intersectionPoint.x, 0, intersectionPoint.y);
      }

It does something similar as the other loop but this time its bouncing back and forth where
d1 < d2
and next iteration its
d1 > d2.
infinitely with the same point. Since the endCell is never reached the loop never ends.

Like I mentioned, Im not sure if setting

clipLedges = false

is just moving the problem somewhere else but I suspect this to be the case. I don’t think I can distill it down to a test case because of the complexity setting up navigation requires.

ill keep working on it and see if I can narrow it down more.

3 Likes