Writing Custom Grid Graph Rules

This tutorial assumes you are at least somewhat familiar with grid graph rules.

If not, take a look at Grid Graph Rules first.

Contents

Why write a grid graph rule

Sometimes you want to modify the scanning process in some way. Maybe your game has its own rules about which nodes are walkable and you want to sync that with the grid graph. You could iterate through all the nodes after the graph has been scanned and apply whatever modifications you want, but this adds complexity and doesn't play nicely with graph updates.

When writing the logic as a grid graph rule it will work seamlessly with graph updates and scripts such as the ProceduralGraphMover. And you can easily use the Unity Job system and the Burst compiler to speed up the code significantly. There are also some helper methods included to make it very easy to for example make a filter for which connections in the grid should be valid and which ones are not valid.

How a rule works conceptually

A rule conceptually works like this:

  1. The rule registers itself and hooks into the scanning process.

  2. When the graph is scanned or updated it will call those hooks.

  3. Inside the hooks the rule can modify the graph data as it wishes.

A rule can register itself to hook into at different points in the scanning process. These points are called passes. Most rules only use a single pass, but it can register multiple ones if it wishes to.

Pass

Where in the scanning process a rule will be executed.

Rules are called both when scanning a graph and when the graph is being updated. However when the graph is being updated it will only provide data for a smaller sub-rectangle of the grid. Your grid graph rule must take this into account and not just assume it is used on the whole graph all the time (see also Data layout).

Rules can be placed anywhere in your project. They will be found dynamically and you will be able to add them using the 'Add Rule' button in the grid graph inspector. You can also add a custom editor GUI to your rule if you want to be able to change its settings from the inspector.

Unity Job System or Main Thread

You have two options for how to run rules

  • Run them on the main thread. This is easier, has less boilerplate and you can access non-thread-safe data from the rule.

  • Run them using the Unity Job System. This has some additional boilerplate, but the job can be run in parallel with other grid graph scanning code and it can use the Burst compiler. This makes it possible to write very fast jobs this way.

For your first job I'd recommend writing a job that runs on the main thread, and if you need the performance you can switch to the job system.

In the following sections a few examples of rules will be shown.

Writing a simple example rule

Let's write a simple rule that sets the walkability for the nodes based on a noise function. The result will look something like this:

To do this we need to iterate through every node and set its walkability.

using UnityEngine;
using Pathfinding;
using Pathfinding.Graphs.Grid.Rules;

// Mark with the Preserve attribute to ensure that this class is not removed when bytecode stripping is used. See https://docs.unity3d.com/Manual/IL2CPP-BytecodeStripping.html
[Pathfinding.Util.Preserve]
public class RuleExampleNodes : GridGraphRule {
public float perlinNoiseScale = 10.0f;
public float perlinNoiseThreshold = 0.4f;

public override void Register (GridGraphRules rules) {
// The Register method will be called once the first time the rule is used
// and it will be called again if any settings for the rule changes in the inspector.
// Use this part to do any precalculations that you need later.

// Hook into the grid graph's calculation code
rules.AddMainThreadPass(Pass.BeforeConnections, context => {
// This callback is called when scanning the graph and during graph updates.
// Here you can modify the graph data as you wish.
// The context.data object contains all the node data as NativeArrays
// Not all data is valid for all passes since it may not have been calculated at that time.
// You can find more info about that on the documentation for the GridGraphScanData object.

// Get the data arrays we need
var nodeWalkable = context.data.nodes.walkable;
var nodePositions = context.data.nodes.positions;

// We iterate through all nodes and mark them as walkable or unwalkable based on some perlin noise
for (int i = 0; i < nodePositions.Length; i++) {
var position = nodePositions[i];
nodeWalkable[i] &= Mathf.PerlinNoise(position.x / perlinNoiseScale, position.z / perlinNoiseScale) > perlinNoiseThreshold;
}
});
}
}

See

In the callback for when the rule is being executed you get a context object with a lot of data about the graph. Take a look at the GridGraphRules.Context class for more info about what data there is to use. In particular the data field of that class which is an instance of the GridGraphScanData class.

You can place this anywhere and it will show up when clicking the "Add Rule" button in the GridGraph inspector.

Every rule also needs a corresponding editor script to be able to show its settings. You should place this script in an Editor folder.

using Pathfinding.Graphs.Grid.Rules;
using UnityEditor;
using UnityEngine;

namespace Pathfinding {
[CustomGridGraphRuleEditor(typeof(RuleExampleNodes), "Simple Example Rule")]
public class RuleExampleNodesEditor : IGridGraphRuleEditor {
public void OnInspectorGUI (GridGraph graph, GridGraphRule rule) {
var target = rule as RuleExampleNodes;

target.perlinNoiseScale = EditorGUILayout.FloatField("Noise Scale", target.perlinNoiseScale);
target.perlinNoiseThreshold = EditorGUILayout.FloatField("Noise Threshold", target.perlinNoiseThreshold);
}

public void OnSceneGUI (GridGraph graph, GridGraphRule rule) { }
}
}

Now the rule will work! Below you can see a video of how this simple rule works.

Writing a rule that uses the Unity Job System

When using the Unity Job System we will use the AddJobSystemPass method instead of the AddMainThreadPass. In this method you should only schedule jobs, not access the data itself.

We can rewrite our previous simple rule to use the job system. We will also use a nice helper function GridIterationUtilities.ForEachNode. To use it our job struct needs to implement the GridIterationUtilities.INodeModifier interface. It will be called once for every relevant node. Note that during graph updates it may only be called for a few nodes, not all nodes in the graph.

