Performance considerations and heuristics
The performance of A* depends mostly on how good we can estimate the actual cost of travelling from A to B. The better this estimate actually matches the true distance from A to B, the less nodes A* has to look at before finding a path.
A heuristic function is said to be admissable as long as it not overestimates the cost between two nodes. As long as your heuristic function is admissable, A* is guarantueed to always return the shortest path possible between two nodes.
One way to lower the amount of nodes that A* has to expand into, is to slightly over estimate the cost. The caveat being that the resultign path may not be the actual shortest path, but in many cases, this will be good enough.
Here's a way to implement a heuristic provider for a 2D grid that overestimates the cost:
public struct RelaxedGridHeuristics : IHeuristicProvider<int2>
{
public readonly float relaxation;
private int2 goal;
public RelaxedGridHeuristics(float relaxtion)
{
this.relaxation = relaxtion;
}
public void SetGoal(int2 goal)
{
// this will be called before A* starts, all measurements happen from x to the goal.
// store the goal value internally for later usage
this.goal = goal;
}
public float Heuristic(int2 x)
{
// the higher the value of relaxation is, the more A* will try to expand in a straight line towards the destination.
// this can greatly reduce the amount of cells that are expanded into, but may not always result in the truly shortest path
// in many cases however, this is not a big deal, especially if the over estimation is low.
// the dot(abs(x - goal), 1f) calculation is just a fast way to calculate manhattan distance on a grid.
return (1 + relaxation) * dot(abs(x - goal), 1f);
}
}
ALT
We can do much better however, by using ALT heuristics.
ALT stands for Admissable Landmarks and Triangle Inequality and is explained in this paper: https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/?from=http%3A%2F%2Fresearch.microsoft.com%2Fpubs%2F154937%2Fsoda05.pdf
The great thing about ALT heuristics is that it works on any type of graph. So this heuristic provider can be used with all of the built in graphs but also on a custom graph type without requiring extra coding.
The trade off for using ALT heuristics is pre processing time and memory consumption. ALT works by selecting a small amount of nodes as "Landmarks". These landmarks are spread out over your graph, ideally placed "behind" frequent starting and goal locations. In the preprocessing stage, distances to and from every landmark are computed. When running A*, these landmark distances can then be used to produce a far better estimate of the true distance between two nodes. Especially on true graph like structures (where eucludian distance performs pretty bad) and maze like structures.
The image below shows the difference between ALT and regular heuristics. The red squares represent the path, the purple squares represent the cells that A* expanded into without using ALT heuristics, the green ones with ALT.
Generating ALT heuristics for your graph
There are 2 stages to generating ALT heuristics for your graph. The first is, selecting which landmarks to use. AnyPath provides two ways to automatically do this. Alternatively, you can manually specify the locations for your landmarks if that works better for your use case.
Once you have your landmark locations, we can contruct the ALT heuristic provider.
// This will store our landmarks, a maximum of 31 is supported
SquareGridCell[] landmarks = new SquareGridCell[31];
// Scans the entire grid and selects landmarks that are spaced apart evenly
LandmarkSelection<SquareGrid, SquareGridCell, SquareGrid.Enumerator>.SelectFarthestLandmarksUndirected(ref grid, grid.GetEnumerator(), landmarks);
// Create our heuristic provider
altHeuristics = new ALT<SquareGridCell>(Allocator.Persistent);
// Compute it for the landmarks we've selected
ALTCompute<SquareGrid, SquareGridCell>.ComputeUndirected(altHeuristics, ref grid, landmarks);
Now for our pathfinding queries, we generate the code for a Finder that uses this provider. We then only need to assign the heuristic provider before making the query:
pathFinder
.SetGraph(grid)
.SetHeuristicProvider(altHeuristics) // assign our ALT heuristics
.SetStartAndGoal(start, goal)
.Run(); // runs on the main thread immediately
Note
Keep in mind that the ALT heuristic provider contains NativeContainers and needs to be disposed when it is no longer used.
Note
Note that we must explicity tell the types for computing ALT heuristics and landmark selection. This is due to a limitation by the burst compiler. For all included graph types this is fairly straightforward. Provide the type of graph, node and the enumerator type, which is usually GRAPH.Enumerator For more information see: https://docs.unity3d.com/Packages/com.unity.burst@1.8/manual/compilation-generic-jobs.html
Directed and undirected
Preprocessing for ALT heuristics is not a cheap operation. The computation of landmark selection and preprocessing is burst compiled and multithreaded where possible. It can still take quite some time for large graphs however. If you know your graph is undirected (which most are), we can cut the processing time in half by using the undirected counterparts of the methods. Of all of the built in graph types, only the PlatformerGraph supports directed edges. And if you don't use directed edges in the platformer graph, you can treat it as an undirected graph.
Note
To compute ALT heuristics for directed graphs, you need to compute a ReversedGraph<TNode> first.
ALT and graph updates/edge mod
As long as edge costs increase, it is not strictly neccessary to recompute ALT heuristics. The bigger the change however, the more off ALT heuristics will be and you will lose some of the performance benefits.
Serializing ALT heuristics
If you have very large static worlds, it may be benificial to serialize the heuristic data and compress it. AnyPath provides the ReadFrom and WriteTo extension methods for usage with a BinaryReader/Writer. You'll only need to provide a function that writes and reads the node data:
public void Read(ALT<SquareGridCell> alt, BinaryReader reader)
{
alt.ReadFrom(reader, reader =>
{
// read X and Y and convert back into cell struct
return new SquareGridCell(new int2(reader.ReadInt32(), reader.ReadInt32()));
});
}
public void Write(ALT<SquareGridCell> alt, BinaryWriter writer)
{
alt.WriteTo(writer, (writer, cell) =>
{
// Just write the X and Y components
writer.Write(cell.Position.x);
writer.Write(cell.Position.y);
});
}
Note
Benchmarking is the way to go here. Your results may vary depending on the size and complexity of your graph. On my machine, computing for a 1000x1000 sized grides takes about 20ms with burst compilation enabled. Serializing the data in such a case may not be useful.