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.

override void	CalculateConnections (GridNodeBase baseNode)
	Calculates the grid connections for a single node.

void	CalculateConnections (int x, int z, int layerIndex, LevelGridNode node)
	Calculates the layered grid graph connections for a single node.

override void	CalculateConnections (int x, int z)
	Calculates connections for all nodes in a cell (there may be multiple layers of nodes)

void	CalculateConnections (int x, int z, int layerIndex)
	Calculates the layered grid graph connections for a single node.

override int	CountNodes ()
	Number of nodes in the graph.

override void	DeserializeExtraInfo (GraphSerializationContext ctx)
	Deserializes graph type specific node data.

override NNInfoInternal	GetNearest (Vector3 position, NNConstraint constraint, GraphNode hint)
	Returns the nearest node to a position using the specified NNConstraint.

override NNInfoInternal	GetNearestForce (Vector3 position, NNConstraint constraint)
	Returns the nearest node to a position using the specified constraint .

override void	GetNodes (System.Action< GraphNode > action)
	Calls a delegate with all nodes in the graph.

override List< GraphNode >	GetNodesInRegion (IntRect rect)
	Get all nodes in a rectangle.

override int	GetNodesInRegion (IntRect rect, GridNodeBase[] buffer)
	Get all nodes in a rectangle.

override void	OnDestroy ()
	This function will be called when this graph is destroyed.

override void	PostDeserialization ()
	Called after all deserialization has been done for all graphs.

override void	RecalculateCell (int x, int z, bool resetPenalties=true, bool resetTags=true)
	Recalculates single cell.

override IEnumerable< Progress >	ScanInternal ()
	Internal method to scan the graph.

override void	SerializeExtraInfo (GraphSerializationContext ctx)
	Serializes graph type specific node data.

new void	UpdateArea (GraphUpdateObject o)

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.

virtual void	CalculateConnections (int x, int z, GridNode node)
	Calculates the grid connections for a single node.

GraphTransform	CalculateTransform ()
	Returns a new transform which transforms graph space to world space.

GraphUpdateThreading	CanUpdateAsync (GraphUpdateObject o)

bool	CheckConnection (GridNode node, int dir)
	Returns if node is connected to it's neighbour in the specified direction.

override void	DeserializeSettingsCompatibility (GraphSerializationContext ctx)
	An old format for serializing settings.

virtual void	ErodeWalkableArea ()
	Erodes the walkable area.

void	ErodeWalkableArea (int xmin, int zmin, int xmax, int zmax)
	Erodes the walkable area.

void	GenerateMatrix ()
	Generates the matrix used for translating nodes from grid coordinates to world coordintes.

uint	GetConnectionCost (int dir)

GridNode	GetNodeConnection (GridNode node, int dir)

List< GraphNode >	GetNodesInArea (Bounds bounds)

List< GraphNode >	GetNodesInArea (GraphUpdateShape shape)

List< GraphNode >	GetNodesInArea (Bounds bounds, GraphUpdateShape shape)

List< GraphNode >	GetNodesInRegion (Bounds bounds)
	All nodes inside the bounding box.

List< GraphNode >	GetNodesInRegion (GraphUpdateShape shape)
	All nodes inside the shape.

Int3	GraphPointToWorld (int x, int z, float height)
	Transform a point in graph space to world space.

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.

bool	Linecast (Vector3 from, Vector3 to)
	Returns if there is an obstacle between from and to on the graph.

bool	Linecast (Vector3 from, Vector3 to, GraphNode hint)
	Returns if there is an obstacle between from and to on the graph.

bool	Linecast (Vector3 from, Vector3 to, GraphNode hint, out GraphHitInfo hit)
	Returns if there is an obstacle between from and to on the graph.

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.

override void	OnDrawGizmos (RetainedGizmos gizmos, bool drawNodes)
	Draw gizmos for the graph.

void	OnPostScan (AstarPath script)
	Auto links grid graphs together.

override void	RelocateNodes (Matrix4x4 deltaMatrix)
	Moves the nodes in this graph.

void	RelocateNodes (Vector3 center, Quaternion rotation, float nodeSize, float aspectRatio=1, float isometricAngle=0)
	Relocate the grid graph using new settings.

void	SetDimensions (int width, int depth, float nodeSize)
	Updates unclampedSize from width, depth and nodeSize values.

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.

virtual void	SetUpOffsetsAndCosts ()
	Sets up neighbourOffsets with the current settings.

bool	SnappedLinecast (Vector3 from, Vector3 to, GraphNode hint, out GraphHitInfo hit)
	Returns if there is an obstacle between from and to on the graph.

void	UpdateArea (GraphUpdateObject o)
	Internal function to update an area of the graph.

void	UpdateAreaInit (GraphUpdateObject o)

void	UpdateAreaPost (GraphUpdateObject o)

virtual void	UpdateNodePositionCollision (GridNode node, int x, int z, bool resetPenalty=true)
	Updates position, walkability and penalty for the node.

