A* Pathfinding Project  4.1.10
The A* Pathfinding Project for Unity 3D
LayerGridGraph Class Reference

Grid Graph, supports layered worlds. More...

Detailed Description

Grid Graph, supports layered worlds.

The GridGraph is great in many ways, reliable, easily configured and updatable during runtime. But it lacks support for worlds which have multiple layers, such as a building with multiple floors.
That's where this graph type comes in. It supports basically the same stuff as the grid graph, but also multiple layers. It uses a more memory, and is probably a bit slower.

Note
Does not support 8 connections per node, only 4.

A* Pro Feature:
This is an A* Pathfinding Project Pro feature only. This function/class/variable might not exist in the Free version of the A* Pathfinding Project or the functionality might be limited
The Pro version can be bought here

Public Member Functions

void CalculateConnections (LevelGridNode[] nodes, LevelGridNode node, int x, int z, int layerIndex)
 Calculates the grid connections for a single node. More...
 
override void CalculateConnections (GridNodeBase baseNode)
 Calculates the grid connections for a single node. More...
 
void CalculateConnections (int x, int z, int layerIndex, LevelGridNode node)
 Calculates the layered grid graph connections for a single node. More...
 
override void CalculateConnections (int x, int z)
 Calculates connections for all nodes in a cell (there may be multiple layers of nodes) More...
 
void CalculateConnections (int x, int z, int layerIndex)
 Calculates the layered grid graph connections for a single node. More...
 
override int CountNodes ()
 Number of nodes in the graph. More...
 
override NNInfoInternal GetNearest (Vector3 position, NNConstraint constraint, GraphNode hint)
 Returns the nearest node to a position using the specified NNConstraint. More...
 
override NNInfoInternal GetNearestForce (Vector3 position, NNConstraint constraint)
 Returns the nearest node to a position using the specified constraint . More...
 
override GridNodeBase GetNode (int x, int z)
 Node in the specified cell in the first layer. More...
 
GridNodeBase GetNode (int x, int z, int layer)
 Node in the specified cell. More...
 
override void GetNodes (System.Action< GraphNode > action)
 Calls a delegate with all nodes in the graph. More...
 
override List< GraphNodeGetNodesInRegion (IntRect rect)
 Get all nodes in a rectangle. More...
 
override int GetNodesInRegion (IntRect rect, GridNodeBase[] buffer)
 Get all nodes in a rectangle. More...
 
override void RecalculateCell (int x, int z, bool resetPenalties=true, bool resetTags=true)
 Recalculates single cell. More...
 
- Public Member Functions inherited from GridGraph
 GridGraph ()
 
virtual void CalculateConnections (GridNode[] nodes, int x, int z, GridNode node)
 Calculates the grid connections for a single node. More...
 
virtual void CalculateConnections (int x, int z, GridNode node)
 Calculates the grid connections for a single node. More...
 
void CalculateConnectionsForCellAndNeighbours (int x, int z)
 Calculates the grid connections for a cell as well as its neighbours. More...
 
GraphTransform CalculateTransform ()
 Returns a new transform which transforms graph space to world space. More...
 
bool CheckConnection (GridNode node, int dir)
 Returns if node is connected to it's neighbour in the specified direction. More...
 
virtual void ErodeWalkableArea ()
 Erodes the walkable area. More...
 
void ErodeWalkableArea (int xmin, int zmin, int xmax, int zmax)
 Erodes the walkable area. More...
 
void GenerateMatrix ()
 Generates the matrix used for translating nodes from grid coordinates to world coordinates. More...
 
uint GetConnectionCost (int dir)
 
GridNode GetNodeConnection (GridNode node, int dir)
 
List< GraphNodeGetNodesInArea (Bounds bounds)
 
List< GraphNodeGetNodesInArea (GraphUpdateShape shape)
 
List< GraphNodeGetNodesInArea (Bounds bounds, GraphUpdateShape shape)
 
List< GraphNodeGetNodesInRegion (Bounds bounds)
 All nodes inside the bounding box. More...
 
List< GraphNodeGetNodesInRegion (GraphUpdateShape shape)
 All nodes inside the shape. More...
 
Int3 GraphPointToWorld (int x, int z, float height)
 Transform a point in graph space to world space. More...
 
