A* Pathfinding Project

Creating Grid Graph from scratch


#1

I’m trying to create a new grid graph entirely in code, not modify an existing grid graph as id shown in the documentation or create a graph then scan it.

I think I’m close but not quite there. I am doing this:

 public void Generate()
    {
        GridGraph gg = m_Astar.data.AddGraph(typeof(GridGraph)) as GridGraph;
        m_Astar.PausePathfinding();

        //not sure if this section of code is needed as i think its for the scan feature which i don't want to use.
        gg.neighbours = NumNeighbours.Six;
        gg.uniformEdgeCosts = true;
        gg.isometricAngle = 60;
        gg.inspectorGridMode = InspectorGridMode.Hexagonal;
        //end

        int width = WorldData.hexData.GetLength(0);
        int height = WorldData.hexData.GetLength(1);
        GridNode[] nodes = new GridNode[width * height];
        GridNode.SetGridGraph(0, gg);
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                GridNode n = new GridNode(m_Astar);
                n.Walkable = WorldData.hexData[x, y].IsWalkable;
                n.NodeInGridIndex = (x + y * width); 
             
                Vector3 pos;
                WorldData.HexToWorld(new Grid2(x, y), out pos); 
                n.position = new Int3(pos);

                nodes[x + y * width] = n;
            }
        }
        gg.SetDimensions(width, height, 8);
        gg.center = new Vector3(0, 0, 0);
        gg.nodes = nodes;
        gg.GetNodes(node => gg.CalculateConnections((GridNodeBase)node));           
    }

That code give me this:

The red is the notwalkable nodes

But the walkable nodes seem to be missing.


Correct way to use AstarPath.active.Scan()
#2

Hi

It might be easier to use this code from the documentation: https://arongranberg.com/astar/docs/graph-updates.php#direct (see documentation for more details about this example).

AstarPath.active.AddWorkItem(new AstarWorkItem(ctx => {
    var gg = AstarPath.active.data.gridGraph;
    for (int z = 0; z < gg.depth; z++) {
        for (int x = 0; x < gg.width; x++) {
            var node = gg.GetNode(x, z);
            // This example uses perlin noise to generate the map
            node.Walkable = Mathf.PerlinNoise(x * 0.087f, z * 0.087f) > 0.4f;
        }
    }

    // Recalculate all grid connections
    // This is required because we have updated the walkability of some nodes
    gg.GetNodes(node => gg.CalculateConnections((GridNodeBase)node));

    // Update the 'area' information in the graph.
    // This is required because we have updated the connectivity of the graph
    ctx.QueueFloodFill();
}));

That does require an existing scanned graph, but you could also create one from scratch like this

// This holds all graph data
AstarData data = AstarPath.active.data;

// This creates a Grid Graph
GridGraph gg = data.AddGraph(typeof(GridGraph)) as GridGraph;

// Setup a grid graph with some values
int width = 50;
int depth = 50;
float nodeSize = 1;

// For making it a grid graph
gg.neighbours = NumNeighbours.Six;
gg.uniformEdgeCosts = true;
// This illustrates why it's usually easier to configure the settings in the unity inspector and then create the nodes from script
gg.isometricAngle = 90-Mathf.Atan(1/Mathf.Sqrt(2))*Mathf.Rad2Deg;
gg.inspectorGridMode = InspectorGridMode.Hexagonal;

gg.center = new Vector3(10, 0, 0);

// Updates internal size from the above values
gg.SetDimensions(width, depth, nodeSize);

// Scans all graphs
AstarPath.active.Scan();

