Class Funnel
Public
Implements the funnel algorithm as well as various related methods.
using UnityEngine;
using Pathfinding;
using Pathfinding.Drawing;
public class FunnelExample : MonoBehaviour {
public Transform target = null;
void Update () {
var path = ABPath.Construct(transform.position, target.position);
AstarPath.StartPath(path);
path.BlockUntilCalculated();
// Apply some default adjustments to the path
// not necessary if you are using the Seeker component
new StartEndModifier().Apply(path);
// Split the path into segments and links
var parts = Funnel.SplitIntoParts(path);
// Optionally simplify the path to make it straighter
var nodes = path.path;
Funnel.Simplify(parts, ref nodes);
using (Draw.WithLineWidth(2)) {
// Go through all the parts and draw them in the scene view
for (int i = 0; i < parts.Count; i++) {
var part = parts[i];
if (part.type == Funnel.PartType.OffMeshLink) {
// Draw off-mesh links as a single line
Draw.Line(part.startPoint, part.endPoint, Color.cyan);
} else {
// Calculate the shortest path through the funnel
var portals = Funnel.ConstructFunnelPortals(nodes, part);
var pathThroghPortals = Funnel.Calculate(portals, splitAtEveryPortal: false);
Draw.Polyline(pathThroghPortals, Color.black);
}
}
}
}
}
In the image you can see the output from the code example above. The cyan lines represent off-mesh links.
Inner Types
Public Static Methods
List<Vector3>
Calculate
(
FunnelPortals | funnel | The portals of the funnel. The first and last vertices portals must be single points (so for example left[0] == right[0]). |
bool | splitAtEveryPortal | If true, then a vertex will be inserted every time the path crosses a portal instead of only at the corners of the path. The result will have exactly one vertex per portal if this is enabled. This may introduce vertices with the same position in the output (esp. in corners where many portals meet). |
)
Calculate the shortest path through the funnel.
The path will be unwrapped into 2D space before the funnel algorithm runs. This makes it possible to support the funnel algorithm in XY space as well as in more complicated cases, such as on curved worlds.
void
Simplify
(
)
Simplifies a funnel path using linecasting.
Running time is roughly O(n^2 log n) in the worst case (where n = end-start) Actually it depends on how the graph looks, so in theory the actual upper limit on the worst case running time is O(n*m log n) (where n = end-start and m = nodes in the graph) but O(n^2 log n) is a much more realistic worst case limit.
Requires graph to implement IRaycastableGraph
List<PathPart>
SplitIntoParts
(
)
Splits the path into a sequence of parts which are either off-mesh links or sequences of adjacent triangles.
Public Static Variables
const int
RightSideBit = 1 << 30
Public Enums
PartType
OffMeshLink |
An off-mesh link between two nodes in the same or different graphs.
|
NodeSequence |
A sequence of adjacent nodes in the same graph.
|
The type of a PathPart.
Private/Protected Members
unsafe int
Calculate
(
refNativeCircularBuffer<float4> | unwrappedPortals | Cache of unwrapped portal segments. This may be empty, but it will be filled with unwrapped portals and next time you run the algorithm it will be faster. |
refNativeCircularBuffer<float3> | leftPortals | Left side of the funnel. Should not contain the start point. |
refNativeCircularBuffer<float3> | rightPortals | Right side of the funnel. Should not contain the end point. |
ref float3 | startPoint | Start point of the funnel. The agent will move from here to the best point between leftPortals[0] and rightPortals[0]. |
ref float3 | endPoint | End point of the funnel. |
refUnsafeSpan<int> | funnelPath | Output indices. Contains an index as well as possibly the RightSideBit set. Corresponds to an index into leftPortals or rightPortals depending on if RightSideBit is set. This must point to an array which is at least maxCorners long. |
int | maxCorners | The first N corners of the optimized path will be calculated. Calculating fewer corners is faster. Pass int.MaxValue if you want to calculate all corners. |
ref float3 | projectionAxis | If set to anything other than (0,0,0), then all portals will be projected on a plane with this normal. |
out bool | lastCorner | True if the final corner of the path was reached. If true, then the return value is guaranteed to be at most maxCorners - 1 (unless maxCorners = 0). |
)
Calculate the shortest path through the funnel.
Return
The number of corners added to the funnelPath array.
bool
LeftOrColinear
(
)
True if b is to the left of or on the line from (0,0) to a.
bool
RightOrColinear
(
)
True if b is to the right of or on the line from (0,0) to a.
float2
Unwrap
(
float3 | leftPortal | |
float3 | rightPortal | |
float2 | leftUnwrappedPortal | |
float2 | rightUnwrappedPortal | |
float3 | point | |
float | sideMultiplier | |
float3 | projectionAxis | |
)