Struct AStar<TNode>

Core A* and Dijkstra algorithm implementation. Create an instance of this struct and use FindPath<TGraph, TH, TMod, TProc, TSeg>(ref TGraph, TNode, TNode, TH, TMod, TProc, NativeList<TSeg>), EvalPath<TGraph, TH, TMod>(ref TGraph, TNode, TNode, TH, TMod) or any of the extension methods to do burst compatible pathfinding queries.

Namespace: AnyPath.Native

Assembly: AnyPath.dll

Syntax

public struct AStar<TNode> where TNode : unmanaged, IEquatable<TNode>

Type Parameters

Name	Description
TNode	The type of nodes to operate on

Remarks

This struct can be re-used for multiple request, but it can only handle one request at a time.

Constructors

AStar(int, Allocator)

Creates the native A* struct

Declaration

public AStar(int maxExpand, Allocator allocator)

Parameters

Type	Name	Description
int	maxExpand	The maximum number of nodes A* may expand into before "giving up". This can provide as an upper bound for targets that are unreachable, reducing computation time because the algorithm will have to search the entire graph before knowing for certain that a target is unreachable.
Allocator	allocator	Unity allocator to use

AStar(Allocator)

Creates a native A* struct with a default maxExpand of 65536

Declaration

public AStar(Allocator allocator)

Parameters

Type	Name	Description
Allocator	allocator	Unity allocator to use

Fields

cameFrom

Contains information about which node lead into the next one, from the last run.

Declaration

[NoAlias]
public NativeHashMap<TNode, AStar<TNode>.CameFrom> cameFrom

Field Value

Type	Description
NativeHashMap<TNode, AStar<TNode>.CameFrom>

maxExpand

The maximum number of nodes A* may expand into before "giving up". This can provide as an upper bound for targets that are unreachable, reducing computation time because the algorithm will have to search the entire graph before knowing for certain that a target is unreachable.

Declaration

public int maxExpand

Field Value

Type	Description
int

Remarks

This value is not used when using Dijkstra<TGraph, TMod>(ref TGraph, TNode, TMod, float)

Properties

IsCreated

Returns wether the native containers inside this structure were allocated

Declaration

public bool IsCreated { get; }

Property Value

Type	Description
bool

Methods

DebugGetAllExpansion(Allocator)

Returns the key-value pairs of all nodes and segments A* expanded too since the last usage.

Declaration

public NativeKeyValueArrays<TNode, AStar<TNode>.CameFrom> DebugGetAllExpansion(Allocator allocator)

Parameters

Type	Name	Description
Allocator	allocator

Returns

Type	Description
NativeKeyValueArrays<TNode, AStar<TNode>.CameFrom>

Dijkstra<TGraph, TMod>(ref TGraph, TNode, TMod, float)

Performs the Dijkstra algorithm on the graph. The result of which can be obtained via the cameFrom set. Every location that is present in cameFrom was reachable from the start of this query.

You can obtain the cost of the path from g property of cameFrom. You can reconstruct a path to any reachable destination using ReconstructPath(TNode, TNode, bool, NativeList<TNode>) after this query has ran. Be careful though and supply the same starting node to that method as was used in this query. If you don't do this, that call may result into an infinite loop or return an invalid result.

Declaration

public void Dijkstra<TGraph, TMod>(ref TGraph graph, TNode start, TMod edgeMod, float maxCost = Infinity) where TGraph : struct, IGraph<TNode> where TMod : struct, IEdgeMod<TNode>

Parameters

Type	Name	Description
TGraph	graph
TNode	start
TMod	edgeMod
float	maxCost	Cost budget for expanding. The algorithm will not traverse further if the cost exceeds this value. Nodes beyond this cost will be considered as not reachable

Type Parameters

Name	Description
TGraph
TMod

Remarks

