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 System.Collections;
//Include generics to be able to use Generics
using System.Collections.Generic;
//Include the Pathfinding namespace to gain access to a lot of useful classes
using Pathfinding;
using JsonFx.Json;

//Inherit our new graph from a base graph type
[JsonOptIn]
public class SimpleGraph : NavGraph {
    
    public override void Scan () {
        //Here we will place our code for scanning 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 Scan function is called when the graph should be scanned. A Scan function should create a number of nodes and place them in the nodes variable.
We will create a Polar Graph, i.e sort of like a grid, but laid out as a circle with rings instead of rows:

The first step is to create the nodes and add some varibles to use

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

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

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

Every code sample 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

Matrix4x4 matrix = Matrix4x4.TRS (center,Quaternion.identity,Vector3.one*scale);
        
nodes[0].position = matrix.MultiplyPoint (Vector3.zero);

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

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

for (int i=1;i<circles;i++) {
    
    for (int j=0;j<steps;j++) {
        //Get the angle to the node relative to the center
        float angle = j * anglesPerStep;
        
        //Get the direction towards the node from the center
        Vector3 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 *= i;
        
        //Multiply it with the matrix to get the node position in world space
        pos = matrix.MultiplyPoint (pos);
        
        //Get the node from an index
        //The middle 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
        
        Node node = nodes[(i-1)*steps + j + 1];
        
        //Assign the node position
        node.position = 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:

//Now all nodes are created, let's create some connections between them!
        
//Loop through all circles except the first one which is only one point
for (int i=1;i<circles;i++) {
    
    for (int j=0;j<steps;j++) {
        //Get the current node
        Node node = nodes[(i-1)*steps + j + 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 = (i < circles-1) ? 4 : 3;
        Node[] connections = new Node[numConnections];
        int[] connectionCosts = new int[numConnections];
        
        //Get the next clockwise node in the current circle.
        //If j++ would overflow steps, it would create a connection to the first node in the next circle, so if it does
        //we have to prevent it by setting the steps index to 0 which will then create a connection to the correct node
        int connId = (i-1)*steps + (j < steps-1 ? j+1 : 0) + 1;
        connections[0] = nodes[connId];
        
        //Counter clockwise node. Here we check for underflow instead
        connId = (i-1)*steps + (j > 0 ? j-1 : steps-1) + 1;
        connections[1] = nodes[connId];
        
        //The node in the next circle (out from the center)
        if (i > 1) {
            connId = (i-2)*steps + j + 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 = i*steps + j + 1;
            connections[3] = nodes[connId];
        }
        
        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
Node centerNode = nodes[0];
centerNode.connections = new Node[steps];
centerNode.connectionCosts = new int[steps];
//Assign all nodes in the first circle as connections to the center node
for (int j=0;j<steps;j++) {
    centerNode.connections[j] = nodes[1+j];
}

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.
But the graph does not yet show up in the Add New Graph list, 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 UnityEngine;
using UnityEditor;
using System.Collections;
using Pathfinding;

[CustomGraphEditor (typeof(PolarGraph),"Polar Graph")]
public class PolarGeneratorEditor : GraphEditor {
    
    //Here goes the GUI
    public override void OnInspectorGUI (NavGraph target) {
        
        PolarGraph 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);
        
    }
}

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.

So here is the complete script:

using UnityEngine;
using System.Collections;
//Include generics to be able to use Generics
using System.Collections.Generic;
//Include the Pathfinding namespace to gain access to a lot of useful classes
using Pathfinding;
using JsonFx.Json;

//Inherit our new graph from a base graph type
[JsonOptIn]
public class PolarGraph : NavGraph {
    
    [JsonMember]
    public int circles = 10;
    [JsonMember]
    public int steps = 20;
    
    [JsonMember]
    public Vector3 center = Vector3.zero;
    
    [JsonMember]
    public float scale = 2;
    
    public override void Scan () {
        
        //Create an array containing all nodes
        nodes = CreateNodes (circles*steps);
        
        Matrix4x4 matrix = Matrix4x4.TRS (center,Quaternion.identity,Vector3.one*scale);
        
        nodes[0].position = matrix.MultiplyPoint (Vector3.zero);
        
        //The number of angles (in radians) each step will use
        float anglesPerStep = (2*Mathf.PI)/steps;
        
        for (int i=1;i<circles;i++) {
            
            for (int j=0;j<steps;j++) {
                //Get the angle to the node relative to the center
                float angle = j * anglesPerStep;
                
                //Get the direction towards the node from the center
                Vector3 pos = new Vector3 (Mathf.Sin (angle),0, Mathf.Cos (angle));
                
                //Multiply it with scale and the circle number to get the node position in graph space
                pos *= i*scale;
                
                //Multiply it with the matrix to get the node position in world space
                pos = matrix.MultiplyPoint (pos);
                
                //Get the node from an index
                //The middle 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
                
                Node node = nodes[(i-1)*steps + j + 1];
                
                //Assign the node position
                node.position = pos;
                
            }
        }
        
        //Now all nodes are created, let's create some connections between them!
        
        //Loop through all circles except the first one which is only one point
        for (int i=1;i<circles;i++) {
            
            for (int j=0;j<steps;j++) {
                //Get the current node
                Node node = nodes[(i-1)*steps + j + 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 = (i < circles-1) ? 4 : 3;
                Node[] connections = new Node[numConnections];
                int[] connectionCosts = new int[numConnections];
                
                //Get the next clockwise node in the current circle.
                //If j++ would overflow steps, it would create a connection to the first node in the next circle, so if it does
                //we have to prevent it by setting the steps index to 0 which will then create a connection to the correct node
                int connId = (i-1)*steps + (j < steps-1 ? j+1 : 0) + 1;
                connections[0] = nodes[connId];
                
                //Counter clockwise node. Here we check for underflow instead
                connId = (i-1)*steps + (j > 0 ? j-1 : steps-1) + 1;
                connections[1] = nodes[connId];
                
                //The node in the next circle (out from the center)
                if (i > 1) {
                    connId = (i-2)*steps + j + 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 = i*steps + j + 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] = (node.position-connections[q].position).costMagnitude;
                }
                
                node.connections = connections;
                node.connectionCosts = connectionCosts;
            }
        }
        
        //The center node is a special case, so we have to deal with it separately
        Node centerNode = nodes[0];
        centerNode.connections = new Node[steps];
        centerNode.connectionCosts = new int[steps];
        //Assign all nodes in the first circle as connections to the center node
        for (int j=0;j<steps;j++) {
            centerNode.connections[j] = nodes[1+j];
            
            //centerNode.position is an Int3, here we get the cost of moving between the two positions
            centerNode.connectionCosts[j] = (centerNode.position-centerNode.connections[j].position).costMagnitude;
        }
        
        //Set all the nodes to be walkable
        for (int i=0;i<nodes.Length;i++) {
            nodes[i].walkable = true;
        }
    }
}

More Stuff

More functions can be overridden to customize other functionality. Especially the GetNearest, GetNearestForce and CreateNodes functions. Which control how the nearest node to a point is found and which node type to use for the graph. Also, 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.