Trying to find all border nodes with ConstantPath in grid graph


#1

I’m using a Grid Graph to create a grid-based movement ala XCOM. But now I’m trying to find the border nodes in a ConstantPath so I can show the outline of allowed move instead of all allowed nodes.

What I have done so far is to check all nodes in the path for neighbours, and if any nodes don’t have all 8 neighbours, they get another color to show that they’re a border node. But either my script only flag some as borders, none as borders or as my last attempt, all as borders. Even those in the middle of the path…

I have a feeling I’ve programmed myself blind on this now, so therefore I post it here in hopes someone can see what I’m doing wrong :slight_smile:

My code so far is:

public void CalculatePossibleMoves(PlayerController player) {
    ConstantPath path = ConstantPath.Construct(player.CurrentPosition, player.playerStats.move * 1000 + 1);
    path.traversalProvider = player.traversalProvider;
    path.nnConstraint.graphMask = (1 << 0) | (1 << 1);

    AstarPath.StartPath(path);
    path.BlockUntilCalculated();

    for (int i = 0; i < path.allNodes.Count; i++) {
        GraphNode node = path.allNodes[i];

        if (node == path.startNode) continue;

        Vector3 nodePosition = (Vector3)node.position;
        nodePosition.y += 0.01f;
        node.position = (Int3)nodePosition;

//TODO: Use pool instead
        GameObject nodeGO = Instantiate(nodePrefab, nodePosition, nodePrefab.transform.rotation);
        Node nodeComponent = nodeGO.GetComponent<Node>();

        nodeComponent.node = node;
        nodeComponent.FindNeighbours();
        if (CheckNodeIfBorder(nodeComponent, path.allNodes)) {
            nodeComponent.ChangeColor(Color.yellow);
        }
        nodeGO.name = "Node " + node.NodeIndex;
        possibleMoves.Add(nodeGO);
    }

}

private bool CheckNodeIfBorder(Node node, List<GraphNode> pathNodes) {
    for (int i = 0; i < node.neighbours.Count; i++) {
        if (!pathNodes.Contains(node.neighbours[i]) || node.neighbours[i] == null) {
            return true;
        }
    }
    return false;
}

// From Nodecomponent - Node.cs
public List<GraphNode> neighbours = new List<GraphNode>();

internal void FindNeighbours() {
    if (node == null) return;

    GridGraph gridGraph = (GridGraph)AstarData.GetGraph(node);
    int index = node.NodeIndex;

    int x = index % gridGraph.Width; // Got this from forum answer by Aron
    int z = index / gridGraph.Width; // Got this from forum answer by Aron

    for (int i = 0; i < 8; i++) {
        if (!IsNeighbourWithinGrid(gridGraph, x, z, i)) {
            neighbours.Add(null);
            continue;
        }
        GridNode neighbour = gridGraph.nodes[index + gridGraph.neighbourOffsets[i]];
        neighbours.Add(neighbour);
    }
}


private bool IsNeighbourWithinGrid(GridGraph gridGraph, int x, int z, int i) {
    int neighbourX = x + gridGraph.neighbourXOffsets[i];
    int neighbourZ = z + gridGraph.neighbourZOffsets[i];

    return !(neighbourX < 0 || neighbourZ < 0 || neighbourX >= gridGraph.Width || neighbourZ >= gridGraph.Depth);
}

#2

Hi

On grid nodes the connections to the adjacent nodes are stored in a bitpacked field to reduce the memory usage. The ‘neighbours’ array is only used for custom connections that do not follow the grid pattern. You can access all neighbors using the GetConnections method which works for all node types.

In this particular case there is actually a built-in solution:

var isBorderNode = !gridNode.HasConnectionsToAllEightNeighbours;

That corresponds to this code:

 var isBorderNode = (gridNode.InternalGridFlags & 0xFF) != 0xFF;

This will check if the lowest 8 bits of the InternalGridFlags field are not all 1. A bit value of 1 corresponds to an enabled connection in that direction.

You can also use a different method like this:

bool ConnectedToAllNeighbors (GridNode baseNode) {

	// Check the four axis aligned connections
	// Replace with 8 to check diagonal connections as well
	for (int i = 0; i < 4; i++) {
		// You can also use node.GetNeighbourAlongDirection to get the node instance (or null if there is no connection)
		if (!node.HasConnectionInDirection(i)) {
			return false;
		}
	}

	return true;
}

If you want to draw the contours of these nodes, you may be interested in the new GraphUtilities class: https://arongranberg.com/astar/documentation/dev_4_1_6_17dee0ac/class_pathfinding_1_1_graph_utilities.php#abed60d6e0649691cf39784407e3498ef
This class only exists in the current beta however.


#3

Oh nice! I will test out your suggestions :smiley:

Love the contours solution you have in beta too, that would fit my purpose perfectly! How stable is the beta?


#4

The current beta should be very stable I think. Probably more stable than the latest release.


#5

I’ve been trying out this one, but ConstantPath.allNodes gives GraphNodes so I can’t find a good way to convert them to GridNodeBase which I can input into the GetContour method. Any suggestions?


#6

Hi

GridNodeBase is a subclass of GraphNode, so you can simply cast them.


#7

That’s what I have been trying to do, and casting works nicely to get a base class from a subclass, but not the other way around. Which also is something that is by design in C#. Though when I try casting from GraphNode to GridNodeBase it works some of the times, but suddenly I get a can’t cast error :\


#8

Hi

It should work using just

GraphNode[] nodes = ...;
GridNodeBase[] gridNodes = new GridNodeBase[nodes.Length];
for (int i = 0; i < nodes.Length; i++) gridNodes[i] = (GridNodeBase)nodes;

Or using LINQ

GridNodeBase[] gridNodes = nodes.Cast<GridNodeBase>().ToArray();

If you are getting a casting error, are you sure all nodes are actually grid nodes?

If not you could use LINQ to filter them out

GridNodeBase[] gridNodes = nodes.OfType<GridNodeBase>().ToArray();

#9

Yeah I started thinking that some of the nodes weren’t grid nodes, so I changed casting from the (GridNodeBase) which casts an exception when not found to as GridNodeBase which simply returns null instead. And it seems to work now. Thank you for pointing me in the right direction :smiley:


#10

I am also trying to do the same thing as RoninaRa. I love that there is already a tool for accomplishing this but I am having trouble implementing it. I am having issue with consistency. The contour seems to show up sometimes but not every time. Also, if I have a cube with a collider in the nodes being checked it will sometimes outline that cube but not the total move area. I am not sure what I am doing wrong here. I will post my code that I am using so you can take a look. I would appreciate any help I could get. I am humble and am willing to take any criticism necessary to get it right. Thank you!

//my code
public void GeneratePossibleMoves(Humanoid humanoid, int movementPoints)
{
ConstantPath path = ConstantPath.Construct(transform.position, (movementPoints * 1000 + 10)*2);
path.traversalProvider = TraversalProvider;

    // Schedule the path for calculation
    AstarPath.StartPath(path);

    // Force the path request to complete immediately
    // This assumes the graph is small enough that
    // this will not cause any lag
    path.BlockUntilCalculated();

    GridNodeBase[] nodesToContourAll = path.allNodes.Cast<GridNodeBase>().ToArray<GridNodeBase>();
    DrawContour(nodesToContourAll);

    OutlineRenderer.TotalPointsOnPath = verticesInContour.Length;
    OutlineRenderer.LineRendererActual.positionCount = OutlineRenderer.TotalPointsOnPath;
    for (int i = 0; i < verticesInContour.Length; i++)
    {
        OutlineRenderer.LineRendererActual.SetPosition(i, verticesInContour[i]);
    }


    foreach (GraphNode node in path.allNodes)
    {
        if (node != path.startNode)
        {
            // Create a new node prefab to indicate a node that can be reached
            // NOTE: If you are going to use this in a real game, you might want to
            // use an object pool to avoid instantiating new GameObjects all the time
            GameObject go = GameObject.Instantiate(GameManager.MoveIndicatorPrefab, (Vector3)node.position, Quaternion.identity) as GameObject;
            possibleMoves.Add(go);

            go.GetComponent<Astar3DButton>().node = node;
        }
    }
}

private void DrawContour(GridNodeBase[] nodesToContour)
{
    //use a version of the code below to draw the contours found above. May need to make the contours list into the scope of the entire class for access to it. Also, the vertices is a list of vector 3's that returns from the method and the => is the callback that handles those vertices.
    //I may be able to save that list of vector 3's and use it seperately in a linerenderer script to draw the outline on screen. I believe the below only draws it into the editor. Aslo, I am not sure I need to find the external nodes of the constant path as is done in the generate possible moves method above.
    //The images on the scripting manual web page make it look like the contour would wrap around the interior of them as well if i did not use all of the nodes... love this pathfinding project.

    GridGraph grid = AstarPath.active.data.gridGraph;

    GraphUtilities.GetContours(grid, vertices =>
    {
        verticesInContour = vertices;

        for (int i = 0; i < vertices.Length; i++)
        {
            Debug.DrawLine(vertices[i], vertices[(i + 1) % vertices.Length], Color.red, 4);
        }
    },

        0, nodesToContour);
}

}

#11

Could you show some examples of the outputs you are getting and which ones are expected and which are unexpected?


#12

Thanks for the quick reply. I went to go and get some snap shots and discovered a separate issue that may lead to my answer. I will follow the rabbit and let you know what I come up with.


