Basic point graph. More...

Detailed Description

Basic point graph.

The point graph is the most basic graph structure, it consists of a number of interconnected points in space called nodes or waypoints.
The point graph takes a Transform object as "root", this Transform will be searched for child objects, every child object will be treated as a node. If recursive is enabled, it will also search the child objects of the children recursively. It will then check if any connections between the nodes can be made, first it will check if the distance between the nodes isn't too large (maxDistance) and then it will check if the axis aligned distance isn't too high. The axis aligned distance, named limits, is useful because usually an AI cannot climb very high, but linking nodes far away from each other, but on the same Y level should still be possible. limits and maxDistance are treated as being set to infinity if they are set to 0 (zero).
Lastly it will check if there are any obstructions between the nodes using raycasting which can optionally be thick.
One thing to think about when using raycasting is to either place the nodes a small distance above the ground in your scene or to make sure that the ground is not in the raycast mask to avoid the raycast from hitting the ground.
Alternatively, a tag can be used to search for nodes.

See also: http://docs.unity3d.com/Manual/Tags.html

For larger graphs, it can take quite some time to scan the graph with the default settings. If you have the pro version you can enable optimizeForSparseGraph which will in most cases reduce the calculation times drastically.

Note: Does not support linecast because of obvious reasons.

Public Types
enum	NodeDistanceMode { Node, Connection }
	Distance query mode. More...

Public Member Functions
PointNode	AddNode (Int3 position)
	Add a node to the graph at the specified position. More...

T	AddNode< T > (T node, Int3 position)
	Add a node with the specified type to the graph at the specified position. More...

void	ConnectNodes ()
	Recalculates connections for all nodes in the graph. 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 void	GetNodes (System.Action< GraphNode > action)
	Calls a delegate with all nodes in the graph. More...

virtual bool	IsValidConnection (GraphNode a, GraphNode b, out float dist)
	Returns if the connection between a and b is valid. More...

void	RebuildConnectionDistanceLookup ()
	Rebuilds a cache used when nearestNodeDistanceMode = #NodeDistanceMode.ToConnection. More...

void	RebuildNodeLookup ()
	Rebuilds the lookup structure for nodes. More...

void	RegisterConnectionLength (long sqrLength)
	Ensures the graph knows that there is a connection with this length. More...

override void	RelocateNodes (Matrix4x4 deltaMatrix)
	Moves the nodes in this graph. 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...

virtual void	OnDrawGizmos (RetainedGizmos gizmos, bool drawNodes)
	Draw gizmos for the graph. 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...

Public Attributes
Vector3	limits
	Max distance along the axis for a connection to be valid. More...

LayerMask	mask
	Layer mask to use for raycast. More...

float	maxDistance
	Max distance for a connection to be valid. More...

NodeDistanceMode	nearestNodeDistanceMode
	Distance query mode. More...

PointNode []	nodes
	All nodes in this graph. More...

bool	optimizeForSparseGraph
	Optimizes the graph for sparse graphs. More...

bool	raycast = true
	Use raycasts to check connections. More...

bool	recursive = true
	Recursively search for child nodes to the root. More...

Transform	root
	Childs of this transform are treated as nodes. More...

string	searchTag
	If no root is set, all nodes with the tag is used as nodes. More...

bool	thickRaycast
	Use thick raycast. More...

float	thickRaycastRadius = 1
	Thick raycast radius. More...

bool	use2DPhysics
	Use the 2D Physics API. 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
void	AddChildren (ref int c, Transform tr)
	Recursively adds childrens of a transform as nodes. More...

virtual PointNode []	CreateNodes (int count)

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

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

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

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

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

Protected Member Functions inherited from NavGraph
virtual void	DestroyAllNodes ()
	Destroys all nodes in the graph. More...

void	DrawUnwalkableNodes (float size)

virtual void	OnDestroy ()
	Function for cleaning up references. More...

Static Protected Member Functions
static int	CountChildren (Transform tr)
	Recursively counds children of a transform. More...

Properties
int	nodeCount `[get, protected set]`
	Number of nodes in this graph. More...

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

string IGraphInternals.	SerializedEditorSettings `[get, set]`

Properties inherited from IGraphInternals
string	SerializedEditorSettings `[get, set]`

Private Member Functions
void	AddToLookup (PointNode node)

GraphUpdateThreading IUpdatableGraph.	CanUpdateAsync (GraphUpdateObject o)

IEnumerable< Progress >	ConnectNodesAsync ()
	Calculates connections for all nodes in the graph. More...