bool HasNodeConnection (GridNode node, int dir)
 
bool HasNodeConnection (int index, int x, int z, int dir)
 
virtual bool IsValidConnection (GridNodeBase node1, GridNodeBase node2)
 Returns true if a connection between the adjacent nodes n1 and n2 is valid. More...
 
bool Linecast (Vector3 from, Vector3 to)
 Returns if there is an obstacle between from and to on the graph. More...
 
bool Linecast (Vector3 from, Vector3 to, GraphNode hint)
 Returns if there is an obstacle between from and to on the graph. More...
 
bool Linecast (Vector3 from, Vector3 to, GraphNode hint, out GraphHitInfo hit)
 Returns if there is an obstacle between from and to on the graph. More...
 
bool Linecast (Vector3 from, Vector3 to, GraphNode hint, out GraphHitInfo hit, List< GraphNode > trace)
 Returns if there is an obstacle between from and to on the graph. More...
 
bool Linecast (GridNodeBase fromNode, GridNodeBase toNode)
 Returns if there is an obstacle between the two nodes on the graph. More...
 
override void OnDrawGizmos (RetainedGizmos gizmos, bool drawNodes)
 Draw gizmos for the graph. More...
 
override void RelocateNodes (Matrix4x4 deltaMatrix)
 Moves the nodes in this graph. More...
 
void RelocateNodes (Vector3 center, Quaternion rotation, float nodeSize, float aspectRatio=1, float isometricAngle=0)
 Relocate the grid graph using new settings. More...
 
void SetDimensions (int width, int depth, float nodeSize)
 Updates unclampedSize from width, depth and nodeSize values. More...
 
void SetNodeConnection (GridNode node, int dir, bool value)
 
void SetNodeConnection (int index, int x, int z, int dir, bool value)
 Set if connection in the specified direction should be enabled. More...
 
virtual void SetUpOffsetsAndCosts ()
 Sets up neighbourOffsets with the current settings. More...
 
bool SnappedLinecast (Vector3 from, Vector3 to, GraphNode hint, out GraphHitInfo hit)
 Returns if there is an obstacle between from and to on the graph. More...
 
virtual void UpdateNodePositionCollision (GridNode node, int x, int z, bool resetPenalty=true)
 Updates position, walkability and penalty for the node. More...
 
void UpdateSizeFromWidthDepth ()
 Updates unclampedSize from width, depth and nodeSize values. More...
 
void UpdateTransform ()
 Updates the transform field which transforms graph space to world space. More...
 
- Public Member Functions inherited from NavGraph
NNInfoInternal GetNearest (Vector3 position)
 Returns the nearest node to a position. More...
 
NNInfoInternal GetNearest (Vector3 position, NNConstraint constraint)
 Returns the nearest node to a position using the specified NNConstraint. More...
 
void GetNodes (System.Func< GraphNode, bool > action)
 Calls a delegate with all nodes in the graph until the delegate returns false. More...
 
void RelocateNodes (Matrix4x4 oldMatrix, Matrix4x4 newMatrix)
 Moves nodes in this graph. More...
 
void Scan ()
 Scan the graph. More...
 
void ScanGraph ()
 Scan the graph. More...
 
void SetMatrix (Matrix4x4 m)
 Use to set both matrix and inverseMatrix at the same time. More...
 

Static Public Member Functions

static bool CheckConnection (LevelGridNode node, int dir)
 Returns if node is connected to it's neighbour in the specified direction. More...
 
- Static Public Member Functions inherited from GridGraph
static void CalculateConnections (GridNode node)
 Calculates the grid connections for a single node. More...
 

Public Attributes

float characterHeight = 0.4F
 Nodes with a short distance to the node above it will be set unwalkable. More...
 
float mergeSpanRange = 0.5F
 If two layered nodes are too close, they will be merged. More...
 
new LevelGridNode [] nodes
 All nodes in this graph. More...
 
- Public Attributes inherited from GridGraph
const int getNearestForceOverlap = 2
 In GetNearestForce, determines how far to search after a valid node has been found. More...
 
readonly uint [] neighbourCosts = new uint[8]
 Costs to neighbour nodes. More...
 
