Customization
The biggest power of AnyPath lies in the fact that you can easily extend it to use your own custom data structures.
To define your own graph type, create a struct that implements the IGraph interface. Then all that is needed is implementing the Collect function that let's the algorithm know which nodes connect to which nodes.
Additionaly, you can make an implementation of IHeuristicProvider to match your custom data structure.
The following example shows a very simple 2D grid that uses an array to store it's values:
namespace AnyPath.Examples
{
/// <summary>
/// An example of a simple 2D grid that uses a 1D array as backing
/// </summary>
public struct SimpleGrid : IGraph<int2>
{
private readonly int width;
private readonly int height;
private NativeArray<bool> cells;
public SimpleGrid(int width, int height, Allocator allocator)
{
this.width = width;
this.height = height;
this.cells = new NativeArray<bool>(width * height, allocator);
}
/// <summary>
/// Sets a wall at a given position. This cell will be unwalkable.
/// </summary>
public void SetWall(int2 position) => cells[PositionToIndex(position)] = true;
/// <summary>
/// Clears the wall at a given position. The cell will be walkable.
/// </summary>
public void ClearWall(int2 position) => cells[PositionToIndex(position)] = false;
/// <summary>
/// Returns wether there is a wall at a given position.
/// </summary>
public bool IsWall(int2 position) => cells[PositionToIndex(position)];
/// <summary>
/// Converts a position into a 1D index into the backing array
/// </summary>
private int PositionToIndex(int2 position) => position.x + position.y * width;
/// <summary>
/// Returns wether a position is in bounds of the grid
/// </summary>
public bool InBounds(int2 position) => position.x >= 0 && position.x < width && position.y >= 0 && position.y < height;
private static readonly int2[] directions =
{
new int2(0, 1), new int2(1, 0), new int2(0, -1), new int2(-1, 0),
};
/// <summary>
/// AnyPath will call this function many times during a pathfinding request. It should return the neighbouring cells from node
/// that are walkable.
/// </summary>
public void Collect(int2 node, ref NativeList<Edge<int2>> edgeBuffer)
{
// Loop over the four directions
for (int i = 0; i < directions.Length; i++)
{
var neighbour = node + directions[i];
// Skip this node if it's out of bounds, or if it is a wall
if (!InBounds(neighbour) || IsWall(neighbour))
continue;
// This neighbour is a valid location to go to next, add it to the edge buffer with a cost of one
edgeBuffer.Add(new Edge<int2>(neighbour, 1));
}
}
// Dispose of the inner NativeArray:
public void Dispose() => cells.Dispose();
public JobHandle Dispose(JobHandle inputDeps) => cells.Dispose(inputDeps);
}
/// <summary>
/// This struct will be used to provde a heuristic value for our pathfinding queries
/// </summary>
public struct SimpleGridHeuristc : IHeuristicProvider<int2>
{
public float Heuristic(int2 x, int2 goal)
{
// Manhattan distance
return math.dot(math.abs(x - goal), 1f);
}
}
}
Note
Because the algorithm runs in burst accelerated code, only a limited subset of C# is allowed in Graph, Path processing and Edge modifier code. See the following: https://docs.unity3d.com/Packages/com.unity.burst@0.2-preview.20/manual/index.html#cnet-language-support
Path Post Processing
Certain graph types can benefit from post processing the list of segments that is produced after a path has been found. For example, the included Navigation Mesh tries to straighten the path it has been found by applying a string pulling algorithm. See the API reference IPathProcessor<TNode, TSeg> for more details.
Note
All of the code that runs in the processor is still performed on the burst accellerated job, ensuring maximum speed.
Modifying and discarding edges on the fly
Say you have a graph that describes your static world but there are some locations contained in it that can have various states, like a door. You can implement your own edge modifer to incorporate such changes without the need to completely rebuild the graph. Saving significant overhead for large worlds.
See IEdgeMod<TNode> or the included 2D grid example on how to incorporate this.
Since verion 1.5, the edge modifiers have been expanded upon so you can also dynamically add edges to your graph on a per-query basis. This gives you the option to define portals, or have dynamic sections of your graph that change but don't require a full rebuild of the graph.
See AnyPath.Native.EdgeMods for details.
Another use case is filtering out unwanted areas using a flag bitmask. See FlagBitmask<TNode> for details.
Creating Finders
To use finders on this graph, you could fill in all of the generic type parameters to the ones defined in your graph, but this is not ideal. AnyPath comes with a tool to quickly generate readable finder definitions. To use it, go to Unity -> Window -> AnyPath Code Generator.
Clicking on the Scan Graph Definitions button will scan your project for graph types. Selecting a graph type will generate the code for all of the finder definitions, saving you the hassle of filling in all the type parameters by yourself.
Note
If you need a custom post processor associated with the finders, change the NoProcessing<,> into the type name of your processor struct.
Combinding several graphs
// This is an example of how you could combine several graphs as 'sections'
// where each section could be updated without affecting other sections
// you would keep the section graphs as separate containers somewhere else, and run the pathfinding query
// on this struct, which doesn't allocate the containers by itself
// the downside is, you'll need to hardcode the amount of sections contained because there is no way to have
// an array of NativeContainers in burst compiled code
public struct ComposedGraph<TGraph, TNode> : IGraph<TNode>
where TGraph : struct, IGraph<TNode>
where TNode : unmanaged, IEquatable<TNode>
{
public TGraph section1;
public TGraph section2;
public TGraph section3;
public TGraph section4;
public void Collect(TNode node, ref NativeList<Edge<TNode>> edgeBuffer)
{
// let each section decide if they have edges coming from this node
// e.g. if the current node was in section 1 and section 2 is connected to it, section 2 will add a node and so on
section1.Collect(node, ref edgeBuffer);
section2.Collect(node, ref edgeBuffer);
section3.Collect(node, ref edgeBuffer);
section4.Collect(node, ref edgeBuffer);
}
// we don't need any disposal here but rather the individual graph sections themselves should be disposed of
public void Dispose()
{
}
public JobHandle Dispose(JobHandle inputDeps) => inputDeps;
}