NNInfoInternal	FindClosestConnectionPoint (PointNode node, Vector3 position)

NNInfoInternal	GetNearestInternal (Vector3 position, NNConstraint constraint, bool fastCheck)

void IUpdatableGraph.	UpdateArea (GraphUpdateObject guo)
	Updates an area in the list graph. More...

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

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

Private Attributes
PointKDTree	lookupTree = new PointKDTree()

long	maximumConnectionLength = 0
	Longest known connection. More...

Member Enumeration Documentation

◆ NodeDistanceMode

enum NodeDistanceMode

strong

Distance query mode.

In the image above there are a few red nodes. Assume the agent is the orange circle. Using the Node mode the closest point on the graph that would be found would be the node at the bottom center which may not be what you want. Using the Connection mode it will find the closest point on the connection between the two nodes in the top half of the image.

When using the Connection option you may also want to use the Connection option for the Seeker's Start End Modifier snapping options. This is not strictly necessary, but it most cases it is what you want.

See also: Pathfinding.StartEndModifier.exactEndPoint

Enumerator

Node

All nearest node queries find the closest node center.

This is the fastest option but it may not be what you want if you have long connections.

Connection

All nearest node queries find the closest point on edges between nodes.

This is useful if you have long connections where the agent might be closer to some unrelated node if it is standing on a long connection between two nodes. This mode is however slower than the Node mode.

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

Member Function Documentation

◆ AddChildren()

void AddChildren	(	ref int	c,
		Transform	tr
	)

protected

Recursively adds childrens of a transform as nodes.

◆ AddNode()

PointNode AddNode ( Int3 position )

Add a node to the graph at the specified position.

Note

Vector3 can be casted to Int3 using (Int3)myVector.

This needs to be called when it is safe to update nodes, which is

when scanning
during a graph update
inside a callback registered using AstarPath.AddWorkItem

        AstarPath.active.AddWorkItem(new AstarWorkItem(ctx => {
            var graph = AstarPath.active.data.pointGraph;
            // Add 2 nodes and connect them
            var node1 = graph.AddNode((Int3)transform.position);
            var node2 = graph.AddNode((Int3)(transform.position + Vector3.right));
            var cost = (uint)(node2.position - node1.position).costMagnitude;
            node1.AddConnection(node2, cost);
            node2.AddConnection(node1, cost);
        }));

See also: Creating graphs during runtime

◆ AddNode< T >()

T AddNode< T >	(	T	node,
		Int3	position
	)

Add a node with the specified type to the graph at the specified position.

Parameters

node	This must be a node created using T(AstarPath.active) right before the call to this method. The node parameter is only there because there is no new(AstarPath) constraint on generic type parameters.
position	The node will be set to this position.

Note

Vector3 can be casted to Int3 using (Int3)myVector.

This needs to be called when it is safe to update nodes, which is

when scanning
during a graph update
inside a callback registered using AstarPath.AddWorkItem

See also: AstarPath.AddWorkItem; Creating graphs during runtime

Type Constraints

T

:

PointNode

◆ AddToLookup()

void AddToLookup ( PointNode node )

private

◆ CanUpdateAsync()

GraphUpdateThreading IUpdatableGraph. CanUpdateAsync ( GraphUpdateObject o )

private

Implements IUpdatableGraph.

◆ ConnectNodes()

void ConnectNodes ( )

Recalculates connections for all nodes in the graph.

This is useful if you have created nodes manually using AddNode and then want to connect them in the same way as the point graph normally connects nodes.

◆ ConnectNodesAsync()

IEnumerable<Progress> ConnectNodesAsync ( )

private

Calculates connections for all nodes in the graph.

This is an IEnumerable, you can iterate through it using e.g foreach to get progress information.

◆ CountChildren()

static int CountChildren ( Transform tr )

staticprotected

Recursively counds children of a transform.

◆ 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 NavGraph.

◆ CreateNodes()

virtual PointNode [] CreateNodes ( int count )

protectedvirtual

◆ DeserializeExtraInfo()

override void DeserializeExtraInfo ( GraphSerializationContext ctx )

protectedvirtual

Deserializes graph type specific node data.

See also: SerializeExtraInfo

Reimplemented from NavGraph.

◆ DeserializeSettingsCompatibility()

override void DeserializeSettingsCompatibility ( GraphSerializationContext ctx )

protectedvirtual

An old format for serializing settings.

Deprecated:: This is deprecated now, but the deserialization code is kept to avoid loosing data when upgrading from older versions.

Reimplemented from NavGraph.

◆ FindClosestConnectionPoint()