readonly int [] neighbourOffsets = new int[8]
 Index offset to get neighbour nodes. More...
 
readonly int [] neighbourXOffsets = new int[8]
 Offsets in the X direction for neighbour nodes. More...
 
readonly int [] neighbourZOffsets = new int[8]
 Offsets in the Z direction for neighbour nodes. More...
 
GridNode [] nodes
 All nodes in this graph. More...
 
InspectorGridMode inspectorGridMode = InspectorGridMode.Grid
 Determines the layout of the grid graph inspector in the Unity Editor. More...
 
int width
 Width of the grid in nodes. More...
 
int depth
 Depth (height) of the grid in nodes. More...
 
float aspectRatio = 1F
 Scaling of the graph along the X axis. More...
 
float isometricAngle
 Angle to use for the isometric projection. More...
 
bool uniformEdgeCosts
 If true, all edge costs will be set to the same value. More...
 
Vector3 rotation
 Rotation of the grid in degrees. More...
 
Vector3 center
 Center point of the grid. More...
 
Vector2 unclampedSize
 Size of the grid. More...
 
float nodeSize = 1
 Size of one node in world units. More...
 
GraphCollision collision
 Settings on how to check for walkability and height. More...
 
float maxClimb = 0.4F
 The max position difference between two nodes to enable a connection. More...
 
float maxSlope = 90
 The max slope in degrees for a node to be walkable. More...
 
int erodeIterations
 Erosion of the graph. More...
 
bool erosionUseTags
 Use tags instead of walkability for erosion. More...
 
int erosionFirstTag = 1
 Tag to start from when using tags for erosion. More...
 
NumNeighbours neighbours = NumNeighbours.Eight
 Number of neighbours for each node. More...
 
bool cutCorners = true
 If disabled, will not cut corners on obstacles. More...
 
float penaltyPositionOffset
 Offset for the position when calculating penalty. More...
 
bool penaltyPosition
 Use position (y-coordinate) to calculate penalty. More...
 
float penaltyPositionFactor = 1F
 Scale factor for penalty when calculating from position. More...
 
bool penaltyAngle
 
float penaltyAngleFactor = 100F
 How much penalty is applied depending on the slope of the terrain. More...
 
float penaltyAnglePower = 1
 How much extra to penalize very steep angles. More...
 
bool useJumpPointSearch
 Use jump point search to speed up pathfinding. More...
 
bool showMeshOutline = true
 Show an outline of the grid nodes in the Unity Editor. More...
 
bool showNodeConnections
 Show the connections between the grid nodes in the Unity Editor. More...
 
bool showMeshSurface = true
 Show the surface of the graph. More...
 
TextureData textureData = new TextureData()
 Holds settings for using a texture as source for a grid graph. More...
 
- Public Attributes inherited from NavGraph
AstarPath active
 Reference to the AstarPath object in the scene. More...
 
bool drawGizmos = true
 Enable to draw gizmos in the Unity scene view. More...
 
uint graphIndex
 Index of the graph, used for identification purposes. More...
 
Guid guid
 Used as an ID of the graph, considered to be unique. More...
 
bool infoScreenOpen
 Used in the editor to check if the info screen is open. More...
 
uint initialPenalty
 Default penalty to apply to all nodes. More...
 
Matrix4x4 inverseMatrix = Matrix4x4.identity
 Inverse of matrix. More...
 
Matrix4x4 matrix = Matrix4x4.identity
 A matrix for translating/rotating/scaling the graph. More...
 
string name
 Name of the graph. More...
 
bool open
 Is the graph open in the editor. More...
 

Protected Member Functions

override void DeserializeExtraInfo (GraphSerializationContext ctx)
 Deserializes graph type specific node data. More...
 
override bool ErosionAnyFalseConnections (GraphNode baseNode)
 True if the node has any blocked connections. More...
 
override List< GraphNodeGetNodesInRegion (Bounds b, GraphUpdateShape shape)
 All nodes inside the shape or if null, the bounding box. More...
 
override void OnDestroy ()
 This function will be called when this graph is destroyed. More...
 
override void PostDeserialization (GraphSerializationContext ctx)
 Called after all deserialization has been done for all graphs. More...
 
override IEnumerable< ProgressScanInternal ()
 Internal method to scan the graph. More...
 
