Implements the funnel algorithm as well as various related methods. More...

Detailed Description

Implements the funnel algorithm as well as various related methods.

See also: http://digestingduck.blogspot.se/2010/03/simple-stupid-funnel-algorithm.html; FunnelModifier for the component that you can attach to objects to use the funnel algorithm.

Classes
struct	FunnelPortals
	Funnel in which the path to the target will be. More...

struct	PathPart
	Part of a path. More...

Static Public Member Functions
static List< Vector3 >	Calculate (FunnelPortals funnel, bool unwrap, bool splitAtEveryPortal)
	Calculate the shortest path through the funnel. More...

static FunnelPortals	ConstructFunnelPortals (List< GraphNode > nodes, PathPart part)

static void	ShrinkPortals (FunnelPortals portals, float shrink)

static void	Simplify (List< PathPart > parts, ref List< GraphNode > nodes)

static void	Simplify (PathPart part, IRaycastableGraph graph, List< GraphNode > nodes, List< GraphNode > result, int[] tagPenalties, int traversableTags)
	Simplifies a funnel path using linecasting. More...

static List< PathPart >	SplitIntoParts (Path path)

static void	Unwrap (FunnelPortals funnel, Vector2[] left, Vector2[] right)
	Unwraps the funnel portals from 3D space to 2D space. More...

Static Protected Member Functions
static Vector3	FromXZ (Vector2 p)

static bool	LeftOrColinear (Vector2 a, Vector2 b)
	True if b is to the left of or on the line from (0,0) to a. More...

static bool	RightOrColinear (Vector2 a, Vector2 b)
	True if b is to the right of or on the line from (0,0) to a. More...

static Vector2	ToXZ (Vector3 p)

Static Private Member Functions
static void	Calculate (Vector2[] left, Vector2[] right, int numPortals, int startIndex, List< int > funnelPath, int maxCorners, out bool lastCorner)
	Funnel algorithm. More...

static int	FixFunnel (Vector2[] left, Vector2[] right, int numPortals)
	Try to fix degenerate or invalid funnels. More...

static bool	UnwrapHelper (Vector3 portalStart, Vector3 portalEnd, Vector3 prevPoint, Vector3 nextPoint, ref Quaternion mRot, ref Vector3 mOffset)

Member Function Documentation

◆ Calculate() [1/2]

static List<Vector3> Calculate	(	FunnelPortals	funnel,
		bool	unwrap,
		bool	splitAtEveryPortal
	)

static

Calculate the shortest path through the funnel.

Parameters

funnel	The portals of the funnel. The first and last vertices portals must be single points (so for example left[0] == right[0]).
unwrap	Determines if twists and bends should be straightened out before running the funnel algorithm.
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).

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.

See also: Unwrap

◆ Calculate() [2/2]

static void Calculate	(	Vector2 []	left,
		Vector2 []	right,
		int	numPortals,
		int	startIndex,
		List< int >	funnelPath,
		int	maxCorners,
		out bool	lastCorner
	)

staticprivate

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]

See also: http://digestingduck.blogspot.se/2010/03/simple-stupid-funnel-algorithm.html

◆ ConstructFunnelPortals()

static FunnelPortals ConstructFunnelPortals	(	List< GraphNode >	nodes,
		PathPart	part
	)

static

◆ FixFunnel()

static int FixFunnel	(	Vector2 []	left,
		Vector2 []	right,
		int	numPortals
	)

staticprivate

Try to fix degenerate or invalid funnels.

Returns: The number of vertices at the start of both arrays that should be ignored or -1 if the algorithm failed.

◆ FromXZ()

static Vector3 FromXZ ( Vector2 p )

staticprotected

◆ LeftOrColinear()

static bool LeftOrColinear	(	Vector2	a,
		Vector2	b
	)

staticprotected

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

◆ RightOrColinear()

static bool RightOrColinear	(	Vector2	a,
		Vector2	b
	)

staticprotected

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

◆ ShrinkPortals()

static void ShrinkPortals	(	FunnelPortals	portals,
		float	shrink
	)

static

◆ Simplify() [1/2]

static void Simplify	(	List< PathPart >	parts,
		ref List< GraphNode >	nodes
	)

static

◆ Simplify() [2/2]

static void Simplify	(	PathPart	part,
		IRaycastableGraph	graph,
		List< GraphNode >	nodes,
		List< GraphNode >	result,
		int []	tagPenalties,
		int	traversableTags
	)

static

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

◆ SplitIntoParts()

static List<PathPart> SplitIntoParts ( Path path )

static

◆ ToXZ()

static Vector2 ToXZ ( Vector3 p )

staticprotected

◆ Unwrap()

static void Unwrap	(	FunnelPortals	funnel,
		Vector2 []	left,
		Vector2 []	right
	)

static

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.

See also: Calculate(FunnelPortals,bool,bool)

◆ UnwrapHelper()

static bool UnwrapHelper	(	Vector3	portalStart,
		Vector3	portalEnd,
		Vector3	prevPoint,
		Vector3	nextPoint,
		ref Quaternion	mRot,
		ref Vector3	mOffset
	)

staticprivate

The documentation for this class was generated from the following file:

/Users/arong/Unity/a-pathfinding-project/Assets/AstarPathfindingProject/Utilities/Funnel.cs

Detailed Description

Classes

Static Public Member Functions

Static Protected Member Functions

Static Private Member Functions

Member Function Documentation

◆ Calculate() [1/2]

◆ Calculate() [2/2]

◆ ConstructFunnelPortals()

◆ FixFunnel()

◆ FromXZ()

◆ LeftOrColinear()

◆ RightOrColinear()

◆ ShrinkPortals()

◆ Simplify() [1/2]

◆ Simplify() [2/2]

◆ SplitIntoParts()

◆ ToXZ()

◆ Unwrap()

◆ UnwrapHelper()