Class FloodPathTracer Extends ABPath

FloodPathTracer ()

Default constructor.

Do not use this. Instead use the static Construct method which can handle path pooling.

FloodPathTracer Construct (

Vector3	start
FloodPath	flood
OnPathDelegate	callback=null

)

void BlockUntilCalculated ()

Blocks until this path has been calculated and returned.

Normally it takes a few frames for a path to be calculated and returned. This function will ensure that the path will be calculated when this function returns and that the callback for that path has been called.

Use this function only if you really need to. There is a point to spreading path calculations out over several frames. It smoothes out the framerate and makes sure requesting a large number of paths at the same time does not cause lag.

Path p = seeker.StartPath (transform.position, transform.position + Vector3.forward * 10);
p.BlockUntilCalculated();
// The path is calculated now


bool CanTraverse (

GraphNode

node

)

Returns if the node can be traversed.

This by default equals to if the node is walkable and if the node's tag is included in enabledTags.

bool CanTraverse (

GraphNode	from
GraphNode	to

)

Returns if the path can traverse a link between from and to and if to can be traversed itself.

This by default equals to if the to is walkable and if the to's tag is included in enabledTags.

void Claim (

System.Object

o

)

Increase the reference count on this path by 1 (for pooling).

A claim on a path will ensure that it is not pooled. If you are using a path, you will want to claim it when you first get it and then release it when you will not use it anymore. When there are no claims on the path, it will be reset and put in a pool.

This is essentially just reference counting.

The object passed to this method is merely used as a way to more easily detect when pooling is not done correctly. It can be any object, when used from a movement script you can just pass "this". This class will throw an exception if you try to call Claim on the same path twice with the same object (which is usually not what you want) or if you try to call Release with an object that has not been used in a Claim call for that path. The object passed to the Claim method needs to be the same as the one you pass to this method.

PathCompleteState CompleteState

Current state of the path.

ABPath Construct (

Vector3	start
Vector3	end
OnPathDelegate	callback=null

)

Construct a path with a start and end point.

The delegate will be called when the path has been calculated. Do not confuse it with the Seeker callback as they are sent at different times. If you are using a Seeker to start the path you can set callback to null.

void Error ()

Aborts the path because of an error.

Sets error to true. This function is called when an error has occurred (e.g a valid path could not be found).

void FailWithError (

string

msg

)

Causes the path to fail and sets errorLog to msg.

ABPath FakePath (

List<Vector3>	vectorPath
List<GraphNode>	nodePath=null

)

Creates a fake path.

Creates a path that looks almost exactly like it would if the pathfinding system had calculated it.

This is useful if you want your agents to follow some known path that cannot be calculated using the pathfinding system for some reason.

var path = ABPath.FakePath(new List<Vector3> { new Vector3(1, 2, 3), new Vector3(4, 5, 6) });

ai.SetPath(path);
You can use it to combine existing paths like this:

var a = Vector3.zero;
var b = new Vector3(1, 2, 3);
var c = new Vector3(2, 3, 4);
var path1 = ABPath.Construct(a, b);
var path2 = ABPath.Construct(b, c);

AstarPath.StartPath(path1);
AstarPath.StartPath(path2);
path1.BlockUntilCalculated();
path2.BlockUntilCalculated();

// Combine the paths
// Note: Skip the first element in the second path as that will likely be the last element in the first path
var newVectorPath = path1.vectorPath.Concat(path2.vectorPath.Skip(1)).ToList();
var newNodePath = path1.path.Concat(path2.path.Skip(1)).ToList();
var combinedPath = ABPath.FakePath(newVectorPath, newNodePath);


uint GetTagPenalty (

int

tag

A value between 0 (inclusive) and 32 (exclusive).

)

Returns penalty for the given tag.

float GetTotalLength ()

Total Length of the path.

Calculates the total length of the vectorPath. Cache this rather than call this function every time since it will calculate the length every time, not just return a cached value.

uint GetTraversalCost (

GraphNode

node

)