override void SerializeExtraInfo (GraphSerializationContext ctx)
 Serializes graph type specific node data. More...
 
- Protected Member Functions inherited from GridGraph
void CalculateAffectedRegions (GraphUpdateObject o, out IntRect originalRect, out IntRect affectRect, out IntRect physicsRect, out bool willChangeWalkability, out int erosion)
 
bool ClipLineSegmentToBounds (Vector3 a, Vector3 b, out Vector3 outA, out Vector3 outB)
 Clips a line segment in graph space to the graph bounds. More...
 
override void DeserializeSettingsCompatibility (GraphSerializationContext ctx)
 An old format for serializing settings. More...
 
override void DestroyAllNodes ()
 Destroys all nodes in the graph. More...
 
IntRect GetRectFromBounds (Bounds bounds)
 A rect with all nodes that the bounds could touch. More...
 
- Protected Member Functions inherited from NavGraph
void DrawUnwalkableNodes (float size)
 

Package Attributes

int lastScannedDepth
 
int lastScannedWidth
 
int layerCount
 Number of layers. More...
 

Properties

override int LayerCount [get]
 
override bool uniformWidthDepthGrid [get]
 
- Properties inherited from GridGraph
int Depth [get, set]
 
virtual int LayerCount [get]
 Number of layers in the graph. More...
 
Vector2 size [get, protected set]
 Size of the grid. More...
 
GraphTransform transform [get, private set]
 Determines how the graph transforms graph space to world space. More...
 
virtual bool uniformWidthDepthGrid [get]
 This is placed here so generators inheriting from this one can override it and set it to false. More...
 
int Width [get, set]
 
bool useRaycastNormal [get]
 Use heigh raycasting normal for max slope calculation. More...
 
- Properties inherited from NavGraph
bool exists [get]
 True if the graph exists, false if it has been destroyed. More...
 
- Properties inherited from ITransformedGraph
GraphTransform transform [get]
 

Private Member Functions

void AddLayers (int count)
 Increases the capacity of the nodes array to hold more layers. More...
 
LevelGridNode GetNearestNode (Vector3 position, int x, int z, NNConstraint constraint)
 
void RemoveGridGraphFromStatic ()
 
LinkedLevelNode SampleCell (int x, int z)
 
void IUpdatableGraph. UpdateArea (GraphUpdateObject o)
 Updates an area using the specified #GraphUpdateObject. More...
 

Additional Inherited Members

- Static Protected Member Functions inherited from GridGraph
static float CrossMagnitude (Vector2 a, Vector2 b)
 Magnitude of the cross product a x b. More...
 
static long CrossMagnitude (Int2 a, Int2 b)
 Magnitude of the cross product a x b. More...
 
- Static Package Attributes inherited from GridGraph
static readonly int [] hexagonNeighbourIndices = { 0, 1, 5, 2, 3, 7 }
 Which neighbours are going to be used when neighbours=6. More...
 

Member Function Documentation

◆ AddLayers()

void AddLayers ( int  count)
private

Increases the capacity of the nodes array to hold more layers.

◆ CalculateConnections() [1/5]

void CalculateConnections ( LevelGridNode []  nodes,
LevelGridNode  node,
int  x,
int  z,
int  layerIndex 
)

Calculates the grid connections for a single node.

Deprecated:
CalculateConnections no longer takes a node array, it just uses the one on the graph

◆ CalculateConnections() [2/5]

override void CalculateConnections ( GridNodeBase  node)
virtual

Calculates the grid connections for a single node.

Convenience function, it's slightly faster to use CalculateConnections(int,int) but that will only show when calculating for a large number of nodes. This function will also work for both grid graphs and layered grid graphs.

Reimplemented from GridGraph.

◆ CalculateConnections() [3/5]

void CalculateConnections ( int  x,
int  z,
int  layerIndex,
LevelGridNode  node 
)

Calculates the layered grid graph connections for a single node.

Deprecated:
Use CalculateConnections(x,z,layerIndex) or CalculateConnections(node) instead

◆ CalculateConnections() [4/5]

override void CalculateConnections ( int  x,
int  z 
)
virtual

Calculates connections for all nodes in a cell (there may be multiple layers of nodes)

