Writing Graph Generators

All graphs in the A* Pathfinding Project are written as add-ons to the system, this makes it (relatively) easy to add your own specialized graph types.

In this tutorial I will show you how to set up a basic Graph Generator which you can use with the system.

A Basic Graph

The simplest graph possible looks like this:

using UnityEngine;
using Pathfinding;
using Pathfinding.Serialization.JsonFx;
using Pathfinding.Serialization;

// Inherit our new graph from a base graph type
[JsonOptIn]
public class SimpleGraph : NavGraph {
    
    public override void ScanInternal (OnScanStatus statusCallback) {
        // Here we will place our code for scanning the graph
    }
    
    public override void GetNodes (GraphNodeDelegateCancelable del) {
        // This method should call the delegate with all nodes in the graph
    }
}

This graph will not generate any nodes, but it should show up greyed out in the Add New Graph list
So let's start creating some scanning logic!

Scanning

First, create a new script containing the code above, but rename it to PolarGraph and save it as PolarGraph.cs.

The ScanInternal method is called when the graph should be scanned. A Scan method should create a number of nodes and create connections between them. We will create a Polar Graph, i.e sort of like a grid, but laid out as a circle with rings instead of rows. I will use "rings" to denote the number of concentric rings in the graph and "steps" as the number of nodes in each circle. Note that in the image below, what you are seeing is the connections between nodes so the nodes themselves are placed at the intersections between those line segments.

The first step is to create the nodes and add some varibles for configuring the graph. We will use the PointNode node type which is used by the PointGraph since it contains essentially the same things that we want to use.

public int circles = 10;
public int steps = 20;

public Vector3 center = Vector3.zero;
public float scale = 2;

// Here we will store all nodes in the graph
PointNode[] nodes;

// Create nodes and return the new array 
PointNode[] CreateNodes (int count) {
    var created = new PointNode[count];
    for (int i = 0; i < created.Length; i++) {
        created[i] = new PointNode(active);
    }
    return created;
}

public override void Scan () {
    // Create an array containing all nodes
    nodes = CreateNodes (circles*steps);
}

Every code fragment below this point should go into the Scan function.

We will use a matrix for placement to enable rotation, positioning and so on of the nodes.
The first node in the array should be the center node which we will place at Vector3.zero. Node positions are stored as Int3s. They are like Vector3s but use integer coordinates instead of floating point coordinates. There is an explicit cast available between Vector3 and Int3.

// Create a matrix which just moves the nodes to #center
// and scales their positions by #scale
// The SetMatrix call will save it to a variable called just "matrix"
SetMatrix (Matrix4x4.TRS (center,Quaternion.identity,Vector3.one*scale));

// Place the center node in the center
nodes[0].position = (Int3)matrix.MultiplyPoint (Vector3.zero);

Next. Assume we have a node at a given angle and in a given circle. We need to calculate the position for that node.

static Vector3 CalculateNodePosition (int circle, float angle, Matrix4x4 matrix) {
    // Get the direction towards the node from the center
    var pos = new Vector3 (Mathf.Sin (angle),0, Mathf.Cos (angle));
    
    // Multiply it with the circle number to get the node position in graph space
    pos *= circle;
    
    // Multiply it with the matrix to get the node position in world space
    pos = matrix.MultiplyPoint (pos);
    return pos;
}

Now we will set up the rest of the graph, circle for circle, node for node

// The number of angles (in radians) each step will use
float anglesPerStep = (2*Mathf.PI)/steps;

// Iterate through all circles
// circle 0 is the center node so we skip that for now
for (int circle = 1; circle < circles; circle++) {
    for (int step = 0; step < steps; step++) {
        // Get the angle to the node relative to the center
        float angle = step * anglesPerStep;

        Vector3 pos = CalculateNodePosition (circle, angle, matrix);

        // Get the node from an index
        // The center node is at index 0
        // The first circle is from 1...steps-1
        // The second circle is from steps...2*steps-1
        // The third is from 2*steps...3*steps-1 and so on
        
        GraphNode node = nodes[(circle-1)*steps + step + 1];
        
        // Assign the node position
        node.position = (Int3)pos;
    }
}

Now we have set up all the nodes to their correct positions, but they have no connections to other nodes, so let's add that:

// Loop through all circles except the first one which is only one point
for (int circle = 1; circle < circles; circle++) {
    for (int step = 0; step < steps; step++) {
        // Get the current node
        PointNode node = nodes[(circle-1)*steps + step + 1];
        
        // The nodes here will always have exactly four connections, like a grid, but polar.
        // Except for those in the last circle which will only have three connections
        int numConnections = (circle < circles-1) ? 4 : 3;
        var connections = new GraphNode[numConnections];
        var connectionCosts = new uint[numConnections];
        
        // Get the next clockwise node in the current circle.
        // The last node in each circle should be linked to the first node
        // in the circle. But if we just did step+1 we would link it to the
        // first node in the *next* circle, which we do not want
        int connId = (circle-1)*steps + (step < steps-1 ? step+1 : 0) + 1;
        connections[0] = nodes[connId];
        
        // Counter clockwise node. Here we check for underflow instead
        connId = (circle-1)*steps + (step > 0 ? step-1 : steps-1) + 1;
        connections[1] = nodes[connId];
        
        // The node in the previous circle (in towards the center)
        if (circle > 1) {
            connId = (circle-2)*steps + step + 1;
        } else {
            // Create a connection to the middle node, special case
            connId = 0;
        }
        connections[2] = nodes[connId];
        
        // Are there any more circles outside this one?
        if (numConnections == 4) {
            // The node in the next circle (out from the center)
            connId = circle*steps + step + 1;
            connections[3] = nodes[connId];
        }
        
        for (int q=0;q<connections.Length;q++) {
            // Node.position is an Int3, here we get the cost of moving between the two positions
            connectionCosts[q] = (uint)(node.position-connections[q].position).costMagnitude;
        }
        
        node.connections = connections;
        node.connectionCosts = connectionCosts;
    }
}

The first node (the center) is a special case, it will have connections to all nodes in the first circle (or second depending on how you look at it).
This means that it will have steps connections, because steps is the number of nodes in each circle and all the nodes in circle one are laid out between index 1 and steps in the nodes array.

// The center node is a special case, so we have to deal with it separately
PointNode centerNode = nodes[0];
centerNode.connections = new GraphNode[steps];
centerNode.connectionCosts = new uint[steps];

// Assign all nodes in the first circle as connections to the center node
for (int step = 0; step < steps; step++) {
    centerNode.connections[step] = nodes[1+step];
    
    // centerNode.position is an Int3, here we get the cost of moving between the two positions
    centerNode.connectionCosts[step] = (uint)(centerNode.position-centerNode.connections[step].position).costMagnitude;
}

Now the only thing left to do, is to make the nodes walkable, the default value is unwalkable. This tutorial will not cover the checking for obstacles or similar, but if you read up on Unity's Physics class you should be able to get that working yourself.

// Set all the nodes to be walkable
for (int i = 0; i < nodes.Length; i++) {
    nodes[i].Walkable = true;
}

If you have placed all the previous snippets after each other in the Scan function like I wrote before, you will have a working scan function.

Finally to be able to scan the graph the GetNodes method needs to be implemented. Since all our nodes are just stored in an array, it is very simple.

public override void GetNodes(GraphNodeDelegateCancelable del) {
    if (nodes == null) return;

    for (int i = 0; i < nodes.Length; i++) {
        // Call the delegate and check if it wants
        // more nodes or not
        if (!del(nodes[i])) {
            // If it did not want more nodes
            // then just return
            return;
        }
    }
}

The graph does not yet show up in the Add New Graph list because that requires a graph editor which we will create now. Create a new script in either AstarPathfindingProject/Editor/GraphEditors/ (or if you have enabled Js support AstarPathfindingEditor/Editor/GraphEditors/) or in any other Editor folder.
Name the script PolarGeneratorEditor.cs

I have below written the a very simple Graph Editor for the polar graph, and it will now show up in the Add New Graph list:

using UnityEditor;
using Pathfinding;

[CustomGraphEditor (typeof(PolarGraph),"Polar Graph")]
public class PolarGeneratorEditor : GraphEditor {

    // Here goes the GUI
    public override void OnInspectorGUI (NavGraph target) {

        var graph = target as PolarGraph;

        graph.circles = EditorGUILayout.IntField ("Circles",graph.circles);
        graph.steps = EditorGUILayout.IntField ("Steps",graph.steps);
        graph.scale = EditorGUILayout.FloatField ("Scale",graph.scale);
        graph.center = EditorGUILayout.Vector3Field ("Center",graph.center);
    }
}

The CustomGraphInspector attribute tells the system that this class is a custom editor for the graph of type PolarGraph, the display-name in the graphs list will be "Polar Graph".
Now you can try it out! Open the Graphs tab in the AstarPath inspector, click Add Graph, and add the Polar Graph which should be in the list now. You should be able to edit the parameters and if you click Scan the graph will appear in the Scene View.
Cool huh?

However, you might notice that if you deselect the inspector and then select it again, your settings have not been saved.
This is because we need to add one last thing, serialization.
All graph settings are serialized to JSON (see http://www.json.org/). For the fields to get serialized, we must add an attribute to each field. The JsonMember attribute will tell the serializer that we want to serialize that field.

The complete script can be found here PolarGraphGenerator.cs

More Stuff

More functions can be overridden to customize other functionality. Especially the GetNearest, GetNearestForce. Which control how the nearest node to a point is found. There is a default implementation but it will search through all nodes in the graph every time which can be a bit slow if you have lots of nodes.

If you need to serialize more information, you can override the SerializeExtraInfo, DeserializeExtraInfo and if you need to set up nodes after they have been loaded, you can override the PostDeserialization function. If you want to add custom gizmos to your graph, you can override the OnDrawGizmos function.

Explaining all functions is beyond the scope of this tutorial, you can have a look at how other graph types have implemented them.

The End

You should now be able to use this graph like any other graph!
I hope this tutorial has helped you get started writing graph generators.

Version

Tested with version 3.6.7