Returns the cost of traversing the given node.

bool IsDone ()

True if this path is done calculating.

Unity.Profiling.ProfilerMarker MarkerOpenCandidateConnectionsToEnd = new Unity.Profiling.ProfilerMarker("OpenCandidateConnectionsToEnd")

Unity.Profiling.ProfilerMarker MarkerTrace = new Unity.Profiling.ProfilerMarker("Trace")

void OnVisitNode (

uint	pathNode
uint	hScore
uint	gScore

)

void OpenCandidateConnection (

uint	parentPathNode	The node that is being opened.
uint	targetPathNode	A neighbour of the parent that is being considered.
uint	parentG	The G value of the parent node. This is the cost to reach the parent node from the start of the path.
uint	connectionCost	The cost of moving from the parent node to the target node.
uint	fractionAlongEdge	Internal value used by the TriangleMeshNode to store where on the shared edge between the nodes we say we cross over.
Int3	targetNodePosition	The position of the target node. This is used by the heuristic to estimate the cost to reach the end node.

)

Opens a connection between two nodes during the A* search.

When a node is "opened" (i.e. searched by the A* algorithm), it will open connections to all its neighbours. This function checks those connections to see if passing through the node to its neighbour is the best way to reach the neighbour that we have seen so far, and if so, it will push the neighbour onto the search heap.

void OpenCandidateConnectionBurst (

refOpenCandidateParams	pars
refBinaryHeap	heap
refHeuristicObjective	heuristicObjective

)

Burst-compiled internal implementation of OpenCandidateConnection.

Compiling it using burst provides a decent 25% speedup. The function itself is much faster, but the overhead of calling it from C# is quite significant.

void OpenCandidateConnectionsToEndNode (

Int3	position	Position of the path node that is being opened. This may be different from the node's position if PathNode.fractionAlongEdge is being used.
uint	parentPathNode	Index of the path node that is being opened. This is often the same as parentNodeIndex, but may be different if the node has multiple path node variants.
uint	parentNodeIndex	Index of the node that is being opened.
uint	parentG	G score of the parent node. The cost to reach the parent node from the start of the path.

)

Open a connection to the temporary end node if necessary.

The start and end nodes are temporary nodes and are not included in the graph itself. This means that we need to handle connections to and from those nodes as a special case. This function will open a connection from the given node to the end node, if such a connection exists.

It is called from the GraphNode.Open function.

PathState PipelineState

Returns the state of the path in the pathfinding pipeline.

void Release (

System.Object	o
bool	silent=false

)

Reduces the reference count on the path by 1 (pooling).

Removes the claim on the path by the specified object. When the reference count reaches zero, the path will be pooled, all variables will be cleared and the path will be put in a pool to be used again. This is great for performance since fewer allocations are made.

If the silent parameter is true, this method will remove the claim by the specified object but the path will not be pooled if the claim count reches zero unless a non-silent Release call has been made earlier. This is used by the internal pathfinding components such as Seeker and AstarPath so that they will not cause paths to be pooled. This enables users to skip the claim/release calls if they want without the path being pooled by the Seeker or AstarPath and thus causing strange bugs.

bool ShouldConsiderPathNode (

uint

pathNodeIndex

)

True if this path node might be worth exploring.

This is used during a search to filter out nodes which have already been fully searched.

void UseSettings (

PathRequestSettings

settings

)

Copies the given settings into this path object.

IEnumerator WaitForPath ()

Waits until this path has been calculated and returned.

Allows for very easy scripting. IEnumerator Start () {
var path = seeker.StartPath(transform.position, transform.position + transform.forward*10, null);
yield return StartCoroutine(path.WaitForPath());
// The path is calculated now
}


bool calculatePartial

Calculate partial path if the target node cannot be reached.

If the target node cannot be reached, the node which was closest (given by heuristic) will be chosen as target node and a partial path will be returned. This only works if a heuristic is used (which is the default). If a partial path is found, CompleteState is set to Partial.

