A* Pathfinding Project  4.1.13
The A* Pathfinding Project for Unity 3D
GraphNode Class Referenceabstract

Base class for all nodes. More...

Detailed Description

Base class for all nodes.

Public Member Functions

abstract void AddConnection (GraphNode node, uint cost)
 
abstract void ClearConnections (bool alsoReverse)
 Remove all connections from this node. More...
 
virtual bool ContainsConnection (GraphNode node)
 Checks if this node has a connection to the specified node. More...
 
virtual void DeserializeNode (GraphSerializationContext ctx)
 Deserializes node data (for example when loading graphs from file). More...
 
virtual void DeserializeReferences (GraphSerializationContext ctx)
 Used to deserialize references to other nodes e.g connections. More...
 
virtual void FloodFill (Stack< GraphNode > stack, uint region)
 Internal method to run a flood fill in order to recalculate the Area property. More...
 
abstract void GetConnections (System.Action< GraphNode > action)
 Calls the delegate with all connections from this node. More...
 
abstract void GetConnections (System.Action< Connection > action)
 Calls the delegate with all connections and respective costs from this node. More...
 
virtual int GetGizmoHashCode ()
 Hash code used for checking if the gizmos need to be updated. More...
 
virtual bool GetPortal (GraphNode other, List< Vector3 > left, List< Vector3 > right, bool backwards)
 Add a portal from this node to the specified node. More...
 
abstract void Open (Path path, PathNode pathNode, PathHandler handler)
 Open the node. More...
 
virtual void OpenCooperative (CooperativeABPath path, PathNodeCooperative pathNode, CooperativePathHandler handler)
 Open the node cooperatively. More...
 
virtual Vector3 RandomPointOnSurface ()
 A random point on the surface of the node. More...
 
virtual void RecalculateConnectionCosts ()
 Recalculates all connection costs from this node. More...
 
abstract void RemoveConnection (GraphNode node)
 
virtual void SerializeNode (GraphSerializationContext ctx)
 Serializes node data (for example when saving graphs to file). More...
 
virtual void SerializeReferences (GraphSerializationContext ctx)
 Used to serialize references to other nodes e.g connections. More...
 
virtual float SurfaceArea ()
 The surface area of the node in square world units. More...
 
virtual void UpdateRecursiveG (Path path, PathNode pathNode, PathHandler handler)
 Internal method to update the G score. More...
 

Public Attributes

const uint MaxAreaIndex = FlagsAreaMask >> FlagsAreaOffset
 
const uint MaxGraphIndex = FlagsGraphMask >> FlagsGraphOffset
 Max number of graphs-1. More...
 
Int3 position
 Position of the node in world space. More...
 

Protected Member Functions

 GraphNode (AstarPath astar)
 Constructor for a graph node. More...
 

Protected Attributes

uint flags
 Bitpacked field holding several pieces of data. More...
 

Package Functions

void Destroy ()
 Destroys the node. More...
 

Properties

uint Area [get, set]
 Connected component that contains the node. More...
 
bool Destroyed [get]
 
uint Flags [get, set]
 Holds various bitpacked variables. More...
 
NavGraph Graph [get]
 Graph which this node belongs to. More...
 
uint GraphIndex [get, set]
 Graph which contains this node. More...
 
int NodeIndex [get, private set]
 Internal unique index. More...
 
uint Penalty [get, set]
 Penalty cost for walking on this node. More...
 
uint Tag [get, set]
 Node tag. More...
 
bool TemporaryFlag1 [get, set]
 Temporary flag for internal purposes. More...
 
bool TemporaryFlag2 [get, set]
 Temporary flag for internal purposes. More...
 
bool Walkable [get, set]
 True if the node can be traversed. More...
 

Private Attributes

const int DestroyedNodeIndex = NodeIndexMask - 1
 
const uint FlagsAreaMask = (131072-1) << FlagsAreaOffset
 Mask of area bits. More...
 
const int FlagsAreaOffset = 1
 Start of area bits. More...
 
const uint FlagsGraphMask = (256u-1) << FlagsGraphOffset
 Mask of graph index bits. More...
 
const int FlagsGraphOffset = 24
 Start of graph index bits. More...
 
const uint FlagsTagMask = (32-1) << FlagsTagOffset
 Mask of tag bits. More...
 