using UnityEngine;
using Unity.Collections;
using Unity.Jobs;
using Unity.Burst;
using Unity.Mathematics;
using Pathfinding;
using Pathfinding.Jobs;
using Pathfinding.Graphs.Grid;
using Pathfinding.Graphs.Grid.Rules;

[Pathfinding.Util.Preserve]
public class RuleExampleNodesBurst : GridGraphRule {
public float perlinNoiseScale = 10.0f;
public float perlinNoiseThreshold = 0.4f;

public override void Register (GridGraphRules rules) {
// Here we use the job system instead of running the rule on the main thread.
// Note that in that case we should *only schedule jobs* inside the callback.
// The data is not safe to access directly in the callback.
rules.AddJobSystemPass(Pass.BeforeConnections, context => {
// This callback is called when scanning the graph and during graph updates.
// The only thing we do is to schedule a job using the Unity job system.
// You do not have to deal with dependencies yourself
// just make sure you use the appropriate [ReadOnly] or [WriteOnly] tags
// See https://docs.unity3d.com/Manual/JobSystem.html for more info.
// The context.data object contains all the node data as NativeArrays
new JobExample {
bounds = context.data.nodes.bounds,
nodeWalkable = context.data.nodes.walkable,
nodePositions = context.data.nodes.positions,
nodeNormals = context.data.nodes.normals,
perlinNoiseScale = perlinNoiseScale,
perlinNoiseThreshold = perlinNoiseThreshold,
}.Schedule(context.tracker);
});
}

[BurstCompile]
struct JobExample : IJob, GridIterationUtilities.INodeModifier {
public IntBounds bounds;
public float perlinNoiseScale;
public float perlinNoiseThreshold;

public NativeArray<bool> nodeWalkable;
[ReadOnly]
public NativeArray<Vector3> nodePositions;
[ReadOnly]
public NativeArray<float4> nodeNormals;

public void Execute () {
// Used to efficiently iterate through all nodes that are being calculated.
// The nodeNormals array is used by the ForEachNode function to determine if a node exists.
// The normal is (0,0,0) if and only if the node doesn't exist (important for layered grid graphs).
GridIterationUtilities.ForEachNode(bounds.size, nodeNormals, ref this);
}

public void ModifyNode (int dataIndex, int dataX, int dataLayer, int dataZ) {
var position = nodePositions[dataIndex];

nodeWalkable[dataIndex] &= Mathf.PerlinNoise(position.x / perlinNoiseScale, position.z / perlinNoiseScale) > perlinNoiseThreshold;
}
}
}

Note

Normally when the Unity Job System is used you have to specify the dependencies of the jobs manually. This is tedious and error prone, so a helper script is used which will read the [ReadOnly] and [WriteOnly] attributes that you use on fields in the job structs and automatically calculate the dependencies for you. For more info take a look at the JobDependencyTracker class.

Connection filters using the Unity Job System

Another common situation is that you want to control which node connections are traversable and which ones are not. You can do this easily with the IConnectionFilter interface and the FilterNodeConnections function.

using UnityEngine;
using Unity.Collections;
using Unity.Jobs;
using Unity.Burst;
using Unity.Mathematics;
using Pathfinding;
using Pathfinding.Jobs;
using Pathfinding.Graphs.Grid.Rules;
using Pathfinding.Graphs.Grid;

[Pathfinding.Util.Preserve]
public class RuleExampleConnection : GridGraphRule {
public override void Register (GridGraphRules rules) {
rules.AddJobSystemPass(Pass.AfterConnections, context => {
new JobExample {
bounds = context.data.nodes.bounds,
nodeConnections = context.data.nodes.connections,
nodeWalkable = context.data.nodes.walkable,
nodePositions = context.data.nodes.positions,
layeredDataLayout = context.data.nodes.layeredDataLayout,
}.Schedule(context.tracker);
});
}

[BurstCompile]
struct JobExample : IJob, GridIterationUtilities.IConnectionFilter {
public IntBounds bounds;
public NativeArray<ulong> nodeConnections;

[WriteOnly]
public NativeArray<bool> nodeWalkable;
[ReadOnly]
public NativeArray<Vector3> nodePositions;
public bool layeredDataLayout;

public void Execute () {
GridIterationUtilities.FilterNodeConnections(bounds, nodeConnections, layeredDataLayout, ref this);
}

public bool IsValidConnection (int dataIndex, int dataX, int dataLayer, int dataZ, int direction, int neighbourDataIndex) {
// Get our position and the adjacent node's position
var position = nodePositions[dataIndex];
var neighbourPosition = nodePositions[neighbourDataIndex];

// Only allow a connection if the adjacent node differs less
// than 1 meter from this one along the Y coordinate.
// This is similar to "Max Climb" in the GridGraph settings.
return math.abs(position.y - neighbourPosition.y) < 1.0f;
}
}
}

See

Data layout for details about how the nodes are laid out in memory.

The IsValidConnection method will be called for every connection that is being updated. It will only be called for connections that are valid at that point in the scanning process. This means that you cannot enable connections that were previously disabled.

Data layout

When a grid graph is scanned or updated all the temporary data is stored in NativeArrays. When only a small section of the grid graph is updated these temporary arrays will be smaller than the whole graph, so you cannot access them with the same indices as the normal nodes.

Note

The code uses the naming convention dataX and dataZ to refer to the x and z coordinates in the NativeArrays used in this graph update/scan.

dataX and dataZ may not correspond to the x and z coordinates in the actual graph since graph updates usually only affect a small portion of the graph. You can convert them to the grid x and z coordinates like this: gridX = dataX + bounds.xmin;
gridZ = dataZ + bounds.zmin;

If you do not use the IConnectionFilter, you can access the neighbours of a node using the GridIterationUtilities.GetNeighbourDataIndex method.