#13

This is my fifth edit to this reply so I apologize if it gives you notifications each time I do. I keep thinking I figured something out and then end up back at square one. I will try to word the issue as best as I can from the observations I have made. I posted a couple pictures, but with my status cannot post anymore so I will try to use them as reference. I have a unit class that uses the pathfinding project library in addition to the new GraphUitilities.GetContours method. The unit class is in a turn based strategy game with designated movement points and turn states. That is somewhat irrelevant but I though I would make all information that might help known. I have followed and copied some of the work from the turn based strategy example. First I generate possible moves and then I pick all of the nodes from that move list and ask the GetContours method to draw a line around them using a linerenderer as well as the default debug lines in the editor. The whole process seems to work perfectly as long as I have a gameobject in the scene designated as an obstacle within movement range of the unit. Any time I assign the unit to move outside the range of the obstacles, the GetContours method returns no vertices on the callback. I have put debug logs throughout the actual method for GetContours to see where it is stopping and it seems to not be making it past the line of code where it checks to see “if there is an obstacle in that direction”. I don’t know if I am setting something up wrong in the editor or if I have made a dumb coding error somewhere. I have what I believe is the important lines from my code to find the problem but please let me know if I can post anything else that will help. The pictures actually tell this same story as well.

This picture below shows the units movement range when it is down to one movement point and an obstacle is near by.

This picture shows a different unit in the open with one movement range left and no contour showing around the potential movement choices.

Below is the current code I am using. I am not sure how to designate it as such in this post so it seems to not place my entire code into one scrollable area leaving off the top couple lines. Sorry, newb.

 public void GeneratePossibleMoves(Humanoid humanoid, int movementPoints)
    {
        ConstantPath path = ConstantPath.Construct(transform.position, (movementPoints * 1000 + 1) *2);
        path.traversalProvider = TraversalProvider;

        AstarPath.StartPath(path);

        path.BlockUntilCalculated();

        GridNodeBase[] nodesToContourAll = path.allNodes.Cast<GridNodeBase>().ToArray<GridNodeBase>();
        DrawContour(nodesToContourAll);

        foreach (GraphNode node in path.allNodes)
        {
            if (node != path.startNode)
            {
                GameObject go = GameObject.Instantiate(GameManager.MoveIndicatorPrefab, (Vector3)node.position, Quaternion.identity) as GameObject;
                possibleMoves.Add(go);

                go.GetComponent<Astar3DButton>().node = node;
            }
        }
    }

    private void DrawContour(GridNodeBase[] nodesToContour)
    {
        GridGraph grid = AstarPath.active.data.gridGraph;

        GraphUtilities.GetContours(grid, vertices =>
        {

            OutlineRenderer.TotalPointsOnPath = vertices.Length;
            OutlineRenderer.LineRendererActual.positionCount = OutlineRenderer.TotalPointsOnPath;
            for (int i = 0; i < OutlineRenderer.TotalPointsOnPath; i++)
            {
                OutlineRenderer.LineRendererActual.SetPosition(i, vertices[i]);
            }

            for (int i = 0; i < vertices.Length; i++)
            {
                Debug.DrawLine(vertices[i], vertices[(i + 1) % vertices.Length], Color.red, 4);
            }
        },

            0, nodesToContour);
    }

#14

Strange. Have you checked how many nodes the ConstantPath search returns? Is it only 1 or multiple ones?

One thing I’m noticing is that in the first example the sphere is intersecting the ground, but in the second example the sphere is a few units above the ground. Note that it will also count that distance above the ground and thus it might not have enough movement points to reach the adjacent nodes. Maybe you could snap it to the closest node instead:

var startPoint = (Vector3)AstarPath.active.GetNearest(transform.position).node.position;
... = ConstantPath.Construct(startPoint, ...);

#15

Hooray! New guy restrictions lifted…

I have checked that the constant path is returning the appropriate amount of nodes for the movement points. That was my first thought too but no luck. The image I think may have been confusing. In both images the spheres are halfway into the plane. The second one only looks like it is above for some reason. I changed the picture I had uploaded for the second image. I think it tells the story better. I also removed all obstacles. I implemented your start node line anyway to be sure and nothing changed.


#16

Ok, which version are you using?
Try upgrading to 4.1.10 if you are using an earlier version.


#17

I believe I am using the correct version. Here is a snapshot from the unity editor window of the change log. Is there any more information I could give you that might help? I am dumbfounded. I have read over the code like a thousand times and can’t seem to figure it out.


#18

Weird. Do you think you could share a simple test scene with me? Maybe there is a bug somewhere.


#19

I would love to have you look at my scene. How do I go about doing that?


#20

Hi

Just upload it to some file sharing service and then I can take a look at it.