Struct ALT<TNode>

ALT heuristic provider that works on any type of graph. This can significantly speed up A* queries on large and complex graphs. Based on this research: 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

To generate ALT heuristics, you must use ALTCompute<TGraph, TNode> and optionally LandmarkSelection<TGraph, TNode, TEnumerator>. The included Square grid example demonstrates this process.

Implements
Namespace: AnyPath.Native.Heuristics
Assembly: AnyPath.dll
Syntax
public struct ALT<TNode> : IHeuristicProvider<TNode>, IDisposable where TNode : unmanaged, IEquatable<TNode>
Type Parameters
Name Description
TNode
Remarks

For best results, landmarks should be placed "behind" frequent start and goal locations.

Constructors

ALT(Allocator)

Allocates an ALT heuristic provider.

Declaration
public ALT(Allocator allocator)
Parameters
Type Name Description
Allocator allocator

Allocator for the ALT heuristics.

Properties

IsDirected

Returns wether this ALT heuristic provider was made for a directed graph.

Declaration
public bool IsDirected { get; }
Property Value
Type Description
bool

LandmarkCount

Returns the amount of landmarks in this provider.

Declaration
public int LandmarkCount { get; }
Property Value
Type Description
int

Methods

GetFromKeyValueArrays(Allocator)

Returns key value arrays containing the graph distances from every landmark. This can be useful if you want to serialize the data. If you know your graph is undirected, it is sufficient to only serialize this data.

Declaration
public NativeKeyValueArrays<TNode, FixedList128Bytes<float>> GetFromKeyValueArrays(Allocator allocator)
Parameters
Type Name Description
Allocator allocator

Allocator to use for the key value array
Returns
Type Description
NativeKeyValueArrays<TNode, FixedList128Bytes<float>>

GetLandmarkLocation(int)

Returns the location of the landmark at a given index.

Declaration
public TNode GetLandmarkLocation(int index)
Parameters
Type Name Description
int index

The index
Returns
Type Description
TNode

The landmark location

GetNativeContainers(out NativeHashMap<TNode, FixedList128Bytes<float>>, out NativeHashMap<TNode, FixedList128Bytes<float>>, out NativeList<TNode>, out NativeReference<bool>)

Returns the internal native containers which can be used to serialize the data.

Declaration
public void GetNativeContainers(out NativeHashMap<TNode, FixedList128Bytes<float>> fromLandmarks, out NativeHashMap<TNode, FixedList128Bytes<float>> toLandmarks, out NativeList<TNode> landmarks, out NativeReference<bool> isDirected)
Parameters
Type Name Description
NativeHashMap<TNode, FixedList128Bytes<float>> fromLandmarks
NativeHashMap<TNode, FixedList128Bytes<float>> toLandmarks
NativeList<TNode> landmarks
NativeReference<bool> isDirected

GetToKeyValueArrays(Allocator)

Returns key value arrays containing the graph distances to every landmark. This can be useful if you want to serialize the data. For undirected graphs, this data will be the same as GetFromKeyValueArrays(Allocator) so doesn't need to be serialized.

Declaration
public NativeKeyValueArrays<TNode, FixedList128Bytes<float>> GetToKeyValueArrays(Allocator allocator)
Parameters
Type Name Description
Allocator allocator

Allocator to use for the key value array
Returns
Type Description
NativeKeyValueArrays<TNode, FixedList128Bytes<float>>

Heuristic(TNode)

Returns a cost estimate of a path between two nodes. Depending on the location of the landmarks, this estimate can be significantly better than a traditional heuristic, resulting in much less expanded nodes and thus faster pathfinding.

Declaration
public float Heuristic(TNode u)
Parameters
Type Name Description
TNode u
Returns
Type Description
float
Remarks

In order for the algorithm to work correctly, the edge cost's may not be negative.

SetGoal(TNode)

Gets called by A* before the algorithm begins, keep track of the goal internally.

Declaration
public void SetGoal(TNode goal)
Parameters
Type Name Description
TNode goal

Implements

Extension Methods