const int FlagsTagOffset = 19
 Start of tag bits. More...
 
const uint FlagsWalkableMask = 1 << FlagsWalkableOffset
 Mask of the walkable bit. More...
 
const int FlagsWalkableOffset = 0
 Position of the walkable bit. More...
 
int nodeIndex
 Internal unique index. More...
 
const int NodeIndexMask = 0xFFFFFFF
 
uint penalty
 Penalty cost for walking on this node. More...
 
const int TemporaryFlag1Mask = 0x10000000
 
const int TemporaryFlag2Mask = 0x20000000
 

Constructor & Destructor Documentation

◆ GraphNode()

GraphNode ( AstarPath  astar)
protected

Constructor for a graph node.

Member Function Documentation

◆ AddConnection()

abstract void AddConnection ( GraphNode  node,
uint  cost 
)
pure virtual

Implemented in MeshNode, GridNodeBase, and PointNode.

◆ ClearConnections()

abstract void ClearConnections ( bool  alsoReverse)
pure virtual

Remove all connections from this node.

Parameters
alsoReverseif true, neighbours will be requested to remove connections to this node.

Implemented in LevelGridNode, MeshNode, GridNodeBase, GridNode, and PointNode.

◆ ContainsConnection()

virtual bool ContainsConnection ( GraphNode  node)
virtual

Checks if this node has a connection to the specified node.

Reimplemented in MeshNode, GridNodeBase, and PointNode.

◆ DeserializeNode()

virtual void DeserializeNode ( GraphSerializationContext  ctx)
virtual

Deserializes node data (for example when loading graphs from file).

See also
SerializeNode

Reimplemented in LevelGridNode, GridNode, TriangleMeshNode, and PointNode.

◆ DeserializeReferences()

virtual void DeserializeReferences ( GraphSerializationContext  ctx)
virtual

Used to deserialize references to other nodes e.g connections.

Use the GraphSerializationContext.GetNodeIdentifier and GraphSerializationContext.GetNodeFromIdentifier methods for serialization and deserialization respectively.

Nodes must override this method and serialize their connections. Graph generators do not need to call this method, it will be called automatically on all nodes at the correct time by the serializer.

Reimplemented in MeshNode, GridNodeBase, and PointNode.

◆ Destroy()

void Destroy ( )
package

Destroys the node.

Cleans up any temporary pathfinding data used for this node. The graph is responsible for calling this method on nodes when they are destroyed, including when the whole graph is destoyed. Otherwise memory leaks might present themselves.

Once called the Destroyed property will return true and subsequent calls to this method will not do anything.

Note
Assumes the current active AstarPath instance is the same one that created this node.
Warning
Should only be called by graph classes on their own nodes

◆ FloodFill()

virtual void FloodFill ( Stack< GraphNode stack,
uint  region 
)
virtual

Internal method to run a flood fill in order to recalculate the Area property.

Reimplemented in LevelGridNode, MeshNode, and GridNode.

◆ GetConnections() [1/2]

abstract void GetConnections ( System.Action< GraphNode action)
pure virtual

Calls the delegate with all connections from this node.

node.GetConnections(connectedTo => {
Debug.DrawLine((Vector3)node.position, (Vector3)connectedTo.position, Color.red);
});

You can add all connected nodes to a list like this

var connections = new List<GraphNode>();
node.GetConnections(connections.Add);

Implemented in LevelGridNode, MeshNode, GridNodeBase, GridNode, and PointNode.

◆ GetConnections() [2/2]

abstract void GetConnections ( System.Action< Connection action)
pure virtual

Calls the delegate with all connections and respective costs from this node.

Implemented in LevelGridNode, MeshNode, TriangleMeshNode, GridNodeBase, GridNode, and PointNode.

◆ GetGizmoHashCode()

virtual int GetGizmoHashCode ( )
virtual

Hash code used for checking if the gizmos need to be updated.

Will change when the gizmos for the node might change.

Reimplemented in LevelGridNode, MeshNode, PointNode, and GridNodeBase.

◆ GetPortal()

virtual bool GetPortal ( GraphNode  other,
List< Vector3 >  left,
List< Vector3 >  right,
bool  backwards 
)
virtual

Add a portal from this node to the specified node.

This function should add a portal to the left and right lists which is connecting the two nodes (this and other).