The endNode and endPoint will be modified and be set to the node which ends up being closest to the target.

OnPathDelegate callback

Callback to call when the path is complete.

This is usually sent to the Seeker component which post processes the path and then calls a callback to the script which requested the path

uint cost

Total cost of this path as used by the pathfinding algorithm.

The cost is influenced by both the length of the path, as well as any tags or penalties on the nodes. By default, the cost to move 1 world unit is Int3.Precision.

If the path failed, the cost will be set to zero.

float duration

How long it took to calculate this path in milliseconds.

int enabledTags = -1

Which graph tags are traversable.

This is a bitmask so -1 = all bits set = all tags traversable. For example, to set bit 5 to true, you would do myPath.enabledTags |= 1 << 5;
To set it to false, you would do myPath.enabledTags &= ~(1 << 5);


The Seeker has a popup field where you can set which tags to use.

GraphNode endNode

End node of the path.

Vector3 endPoint

End point of the path.

This is the closest point on the endNode to originalEndPoint

bool endPointKnownBeforeCalculation

True if this path type has a well defined end point, even before calculation starts.

This is for example true for the ABPath type, but false for the RandomPath type.

PathEndingCondition endingCondition

Optional ending condition for the path.

The ending condition determines when the path has been completed. Can be used to for example mark a path as complete when it is within a specific distance from the target.

If ending conditions are used that are not centered around the endpoint of the path, then you should also set the heuristic to None to ensure the path is still optimal. The performance impact of setting the heuristic to None is quite large, so you might want to try to run it with the default heuristic to see if the path is good enough for your use case anyway.

If null, no custom ending condition will be used. This means that the path will end when the target node has been reached.

bool error

If the path failed, this is true.

string errorLog

Additional info on why a path failed.

Heuristic heuristic

Determines which heuristic to use.

float heuristicScale = 1F

Scale of the heuristic values.

OnPathDelegate immediateCallback

Immediate callback to call when the path is complete.

NNConstraint nnConstraint = PathNNConstraint.Walkable

Constraint for how to search for nodes.

Vector3 originalEndPoint

End Point exactly as in the path request.

Vector3 originalStartPoint

Start Point exactly as in the path request.

List<GraphNode> path

Holds the path as a GraphNode list.

These are all nodes that the path traversed, as calculated by the pathfinding algorithm. This may not be the same nodes as the post processed path traverses.

ushort pathID

ID of this path.

Used to distinguish between different paths

int searchedNodes

Number of nodes this path has searched.

GraphNode startNode

Start node of the path.

Vector3 startPoint

Start point of the path.

This is the closest point on the startNode to originalStartPoint

int[]? tagPenalties

Penalties for each tag.

Tag 0 which is the default tag, will get a penalty of tagPenalties[0]. These should only be non-negative values since the A* algorithm cannot handle negative penalties.

When assigning an array to this property it must have a length of 32.

ITraversalProvider traversalProvider

Provides additional traversal information to a path request.

List<Vector3> vectorPath

Holds the (possibly post-processed) path as a Vector3 list.

This list may be modified by path modifiers to be smoother or simpler compared to the raw path generated by the pathfinding algorithm.

void AddStartNodesToHeap ()

void CalculateStep (

long

targetTick

)

Calculates the path until completed or until the time has passed targetTick.

Usually a check is only done every 500 nodes if the time has passed targetTick. Time/Ticks are got from System.DateTime.UtcNow.Ticks.

Basic outline of what the function does for the standard path (Pathfinding.ABPath). while the end has not been found and no error has occurred
pop the next node of the heap and set it as current
check if we have reached the end
if so, exit and return the path

open the current node, i.e loop through its neighbours, mark them as visited and put them on a heap

check if there are still nodes left to process (or have we searched the whole graph)
if there are none, flag error and exit

check if the function has exceeded the time limit
if so, return and wait for the function to get called again


void Cleanup ()

Always called after the path has been calculated.

Guaranteed to be called before other paths have been calculated on the same thread. Use for cleaning up things like node tagging and similar.