*Warning* If no max cost is specified and your graph has no boundary (which could be the case for an infinite grid) then running this algorithm will result in an infinite loop, as the algorithm will keep expandig. All of the included graphs with AnyPath have a set boundary, so if you're using any of these you don't have to worry about this. It will however still benefit performance to set a maximum cost.

The maxExpand setting on this object is not used.

Dispose()

Dispose this memory and all of it's native containers

Declaration

public void Dispose()

Dispose(JobHandle)

Dispose this memory and all of it's native containers

Declaration

public void Dispose(JobHandle inputDeps)

Parameters

Type	Name	Description
JobHandle	inputDeps	JobHandle to use as a dependency

EvalPath<TGraph, TH, TMod>(ref TGraph, TNode, TNode, TH, TMod)

Evaluates if a path exists between a start and goal. The path can later be reconstructed with ReconstructPath(TNode, TNode, bool, NativeList<TNode>). Alternatively, use FindPath<TGraph, TH, TMod, TProc, TSeg>(ref TGraph, TNode, TNode, TH, TMod, TProc, NativeList<TSeg>)

Declaration

public AStarEvalResult EvalPath<TGraph, TH, TMod>(ref TGraph graph, TNode start, TNode goal, TH heuristicProvider, TMod edgeMod) where TGraph : struct, IGraph<TNode> where TH : struct, IHeuristicProvider<TNode> where TMod : struct, IEdgeMod<TNode>

Parameters

Type	Name	Description
TGraph	graph	The graph to perform the request on
TNode	start	The starting location
TNode	goal	The goal location
TH	heuristicProvider	Heuristic provider to use
TMod	edgeMod	Edge modifier to use. Use NoEdgeMod<TNode> for none.

Returns

Type	Description
AStarEvalResult	A AStarFindPathResult struct indicating if a path was found

Type Parameters

Name	Description
TGraph	The type of graph to find a path on
TH	Type of heuristic provider
TMod	Type of edge modifier

FindPath<TGraph, TH, TMod, TProc, TSeg>(ref TGraph, TNode, TNode, TH, TMod, TProc, NativeList<TSeg>)

Evaluates and then reconstructs a path from start to goal.

Declaration

public AStarFindPathResult FindPath<TGraph, TH, TMod, TProc, TSeg>(ref TGraph graph, TNode start, TNode goal, TH heuristicProvider, TMod edgeMod, TProc pathProcessor, NativeList<TSeg> pathBuffer) where TGraph : struct, IGraph<TNode> where TH : struct, IHeuristicProvider<TNode> where TMod : struct, IEdgeMod<TNode> where TProc : struct, IPathProcessor<TNode, TSeg> where TSeg : unmanaged

Parameters

Type	Name	Description
TGraph	graph	The graph to perform the request on
TNode	start	The starting location
TNode	goal	The goal location
TH	heuristicProvider	Heuristic provider to use
TMod	edgeMod	Edge modifier to use. Use NoEdgeMod<TNode> for none.
TProc	pathProcessor	Path processor to use NoProcessing<TNode> for none.
NativeList<TSeg>	pathBuffer	The segment buffer to append the path to. This buffer is not cleared.

Returns

Type	Description
AStarFindPathResult	A AStarFindPathResult struct indicating if a path was found and the offsets in the path buffer

Type Parameters

Name	Description
TGraph	The type of graph to find a path on
TH	Type of heuristic provider
TMod	Type of edge modifier
TProc	Type of the path processor
TSeg	Type of segments make up the path

ReconstructPath(TNode, TNode, bool, NativeList<TNode>)

Appends the last found path from start to goal into pathBuffer

Declaration

public void ReconstructPath(TNode start, TNode goal, bool insertQueryStart, NativeList<TNode> pathBuffer)

Parameters

Type	Name	Description
TNode	start	The starting node of the original request
TNode	goal	The goal node of the original request
bool	insertQueryStart	Should the starting node be part of the path?
NativeList<TNode>	pathBuffer	The buffer to append the path to. This list is not cleared.