Parameters
otherThe node which is on the other side of the portal (strictly speaking it does not actually have to be on the other side of the portal though).
leftList of portal points on the left side of the funnel
rightList of portal points on the right side of the funnel
backwardsIf this is true, the call was made on a node with the other node as the node before this one in the path. In this case you may choose to do nothing since a similar call will be made to the other node with this node referenced as other (but then with backwards = true). You do not have to care about switching the left and right lists, that is done for you already.
Returns
True if the call was deemed successful. False if some unknown case was encountered and no portal could be added. If both calls to node1.GetPortal (node2,...) and node2.GetPortal (node1,...) return false, the funnel modifier will fall back to adding to the path the positions of the node.

The default implementation simply returns false.

This function may add more than one portal if necessary.

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

Reimplemented in LevelGridNode, GridNode, and NodeLink3Node.

◆ Open()

abstract void Open ( Path  path,
PathNode  pathNode,
PathHandler  handler 
)
pure virtual

Open the node.

Adds all neighbours of this node to the open list.

See also
https://en.wikipedia.org/wiki/A*_search_algorithm

Implemented in LevelGridNode, GridNode, TriangleMeshNode, GridNodeBase, and PointNode.

◆ OpenCooperative()

virtual void OpenCooperative ( CooperativeABPath  path,
PathNodeCooperative  pathNode,
CooperativePathHandler  handler 
)
virtual

Open the node cooperatively.

Adds all neighbours of this node to the open list.

See also
https://en.wikipedia.org/wiki/A*_search_algorithm

◆ RandomPointOnSurface()

virtual Vector3 RandomPointOnSurface ( )
virtual

A random point on the surface of the node.

For point nodes and other nodes which do not have a surface, this will always return the position of the node.

Reimplemented in TriangleMeshNode, and GridNodeBase.

◆ RecalculateConnectionCosts()

virtual void RecalculateConnectionCosts ( )
virtual

Recalculates all connection costs from this node.

Depending on the node type, this may or may not be supported. Nothing will be done if the operation is not supported

Todo:
Use interface?

◆ RemoveConnection()

abstract void RemoveConnection ( GraphNode  node)
pure virtual

Implemented in MeshNode, GridNodeBase, and PointNode.

◆ SerializeNode()

virtual void SerializeNode ( GraphSerializationContext  ctx)
virtual

Serializes node data (for example when saving graphs to file).

See also
DeserializeNode

Reimplemented in LevelGridNode, GridNode, TriangleMeshNode, and PointNode.

◆ SerializeReferences()

virtual void SerializeReferences ( GraphSerializationContext  ctx)
virtual

Used to serialize references to other nodes e.g connections.

Use the GraphSerializationContext.GetNodeIdentifier and GraphSerializationContext.GetNodeFromIdentifier methods for serialization and deserialization respectively.

Nodes must override this method and serialize their connections. Graph generators do not need to call this method, it will be called automatically on all nodes at the correct time by the serializer.

Reimplemented in MeshNode, GridNodeBase, and PointNode.

◆ SurfaceArea()

virtual float SurfaceArea ( )
virtual

The surface area of the node in square world units.

Reimplemented in TriangleMeshNode, and GridNodeBase.

◆ UpdateRecursiveG()

virtual void UpdateRecursiveG ( Path  path,
PathNode  pathNode,
PathHandler  handler 
)
virtual

Internal method to update the G score.

Internal method to update the G score for this node and all children of it in the search graph

Reimplemented in LevelGridNode, MeshNode, GridNode, TriangleMeshNode, GridNodeBase, and PointNode.

Member Data Documentation

◆ DestroyedNodeIndex

const int DestroyedNodeIndex = NodeIndexMask - 1
private

◆ flags

uint flags
protected

Bitpacked field holding several pieces of data.

See also
Walkable
Area
GraphIndex
Tag

◆ FlagsAreaMask

const uint FlagsAreaMask = (131072-1) << FlagsAreaOffset
private

Mask of area bits.

See also
Area

◆ FlagsAreaOffset

const int FlagsAreaOffset = 1
private

Start of area bits.

See also
Area

◆ FlagsGraphMask

const uint FlagsGraphMask = (256u-1) << FlagsGraphOffset
private

Mask of graph index bits.

See also
GraphIndex

◆ FlagsGraphOffset

const int FlagsGraphOffset = 24
private

