Class Funnel

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	unwrap	Determines if twists and bends should be straightened out before running the funnel algorithm.
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.

If the unwrap option is disabled the funnel will simply be projected onto the XZ plane. If the unwrap option is enabled then the funnel may be oriented arbitrarily and may have twists and bends. This makes it possible to support the funnel algorithm in XY space as well as in more complicated cases, such as on curved worlds.

FunnelPortals ConstructFunnelPortals (

List<GraphNode>	nodes
PathPart	part

)

void ShrinkPortals (

FunnelPortals	portals
float	shrink

)

void Simplify (

List<PathPart>	parts
ref List<GraphNode>	nodes

)

void Simplify (

PathPart	part
IRaycastableGraph	graph
List<GraphNode>	nodes
List<GraphNode>	result
int []	tagPenalties
int	traversableTags

)

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 (

Path

path

)

void Unwrap (

FunnelPortals	funnel
Vector2 []	left
Vector2 []	right

)

Unwraps the funnel portals from 3D space to 2D space.

The result is stored in the left and right arrays which must be at least as large as the funnel.left and funnel.right lists.

The input is a funnel like in the image below. It may be rotated and twisted. The output will be a funnel in 2D space like in the image below. All twists and bends will have been straightened out.

void Calculate (

Vector2 []	left
Vector2 []	right
int	numPortals
int	startIndex
List<int>	funnelPath
int	maxCorners
out bool	lastCorner

)

Funnel algorithm.

funnelPath will be filled with the result. The result is the indices of the vertices that were picked, a non-negative value refers to the corresponding index in the left array, a negative value refers to the corresponding index in the right array. So e.g 5 corresponds to left[5] and -2 corresponds to right[2]

int FixFunnel (

Vector2 []	left
Vector2 []	right
int	numPortals

)

Try to fix degenerate or invalid funnels.

Vector3 FromXZ (

Vector2

p

)

bool LeftOrColinear (

Vector2	a
Vector2	b

)

True if b is to the left of or on the line from (0,0) to a.

bool RightOrColinear (

Vector2	a
Vector2	b

)

True if b is to the right of or on the line from (0,0) to a.

Vector2 ToXZ (

Vector3

p

)

bool UnwrapHelper (

Vector3	portalStart
Vector3	portalEnd
Vector3	prevPoint
Vector3	nextPoint
ref Quaternion	mRot
ref Vector3	mOffset

)