void	UpdateSizeFromWidthDepth ()
	Updates unclampedSize from width, depth and nodeSize values.

void	UpdateTransform ()
	Updates the transform field which transforms graph space to world space.

Public Member Functions inherited from NavGraph
NNInfoInternal	GetNearest (Vector3 position)
	Returns the nearest node to a position using the default NNConstraint.

NNInfoInternal	GetNearest (Vector3 position, NNConstraint constraint)
	Returns the nearest node to a position using the specified NNConstraint.

void	GetNodes (System.Func< GraphNode, bool > action)
	Calls a delegate with all nodes in the graph until the delegate returns false.

void	RelocateNodes (Matrix4x4 oldMatrix, Matrix4x4 newMatrix)
	Moves nodes in this graph.

void	Scan ()

void	ScanGraph ()
	Partially scan the graph.

void	SetMatrix (Matrix4x4 m)
	Use to set both matrix and inverseMatrix at the same time.

Public Member Functions inherited from IUpdatableGraph
GraphUpdateThreading	CanUpdateAsync (GraphUpdateObject o)

void	UpdateArea (GraphUpdateObject o)
	Updates an area using the specified GraphUpdateObject.

void	UpdateAreaInit (GraphUpdateObject o)
	May be called on the Unity thread before starting the update.

void	UpdateAreaPost (GraphUpdateObject o)
	May be called on the Unity thread after executing the update.

Public Member Functions inherited from IRaycastableGraph
bool	Linecast (Vector3 start, Vector3 end)

bool	Linecast (Vector3 start, Vector3 end, GraphNode hint)

bool	Linecast (Vector3 start, Vector3 end, GraphNode hint, out GraphHitInfo hit)

bool	Linecast (Vector3 start, Vector3 end, GraphNode hint, out GraphHitInfo hit, List< GraphNode > trace)

Static Public Member Functions
static bool	CheckConnection (LevelGridNode node, int dir)
	Returns if node is connected to it's neighbour in the specified direction.

Static Public Member Functions inherited from GridGraph
static void	CalculateConnections (GridNode node)
	Calculates the grid connections for a single node.

Public Attributes
float	characterHeight = 0.4F
	Nodes with a short distance to the node above it will be set unwalkable.

int	layerCount
	Number of layers.

float	mergeSpanRange = 0.5F
	If two layered nodes are too close, they will be merged.

new LevelGridNode[]	nodes

Public Attributes inherited from GridGraph
const int	getNearestForceOverlap = 2
	In GetNearestForce, determines how far to search after a valid node has been found.

readonly uint[]	neighbourCosts = new uint[8]
	Costs to neighbour nodes.

readonly int[]	neighbourOffsets = new int[8]
	Index offset to get neighbour nodes.

readonly int[]	neighbourXOffsets = new int[8]
	Offsets in the X direction for neighbour nodes.

readonly int[]	neighbourZOffsets = new int[8]
	Offsets in the Z direction for neighbour nodes.

GridNode[]	nodes
	All nodes in this graph.

int	width
	Width of the grid in nodes.

int	depth
	Depth (height) of the grid in nodes.

float	aspectRatio = 1F
	Scaling of the graph along the X axis.

float	isometricAngle
	Angle to use for the isometric projection.

bool	uniformEdgeCosts
	If true, all edge costs will be set to the same value.

Vector3	rotation
	Rotation of the grid in degrees.

Vector3	center
	Center point of the grid.

Vector2	unclampedSize
	Size of the grid.

float	nodeSize = 1
	Size of one node in world units.

GraphCollision	collision
	Settings on how to check for walkability and height.

float	maxClimb = 0.4F
	The max position difference between two nodes to enable a connection.

float	maxSlope = 90
	The max slope in degrees for a node to be walkable.

int	erodeIterations
	Erosion of the graph.

bool	erosionUseTags
	Use tags instead of walkability for erosion.

int	erosionFirstTag = 1
	Tag to start from when using tags for erosion.

bool	autoLinkGrids
	Auto link the graph's edge nodes together with other GridGraphs in the scene on Scan.

float	autoLinkDistLimit = 10F
	Distance limit for grid graphs to be auto linked.

NumNeighbours	neighbours = NumNeighbours.Eight
	Number of neighbours for each node.

bool	cutCorners = true
	If disabled, will not cut corners on obstacles.

float	penaltyPositionOffset
	Offset for the position when calculating penalty.

bool	penaltyPosition
	Use position (y-coordinate) to calculate penalty.

float	penaltyPositionFactor = 1F
	Scale factor for penalty when calculating from position.

bool	penaltyAngle

float	penaltyAngleFactor = 100F
	How much penalty is applied depending on the slope of the terrain.

float	penaltyAnglePower = 1
	How much extra to penalize very steep angles.

bool	useJumpPointSearch

bool	showMeshOutline = true
	Show an outline of the grid nodes in the Unity Editor.

