Class FloodPath
Extends
Path
Public
Calculates paths from everywhere to a single point.
This path is a bit special, because it does not do anything useful by itself. What it does is that it calculates paths to all nodes it can reach, it floods the graph. This data will remain stored in the path. Then you can calculate a FloodPathTracer path. That path will trace the path from its starting point all the way to where this path started. A FloodPathTracer search is extremely fast to calculate compared to a normal path request.
It is very useful in for example tower defence games, where all your AIs will walk to the same point but from different places, and you do not update the graph or change the target point very often.
Usage:
At start, you calculate ONE FloodPath and save the reference (it will be needed later).
Then when a unit is spawned or needs its path recalculated, start a FloodPathTracer path from the unit's position. It will then find the shortest path to the point specified when you calculated the FloodPath extremely quickly.
If you update the graph (for example place a tower in a TD game) or need to change the target point, you calculate a new FloodPath and make all AIs calculate new FloodPathTracer paths.
Note
Since a FloodPathTracer path only uses precalculated information, it will always use the same penalties/tags as the FloodPath it references. If you want to use different penalties/tags, you will have to calculate a new FloodPath.
Here follows some example code of the above list of steps: public static FloodPath fpath;
public void Start () {
fpath = FloodPath.Construct (someTargetPosition, null);
AstarPath.StartPath (fpath);
}
When searching for a new path to someTargetPosition from let's say transform.position, you do FloodPathTracer fpathTrace = FloodPathTracer.Construct (transform.position,fpath,null);
seeker.StartPath (fpathTrace,OnPathComplete);
Where OnPathComplete is your callback function.
Another thing to note is that if you are using an NNConstraint on the FloodPathTracer, they must always inherit from FloodPathConstraint.
The easiest is to just modify the instance of FloodPathConstraint which is created as the default one.
Integration with the built-in movement scripts
The built-in movement scripts cannot calculate a FloodPathTracer path themselves, but you can use the SetPath method to assign such a path to them: var ai = GetComponent<IAstarAI>();
// Disable the agent's own path recalculation code
ai.canSearch = false;
ai.SetPath(FloodPathTracer.Construct(ai.position, floodPath));
A* Pro Feature:
This is an A* Pathfinding Project Pro feature only. This function/class/variable might not exist in the Free version of the A* Pathfinding Project or the functionality might be limited.
The Pro version can be bought here
Public Methods
FloodPath
()
Default constructor.
Do not use this. Instead use the static Construct method which can handle path pooling.
void
OnVisitNode
(
uint | pathNode | |
uint | hScore | |
uint | gScore | |
)
Called for every node that the path visits.
This is used by path types to check if the target node has been reached, to log debug data, etc.
Public Static Methods
Public Variables
bool
saveParents = true
If false, will not save any information.
Used by some internal parts of the system which doesn't need it.
Public Static Variables
const uint
TemporaryNodeBit = 1u << 31
Inherited Public Members
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.
Note
Graph updates and other callbacks might get called during the execution of this function.
var path = seeker.StartPath(transform.position, transform.position + Vector3.forward * 10, OnPathComplete);
path.BlockUntilCalculated();
// The path is calculated now, and the OnPathComplete callback has been called
bool
CanTraverse
(
)
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
(
)
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
(
)
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.
Current state of the path.
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
(
)
Causes the path to fail and sets errorLog to msg.
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
(
)
Returns the cost of traversing the given node.
bool
IsDone
()
True if this path is done calculating.
Note
The callback for the path might not have been called yet.
See
Seeker.IsDone which also takes into account if the path callback has been called and had Modifiers applied.
Unity.Profiling.ProfilerMarker
MarkerOpenCandidateConnectionsToEnd = new Unity.Profiling.ProfilerMarker("OpenCandidateConnectionsToEnd")
Unity.Profiling.ProfilerMarker
MarkerTrace = new Unity.Profiling.ProfilerMarker("Trace")
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
(
)
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.
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
(
)
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
(
)
Copies the given settings into this path.
IEnumerator
WaitForPath
()
Waits until this path has been calculated and returned.
Allows for very easy scripting.
IEnumerator Start () {
// Get the seeker component attached to this GameObject
var seeker = GetComponent<Seeker>();
var path = seeker.StartPath(transform.position, transform.position + Vector3.forward * 10, null);
// Wait... This may take a frame or two depending on how complex the path is
// The rest of the game will continue to run while we wait
yield return StartCoroutine(path.WaitForPath());
// The path is calculated now
// Draw the path in the scene view for 10 seconds
for (int i = 0; i < path.vectorPath.Count - 1; i++) {
Debug.DrawLine(path.vectorPath[i], path.vectorPath[i+1], Color.red, 10);
}
}
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
float
duration
How long it took to calculate this path in milliseconds.
bool
error
If the path failed, this is true.
See
errorLog
This is equivalent to checking path.CompleteState == PathCompleteState.Error
string
errorLog
Additional info on why a path failed.
Determines which heuristic to use.
float
heuristicScale = 1F
Scale of the heuristic values.
Constraint for how to search for nodes.
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.
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.
Note
Setting this to null will make all tag penalties be treated as if they are zero.
If you are using a Seeker. The Seeker will set this value to what is set in the inspector field when you call seeker.StartPath. So you need to change the Seeker's value via script, not set this value.
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.
Private/Protected Members
void
AddStartNodesToHeap
()
void
CalculateStep
(
)
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
(
)
Returns a string with information about it.
More information is emitted when logMode == Heavy. An empty string is returned if logMode == None or logMode == OnlyErrors and this path did not fail.
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.
int3
FirstTemporaryEndNode
()
bool
IsValid
(
)
Checks if the flood path data is still valid.
This check is quite strict, not allowing any nodes to have been destroyed since the path was calculated. The reason for this strictness is that if a node has been destroyed, and then a node has been created, they may end up sharing the same node index. This could cause the path generated by a FloodPathTracer to be completely messed up if it would have passed through the destroyed node.
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.
Warning
Do not call this function manually.
void
OnFoundEndNode
(
uint | pathNode | |
uint | hScore | |
uint | gScore | |
)
Called when a valid node has been found for the end of the path.
This function should trace the path back to the start node, and set CompleteState to Complete. If CompleteState is unchanged, the search will continue.
void
OnHeapExhausted
()
Called when there are no more nodes to search.
This may be used to calculate a partial path as a fallback.
void
Prepare
()
Called before the path is started.
Called right before Initialize
void
PrepareBase
(
)
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.
Note
All inheriting path types (e.g ConstantPath, RandomPath, etc.) which declare their own variables need to override this function, resetting ALL their variables to enable pooling of paths. If this is not done, trying to use that path type for pooling could result in weird behaviour. The best way is to reset to default values the variables declared in the extended path type and then call the base function in inheriting types with base.Reset().
void
ReturnPath
()
Calls callback to return the calculated path.
void
TemporaryEndNodesBoundingBox
(
)
void
Trace
(
)
Traces the calculated path from the end node to the start.
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. Assumes the vectorPath and path are empty and not null (which will be the case for a correctly initialized path).
int[]
ZeroTagPenalties = new int[32]
List of zeroes to use as default tag penalties.
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.
Target to use for H score calculations.
int[]
internalTagPenalties
The tag penalties that are actually used.
Dictionary<uint, uint>
parents
Data for the thread calculating this path.