Class MultiTargetPath
Extends
ABPath
Public
A path which searches from one point to a number of different targets in one search or from a number of different start points to a single target.
This is faster than searching with an ABPath for each target if pathsForAll is true. This path type can be used for example when you want an agent to find the closest target of a few different options.
When pathsForAll is true, it will calculate a path to each target point, but it can share a lot of calculations for the different paths so it is faster than requesting them separately.
When pathsForAll is false, it will perform a search using the heuristic set to None and stop as soon as it finds the first target. This may be faster or slower than requesting each path separately. It will run a Dijkstra search where it searches all nodes around the start point until the closest target is found. Note that this is usually faster if some target points are very close to the start point and some are very far away, but it can be slower if all target points are relatively far away because then it will have to search a much larger region since it will not use any heuristics.
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
Version
Since 3.7.1 the vectorPath and path fields are always set to the shortest path even when pathsForAll is true.
Public Methods
MultiTargetPath
()
Default constructor.
Do not use this. Instead use the static Construct method which can handle path pooling.
Public Static Methods
Public Variables
Callbacks to call for each individual path.
int
chosenTarget = -1
The closest target index (if any target was found)
HeuristicMode
heuristicMode = HeuristicMode.Sequential
How to calculate the heuristic.
The heuristic target point can be calculated in different ways, by taking the Average position of all targets, or taking the mid point of them (i.e center of the AABB encapsulating all targets).
The one which works best seems to be Sequential, it sets hTarget to the target furthest away, and when that target is found, it moves on to the next one.
Some modes have the option to be 'moving' (e.g 'MovingAverage'), that means that it is updated every time a target is found.
The H score is calculated according to AstarPath.heuristic
Note
If pathsForAll is false then this option is ignored and it is always treated as being set to None
bool
inverted
False if the path goes from one point to multiple targets.
True if it goes from multiple start points to one target point
List<GraphNode> []
nodePaths
Stores all paths to the targets.
Elements are null if no path was found
Vector3 []
originalTargetPoints
Target points specified when creating the path.
These are not snapped to the nearest nodes
bool
pathsForAll = true
If true, a path to all targets will be returned, otherwise just the one to the closest one.
Vector3 []
targetPoints
Target points specified when creating the path.
These are snapped to the nearest nodes
bool []
targetsFound
Indicates if the target has been found.
Also true if the target cannot be reached (is in another area)
List<Vector3> []
vectorPaths
Stores all vector paths to the targets.
Elements are null if no path was found
Public Enums
HeuristicMode
None |
|
Average |
|
MovingAverage |
|
Midpoint |
|
MovingMidpoint |
|
Sequential |
|
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.
Path p = seeker.StartPath (transform.position, transform.position + Vector3.forward * 10);
p.BlockUntilCalculated();
// 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.
Note
It is not required by other path types to respect this setting
Warning
This feature is currently a work in progress and may not work in the current version
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
void
Claim
(
)
Claim this path (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.
)
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.
Return
The constructed path object
bool
error
If the path failed, this is true.
See
errorLog
This is equivalent to checking path.CompleteState == PathCompleteState.Error
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).
string
errorLog
Additional info on why a path failed.
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.
Determines which heuristic to use.
float
heuristicScale = 1F
Scale of the heuristic values.
bool
IsDone
()
Returns 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.
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.
Holds the path as a Node array.
All nodes the path traverses. This may not be the same nodes as the post processed path traverses.
void
Release
(
System.Object | o | |
bool | silent=false | |
)
Releases a path claim (pooling).
Removes the claim of the path by the specified object. When the claim 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 Release call (not silent) 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.
Int3
startIntPoint
Start point in integer coordinates.
int []
tagPenalties
Penalties for each tag.
Tag 0 which is the default tag, will have added a penalty of tagPenalties[0]. These should only be positive values since the A* algorithm cannot handle negative penalties.
Note
This array will never be null. If you try to set it to null or with a length which is not 32. It will be set to "new int[0]".
If you are using a Seeker. The Seeker will set this value to what is set in the inspector field on StartPath. So you need to change the Seeker value via script, not set this value if you want to change it via script.
Provides additional traversal information to a path request.
List<Vector3>
vectorPath
Holds the (possibly post processed) path as a Vector3 list.
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
}
Private/Protected Members
uint
CalculateHScore
(
)
Estimated cost from the specified node to the target.
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
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
pop the next node of the heap and set it as current
check if the function has exceeded the time limit
if so, return and wait for the function to get called again
bool
CanTraverse
(
)
Returns if the node can be traversed.
This per default equals to if the node is walkable and if the node's tag is included in enabledTags
void
ChooseShortestPath
()
Set chosenTarget to the index of the shortest path.
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.
void
CompletePathIfStartIsValidTarget
()
Checks if the start node is the target and complete the path if that is the case.
This is necessary so that subclasses (e.g XPath) can override this behaviour.
If the start node is a valid target point, this method should set CompleteState to Complete and trace the path.
The node currently being processed.
string
DebugString
(
)
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.
float
duration
How long it took to calculate this path in milliseconds.
int []
endNodeCosts
Saved original costs for the end node.
bool
EndPointGridGraphSpecialCase
(
)
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.
Return
True if the workaround was applied. If this happens the endPoint, endNode, hTarget and hTargetNode fields will be modified.
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
void
FailWithError
(
)
Causes the path to fail and sets errorLog to msg.
bool
FloodingPath
True for paths that want to search all nodes and not jump over nodes as optimizations.
This disables Jump Point Search when that is enabled to prevent e.g ConstantPath and FloodPath to become completely useless.
uint
GetConnectionSpecialCost
(
GraphNode | a | Moving from this node |
GraphNode | b | Moving to this node |
uint | currentCost | The cost of moving between the nodes. Return this value if there is no meaningful special cost to return. |
)
May be called by graph nodes to get a special cost for some connections.
Nodes may call it when PathNode.flag2 is set to true, for example mesh nodes, which have a very large area can be marked on the start and end nodes, this method will be called to get the actual cost for moving from the start position to its neighbours instead of as would otherwise be the case, from the start node's position to its neighbours. The position of a node and the actual start point on the node can vary quite a lot.
The default behaviour of this method is to return the previous cost of the connection, essentiall making no change at all.
This method should return the same regardless of the order of a and b. That is f(a,b) == f(b,a) should hold.
uint
GetTagPenalty
(
int | tag | A value between 0 (inclusive) and 32 (exclusive). |
)
Returns penalty for the given tag.
uint
GetTraversalCost
(
)
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.
Target to use for H score calculations.
Target to use for H score calculation.
Used alongside hTarget.
void
Initialize
()
Initializes the path.
Sets up the open list and adds the first node to it
int []
internalTagPenalties
The tag penalties that are actually used.
If manualTagPenalties is null, this will be ZeroTagPenalties
int []
manualTagPenalties
Tag penalties set by other scripts.
Internal linked list implementation.
Warning
This is used internally by the system. You should never change this.
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.
PathNode
partialBestTarget
Current best target for the partial path.
This is the node with the lowest H score.
Warning
This feature is currently a work in progress and may not work in the current version
Data for the thread calculating this path.
ushort
pathID
ID of this path.
Used to distinguish between different paths
Returns the state of the path in the pathfinding pipeline.
void
Prepare
()
Prepares the path.
Searches for start and end nodes and does some simple checking if a path is at all possible
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
RecalculateHTarget
(
)
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
ResetFlags
()
Reset flag1 on all nodes after the pathfinding has completed (no matter if an error occurs or if the path is canceled)
void
ReturnPath
()
Calls callback to return the calculated path.
int
searchedNodes
Number of nodes this path has searched.
int
sequentialTarget
Current target for Sequential heuristicMode.
Refers to an item in the targetPoints array
void
SetPathParametersForReturn
(
)
int
targetNodeCount
Number of target nodes left to find.
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).
