A* Pathfinding Project  4.1.23
The A* Pathfinding Project for Unity 3D
HierarchicalGraph Class Reference

Holds a hierarchical graph to speed up certain pathfinding queries. More...

Detailed Description

Holds a hierarchical graph to speed up certain pathfinding queries.

A common type of query that needs to be very fast is on the form 'is this node reachable from this other node'. This is for example used when picking the end node of a path. The end node is determined as the closest node to the end point that can be reached from the start node.

This data structure's primary purpose is to keep track of which connected component each node is contained in, in order to make such queries fast.

See also
https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

A connected component is a set of nodes such that there is a valid path between every pair of nodes in that set. Thus the query above can simply be answered by checking if they are in the same connected component. The connected component is exposed on nodes as the Pathfinding.GraphNode.Area property and on this class using the #GetArea method.

In the image below (showing a 200x200 grid graph) each connected component is colored using a separate color. The actual color doesn't signify anything in particular however, only that they are different.

Prior to version 4.2 the connected components were just a number stored on each node, and when a graph was updated the connected components were completely recalculated. This can be done relatively efficiently using a flood filling algorithm (see https://en.wikipedia.org/wiki/Flood_fill) however it still requires a pass through every single node which can be quite costly on larger graphs.

This class instead builds a much smaller graph that still respects the same connectivity as the original graph. Each node in this hierarchical graph represents a larger number of real nodes that are one single connected component. Take a look at the image below for an example. In the image each color is a separate hierarchical node, and the black connections go between the center of each hierarchical node.

With the hierarchical graph, the connected components can be calculated by flood filling the hierarchical graph instead of the real graph. Then when we need to know which connected component a node belongs to, we look up the connected component of the hierarchical node the node belongs to.

The benefit is not immediately obvious. The above is just a bit more complicated way to accomplish the same thing. However the real benefit comes when updating the graph. When the graph is updated, all hierarchical nodes which contain any node that was affected by the update is removed completely and then once all have been removed new hierarchical nodes are recalculated in their place. Once this is done the connected components of the whole graph can be updated by flood filling only the hierarchical graph. Since the hierarchical graph is vastly smaller than the real graph, this is significantly faster.

So finally using all of this, the connected components of the graph can be recalculated very quickly as the graph is updated. The effect of this grows larger the larger the graph is, and the smaller the graph update is. Making a small update to a 1000x1000 grid graph is on the order of 40 times faster with these optimizations. When scanning a graph or making updates to the whole graph at the same time there is however no speed boost. In fact due to the extra complexity it is a bit slower, however after profiling the extra time seems to be mostly insignificant compared to the rest of the cost of scanning the graph.

See also
Pathfinding.PathUtilities.IsPathPossible
Pathfinding.NNConstraint
Pathfinding.GraphNode.Area

Public Member Functions

 HierarchicalGraph ()
 
uint GetConnectedComponent (int hierarchicalNodeIndex)
 Get the connected component index of a hierarchical node. More...
 
void OnDrawGizmos (Pathfinding.Util.RetainedGizmos gizmos)
 
void RecalculateAll ()
 Recalculate everything from scratch. More...
 
void RecalculateIfNecessary ()
 Recalculate the hierarchical graph and the connected components if any nodes have been marked as dirty. More...
 

Public Attributes

System.Action onConnectedComponentsChanged
 

Package Functions

void AddDirtyNode (GraphNode node)
 
void OnCreatedNode (GraphNode node)
 

Properties

int NumConnectedComponents [get, private set]
 
int version [get, private set]
 

Private Member Functions

void FindHierarchicalNodeChildren (int hierarchicalNode, GraphNode startNode)
 Run a BFS out from a start node and assign up to MaxChildrenPerNode nodes to the specified hierarchical node which are not already assigned to another hierarchical node. More...
 
void FloodFill ()
 Flood fills the graph of hierarchical nodes and assigns the same area ID to all hierarchical nodes that are in the same connected component. More...
 
int GetHierarchicalNodeIndex ()
 
void Grow ()
 
void RemoveHierarchicalNode (int hierarchicalNode, bool removeAdjacentSmallNodes)
 

Private Attributes

int [] areas = new int[0]
 
List< GraphNode > [] children = new List<GraphNode>[0]
 
System.Action< GraphNodeconnectionCallback
 
List< int > [] connections = new List<int>[0]
 
List< GraphNodecurrentChildren = null
 
List< int > currentConnections = null
 
int currentHierarchicalNodeIndex
 
byte [] dirty = new byte[0]
 
GraphNode [] dirtyNodes = new GraphNode[128]
 
Stack< int > freeNodeIndices = new Stack<int>()
 
int gizmoVersion = 0
 
const int MaxChildrenPerNode = Tiling * Tiling
 
const int MinChildrenPerNode = MaxChildrenPerNode/2
 
int numDirtyNodes = 0
 
Queue< GraphNodetemporaryQueue = new Queue<GraphNode>()
 
Stack< int > temporaryStack = new Stack<int>()
 
const int Tiling = 16
 

Constructor & Destructor Documentation

◆ HierarchicalGraph()

Member Function Documentation

◆ AddDirtyNode()

void AddDirtyNode ( GraphNode  node)
package

◆ FindHierarchicalNodeChildren()

void FindHierarchicalNodeChildren ( int  hierarchicalNode,
GraphNode  startNode 
)
private

Run a BFS out from a start node and assign up to MaxChildrenPerNode nodes to the specified hierarchical node which are not already assigned to another hierarchical node.

◆ FloodFill()

void FloodFill ( )
private

Flood fills the graph of hierarchical nodes and assigns the same area ID to all hierarchical nodes that are in the same connected component.

◆ GetConnectedComponent()

uint GetConnectedComponent ( int  hierarchicalNodeIndex)

Get the connected component index of a hierarchical node.

◆ GetHierarchicalNodeIndex()

int GetHierarchicalNodeIndex ( )
private

◆ Grow()

void Grow ( )
private

◆ OnCreatedNode()

void OnCreatedNode ( GraphNode  node)
package

◆ OnDrawGizmos()

void OnDrawGizmos ( Pathfinding.Util.RetainedGizmos  gizmos)

◆ RecalculateAll()

void RecalculateAll ( )

Recalculate everything from scratch.

This is primarily to be used for legacy code for compatibility reasons, not for any new code.

See also
RecalculateIfNecessary

◆ RecalculateIfNecessary()

void RecalculateIfNecessary ( )

Recalculate the hierarchical graph and the connected components if any nodes have been marked as dirty.

◆ RemoveHierarchicalNode()

void RemoveHierarchicalNode ( int  hierarchicalNode,
bool  removeAdjacentSmallNodes 
)
private

Member Data Documentation

◆ areas

int [] areas = new int[0]
private

◆ children

List<GraphNode> [] children = new List<GraphNode>[0]
private

◆ connectionCallback

System.Action<GraphNode> connectionCallback
private

◆ connections

List<int> [] connections = new List<int>[0]
private

◆ currentChildren

List<GraphNode> currentChildren = null
private

◆ currentConnections

List<int> currentConnections = null
private

◆ currentHierarchicalNodeIndex

int currentHierarchicalNodeIndex
private

◆ dirty

byte [] dirty = new byte[0]
private

◆ dirtyNodes

GraphNode [] dirtyNodes = new GraphNode[128]
private

◆ freeNodeIndices

Stack<int> freeNodeIndices = new Stack<int>()
private

◆ gizmoVersion

int gizmoVersion = 0
private

◆ MaxChildrenPerNode

const int MaxChildrenPerNode = Tiling * Tiling
private

◆ MinChildrenPerNode

const int MinChildrenPerNode = MaxChildrenPerNode/2
private

◆ numDirtyNodes

int numDirtyNodes = 0
private

◆ onConnectedComponentsChanged

System.Action onConnectedComponentsChanged

◆ temporaryQueue

Queue<GraphNode> temporaryQueue = new Queue<GraphNode>()
private

◆ temporaryStack

Stack<int> temporaryStack = new Stack<int>()
private

◆ Tiling

const int Tiling = 16
private

Property Documentation

◆ NumConnectedComponents

int NumConnectedComponents
getprivate set

◆ version

int version
getprivate set

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