A* Pathfinding Project
4.1.7
The A* Pathfinding Project for Unity 3D
|
Basic point graph. More...
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.
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.
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... | |
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 | RebuildNodeLookup () |
Rebuilds the lookup structure for nodes. 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 using the default NNConstraint. 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... | |
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... | |
Private Member Functions | |
void | AddToLookup (PointNode node) |
GraphUpdateThreading IUpdatableGraph. | CanUpdateAsync (GraphUpdateObject o) |
IEnumerable< Progress > | ConnectNodes () |
Calculates connections for all nodes in the graph. More... | |
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() |
|
protected |
Recursively adds childrens of a transform as nodes.
Add a node to the graph at the specified position.
Add a node with the specified type to the graph at the specified position.
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. |
T | : | PointNode |
|
private |
|
private |
Implements IUpdatableGraph.
|
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.
|
staticprotected |
Recursively counds children of a transform.
|
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.
|
protectedvirtual |
|
protectedvirtual |
|
protectedvirtual |
An old format for serializing settings.
Reimplemented from NavGraph.
|
virtual |
Returns the nearest node to a position using the specified NNConstraint.
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.
|
virtual |
Returns the nearest node to a position using the specified constraint .
Reimplemented from NavGraph.
|
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.
If you want to store all nodes in a list you can do this
Implements NavGraph.
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.
|
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.
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%.
|
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
Reimplemented from NavGraph.
|
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.
|
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.
|
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
Implements IUpdatableGraph.
|
private |
May be called on the Unity thread before starting the update.
Implements IUpdatableGraph.
|
private |
May be called on the Unity thread after executing the update.
Implements IUpdatableGraph.
Vector3 limits |
Max distance along the axis for a connection to be valid.
0 = infinity
|
private |
LayerMask mask |
Layer mask to use for raycast.
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.
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.
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).
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.
bool raycast = true |
Use raycasts to check connections.
bool recursive = true |
Recursively search for child nodes to the root.
Transform root |
Childs of this transform are treated as nodes.
string searchTag |
If no root is set, all nodes with the tag is used as nodes.
bool thickRaycast |
Use thick raycast.
float thickRaycastRadius = 1 |
Thick raycast radius.
bool use2DPhysics |
Use the 2D Physics API.
|
getprotected set |
Number of nodes in this graph.