Reimplemented from GridGraph.

◆ CalculateConnections() [5/5]

void CalculateConnections ( int  x,
int  z,
int  layerIndex 
)

Calculates the layered grid graph connections for a single node.

◆ CheckConnection()

static bool CheckConnection ( LevelGridNode  node,
int  dir 
)
static

Returns if node is connected to it's neighbour in the specified direction.

Deprecated:
Use node.GetConnection instead

◆ CountNodes()

override int CountNodes ( )
virtual

Number of nodes in the graph.

Note that this is, unless the graph type has overriden it, an O(n) operation.

This is an O(1) operation for grid graphs and point graphs. For layered grid graphs it is an O(n) operation.

Reimplemented from GridGraph.

◆ DeserializeExtraInfo()

override void DeserializeExtraInfo ( GraphSerializationContext  ctx)
protectedvirtual

Deserializes graph type specific node data.

See also
SerializeExtraInfo

Reimplemented from GridGraph.

◆ ErosionAnyFalseConnections()

override bool ErosionAnyFalseConnections ( GraphNode  baseNode)
protectedvirtual

True if the node has any blocked connections.

For 4 and 8 neighbours the 4 axis aligned connections will be checked. For 6 neighbours all 6 neighbours will be checked.

Internal method used for erosion.

Reimplemented from GridGraph.

◆ GetNearest()

override NNInfoInternal GetNearest ( Vector3  position,
NNConstraint  constraint,
GraphNode  hint 
)
virtual

Returns the nearest node to a position using the specified NNConstraint.

Parameters
positionThe position to try to find a close node to
hintCan be passed to enable some graph generators to find the nearest node faster.
constraintCan for example tell the function to try to return a walkable node. If you do not get a good node back, consider calling GetNearestForce.

Reimplemented from GridGraph.

◆ GetNearestForce()

override NNInfoInternal GetNearestForce ( Vector3  position,
NNConstraint  constraint 
)
virtual

Returns the nearest node to a position using the specified constraint .

Returns
an NNInfo. This method will only return an empty NNInfo if there are no nodes which comply with the specified constraint.

Reimplemented from GridGraph.

◆ GetNearestNode()

LevelGridNode GetNearestNode ( Vector3  position,
int  x,
int  z,
NNConstraint  constraint 
)
private

◆ GetNode() [1/2]

override GridNodeBase GetNode ( int  x,
int  z 
)
virtual

Node in the specified cell in the first layer.

var gg = AstarPath.active.data.gridGraph;
int x = 5;
int z = 8;
GridNodeBase node = gg.GetNode(x, z);

Reimplemented from GridGraph.

◆ GetNode() [2/2]

GridNodeBase GetNode ( int  x,
int  z,
int  layer 
)

Node in the specified cell.

◆ GetNodes()

override void GetNodes ( System.Action< GraphNode action)
virtual

Calls a delegate with all nodes in the graph.

This is the primary way of iterating through all nodes in a graph.

Do not change the graph structure inside the delegate.

var gg = AstarPath.active.data.gridGraph;
gg.GetNodes(node => {
// Here is a node
Debug.Log("I found a node at position " + (Vector3)node.position);
});

If you want to store all nodes in a list you can do this

var gg = AstarPath.active.data.gridGraph;
List<GraphNode> nodes = new List<GraphNode>();
gg.GetNodes((System.Action<GraphNode>)nodes.Add);

Reimplemented from GridGraph.

◆ GetNodesInRegion() [1/3]

override List<GraphNode> GetNodesInRegion ( Bounds  bounds,
GraphUpdateShape  shape 
)
protectedvirtual

All nodes inside the shape or if null, the bounding box.

If a shape is supplied, it is assumed to be contained inside the bounding box.

See also
GraphUpdateShape.GetBounds

Reimplemented from GridGraph.

◆ GetNodesInRegion() [2/3]

override List<GraphNode> GetNodesInRegion ( IntRect  rect)
virtual

Get all nodes in a rectangle.

Parameters
rectRegion in which to return nodes. It will be clamped to the grid.

Reimplemented from GridGraph.

◆ GetNodesInRegion() [3/3]

override int GetNodesInRegion ( IntRect  rect,
GridNodeBase []  buffer 
)
virtual