NNInfoInternal FindClosestConnectionPoint	(	PointNode	node,
		Vector3	position
	)

private

◆ GetNearest()

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 NavGraph.

◆ 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 NavGraph.

◆ GetNearestInternal()

NNInfoInternal GetNearestInternal	(	Vector3	position,
		NNConstraint	constraint,
		bool	fastCheck
	)

private

◆ 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);

See also: Pathfinding.AstarData.GetNodes

Implements NavGraph.

◆ IsValidConnection()

virtual bool IsValidConnection	(	GraphNode	a,
		GraphNode	b,
		out float	dist
	)

virtual

Returns if the connection between a and b is valid.

Checks for obstructions using raycasts (if enabled) and checks for height differences.
As a bonus, it outputs the distance between the nodes too if the connection is valid.

Note: This is not the same as checking if node a is connected to node b. That should be done using a.ContainsConnection(b)

◆ 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 NavGraph.

◆ RebuildConnectionDistanceLookup()

void RebuildConnectionDistanceLookup ( )

Rebuilds a cache used when nearestNodeDistanceMode = #NodeDistanceMode.ToConnection.

◆ RebuildNodeLookup()

void RebuildNodeLookup ( )

Rebuilds the lookup structure for nodes.

This is used when optimizeForSparseGraph is enabled.

You should call this method every time you move a node in the graph manually and you are using optimizeForSparseGraph, otherwise pathfinding might not work correctly.

You may also call this after you have added many nodes using the AddNode method. When adding nodes using the AddNode method they will be added to the lookup structure. The lookup structure will rebalance itself when it gets too unbalanced however if you are sure you won't be adding any more nodes in the short term, you can make sure it is perfectly balanced and thus squeeze out the last bit of performance by calling this method. This can improve the performance of the GetNearest method slightly. The improvements are on the order of 10-20%.

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

◆ RegisterConnectionLength()

void RegisterConnectionLength ( long sqrLength )

Ensures the graph knows that there is a connection with this length.

This is used when the nearest node distance mode is set to ToConnection. If you are modifying node connections yourself (i.e. manipulating the PointNode.connections array) then you must call this function when you add any connections.

When using PointNode.AddConnection this is done automatically. It is also done for all nodes when RebuildNodeLookup is called.

Parameters

sqrLength The length of the connection in squared Int3 units. This can be calculated using (node1.position - node2.position).sqrMagnitudeLong.

◆ RelocateNodes()

override void RelocateNodes ( Matrix4x4 deltaMatrix )

virtual

Moves the nodes in this graph.

Multiplies all node positions by deltaMatrix.

For example if you want to move all your nodes in e.g a point graph 10 units along the X axis from the initial position

var graph = AstarPath.data.pointGraph;
var m = Matrix4x4.TRS (new Vector3(10,0,0), Quaternion.identity, Vector3.one);
graph.RelocateNodes (m);

Note: For grid graphs, navmesh graphs and recast graphs it is recommended to use their custom overloads of the RelocateNodes method which take parameters for e.g center and nodeSize (and additional parameters) instead since they are both easier to use and are less likely to mess up pathfinding.

Warning: This method is lossy for PointGraphs, so calling it many times may cause node positions to lose precision. For example if you set the scale to 0 in one call then all nodes will be scaled/moved to the same point and you will not be able to recover their original positions. The same thing happens for other - less extreme - values as well, but to a lesser degree.

Reimplemented from NavGraph.

◆ 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.

Implements NavGraph.

◆ 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 NavGraph.

◆ UpdateArea()

void IUpdatableGraph. UpdateArea ( GraphUpdateObject guo )

private

Updates an area in the list graph.

Recalculates possibly affected connections, i.e all connectionlines passing trough the bounds of the guo will be recalculated

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

Implements IUpdatableGraph.

◆ UpdateAreaInit()

void IUpdatableGraph. UpdateAreaInit ( GraphUpdateObject o )

private

May be called on the Unity thread before starting the update.

See also: CanUpdateAsync

Implements IUpdatableGraph.

◆ UpdateAreaPost()

void IUpdatableGraph. UpdateAreaPost ( GraphUpdateObject o )

private

May be called on the Unity thread after executing the update.

See also: CanUpdateAsync

Implements IUpdatableGraph.

Member Data Documentation

◆ limits

Vector3 limits

Max distance along the axis for a connection to be valid.

0 = infinity

◆ lookupTree

PointKDTree lookupTree = new PointKDTree()

private

◆ mask

LayerMask mask

Layer mask to use for raycast.

