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.

Warning

This struct allocates unmanaged memory. You must call Dispose when you are done with it, to avoid memory leaks.

Note

This 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

AppendNode (toStart, node)
Public
AppendPath (toStart, path)

Appends the given nodes to the start or to the end of the path, one by one.

Public
AssertValidInPath (absoluteNodeIndex)
Public
CalculateFunnelPortals (startNodeIndex, endNodeIndex, outLeftPortals, outRightPortals)
Public
CheckInvariants ()

Checks that invariants are satisfied.

Public
Clear ()

Clears the current path.

Public
Clone ()

Returns a deep clone of this object.

Public
ConvertCornerIndicesToPathProjected (cornerIndices, numCorners, lastCorner, buffer, up)

Converts corner indices to world space positions.

Public
Dispose ()

Disposes of all unmanaged memory allocated by this path tracer and resets all properties.

Public
DrawFunnel (draw, movementPlane)

Renders the funnel for debugging purposes.

Public
EstimateRemainingPath (maxCorners, movementPlane)

Estimates the remaining distance to the end of the current path part.

Public
FirstInnerVertex (indices, numCorners, alternativePath, alternativeStartIndex, alternativeEndIndex, traversalProvider, path)
Public
GetLinkInfo (partIndex=0)
Public
GetNextCornerIndices (buffer, maxCorners, allocator, lastCorner, traversalProvider, path)

Calculate the indices of the next corners in the path.

Public
GetNextCorners (buffer, maxCorners, scratchArray, allocator, traversalProvider, path)

Calculate the next corners in the path.

Public
GetPartType (partIndex=0)

Indicates if the given path part is a regular path part or an off-mesh link.

Public Readonly
GetTempQueue (queue, connections)
Public
HeuristicallyPopPortals (isStartOfPart, point)

Use a heuristic to determine when an agent has passed a portal and we need to pop it.

Public
LocalSearch (currentNode, point, maxNodesToSearch, movementPlane, reverse, traversalProvider, path)

Searches from currentNode until it finds a node that contains the given point.

Public
PartContainsDestroyedNodes (partIndex=0)
Public Readonly
PathTracer (allocator)

Create a new empty path tracer.

Public
PopParts (count, traversalProvider, path)

Remove the first count parts of the path.

Public
RemoveAllPartsExceptFirst ()
Public
Repair (point, isStart, quality, movementPlane, traversalProvider, path, allowCache=true)
Public
RepairFull (point, isStart, quality, movementPlane, traversalProvider, path)
Public
SetFromSingleNode (node, position, movementPlane)

Replaces the current path with a single node.

Public
SetFunnelState (part)
Public
SetPath (path, movementPlane)

Replaces the current path with the given path.

Public
SetPath (parts, nodes, unclampedStartPoint, unclampedEndPoint, movementPlane, traversalProvider, path)

Replaces the current path with the given path.

Public
SplicePath (startIndex, toRemove, toInsert)

Removes nodes [startIndex, startIndex+toRemove) and then inserts the given nodes at startIndex.

Public
UpdateEnd (position, quality, movementPlane, traversalProvider, path)

Update the end point of the path, clamping it to the graph, and repairing the path if necessary.

Public
UpdateStart (position, quality, movementPlane, traversalProvider, path)

Update the start point of the path, clamping it to the graph, and repairing the path if necessary.

Public
ValidInPath (absoluteNodeIndex)
Public Readonly

Public Static Methods

ContainsAndProject (a, b, c, p, height, movementPlane, projected)

Burstified function which checks if a point is inside a triangle-node and if so, projects that point onto the node's surface.

Public Static
ContainsPoint (node, point, plane)
Public Static
EstimateRemainingPath (funnelState, part, maxCorners, movementPlane)
Public Static
HashNode (node)

Returns a hash with the most relevant information about a node.

Public Static
IsInnerVertex (nodes, part, portalIndex, rightSide, alternativeNodes, nnConstraint, startIndex, endIndex, traversalProvider, path)
Public Static
IsInnerVertexGrid (nodes, part, portalIndex, rightSide, alternativeNodes, nnConstraint, startIndex, endIndex, traversalProvider, path)
Public Static
IsInnerVertexTriangleMesh (nodes, part, portalIndex, rightSide, alternativeNodes, nnConstraint, startIndex, endIndex, traversalProvider, path)
Public Static
MaybeSetYZero (p, setYToZero)
Public Static
PartGraphTypeFromNode (node)
Public Static
ProjectOnSurface (a, b, c, p, up)
Public Static
QueueHasNode (queue, count, node)
Public Static
RemainingDistanceLowerBound (nextCorners, endOfPart, movementPlane)

Calculates a lower bound on the remaining distance to the end of the path part.

Public Static
RemoveGridPathDiagonals (parts, partIndex, path, pathNodeHashes, nnConstraint, traversalProvider, pathObject)

Removes diagonal connections in a grid path and replaces them with two axis-aligned connections.

Public Static
ResolveNormalizedGridPoint (grid, nodes, cornerIndices, part, index, nodeIndex)
Public Static
SimplifyGridInnerVertex (nodes, cornerIndices, part, portalIsNotInnerCorner, alternativePath, alternativeStartIndex, alternativeEndIndex, nnConstraint, traversalProvider, path, lastCorner)
Public Static
SquaredDistanceToNode (node, point, projectionParams)

Calculates the squared distance from a point to the closest point on the node.

Public Static
Valid (node)
Public Static

Public Variables

desiredCornersForGoodSimplification

The minimum number of corners to request from GetNextCornerIndices to ensure the path can be simplified well.

Public
endIsUpToDate
Public
endPoint

End point of the path.

Public Readonly
endPointOfFirstPart

End point of the current path part.

Public Readonly
firstPartContainsDestroyedNodes

If true, the first part contains destroyed nodes.

Public
firstPartIndex
Public
funnelState
Public
hasPath

True if there is a path to follow.

Public Readonly
isCreated

True until Dispose is called.

Public Readonly
isNextPartValidLink

True if the next part in the path exists, and is a valid link.

isStale

True if the path is stale and should be recalculated as quickly as possible.

Public Readonly
nnConstraint
Public
nodeHashes

Hashes of some important data for each node, to determine if the node has been invalidated in some way.

Public
nodes

All nodes in the path.

Public
partCount

Number of parts in the path.

Public Readonly
partGraphType

The type of graph that the current path part is on.

Public
parts
Public
portalIsNotInnerCorner

Indicates if portals are definitely not inner corners, or if they may be.

Public
startIsUpToDate
Public
startNode

Current start node of the path.

Public
startNodeInternal
Public
startPoint

Start point of the path.

Public Readonly
unclampedEndPoint
Public
unclampedStartPoint
Public
version

Incremented whenever the path is changed.

Public

Public Static Variables

NODES_TO_CHECK_FOR_DESTRUCTION
Public Static
SplittingCoefficients
Public Static
TempConnectionLists
Public Static Readonly
TempQueues
Public Static Readonly

Public Enums

PartGraphType

Type of graph that the current path part is on.

Public
RepairQuality
Public

Private/Protected Members

MarkerClosest
Private Static Readonly
MarkerContains
Private Static Readonly
MarkerGetNearest
Private Static Readonly
MarkerSimplify
Private Static Readonly
scratchList
Private Static