Struct PathTracer
Public
Helper for following a path.
This struct keeps track of the path from the agent's current position to the end of the path. Whenever the agent moves you should call UpdateStart to update the path. This will automatically update the path if the agent has moved to the next node, or repair the path if the agent has been pushed away into a node which wasn't even on the original path. If the destination changes you should call UpdateEnd to update the path. This also repairs the path and it allows you to instantly get a valid path to the new destination, unless the destination has changed so much that the repair is insufficient. In that case you will have to wait for the next path recalculation. Check isStale to see if the PathTracer recommends that the path be recalculated.
After repairing the path, it will be valid, but it will not necessarily be the shortest possible path. Therefore it is still recommended that you recalculate the path every now and then.
The PathTracer stores the current path as a series of nodes. When the direction to move in is requested (by calling GetNextCorners), a path will be found which passes through all those nodes, using the funnel algorithm to simplify the path. In some cases the path will contain inner vertices which make the path longer than it needs to be. Those will be iteratively removed until the path is as short as possible. For performance only a limited number of iterations are performed per frame, but this is usually fast enough that the simplification appears to be instant.
WarningThis struct allocates unmanaged memory. You must call Dispose when you are done with it, to avoid memory leaks.
NoteThis is a struct, not a class. This means that if you need to pass it around, or return it from a property, you must use the ref keyword, as otherwise C# will just make a copy.
using Pathfinding;
using Pathfinding.Drawing;
using Pathfinding.Util;
using Unity.Collections;
using Unity.Mathematics;
using UnityEngine;
public class PathTracerTest : MonoBehaviour {
PathTracer tracer;
NativeMovementPlane movementPlane => new NativeMovementPlane(Quaternion.identity);
ABPath lastCalculatedPath;
void OnEnable () {
tracer = new PathTracer(Allocator.Persistent);
}
void OnDisable () {
// Release all unmanaged memory from the path tracer, to avoid memory leaks
tracer.Dispose();
}
void Start () {
// Schedule a path calculation to a point ahead of this object
var path = ABPath.Construct(transform.position, transform.position + transform.forward*10, (p) => {
// This callback will be called when the path has been calculated
var path = p as ABPath;
if (path.error) {
// The path could not be calculated
Debug.LogError("Could not calculate path");
return;
}
// Split the path into normal sequences of nodes, and off-mesh links
var parts = Funnel.SplitIntoParts(path);
// Assign the path to the PathTracer
tracer.SetPath(parts, path.path, path.originalStartPoint, path.originalEndPoint, movementPlane, path.traversalProvider, path);
lastCalculatedPath = path;
});
AstarPath.StartPath(path);
}
void Update () {
if (lastCalculatedPath == null || !tracer.isCreated) return;
// Repair the path to start from the transform's position
// If you move the transform around in the scene view, you'll see the path update in real time
tracer.UpdateStart(transform.position, PathTracer.RepairQuality.High, movementPlane, lastCalculatedPath.traversalProvider, lastCalculatedPath);
// Get up to the next 10 corners of the path
var buffer = new NativeList<float3>(Allocator.Temp);
NativeArray<int> scratchArray = default;
tracer.GetNextCorners(buffer, 10, ref scratchArray, Allocator.Temp, lastCalculatedPath.traversalProvider, lastCalculatedPath);
// Draw the next 10 corners of the path in the scene view
using (Draw.WithLineWidth(2)) {
Draw.Polyline(buffer.AsArray(), Color.red);
}
// Release all temporary unmanaged memory
buffer.Dispose();
scratchArray.Dispose();
}
}
Inner Types
Public Methods
void
AppendPath
(
)
Appends the given nodes to the start or to the end of the path, one by one.
void
AssertValidInPath
(
)
void
CalculateFunnelPortals
(
int | startNodeIndex | |
int | endNodeIndex | |
List<float3> | outLeftPortals | |
List<float3> | outRightPortals | |
)
void
CheckInvariants
()
Checks that invariants are satisfied.
This is only called in the editor for performance reasons.
firstPartIndex must be in bounds of parts.
The first part must contain at least 1 node (unless there are no parts in the path at all).
The number of nodes in the first part must be equal to the number of portals in the funnel state + 1.
The number of portals in the funnel state must equal portalIsNotInnerCorner.Length.
The last node of the last part must end at the end of the path.
The first node of the first part must start at the start of the path.
firstPartContainsDestroyedNodes implies that there must be at least one destroyed node in the first part (this is an implication, not an equivalence).
If the first node is not destroyed, then startNode must be the first node in the first part.
void
Clear
()
Clears the current path.
Returns a deep clone of this object.
void
ConvertCornerIndicesToPathProjected
(
NativeArray<int> | cornerIndices | The corner indices to convert. You can get these from GetNextCornerIndices. |
int | numCorners | The number of indices in the cornerIndices array. |
bool | lastCorner | True if the last corner in the path has been reached. |
NativeList<float3> | buffer | The buffer to store the converted positions in. |
float3 | up | The up axis of the agent's movement plane. |
)
Converts corner indices to world space positions.
The corners will not necessarily be in the same world space position as the real corners. Instead the path will be unwrapped and flattened, and then transformed onto a plane that lines up with the first portal in the funnel. For most 2D and 3D worlds, this distinction is irrelevant, but for curved worlds (e.g. a spherical world) this can make a big difference. In particular, steering towards unwrapped corners is much more likely to work well than steering towards the real corners, as they can be e.g. on the other side of a round planet.
void
Dispose
()
Disposes of all unmanaged memory allocated by this path tracer and resets all properties.
void
DrawFunnel
(
CommandBuilder | draw | The command builder to use for drawing. |
NativeMovementPlane | movementPlane | The movement plane of the agent. |
)
Renders the funnel for debugging purposes.
float
EstimateRemainingPath
(
)
Estimates the remaining distance to the end of the current path part.
NoteThis method may modify the internal PathTracer state, so it is not safe to call it from multiple threads at the same time.
bool
FirstInnerVertex
(
NativeArray<int> | indices | |
int | numCorners | |
List<GraphNode> | alternativePath | |
out int | alternativeStartIndex | |
out int | alternativeEndIndex | |
ITraversalProvider | traversalProvider | |
Path | path | |
)
void
GetNextCorners
(
NativeList<float3> | buffer | The buffer to store the corners in. The first corner will be the start point. |
int | maxCorners | The maximum number of corners to store in the buffer. At least 2 corners will always be stored. |
ref NativeArray<int> | scratchArray | A temporary array to use for calculations. This array will be resized if it is too small or uninitialized. |
Allocator | allocator | The allocator to use for the scratchArray, if it needs to be reallocated. |
ITraversalProvider | traversalProvider | The traversal provider to use for the path. Or null to use the default traversal provider. |
Path | path | The path to pass to the traversal provider. Or null. |
)
Calculate the next corners in the path.
This will also do additional simplifications to the path if possible. Inner corners will be removed. There is a limit to how many simplifications will be done per frame.
If the path contains destroyed nodes, then isStale will become true and a best-effort result will be returned.
NoteThis method may modify the PathTracer state, so it is not safe to call it from multiple threads at the same time.
int | partIndex=0 | The index of the path part. Zero is the always the current path part. |
)
Indicates if the given path part is a regular path part or an off-mesh link.
void
HeuristicallyPopPortals
(
)
Use a heuristic to determine when an agent has passed a portal and we need to pop it.
Assumes the start point/end point of the first part is point, and simplifies the funnel accordingly. It uses the cached portals to determine if the agent has passed a portal. This works even if nodes have been destroyed.
NoteDoes not update the start/end point of the first part.
)
Searches from currentNode until it finds a node that contains the given point.
The return value is a list of nodes that start with currentNode and ends with the node that contains the given point, if it could be found. Otherwise, the return value will be an empty list.
bool
PartContainsDestroyedNodes
(
)
PathTracer
(
)
Create a new empty path tracer.
void
PopParts
(
int | count | The number of parts to remove. |
ITraversalProvider | traversalProvider | The traversal provider to use for the path. Or null to use the default traversal provider. |
Path | path | The path to pass to the traversal provider. Or null. |
)
Remove the first count parts of the path.
This is used when an agent has traversed an off-mesh-link, and we want to start following the path after the off-mesh-link.
void
RemoveAllPartsExceptFirst
()
void
SetFromSingleNode
(
)
Replaces the current path with a single node.
void
SetPath
(
)
Replaces the current path with the given path.
void
SetPath
(
List<Funnel.PathPart> | parts | The individual parts of the path. See Funnel.SplitIntoParts. |
List<GraphNode> | nodes | All nodes in the path. The path parts refer to slices of this array. |
Vector3 | unclampedStartPoint | The start point of the path. This is typically the start point that was passed to the path request, or the agent's current position. |
Vector3 | unclampedEndPoint | The end point of the path. This is typically the destination point that was passed to the path request. |
NativeMovementPlane | movementPlane | The movement plane of the agent. |
ITraversalProvider | traversalProvider | The traversal provider to use for the path. Or null to use the default traversal provider. |
Path | path | The path to pass to the traversal provider. Or null. |
)
Replaces the current path with the given path.
bool
SplicePath
(
int | startIndex | Absolute index of the first node to remove |
int | toRemove | Number of nodes to remove |
List<GraphNode> | toInsert | Nodes to insert at startIndex. The nodes must not be destroyed. Passing null is equivalent to an empty list. |
)
Removes nodes [startIndex, startIndex+toRemove) and then inserts the given nodes at startIndex.
Returns true if the splicing succeeded. Returns false if splicing failed because it would have to access destroyed nodes. In that case the path is left unmodified.
)
Update the end point of the path, clamping it to the graph, and repairing the path if necessary.
This may cause isStale to become true, if the path could not be repaired successfully.
ReturnThe new end point, which has been clamped to the graph.
)
Update the start point of the path, clamping it to the graph, and repairing the path if necessary.
This may cause isStale to become true, if the path could not be repaired successfully.
ReturnThe new start point, which has been clamped to the graph.
Public Static Methods
bool
ContainsAndProject
(
)
Burstified function which checks if a point is inside a triangle-node and if so, projects that point onto the node's surface.
ReturnIf the point is inside the node.
float
EstimateRemainingPath
(
)
int
HashNode
(
)
Returns a hash with the most relevant information about a node.
bool
IsInnerVertexGrid
(
)
bool
IsInnerVertexTriangleMesh
(
)
float3
ProjectOnSurface
(
float3 | a | |
float3 | b | |
float3 | c | |
float3 | p | |
float3 | up | |
)
float
RemainingDistanceLowerBound
(
)
Calculates a lower bound on the remaining distance to the end of the path part.
It assumes the agent will follow the path, and then move in a straight line to the end of the path part.
void
RemoveGridPathDiagonals
(
)
Removes diagonal connections in a grid path and replaces them with two axis-aligned connections.
This is done to make the funnel algorithm work better on grid graphs.
int2
ResolveNormalizedGridPoint
(
)
bool
SimplifyGridInnerVertex
(
)
float
SquaredDistanceToNode
(
GraphNode | node | The node to calculate the distance to |
Vector3 | point | The point to calculate the distance from. For navmesh/recast/grid graphs this point should be in graph space. |
refBBTree.ProjectionParams | projectionParams | Parameters for the projection, if the node is a triangle mesh node. The projection should be based on the node's graph. |
)
Calculates the squared distance from a point to the closest point on the node.
Public Variables
int
desiredCornersForGoodSimplification
The minimum number of corners to request from GetNextCornerIndices to ensure the path can be simplified well.
The path simplification algorithm requires at least 2 corners on navmesh graphs, but 3 corners on grid graphs.
End point of the path.
This is not necessarily the same as the destination, as this point may be clamped to the graph.
Vector3
endPointOfFirstPart
End point of the current path part.
If the path has multiple parts, this is typically the start of an off-mesh link. If the path has only one part, this is the same as endPoint.
bool
firstPartContainsDestroyedNodes
If true, the first part contains destroyed nodes.
This can happen if the graph is updated and some nodes are destroyed.
If this is true, the path is considered stale and should be recalculated.
The opposite is not necessarily true. If this is false, the path may still be stale.
bool
hasPath
True if there is a path to follow.
bool
isCreated
True until Dispose is called.
bool
isNextPartValidLink
True if the next part in the path exists, and is a valid link.
This is true if the path has at least 2 parts and the second part is an off-mesh link.
If any nodes in the second part have been destroyed, this will return false.
bool
isStale
True if the path is stale and should be recalculated as quickly as possible.
This is true if the path has become invalid (e.g. due to a graph update), or if the destination has changed so much that we don't have a path to the destination at all.
For performance reasons, the agent tries to avoid checking if nodes have been destroyed unless it needs to access them to calculate its movement. Therefore, if a path is invalidated further ahead, the agent may not realize this until it has moved close enough.
Hashes of some important data for each node, to determine if the node has been invalidated in some way.
For e.g. the grid graph, this is done using the node's index in the grid. This ensures that the node is counted as invalid if the node is for example moved to the other side of the graph using the ProceduralGraphMover.
For all nodes, this includes if info about if the node has been destroyed, and if it is walkable.
This will always have the same length as the nodes array, and the absolute indices in this array will correspond to the absolute indices in the nodes array.
int
partCount
Number of parts in the path.
A part is either a sequence of adjacent nodes, or an off-mesh link.
The type of graph that the current path part is on.
This is either a grid-like graph, or a navmesh-like graph.
CircularBuffer<byte>
portalIsNotInnerCorner
Indicates if portals are definitely not inner corners, or if they may be.
For each portal, if bit 0 is set then the left side of the portal is definitely not an inner corner. If bit 1 is set that means the same thing but for the right side of the portal.
Should always have the same length as the portals in funnelState.
Current start node of the path.
Since the path is updated every time the agent moves, this will be the node which the agent is inside.
In case the path has become invalid, this will be set to the closest node to the agent, or if no such node could be found, it will be set to null.
NoteNot necessarily up to date unless UpdateStart has been called first.
ushort
version
Incremented whenever the path is changed.
Public Static Variables
const int
NODES_TO_CHECK_FOR_DESTRUCTION = 5
int[]
SplittingCoefficients = new int[] {
0, 1,
1, 2,
1, 4,
3, 4,
1, 8,
3, 8,
5, 8,
7, 8,
}
Public Enums
PartGraphType
Type of graph that the current path part is on.
Private/Protected Members
ProfilerMarker
MarkerClosest = new ProfilerMarker("ClosestPointOnNode")
ProfilerMarker
MarkerContains = new ProfilerMarker("ContainsNode")
ProfilerMarker
MarkerGetNearest = new ProfilerMarker("GetNearest")
ProfilerMarker
MarkerSimplify = new ProfilerMarker("Simplify")