Class LandmarkSelection<TGraph, TNode, TEnumerator>
Contains utility functions for selecting landmarks to use with ALT<TNode> heuristics. These provide a general approach to selecting landmarks.
If you know that your requests will often have the same start or goal locations, it may be benificial to manually place landmarks "behind" these locations. Strategic placement of landmarks can vastly improve the efficiency of the algorithm.
Namespace: AnyPath.Native.Heuristics
Assembly: AnyPath.dll
Syntax
public class LandmarkSelection<TGraph, TNode, TEnumerator> where TGraph : struct, IGraph<TNode> where TNode : unmanaged, IEquatable<TNode> where TEnumerator : struct, IEnumerator<TNode>Type Parameters
| Name | Description |
|---|---|
| TGraph | |
| TNode | |
| TEnumerator |
Remarks
All of these methods use Unity's job system internally to speed up the process.
Because of a limitation of the burst compiler, you need to explicity provide the types to this class when calling any of the static methods it contains. See https://docs.unity3d.com/Packages/com.unity.burst@1.8/manual/compilation-generic-jobs.html for more information.
Constructors
LandmarkSelection()
Declaration
public LandmarkSelection()Methods
ScheduleSelectFarthestLandmarksDirected(ref TGraph, ref ReversedGraph<TNode>, TEnumerator, NativeArray<TNode>, JobHandle)
Schedules a job that selects a set of landmarks that are spaced apart evenly. Use this method if your graph contains directed edges. This method requires more computation than ScheduleSelectFarthestLandmarksUndirected(ref TGraph, TEnumerator, NativeArray<TNode>, JobHandle), since paths from and to every node need to be computed.
Declaration
public static JobHandle ScheduleSelectFarthestLandmarksDirected(ref TGraph graph, ref ReversedGraph<TNode> reversedGraph, TEnumerator nodeEnumerator, NativeArray<TNode> destLandmarks, JobHandle dependsOn = default)Parameters
| Type | Name | Description |
|---|---|---|
| TGraph | graph | The graph to select landmarks for |
| ReversedGraph<TNode> | reversedGraph | |
| TEnumerator | nodeEnumerator | Enumerator that yields all nodes contained in the graph |
| NativeArray<TNode> | destLandmarks | The array to fill with the selected landmarks. The amount of landmarks that will be chosen is equal to the length of this array |
| JobHandle | dependsOn | Optional jobhandle that must be completed before this job gets scheduled. |
Returns
| Type | Description |
|---|---|
| JobHandle | A jobhandle for the scheduled job |
Remarks
This gives better results than SelectRandomLandmarks(TEnumerator, TNode[]), but requires more processing time. It is recommended to enable burst compilation because this can take a long time for large graphs. Consider serializing your landmarks if you use a static world.
ScheduleSelectFarthestLandmarksUndirected(ref TGraph, TEnumerator, NativeArray<TNode>, JobHandle)
Schedules a job that selects a set of landmarks that are spaced apart evenly. This method is sufficient for undirected graphs and less computationally expensive than the ScheduleSelectFarthestLandmarksDirected(ref TGraph, ref ReversedGraph<TNode>, TEnumerator, NativeArray<TNode>, JobHandle) method.
Declaration
public static JobHandle ScheduleSelectFarthestLandmarksUndirected(ref TGraph graph, TEnumerator nodeEnumerator, NativeArray<TNode> destLandmarks, JobHandle dependsOn = default)Parameters
| Type | Name | Description |
|---|---|---|
| TGraph | graph | The graph to select landmarks for |
| TEnumerator | nodeEnumerator | Enumerator that yields all nodes contained in the graph |
| NativeArray<TNode> | destLandmarks | The array to fill with the selected landmarks. The amount of landmarks that will be chosen is equal to the length of this array |
| JobHandle | dependsOn | Optional jobhandle that must be completed before this job gets scheduled. |
Returns
| Type | Description |
|---|---|
| JobHandle | A jobhandle for the scheduled job |
Remarks
This gives better results than SelectRandomLandmarks(TEnumerator, TNode[]), but requires more processing time. It is recommended to enable burst compilation because this can take a long time for large graphs. Consider serializing your landmarks if you use a static world.
ScheduleSelectRandomLandmarks(TEnumerator, NativeArray<TNode>, JobHandle)
Schedules a job that selects a set of unique, random landmarks from a graph
Declaration
public static JobHandle ScheduleSelectRandomLandmarks(TEnumerator nodeEnumerator, NativeArray<TNode> destLandmarks, JobHandle dependsOn = default)Parameters
| Type | Name | Description |
|---|---|---|
| TEnumerator | nodeEnumerator | The node enumerator of the graph. Note that this algorithm does not validate if random nodes picked from this enumerator are reachable at all. |
| NativeArray<TNode> | destLandmarks | Array to fill with the landmarks. The length of this array determines the amount of landmarks that will be selected. If there are less nodes in the graph than the supplied array, the array will be filled with the amount of nodes available. |
| JobHandle | dependsOn | Optional jobhandle that must be completed before this job gets scheduled. |
Returns
| Type | Description |
|---|---|
| JobHandle |
SelectFarthestLandmarkDirected(ref TGraph, ref ReversedGraph<TNode>, TEnumerator, TNode[])
Runs a job on the main thread that selects a set of landmarks that are spaced apart evenly. Use this method if your graph contains directed edges. This method requires more computation than SelectFarthestLandmarksUndirected(ref TGraph, TEnumerator, TNode[]), since paths from and to every node need to be computed.
Declaration
public static void SelectFarthestLandmarkDirected(ref TGraph graph, ref ReversedGraph<TNode> reversedGraph, TEnumerator nodeEnumerator, TNode[] selectedLandmarks)Parameters
| Type | Name | Description |
|---|---|---|
| TGraph | graph | The graph to select landmarks for |
| ReversedGraph<TNode> | reversedGraph | The reversed graph of the graph. |
| TEnumerator | nodeEnumerator | Enumerator that yields all nodes contained in the graph |
| TNode[] | selectedLandmarks | Array that will be filled with the selected landmarks. The length of this array determines the amount of landmarks that will be selected. Note that the ALT<TNode> implementation currently supports a maximum of 32. |
Remarks
This gives better results than SelectRandomLandmarks(TEnumerator, TNode[]), but requires more processing time. It is recommended to enable burst compilation because this can take a long time for large graphs. Consider serializing your landmarks if you use a static world.
SelectFarthestLandmarksUndirected(ref TGraph, TEnumerator, TNode[])
Runs a job on the main thread that selects a set of landmarks that are spaced apart evenly. This method is sufficient for undirected graphs and less computationally expensive than the directed version, since from and to path lengths will be equal.
Declaration
public static void SelectFarthestLandmarksUndirected(ref TGraph graph, TEnumerator nodeEnumerator, TNode[] selectedLandmarks)Parameters
| Type | Name | Description |
|---|---|---|
| TGraph | graph | The graph to select landmarks for |
| TEnumerator | nodeEnumerator | Enumerator that yields all nodes contained in the graph |
| TNode[] | selectedLandmarks |
Remarks
This gives better results than SelectRandomLandmarks(TEnumerator, TNode[]), but requires more processing time. It is recommended to enable burst compilation because this can take a long time for large graphs. Consider serializing your landmarks if you use a static world.
SelectRandomLandmarks(TEnumerator, TNode[])
Selects a number of random landmarks from a graph.
Declaration
public static void SelectRandomLandmarks(TEnumerator nodeEnumerator, TNode[] selectedLandmarks)Parameters
| Type | Name | Description |
|---|---|---|
| TEnumerator | nodeEnumerator | The node enumerator of the graph. Note that this algorithm does not validate if random nodes picked from this enumerator are reachable at all. |
| TNode[] | selectedLandmarks |
Remarks
This method is much faster to compute than the Farthest Landmarks selection, but may not produce landmarks that are placed as optimal.