Contains useful functions for working with paths and nodes. More...

Detailed Description

Contains useful functions for working with paths and nodes.

This class works a lot with the GraphNode class, a useful function to get nodes is AstarPath.GetNearest.

See also: AstarPath.GetNearest; Pathfinding.GraphUpdateUtilities; Pathfinding.GraphUtilities

Static Public Member Functions
static List< GraphNode >	BFS (GraphNode seed, int depth, int tagMask=-1, System.Func< GraphNode, bool > filter=null)
	Returns all nodes up to a given node-distance from the seed node. More...

static void	GetPointsAroundPoint (Vector3 center, IRaycastableGraph g, List< Vector3 > previousPoints, float radius, float clearanceRadius)
	Will calculate a number of points around center which are on the graph and are separated by clearance from each other. More...

static void	GetPointsAroundPointWorld (Vector3 p, IRaycastableGraph g, List< Vector3 > previousPoints, float radius, float clearanceRadius)
	Will calculate a number of points around p which are on the graph and are separated by clearance from each other. More...

static List< Vector3 >	GetPointsOnNodes (List< GraphNode > nodes, int count, float clearanceRadius=0)
	Returns randomly selected points on the specified nodes with each point being separated by clearanceRadius from each other. More...

static List< GraphNode >	GetReachableNodes (GraphNode seed, int tagMask=-1, System.Func< GraphNode, bool > filter=null)
	Returns all nodes reachable from the seed node. More...

static List< Vector3 >	GetSpiralPoints (int count, float clearance)
	Returns points in a spiral centered around the origin with a minimum clearance from other points. More...

static bool	IsPathPossible (GraphNode node1, GraphNode node2)
	Returns if there is a walkable path from node1 to node2. More...

static bool	IsPathPossible (List< GraphNode > nodes)
	Returns if there are walkable paths between all nodes. More...

static bool	IsPathPossible (List< GraphNode > nodes, int tagMask)
	Returns if there are walkable paths between all nodes. More...

Static Private Member Functions
static Vector3	InvoluteOfCircle (float a, float t)
	Returns the XZ coordinate of the involute of circle. More...

Static Private Attributes
static Dictionary< GraphNode, int >	BFSMap

static Queue< GraphNode >	BFSQueue

Member Function Documentation

◆ BFS()

static List<GraphNode> BFS	(	GraphNode	seed,
		int	depth,
		int	tagMask = `-1`,
		System.Func< GraphNode, bool >	filter = `null`
	)

static

Returns all nodes up to a given node-distance from the seed node.

This function performs a BFS (breadth-first search) or flood fill of the graph and returns all nodes within a specified node distance which can be reached from the seed node. In almost all cases when depth is large enough this will be identical to returning all nodes which have the same area as the seed node. In the editor areas are displayed as different colors of the nodes. The only case where it will not be so is when there is a one way path from some part of the area to the seed node but no path from the seed node to that part of the graph.

The returned list is sorted by node distance from the seed node i.e distance is measured in the number of nodes the shortest path from seed to that node would pass through. Note that the distance measurement does not take heuristics, penalties or tag penalties.

Depending on the number of nodes, this function can take quite some time to calculate so don't use it too often or it might affect the framerate of your game.

Parameters

seed	The node to start the search from.
depth	The maximum node-distance from the seed node.
tagMask	Optional mask for tags. This is a bitmask.
filter	Optional filter for which nodes to search. You can combine this with depth = int.MaxValue and tagMask = -1 to make the filter determine everything. Only walkable nodes are searched regardless of the filter. If the filter function returns false the node will be treated as unwalkable.

Returns: A List<GraphNode> containing all nodes reachable up to a specified node distance from the seed node. For better memory management the returned list should be pooled, see Pathfinding.Util.ListPool

Warning: This method is not thread safe. Only use it from the Unity thread (i.e normal game code).

The video below shows the BFS result with varying values of depth. Points are sampled on the nodes using GetPointsOnNodes.