◆ maxDistance

float maxDistance

Max distance for a connection to be valid.

The value 0 (zero) will be read as infinity and thus all nodes not restricted by other constraints will be added as connections.

A negative value will disable any neighbours to be added. It will completely stop the connection processing to be done, so it can save you processing power if you don't these connections.

◆ maximumConnectionLength

long maximumConnectionLength = 0

private

Longest known connection.

In squared Int3 units.

See also: RegisterConnectionLength

◆ nearestNodeDistanceMode

NodeDistanceMode nearestNodeDistanceMode

Distance query mode.

In the image above there are a few red nodes. Assume the agent is the orange circle. Using the Node mode the closest point on the graph that would be found would be the node at the bottom center which may not be what you want. Using the Connection mode it will find the closest point on the connection between the two nodes in the top half of the image.

When using the Connection option you may also want to use the Connection option for the Seeker's Start End Modifier snapping options. This is not strictly necessary, but it most cases it is what you want.

See also: Pathfinding.StartEndModifier.exactEndPoint; NodeDistanceMode

If you enable this during runtime, you will need to call RebuildConnectionDistanceLookup to make sure some cache data is properly recalculated. If the graph doesn't have any nodes yet or if you are going to scan the graph afterwards then you do not need to do this.

◆ nodes

PointNode [] nodes

All nodes in this graph.

Note that only the first nodeCount will be non-null.

You can also use the GetNodes method to get all nodes.

◆ optimizeForSparseGraph

bool optimizeForSparseGraph

Optimizes the graph for sparse graphs.

This can reduce calculation times for both scanning and for normal path requests by huge amounts. It reduces the number of node-node checks that need to be done during scan, and can also optimize getting the nearest node from the graph (such as when querying for a path).

Try enabling and disabling this option, check the scan times logged when you scan the graph to see if your graph is suited for this optimization or if it makes it slower.

The gain of using this optimization increases with larger graphs, the default scan algorithm is brute force and requires O(n^2) checks, this optimization along with a graph suited for it, requires only O(n) checks during scan (assuming the connection distance limits are reasonable).

Warning: When you have this enabled, you will not be able to move nodes around using scripting unless you recalculate the lookup structure at the same time.

See also: RebuildNodeLookup

If you enable this during runtime, you will need to call RebuildNodeLookup to make sure any existing nodes are added to the lookup structure. If the graph doesn't have any nodes yet or if you are going to scan the graph afterwards then you do not need to do this.

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

◆ raycast

bool raycast = true

Use raycasts to check connections.

◆ recursive

bool recursive = true

Recursively search for child nodes to the root.

◆ root

Transform root

Childs of this transform are treated as nodes.

◆ searchTag

string searchTag

If no root is set, all nodes with the tag is used as nodes.

◆ thickRaycast

bool thickRaycast

Use thick raycast.

◆ thickRaycastRadius

float thickRaycastRadius = 1

Thick raycast radius.

◆ use2DPhysics

bool use2DPhysics

Use the 2D Physics API.

Property Documentation

◆ nodeCount

int nodeCount

getprotected set

Number of nodes in this graph.

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

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

Detailed Description

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Static Protected Member Functions

Properties

Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ NodeDistanceMode

Member Function Documentation

◆ AddChildren()

◆ AddNode()

◆ AddNode< T >()

◆ AddToLookup()

◆ CanUpdateAsync()

◆ ConnectNodes()

◆ ConnectNodesAsync()

◆ CountChildren()

◆ CountNodes()

◆ CreateNodes()

◆ DeserializeExtraInfo()

◆ DeserializeSettingsCompatibility()

◆ FindClosestConnectionPoint()

◆ GetNearest()

◆ GetNearestForce()

◆ GetNearestInternal()

◆ GetNodes()

◆ IsValidConnection()

◆ PostDeserialization()

◆ RebuildConnectionDistanceLookup()

◆ RebuildNodeLookup()

◆ RegisterConnectionLength()

◆ RelocateNodes()

◆ ScanInternal()

◆ SerializeExtraInfo()

◆ UpdateArea()

◆ UpdateAreaInit()

◆ UpdateAreaPost()

Member Data Documentation

◆ limits

◆ lookupTree

◆ mask

◆ maxDistance

◆ maximumConnectionLength

◆ nearestNodeDistanceMode

◆ nodes

◆ optimizeForSparseGraph

◆ raycast

◆ recursive

◆ root

◆ searchTag

◆ thickRaycast

◆ thickRaycastRadius

◆ use2DPhysics

Property Documentation

◆ nodeCount