Get all nodes in a rectangle.

Parameters
rectRegion in which to return nodes. It will be clamped to the grid.
bufferBuffer in which the nodes will be stored. Should be at least as large as the number of nodes that can exist in that region.
Returns
The number of nodes written to the buffer.

Reimplemented from GridGraph.

◆ OnDestroy()

override void OnDestroy ( )
protectedvirtual

This function will be called when this graph is destroyed.

Reimplemented from GridGraph.

◆ PostDeserialization()

override void PostDeserialization ( GraphSerializationContext  ctx)
protectedvirtual

Called after all deserialization has been done for all graphs.

Can be used to set up more graph data which is not serialized

Reimplemented from GridGraph.

◆ RecalculateCell()

override void RecalculateCell ( int  x,
int  z,
bool  resetPenalties = true,
bool  resetTags = true 
)
virtual

Recalculates single cell.

For a layered grid graph this will recalculate all nodes at a specific (x,z) coordinate in the grid. For grid graphs this will simply recalculate the single node at those coordinates.

Parameters
xX coordinate of the cell
zZ coordinate of the cell
resetPenaltiesIf true, the penalty of the nodes will be reset to the initial value as if the graph had just been scanned.
resetTagsIf true, the penalty will be reset to zero (the default tag).
Note
This must only be called when it is safe to update nodes. For example when scanning the graph or during a graph update.
This will not recalculate any connections as this method is often run for several adjacent nodes at a time. After you have recalculated all the nodes you will have to recalculate the connections for the changed nodes as well as their neighbours.
See also
CalculateConnections

Reimplemented from GridGraph.

◆ RemoveGridGraphFromStatic()

void RemoveGridGraphFromStatic ( )
private

◆ SampleCell()

LinkedLevelNode SampleCell ( int  x,
int  z 
)
private

◆ ScanInternal()

override IEnumerable<Progress> ScanInternal ( )
protectedvirtual

Internal method to scan the graph.

Called from AstarPath.ScanAsync. Override this function to implement custom scanning logic. Progress objects can be yielded to show progress info in the editor and to split up processing over several frames when using async scanning.

Reimplemented from GridGraph.

◆ SerializeExtraInfo()

override void SerializeExtraInfo ( GraphSerializationContext  ctx)
protectedvirtual

Serializes graph type specific node data.

This function can be overriden to serialize extra node information (or graph information for that matter) which cannot be serialized using the standard serialization. Serialize the data in any way you want and return a byte array. When loading, the exact same byte array will be passed to the DeserializeExtraInfo function.
These functions will only be called if node serialization is enabled.

Reimplemented from GridGraph.

◆ UpdateArea()

void IUpdatableGraph. UpdateArea ( GraphUpdateObject  o)
private

Updates an area using the specified #GraphUpdateObject.

Notes to implementators. This function should (in order):

  1. Call o.WillUpdateNode on the GUO for every node it will update, it is important that this is called BEFORE any changes are made to the nodes.
  2. Update walkabilty using special settings such as the usePhysics flag used with the GridGraph.
  3. Call Apply on the GUO for every node which should be updated with the GUO.
  4. Update connectivity info if appropriate (GridGraphs updates connectivity, but most other graphs don't since then the connectivity cannot be recovered later).

Implements IUpdatableGraph.

Member Data Documentation

◆ characterHeight

float characterHeight = 0.4F

Nodes with a short distance to the node above it will be set unwalkable.

◆ lastScannedDepth

int lastScannedDepth
package

◆ lastScannedWidth

int lastScannedWidth
package

◆ layerCount

int layerCount
package

Number of layers.

Warning
Do not modify this variable

◆ mergeSpanRange

float mergeSpanRange = 0.5F

If two layered nodes are too close, they will be merged.

◆ nodes

new LevelGridNode [] nodes

All nodes in this graph.

var gg = AstarPath.active.data.layerGridGraph;
int x = 5;
int z = 8;
int y = 2; // Layer
LevelGridNode node = gg.nodes[y*gg.width*gg.depth + z*gg.width + x];
See also
GetNodes

Property Documentation

◆ LayerCount

override int LayerCount
get

◆ uniformWidthDepthGrid

override bool uniformWidthDepthGrid
get

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