◆ GetPointsAroundPoint()

static void GetPointsAroundPoint	(	Vector3	center,
		IRaycastableGraph	g,
		List< Vector3 >	previousPoints,
		float	radius,
		float	clearanceRadius
	)

static

Will calculate a number of points around center which are on the graph and are separated by clearance from each other.

The maximum distance from center to any point will be radius. Points will first be tried to be laid out as previousPoints and if that fails, random points will be selected. This is great if you want to pick a number of target points for group movement. If you pass all current agent points from e.g the group's average position this method will return target points so that the units move very little within the group, this is often aesthetically pleasing and reduces jitter if using some kind of local avoidance.

Parameters

center	The point to generate points around
g	The graph to use for linecasting. If you are only using one graph, you can get this by AstarPath.active.graphs[0] as IRaycastableGraph. Note that not all graphs are raycastable, recast, navmesh and grid graphs are raycastable. On recast and navmesh it works the best.
previousPoints	The points to use for reference. Note that these should not be in world space. They are treated as relative to center. The new points will overwrite the existing points in the list. The result will be in world space, not relative to center.
radius	The final points will be at most this distance from center.
clearanceRadius	The points will if possible be at least this distance from each other.

Todo:: Write unit tests

◆ GetPointsAroundPointWorld()

static void GetPointsAroundPointWorld	(	Vector3	p,
		IRaycastableGraph	g,
		List< Vector3 >	previousPoints,
		float	radius,
		float	clearanceRadius
	)

static

Will calculate a number of points around p which are on the graph and are separated by clearance from each other.

This is like GetPointsAroundPoint except that previousPoints are treated as being in world space. The average of the points will be found and then that will be treated as the group center.

Parameters

p	The point to generate points around
g	The graph to use for linecasting. If you are only using one graph, you can get this by AstarPath.active.graphs[0] as IRaycastableGraph. Note that not all graphs are raycastable, recast, navmesh and grid graphs are raycastable. On recast and navmesh it works the best.
previousPoints	The points to use for reference. Note that these are in world space. The new points will overwrite the existing points in the list. The result will be in world space.
radius	The final points will be at most this distance from p.
clearanceRadius	The points will if possible be at least this distance from each other.

◆ GetPointsOnNodes()

static List<Vector3> GetPointsOnNodes	(	List< GraphNode >	nodes,
		int	count,
		float	clearanceRadius = `0`
	)

static

Returns randomly selected points on the specified nodes with each point being separated by clearanceRadius from each other.

Selecting points ON the nodes only works for TriangleMeshNode (used by Recast Graph and Navmesh Graph) and GridNode (used by GridGraph). For other node types, only the positions of the nodes will be used.

clearanceRadius will be reduced if no valid points can be found.

Note: This method assumes that the nodes in the list have the same type for some special cases. More specifically if the first node is not a TriangleMeshNode or a GridNode, it will use a fast path which assumes that all nodes in the list have the same surface area (which usually is a surface area of zero and the nodes are all PointNodes).

◆ GetReachableNodes()

static List<GraphNode> GetReachableNodes	(	GraphNode	seed,
		int	tagMask = `-1`,
		System.Func< GraphNode, bool >	filter = `null`
	)

static

Returns all nodes reachable from the seed node.

This function performs a DFS (depth-first-search) or flood fill of the graph and returns all nodes which can be reached from the seed node. In almost all cases this will be identical to returning all nodes which have the same area as the seed node. In the editor areas are displayed as different colors of the nodes. The only case where it will not be so is when there is a one way path from some part of the area to the seed node but no path from the seed node to that part of the graph.

The returned list is not sorted in any particular way.

Depending on the number of reachable nodes, this function can take quite some time to calculate so don't use it too often or it might affect the framerate of your game.

Parameters

seed	The node to start the search from.
tagMask	Optional mask for tags. This is a bitmask.

See also: Bitmask Tutorial.

Parameters

