How to prevent scan from creating nodes with no connections

General Grid graph
1

I have an issue where rescans of areas are occasionally creating nodes with no connections (due to slope restrictions). This is causing my AI agents to become stuck when the closest node to them happens to be one of these nodes; they can’t seem to break free.

Is there a way to prevent this from happening?

In addition, is there a way to get a list of N nearest nodes, as opposed to just the one with GetNearest? My original idea to get around this was to find the next nearest node, and teleport to it to break free of the issue, but I couldn’t find a version that woudl give me a node list like that.

2

Hi

Assuming you are using a grid graph. Possibly you can use the erosion setting (set it to 1) to filter out single walkable nodes.

3

Yes it is a gridgraph. I can’t use erosion settings as that would mess up other aspects of my game; unless there is a way to use erosion just for the graph update object, but there doesn’t seem to be a way for me to set erosion there; just whether to update erosion or not.

Any other suggestion? Ideally, a scan would not create nodes with no connections, as that would be a useless node; but I am willing to use a workaround for now.

4

Hi

They are not necessarily useless. It depends on the game. For example in a 2D tile based game, one would not want to remove such nodes.

You can easily make a post processing effect for this if you want

 public class MyGUO : GraphUpdateObject {
      public override void Apply (GraphNode node) {
           var gridNode = node as GridNode;
             // Checks if there are no connections from this node, can be done in nicer ways, but that takes more code and I am lazy
             if ((gridNode.InternalGridFlags & 0xFF) == 0) {
                  gridNode.Walkable = false;
             }
      }
 }

 var guo = new MyGUO();
 // Update everything!
 guo.bounds = new Bounds(Vector3.zero, new Vector3(1000000, 1000000, 100000));
 guo.updatePhysics = false;
 AstarPath.active.UpdateGraphs(guo);

I am just writing this in the post directly, I haven’t tested it, but I think it should work.

Alternatively you can modify the GridGraph code a bit to discard these nodes.

5

This seems to work, but unfortunately it appears it is not the only cause of my issues. :confused:

http://i.imgur.com/iKqaSEq.jpg

You can see in this image that the nodes with no connections have been made unwalkable, but what I am failing to understand now is two things:

1.) why did they have no connections? this is a nearly flat surface; by all rights these should have had connections.

2.) if you look closely, you will see a green point, and a black wire cylinder near the agent that triggered the exception (of not being able to find a path. This is the code I run in that error to help diagnose the issue:

if (path.error) {
Debug.LogError(this.name + ": " + path.errorLog);

                    DebugExtension.DebugPoint(transform.position, Color.green, 0.25f, float.MaxValue, false);

                    pathfindingState = PathfindingState.CalculatedFail;                       

                    // when there is an error, it is usually either because we are stuck, or because
                    // there is an issue with the end point. Let's just find the closest node and
                    // move to it.
                    NNConstraint nnc = new NNConstraint();
                    nnc.constrainWalkability = true;                       
                    NNInfo nni = AstarPath.active.GetNearest(transform.position, nnc);
                    controller.Teleport(nni.clampedPosition);

                    int connectionCount = 0;
                    nni.node.GetConnections((GraphNode node) => {
                        connectionCount++;
                    });

                    if (connectionCount < 1) {
                        Debug.LogError("Found node has " + connectionCount + " connections");
                    }
                    DebugExtension.DebugCylinder(nni.clampedPosition, nni.clampedPosition + Vector3.up, Color.black, 0.0825f, float.MaxValue, false);
                    
                    controller.Move(transform.position.NormalTo(nni.clampedPosition));

                    yield break;
                }

(Sorry, that did not copy very well). Any ideas why this is happening? to give further context, the agent moves up to a tree, “harvests” it, and then a rescan of the graph is made to fill in the area the tree once stood in, in addition to a buffer area around it to ensure we capture everything. the agent is then instructed to go elsewhere. It mostly works, but agents eventually get stuck like this.

6

Hi

For 1. Check the max climb setting. It seems pretty low if your characters are a standard 1.5-2 meters tall.

7

I was a bit confused about that. Yeah my characters are 1.8 meters tall. What woudl you recommend as a good setting for that?

8

Yeah. I’ve been meaning to add a warning when it results in an effective max angle of less than the max angle setting. Since you have a node size of 2, the effective max angle is atan(0.4/2) which is approximately 11 degrees. I would suggest raising it to maybe 1 or 2. Unfortunately since your node size is that large, it is not that useful for detecting large steps since it cannot distinguish them from slopes.

9

I see. Ok I can try that. I am still a little confused though. I had thought “max climb” meant basically “largest step in a staircase an agent can walk over” so to speak. I didn’t realize they had any correlation to eachother.

Yeah I would have liked a smaller node size, but I needed to graph a 2km sq area, and this was the smallest I could go before needing multiple graphs.

10

It is intended as that. So if that check is done between two nodes with positions A and B, it checks that abs(A.y - B.y) < maxClimb. Since the node size is fixed, this gives an effective maximum angle between two nodes (not of the ground that the raycast hits).

11

I see. I just looked it up in the documentation as well. It is a little confusing since one controls walkability, and the other connections.

Anyways, that appeared to be the root cause of the problem. everything seems fine now. Thanks!

I anticipate having issues with agents walking over fences and such, but for now I can move onto other aspects. :slight_smile: