A* Pathfinding Project
4.1.19
The A* Pathfinding Project for Unity 3D
|
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.
The complete script can be found here PolarGraphGenerator.cs
The simplest graph possible looks like this:
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!
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 "circles" 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 are the connections between the nodes. The nodes themselves are placed at the intersections between those line segments.
The first step is to create a tempoary array for holding the nodes and add some variables 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.
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
Below is a very simple editor for the polar graph. Copy this code into the file you just crated. After you have done this you should be able to create the graph.
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".
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.
Now we need to get to work with actually creating a graph. 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.
Next. Assume we have a node at a given angle and in a given circle. We need to calculate the position for that node.
Now we will set up the rest of the graph, circle for circle, node for node
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:
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.
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.
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.
You should be able to create the graph, 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 methods can be overridden to customize other functionality. Especially the GetNearest and GetNearestForce methods. 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 your graph contains a lot of nodes. You can also override the OnDrawGizmos method if you want to draw the graph differently than the default implementation.
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.
Explaining all functions is beyond the scope of this tutorial, you can have a look at how other graph types have implemented them.
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.