Start of graph index bits.

See also
GraphIndex

◆ FlagsTagMask

const uint FlagsTagMask = (32-1) << FlagsTagOffset
private

Mask of tag bits.

See also
Tag

◆ FlagsTagOffset

const int FlagsTagOffset = 19
private

Start of tag bits.

See also
Tag

◆ FlagsWalkableMask

const uint FlagsWalkableMask = 1 << FlagsWalkableOffset
private

Mask of the walkable bit.

See also
Walkable

◆ FlagsWalkableOffset

const int FlagsWalkableOffset = 0
private

Position of the walkable bit.

See also
Walkable

◆ MaxAreaIndex

const uint MaxAreaIndex = FlagsAreaMask >> FlagsAreaOffset

◆ MaxGraphIndex

const uint MaxGraphIndex = FlagsGraphMask >> FlagsGraphOffset

Max number of graphs-1.

◆ nodeIndex

int nodeIndex
private

Internal unique index.

Also stores some bitpacked values such as TemporaryFlag1 and TemporaryFlag2. This index is not necessarily correlated with e.g the position of the node in the graph.

Will be unique as long as the node is active. When the node is destroyed, the index may be reused by other nodes.

◆ NodeIndexMask

const int NodeIndexMask = 0xFFFFFFF
private

◆ penalty

uint penalty
private

Penalty cost for walking on this node.

This can be used to make it harder/slower to walk over certain nodes.

A penalty of 1000 (Int3.Precision) corresponds to the cost of walking one world unit.

◆ position

Int3 position

Position of the node in world space.

Note
The position is stored as an Int3, not a Vector3. You can convert an Int3 to a Vector3 using an explicit conversion.
var v3 = (Vector3)node.position;
and vice versa
node.position = (Int3)new Vector3(1,2,3);

◆ TemporaryFlag1Mask

const int TemporaryFlag1Mask = 0x10000000
private

◆ TemporaryFlag2Mask

const int TemporaryFlag2Mask = 0x20000000
private

Property Documentation

◆ Area

uint Area
getset

Connected component that contains the node.

This is visualized in the scene view as differently colored nodes (if the graph coloring mode is set to 'Areas'). Each area represents a set of nodes such that there is no valid path between nodes of different colors.

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

For performance reasons the graph is split up into several connected components using a flood fill. This is done so that if a path request is made between two nodes for which there is no possible path then it should be able to abort quickly instead of having to search the whole graph (which can be very expensive). It is also used to better be able to search for target nodes for paths (it will try to find the closest target node that can be reached instead of just the closest node to the target point).

When a graph update is done, this value usually needs to be updated. When using a GraphUpdateObject, that is done automatically, but for other kinds of updates, you may need to call some functions to update it (see docs on updating graphs).

See also
graph-updates
Tag

◆ Destroyed

bool Destroyed
get

◆ Flags

uint Flags
getset

Holds various bitpacked variables.

See also
Walkable
Area
GraphIndex
Tag

◆ Graph

NavGraph Graph
get

Graph which this node belongs to.

If you know the node belongs to a particular graph type, you can cast it to that type:

GraphNode node = ...;
GridGraph graph = node.Graph as GridGraph;

Will return null if the node has been destroyed.

◆ GraphIndex

uint GraphIndex
getset

Graph which contains this node.

See also
Pathfinding.AstarData.graphs

◆ NodeIndex

int NodeIndex
getprivate set

Internal unique index.

This index is not necessarily correlated with e.g the position of the node in the graph.

Will be unique as long as the node is active. When the node is destroyed, the index may be reused by other nodes.

◆ Penalty

uint Penalty
getset

Penalty cost for walking on this node.

This can be used to make it harder/slower to walk over certain areas. A cost of 1000 (Int3.Precision) corresponds to the cost of moving 1 world unit.

◆ Tag

uint Tag
getset

Node tag.

See also
Working with tags

◆ TemporaryFlag1

bool TemporaryFlag1
getsetpackage

Temporary flag for internal purposes.

May only be used in the Unity thread. Must be reset to false after every use.

◆ TemporaryFlag2

bool TemporaryFlag2
getsetpackage

Temporary flag for internal purposes.

May only be used in the Unity thread. Must be reset to false after every use.

◆ Walkable

bool Walkable
getset

True if the node can be traversed.


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