Struct PathTracer

void AppendNode (

bool	toStart
GraphNode	node

)

void AppendPath (

bool	toStart
CircularBuffer<GraphNode>	path

)

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

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.

PathTracer Clone ()

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.

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 (

int	maxCorners
refNativeMovementPlane	movementPlane

)

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

bool FirstInnerVertex (

NativeArray<int>	indices
int	numCorners
List<GraphNode>	alternativePath
out int	alternativeStartIndex
out int	alternativeEndIndex
ITraversalProvider	traversalProvider
Path	path

)

LinkInfo GetLinkInfo (

int

partIndex=0

)

int GetNextCornerIndices (

ref NativeArray<int>	buffer
int	maxCorners
Allocator	allocator
out bool	lastCorner
ITraversalProvider	traversalProvider
Path	path

)

Calculate the indices of the next corners in the path.

This is like GetNextCorners, except that it returns indices referring to the internal funnelState. You can use ConvertCornerIndicesToPathProjected or funnelState.ConvertCornerIndicesToPath to convert the indices to world space positions.

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.

PartType GetPartType (

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 (

bool	isStartOfPart
Vector3	point

)

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.

CircularBuffer<GraphNode> LocalSearch (

GraphNode	currentNode
Vector3	point
int	maxNodesToSearch
NativeMovementPlane	movementPlane
ITraversalProvider	traversalProvider
Path	path

)

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 (

int

partIndex=0

)

PathTracer (

Allocator

allocator

)

Create a new empty path tracer.

void PopParts (

int

count

The number of parts to remove.

)

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 Repair (

Vector3	point
bool	isStart
RepairQuality	quality
NativeMovementPlane	movementPlane
ITraversalProvider	traversalProvider
Path	path
bool	allowCache=true

)

void RepairFull (

Vector3	point
bool	isStart
RepairQuality	quality
NativeMovementPlane	movementPlane
ITraversalProvider	traversalProvider
Path	path

)

void SetFromSingleNode (

GraphNode	node
Vector3	position
NativeMovementPlane	movementPlane

)

Replaces the current path with a single node.

void SetFunnelState (

PathPart

part

)

void SetPath (

List<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.

Vector3 UpdateEnd (

Vector3	position
RepairQuality	quality
NativeMovementPlane	movementPlane
ITraversalProvider	traversalProvider
Path	path

)

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

This may cause isStale to become false, if the path could not be repaired successfully.

Vector3 UpdateStart (

Vector3	position
RepairQuality	quality
NativeMovementPlane	movementPlane
ITraversalProvider	traversalProvider
Path	path

)

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

This may cause isStale to become false, if the path could not be repaired successfully.

bool ContainsAndProject (

refInt3	a
refInt3	b
refInt3	c
ref Vector3	p
float	height
refNativeMovementPlane	movementPlane
out Vector3	projected

)

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

bool ContainsPoint (

GraphNode	node
Vector3	point
NativeMovementPlane	plane

)

float EstimateRemainingPath (

ref FunnelState	funnelState
ref PathPart	part
int	maxCorners
refNativeMovementPlane	movementPlane

)

bool IsInnerVertex (

CircularBuffer<GraphNode>	nodes
PathPart	part
int	portalIndex
bool	rightSide
List<GraphNode>	alternativeNodes
NNConstraint	nnConstraint
out int	startIndex
out int	endIndex
ITraversalProvider	traversalProvider
Path	path

)

bool IsInnerVertexGrid (

CircularBuffer<GraphNode>	nodes
PathPart	part
int	portalIndex
bool	rightSide
List<GraphNode>	alternativeNodes
NNConstraint	nnConstraint
out int	startIndex
out int	endIndex
ITraversalProvider	traversalProvider
Path	path

)

bool IsInnerVertexTriangleMesh (

CircularBuffer<GraphNode>	nodes
PathPart	part
int	portalIndex
bool	rightSide
List<GraphNode>	alternativeNodes
NNConstraint	nnConstraint
out int	startIndex
out int	endIndex
ITraversalProvider	traversalProvider
Path	path

)

Int3 MaybeSetYZero (

Int3	p
bool	setYToZero

)

PartGraphType PartGraphTypeFromNode (

GraphNode

node

)

float3 ProjectOnSurface (

float3	a
float3	b
float3	c
float3	p
float3	up

)

float RemainingDistanceLowerBound (

inUnsafeSpan<float3>	nextCorners
in float3	endOfPart
inNativeMovementPlane	movementPlane

)

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 (

PathPart[]	parts
int	partIndex
refCircularBuffer<GraphNode>	path

)

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 (

GridGraph	grid
refCircularBuffer<GraphNode>	nodes
UnsafeSpan<int>	cornerIndices
PathPart	part
int	index
out int	nodeIndex

)

bool SimplifyGridInnerVertex (

refCircularBuffer<GraphNode>	nodes
UnsafeSpan<int>	cornerIndices
PathPart	part
refCircularBuffer<byte>	portalIsNotInnerCorner
List<GraphNode>	alternativePath
out int	alternativeStartIndex
out int	alternativeEndIndex
ITraversalProvider	traversalProvider
Path	path
bool	lastCorner

)

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.

bool Valid (

GraphNode

node

)

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.

bool endIsUpToDate

Vector3 endPoint

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.

int firstPartIndex

FunnelState funnelState

bool hasPath

True if there is a path to follow.

bool isCreated

True until Dispose is called.

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.

NNConstraint nnConstraint

CircularBuffer<GraphNode> nodes

int partCount

Number of parts in the path.

A part is either a sequence of adjacent nodes, or an off-mesh link.

PartGraphType partGraphType

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

This is either a grid-like graph, or a navmesh-like graph.

PathPart[] parts

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.

bool startIsUpToDate

GraphNode? startNode

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.

GraphNode startNodeInternal

Vector3 startPoint

Start point of the path.

Vector3 unclampedEndPoint

Vector3 unclampedStartPoint

ushort version

Incremented whenever the path is changed.

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, }

PartGraphType

Type of graph that the current path part is on.

RepairQuality

ProfilerMarker MarkerClosest = new ProfilerMarker("ClosestPointOnNode")

ProfilerMarker MarkerContains = new ProfilerMarker("ContainsNode")

ProfilerMarker MarkerGetNearest = new ProfilerMarker("GetNearest")

ProfilerMarker MarkerSimplify = new ProfilerMarker("Simplify")

List<GraphNode> scratchList