(from https://arongranberg.com/astar/docs/gridgraph.html)

Note that the grid graph will not work at all if you try to assign positions to nodes that they couldn’t have had using a normal grid graph. The nearest neighbour lookups will fail completely.


#3

Thanks for the response,

I have tried that approach but is is somewhat tricky to align your hexagons with my hexagons as it requires you grid to be at a 135 angle and i have to swap width with height. Also you seem to have chosen something different to me for the node size as my hexagons are 1 unit centre to centre yours seem to be something different (width?).

Is it not possible to just make a grid and assign all connections manually? Then use that grid for pathfinding? I realise why you have made the code very visual and inspector based as this makes it easier for most people but all I am really interested in is the underlying path finding.

Thanks.

Ken


#4

Hi

You can set the rotation to plus or minus 45 degrees if you want to rotate it.

The sizes of the hexagons are not optimal right now though, I agree. It was never intended to be that way, but it happened due to a bug, and now I need to create some backwards compatible upgrade that fixes it.

Here are some reference pictures for size conversion:


If you want to just connect some points together in a completely custom way you can use a point graph or write your own graph (point graph is usually better).
This can be done using PointGraph.AddNode. However it will be slightly slower than a grid graph because it cannot take advantage of the grid like structure.
Also see this tutorial: https://arongranberg.com/astar/docs/writinggraphgenerators.html however I do recommend using the point graph instead because it is easier and it can optimize things a bit for you.


#5

Thanks for the info really helpful,

This is what I’m at now, its just off because the Graph Transform is wrong and I can’t work out how to correct it properly. I have tried overwriting it but it seems that it is recalculated very frame. Of course I could get round this by disabling that function. I’m not sure why the unwalkable nodes are positioned correctly while the walkable ones do something crazy. (they seems to respect this graph transform then remake the points into something new and not what was defined)

However is there no way I can just write directly to pathfinding. I don’t want it to do any walkability calculations all i want to do is define the array and connections penalties etc. Where about in the code are those hexagons calculated?? (I can’t seem to find it). Where can I write directly into the pathfinding? I can do all the conversions and required properties myself.

All i want to be able to do is the pathfinding I don’t want you program to try calculate the grid, transform the points or try to be smart in any way I just want it to do the actual pathfinding. I also don’t want to write a custom grid as I don’t want it to do any scanning calculations etc.

Thanks,

Ken


#6

Hi

If you want to do all setup yourself including arbitrary positions, then use the PointGraph.AddNode approach I described above. The reason you have to fiddle with the graph settings when using grid graphs is because the grid graph assumes the nodes are laid out in a particular pattern, which it uses when e.g searching for the closest node to a point.

The nodes in the grid graph are calculated in the GridGraph.ScanInternal method. The positions are set in the RecalculateCell method based on the GraphPointToWorld method which uses the graph transform.

If you are going to use a grid graph then I strongly recommend that you plot the hexagon points that you want to use in the editor somehow, then tweak the grid graph settings in the inspector until they line up perfectly, and then use those settings in your script.

Note that ‘Scanning’ is just what this package calls ‘generating the graph’.


#7

Thanks,

I think I understand now, sorry I wasn’t getting my head around the fact that your using fractional coordinates to work out the start index and that of course requires the graph to have the correct transform.

Think I will create my own graph that doesn’t do this then as in my world I as can easy covert already between hex indices and world points that’s why I was wanting to write straight into an array that isn’t converting anything as I just want to input array indices and retrieve indices or fractional indices.

Any hex in the world has the formula x’ = y * 0.5f + x, y’ = y * 0.8660254038f (this is Sqrt(3) / 2f) where x’ and y’ are array indices.

I can’t plot the hexagons in the editor beforehand as its all procedural gen therefore I have so idea of the scale, and offset there fore I have no idea where the centre should be or the size it needs to be. Also the island don’t exist until runtime

I’m going to try and write it so it is just working with the array and outputting the path in terms of indices instead of world positions and ignores all the transformations.

I will let you know how i get on,

Ken


#8

Ah, so you really don’t care at all for how the graph is laid out in the world?
Well in that case don’t bother with the graph transformations, just create a graph, any graph with the right width and depth and fill in your node values. I recommend that you scan a grid graph and then replace the scanned node data to minimize the hassle. This is because the nodes will need to be placed at reasonable positions in the world for A* to work (if you know some pathfinding, it is because the heuristic needs to be admissable).
Now the path requests that the system uses all find the closest node to the start and end points, in your case you don’t want to do that. But it is possible to work around it. You can create a custom Path class which allows you to set the start end end nodes.

I think this should work:

public MyABPath : ABPath {
    /** Construct a path with a start and end node.
     * The delegate will be called when the path has been calculated.
     * Do not confuse it with the Seeker callback as they are sent at different times.
     * If you are using a Seeker to start the path you can set \a callback to null.
     *
     * \returns The constructed path object
     */
    public static MyABPath Construct (GraphNode start, GraphNode end, OnPathDelegate callback = null) {
        var p = PathPool.GetPath<MyABPath>();
        p.Setup((Vector3)start.position, (Vector3)end.position, callback);
        startNode = start;
        endNode = end;
        return p;
    }

    protected override void Prepare () {
        // Nothing to do here
    }
}

Note that when the path has been calculated you can access all nodes it traversed using the .path field.

MyABPath path = ...;
for (int i = 0; i < path.path.Count; i++) {
    var gridNode = path.path[i] as GridNode;
    Debug.Log("Traversed: " + gridNode.XCoordinateInGrid + ", " + gridNode.ZCoordinateInGrid);
}

You can access nodes in the grid by index using GridGraph.GetNode(x,z).

So for example

var grid = ...;
var path = MyABPath.Construct(grid.GetNode(5, 3), grid.GetNode(8, 12), null);
AstarPath.SearchPath(path);
path.BlockUntilCalculated();

if (!path.error) {
    for (int i = 0; i < path.path.Count; i++) {
        var gridNode = path.path[i] as GridNode;
        Debug.Log("Traversed: " + gridNode.XCoordinateInGrid + ", " + gridNode.ZCoordinateInGrid);
    }
}

#9

Thanks that is exactly what I want to do!

Ken