filter Optional filter for which nodes to search. You can combine this with tagMask = -1 to make the filter determine everything. Only walkable nodes are searched regardless of the filter. If the filter function returns false the node will be treated as unwalkable.

Returns: A List<Node> containing all nodes reachable from the seed node. For better memory management the returned list should be pooled, see Pathfinding.Util.ListPool.

◆ GetSpiralPoints()

static List<Vector3> GetSpiralPoints	(	int	count,
		float	clearance
	)

static

Returns points in a spiral centered around the origin with a minimum clearance from other points.

The points are laid out on the involute of a circle

See also: http://en.wikipedia.org/wiki/Involute Which has some nice properties. All points are separated by clearance world units. This method is O(n), yes if you read the code you will see a binary search, but that binary search has an upper bound on the number of steps, so it does not yield a log factor.

Note: Consider recycling the list after usage to reduce allocations.

See also: Pathfinding.Util.ListPool

◆ InvoluteOfCircle()

static Vector3 InvoluteOfCircle	(	float	a,
		float	t
	)

staticprivate

Returns the XZ coordinate of the involute of circle.

See also: http://en.wikipedia.org/wiki/Involute

◆ IsPathPossible() [1/3]

static bool IsPathPossible	(	GraphNode	node1,
		GraphNode	node2
	)

static

Returns if there is a walkable path from node1 to node2.

This method is extremely fast because it only uses precalculated information.

        GraphNode node1 = AstarPath.active.GetNearest(point1, NNConstraint.Default).node;
        GraphNode node2 = AstarPath.active.GetNearest(point2, NNConstraint.Default).node;
        if (PathUtilities.IsPathPossible(node1, node2)) {
            // Yay, there is a path between those two nodes
        }

Note: If you are making changes to the graph without using e.g AstarPath.UpdateGraphs or the GraphUpdateScene component, areas must first be recaculated using AstarPath.FloodFill().

See also: Graph Updates during Runtime; AstarPath.GetNearest

◆ IsPathPossible() [2/3]

static bool IsPathPossible ( List< GraphNode > nodes )

static

Returns if there are walkable paths between all nodes.

Note: If you are making changes to the graph without using e.g AstarPath.UpdateGraphs or the GraphUpdateScene component, areas must first be recaculated using e.g AstarPath.FloodFill().

See also: Graph Updates during Runtime

Returns true for empty lists.

See also: AstarPath.GetNearest

◆ IsPathPossible() [3/3]

static bool IsPathPossible	(	List< GraphNode >	nodes,
		int	tagMask
	)

static

Returns if there are walkable paths between all nodes.

Note: If you are making changes to the graph without using e.g AstarPath.UpdateGraphs or the GraphUpdateScene component, areas must first be recaculated using e.g AstarPath.FloodFill().

See also: Graph Updates during Runtime

This method will actually only check if the first node can reach all other nodes. However this is equivalent in 99% of the cases since almost always the graph connections are bidirectional. If you are not aware of any cases where you explicitly create unidirectional connections this method can be used without worries.

Returns true for empty lists

Warning: This method is significantly slower than the IsPathPossible method which does not take a tagMask

See also: AstarPath.GetNearest

Member Data Documentation

◆ BFSMap

Dictionary<GraphNode, int> BFSMap

staticprivate

◆ BFSQueue

Queue<GraphNode> BFSQueue

staticprivate

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

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

Detailed Description

Static Public Member Functions

Static Private Member Functions

Static Private Attributes

Member Function Documentation

◆ BFS()

◆ GetPointsAroundPoint()

◆ GetPointsAroundPointWorld()

◆ GetPointsOnNodes()

◆ GetReachableNodes()

◆ GetSpiralPoints()

◆ InvoluteOfCircle()

◆ IsPathPossible() [1/3]

◆ IsPathPossible() [2/3]

◆ IsPathPossible() [3/3]

Member Data Documentation

◆ BFSMap

◆ BFSQueue