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
Namespace: AnyPath.Native
Assembly: Assembly-CSharp.dll
Syntax
public struct ALT<TNode> : IHeuristicProvider<TNode>, INativeDisposable, IDisposable where TNode : struct, IEquatable<TNode>
Type Parameters
Name | Description |
---|---|
TNode |
Constructors
| Improve this Doc View SourceALT(Allocator)
Allocates an ALT heuristic provider.
Declaration
public ALT(Allocator allocator)
Parameters
Type | Name | Description |
---|---|---|
Unity.Collections.Allocator | allocator | Allocator for the ALT heuristics. |
Properties
| Improve this Doc View SourceIsDirected
Returns wether this ALT heuristic provider was made for a directed graph.
Declaration
public readonly bool IsDirected { get; }
Property Value
Type | Description |
---|---|
System.Boolean |
LandmarkCount
Returns the amount of landmarks in this provider.
Declaration
public readonly int LandmarkCount { get; }
Property Value
Type | Description |
---|---|
System.Int32 |
Methods
| Improve this Doc View SourceComputeDirected<TGraph>(ref TGraph, ref ReversedGraph<TNode>, TNode[])
Computes ALT heuristics for a set of landmarks. Use this version if your graph contains directed edges.
Declaration
public void ComputeDirected<TGraph>(ref TGraph graph, ref ReversedGraph<TNode> reversedGraph, TNode[] landmarks)
where TGraph : struct, IGraph<TNode>
Parameters
Type | Name | Description |
---|---|---|
TGraph | graph | The graph to compute ALt heuristics for |
ReversedGraph<TNode> | reversedGraph | The reversed version of the graph. ReversedGraph<TNode>. |
TNode[] | landmarks | Array containing the landmarks. Ideally, landmarks should be placed "behind" frequent starting and goal locations in the graph. Currently a maximum of 31 landmarks is supported. |
Type Parameters
Name | Description |
---|---|
TGraph |
Remarks
The computation can be resource intensive for large graphs. This operation is done in parallel and using Unity's Burst compiler to maximize performance.
ComputeUndirected<TGraph>(ref TGraph, TNode[])
Declaration
public void ComputeUndirected<TGraph>(ref TGraph graph, TNode[] landmarks)
where TGraph : struct, IGraph<TNode>
Parameters
Type | Name | Description |
---|---|---|
TGraph | graph | |
TNode[] | landmarks |
Type Parameters
Name | Description |
---|---|
TGraph |
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, FixedListFloat128> GetFromKeyValueArrays(Allocator allocator)
Parameters
Type | Name | Description |
---|---|---|
Unity.Collections.Allocator | allocator | Allocator to use for the key value array |
Returns
Type | Description |
---|---|
Unity.Collections.NativeKeyValueArrays<TNode, Unity.Collections.FixedListFloat128> |
GetLandmarkLocation(Int32)
Returns the location of the landmark at a given index.
Declaration
public TNode GetLandmarkLocation(int index)
Parameters
Type | Name | Description |
---|---|---|
System.Int32 | index | The index |
Returns
Type | Description |
---|---|
TNode | The landmark location |
GetMemoryConsumption()
Gets an estimated value of the amount of bytes this data structure uses.
Declaration
public int GetMemoryConsumption()
Returns
Type | Description |
---|---|
System.Int32 |
GetNativeContainers(out NativeHashMap<TNode, FixedListFloat128>, out NativeHashMap<TNode, FixedListFloat128>, out NativeList<TNode>, out NativeReference<Boolean>)
Returns the internal native containers which can be used to serialize the data.
Declaration
public void GetNativeContainers(out NativeHashMap<TNode, FixedListFloat128> fromLandmarks, out NativeHashMap<TNode, FixedListFloat128> toLandmarks, out NativeList<TNode> landmarks, out NativeReference<bool> isDirected)
Parameters
Type | Name | Description |
---|---|---|
Unity.Collections.NativeHashMap<TNode, Unity.Collections.FixedListFloat128> | fromLandmarks | |
Unity.Collections.NativeHashMap<TNode, Unity.Collections.FixedListFloat128> | toLandmarks | |
Unity.Collections.NativeList<TNode> | landmarks | |
Unity.Collections.NativeReference<System.Boolean> | 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, FixedListFloat128> GetToKeyValueArrays(Allocator allocator)
Parameters
Type | Name | Description |
---|---|---|
Unity.Collections.Allocator | allocator | Allocator to use for the key value array |
Returns
Type | Description |
---|---|
Unity.Collections.NativeKeyValueArrays<TNode, Unity.Collections.FixedListFloat128> |
Heuristic(TNode, 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, TNode t)
Parameters
Type | Name | Description |
---|---|---|
TNode | u | |
TNode | t |
Returns
Type | Description |
---|---|
System.Single |
Remarks
In order for the algorithm to work correctly, the edge cost's may not be negative.
ScheduleComputeDirected<TGraph>(ref TGraph, ref ReversedGraph<TNode>, NativeArray<TNode>, JobHandle)
Computes this ALT heuristic provider in parallel using Unity's Job system. This is the fastest way to compute ALT heuristics.
Declaration
public JobHandle ScheduleComputeDirected<TGraph>(ref TGraph graph, ref ReversedGraph<TNode> reversedGraph, NativeArray<TNode> landmarks, JobHandle dependsOn = default(JobHandle))
where TGraph : struct, IGraph<TNode>
Parameters
Type | Name | Description |
---|---|---|
TGraph | graph | |
ReversedGraph<TNode> | reversedGraph | |
Unity.Collections.NativeArray<TNode> | landmarks | |
Unity.Jobs.JobHandle | dependsOn |
Returns
Type | Description |
---|---|
Unity.Jobs.JobHandle | A jobhandle that must be completed before this heuristic provider can be used |
Type Parameters
Name | Description |
---|---|
TGraph |
ScheduleComputeUndirected<TGraph>(ref TGraph, NativeArray<TNode>, JobHandle)
Computes this ALT heuristic provider in parallel using Unity's Job system. This is the fastest way to compute ALT heuristics.
Declaration
public JobHandle ScheduleComputeUndirected<TGraph>(ref TGraph graph, NativeArray<TNode> landmarks, JobHandle dependsOn = default(JobHandle))
where TGraph : struct, IGraph<TNode>
Parameters
Type | Name | Description |
---|---|---|
TGraph | graph | |
Unity.Collections.NativeArray<TNode> | landmarks | |
Unity.Jobs.JobHandle | dependsOn |
Returns
Type | Description |
---|---|
Unity.Jobs.JobHandle | A jobhandle that must be completed before this heuristic provider can be used |
Type Parameters
Name | Description |
---|---|
TGraph |