string DebugString (

PathLog

logMode

)

Returns a debug string for this path.

void DebugStringPrefix (

PathLog	logMode
System.Text.StringBuilder	text

)

Writes text shared for all overrides of DebugString to the string builder.

void DebugStringSuffix (

PathLog	logMode
System.Text.StringBuilder	text

)

Writes text shared for all overrides of DebugString to the string builder.

bool EndPointGridGraphSpecialCase (

GraphNode	closestWalkableEndNode
Vector3	originalEndPoint
int	targetIndex

)

Applies a special case for grid nodes.

Assume the closest walkable node is a grid node. We will now apply a special case only for grid graphs. In tile based games, an obstacle often occupies a whole node. When a path is requested to the position of an obstacle (single unwalkable node) the closest walkable node will be one of the 8 nodes surrounding that unwalkable node but that node is not neccessarily the one that is most optimal to walk to so in this special case we mark all nodes around the unwalkable node as targets and when we search and find any one of them we simply exit and set that first node we found to be the 'real' end node because that will be the optimal node (this does not apply in general unless the heuristic is set to None, but for a single unwalkable node it does). This also applies if the nearest node cannot be traversed for some other reason like restricted tags.

Image below shows paths when this special case is applied. The path goes from the white sphere to the orange box.

Image below shows paths when this special case has been disabled

int3 FirstTemporaryEndNode ()

void MarkNodesAdjacentToTemporaryEndNodes ()

void OnEnterPool ()

Called when the path enters the pool.

This method should release e.g pooled lists and other pooled resources The base version of this method releases vectorPath and path lists. Reset() will be called after this function, not before.

void OnFoundEndNode (

uint	pathNode
uint	hScore
uint	gScore

)

void OnHeapExhausted ()

void Prepare ()

Initializes the path.

Traces the path from the start node.

void PrepareBase (

PathHandler

pathHandler

)

Prepares low level path variables for calculation.

Called before a path search will take place. Always called before the Prepare, Initialize and CalculateStep functions

void Reset ()

Reset all values to their default values.

All inheriting path types must implement this function, resetting ALL their variables to enable recycling of paths. Call this base function in inheriting types with base.Reset ();

void ReturnPath ()

Calls callback to return the calculated path.

void Setup (

Vector3	start
Vector3	end
OnPathDelegate	callbackDelegate

)

void Setup (

Vector3	start
FloodPath	flood
OnPathDelegate	callback

)

void TemporaryEndNodesBoundingBox (

out int3	mn
out int3	mx

)

void Trace (

uint

fromPathNodeIndex

)

Traces the calculated path from the start node to the end.

This will build an array (path) of the nodes this path will pass through and also set the vectorPath array to the path arrays positions. This implementation will use the flood (FloodPath) to trace the path from precalculated data.

void UpdateStartEnd (

Vector3	start
Vector3	end

)

Sets the start and end points.

Sets originalStartPoint, originalEndPoint, startPoint, endPoint

int[] ZeroTagPenalties = new int[32]

List of zeroes to use as default tag penalties.

PathCompleteState completeState

Backing field for CompleteState.

FloodPath flood

Reference to the FloodPath which searched the path originally.

GraphNode hTargetNode

Target to use for H score calculation.

bool hasBeenReset

True if the Reset function has been called.

Used to alert users when they are doing something wrong.

bool hasEndPoint

Determines if a search for an end node should be done.

Set by different path types.

bool hasEndPoint

HeuristicObjective heuristicObjective

Target to use for H score calculations.

refHeuristicObjective heuristicObjectiveInternal

int[] internalTagPenalties

The tag penalties that are actually used.

uint partialBestTargetGScore = uint.MaxValue

uint partialBestTargetHScore = uint.MaxValue

uint partialBestTargetPathNodeIndex = GraphNode.InvalidNodeIndex

Current best target for the partial path.

This is the node with the lowest H score.

PathHandler pathHandler

Data for the thread calculating this path.