bool	showNodeConnections
	Show the connections between the grid nodes in the Unity Editor.

bool	showMeshSurface = true
	Show the surface of the graph.

TextureData	textureData = new TextureData()
	Holds settings for using a texture as source for a grid graph.

Public Attributes inherited from NavGraph
AstarPath	active
	Reference to the AstarPath object in the scene.

bool	drawGizmos = true
	Enable to draw gizmos in the Unity scene view.

uint	graphIndex
	Index of the graph, used for identification purposes.

Guid	guid
	Used as an ID of the graph, considered to be unique.

bool	infoScreenOpen
	Used in the editor to check if the info screen is open.

uint	initialPenalty
	Default penalty to apply to all nodes.

Matrix4x4	inverseMatrix = Matrix4x4.identity
	Inverse of matrix.

Matrix4x4	matrix = Matrix4x4.identity
	A matrix for translating/rotating/scaling the graph.

string	name
	Name of the graph.

bool	open
	Is the graph open in the editor.

Protected Member Functions
override bool	ErosionAnyFalseConnections (GraphNode baseNode)
	True if the node has any blocked connections.

override List< GraphNode >	GetNodesInRegion (Bounds b, GraphUpdateShape shape)
	All nodes inside the shape or if null, the bounding box.

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.

IntRect	GetRectFromBounds (Bounds bounds)
	A rect with all nodes that the bounds could touch.

Protected Member Functions inherited from NavGraph
void	DrawUnwalkableNodes (float size)

Package Attributes
int	lastScannedDepth

int	lastScannedWidth

Properties
override int	LayerCount `[get]`

override bool	uniformWidthDepthGrid `[get]`

Properties inherited from GridGraph
int	Depth `[get, set]`

virtual int	LayerCount `[get]`

Vector2	size `[get, set]`
	Size of the grid.

GraphTransform	transform `[get, set]`
	Determines how the graph transforms graph space to world space.

virtual bool	uniformWidthDepthGrid `[get]`
	This is placed here so generators inheriting from this one can override it and set it to false.

int	Width `[get, set]`

bool	useRaycastNormal `[get]`
	Use heigh raycasting normal for max slope calculation.

Properties inherited from NavGraph
bool	exists `[get]`
	True if the graph exists, false if it has been destroyed.

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.

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

void	RemoveGridGraphFromStatic ()

LinkedLevelNode	SampleCell (int x, int z)

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.

Package Functions inherited from GridGraph
override void	DestroyAllNodesInternal ()
	Destroys all nodes in the graph.

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.

Member Function Documentation

void AddLayers ( int count )

private

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

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

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.

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

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.

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

Calculates the layered grid graph connections for a single node.

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

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.

override void DeserializeExtraInfo ( GraphSerializationContext ctx )

virtual

Deserializes graph type specific node data.

See Also: SerializeExtraInfo

Reimplemented from GridGraph.

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.

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

virtual

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

Parameters

position	The position to try to find a close node to
hint	Can be passed to enable some graph generators to find the nearest node faster.
constraint	Can 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.

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.

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

private

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.

myGraph.GetNodes (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

List<GraphNode> nodes = new List<GraphNode>();

myGraph.GetNodes(nodes.Add);

Reimplemented from GridGraph.

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.

override List<GraphNode> GetNodesInRegion ( IntRect rect )

virtual

Get all nodes in a rectangle.

Parameters

rect	Region in which to return nodes. It will be clamped to the grid.

Reimplemented from GridGraph.

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

virtual

Get all nodes in a rectangle.

Parameters

rect	Region in which to return nodes. It will be clamped to the grid.
buffer	Buffer 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.

override void OnDestroy ( )

virtual

This function will be called when this graph is destroyed.

Reimplemented from GridGraph.

override void PostDeserialization ( )

virtual

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.

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

x	X coordinate of the cell
z	Z coordinate of the cell
resetPenalties	If true, the penalty of the nodes will be reset to the initial value as if the graph had just been scanned.
resetTags	If 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.

void RemoveGridGraphFromStatic ( )

private

LinkedLevelNode SampleCell	(	int	x,
		int	z
	)

private

override IEnumerable<Progress> ScanInternal ( )

virtual

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.

override void SerializeExtraInfo ( GraphSerializationContext ctx )

virtual

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.

new void UpdateArea ( GraphUpdateObject o )

Member Data Documentation

float characterHeight = 0.4F

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

int lastScannedDepth

package

int lastScannedWidth

package

int layerCount

Number of layers.

Warning: Do not modify this variable

float mergeSpanRange = 0.5F

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

new LevelGridNode [] nodes

Property Documentation

override int LayerCount

getprotected

override bool uniformWidthDepthGrid

get

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

/Users/arong/Unity/a-pathfinding-project/Assets/AstarPathfindingProject/Generators/LayerGridGraphGenerator.cs

Detailed Description

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Package Attributes

Properties

Private Member Functions

Additional Inherited Members

Member Function Documentation

Member Data Documentation

Property Documentation