A* Pathfinding Project
4.1.0
The A* Pathfinding Project for Unity 3D
|
How to access graphs and nodes.
All data in the graphs can be accessed. There are for example many cases where the API expects a GraphNode as a parameter so you need to be able to find those. And there can be other cases where you need to extensively modify the graph data to suit your game. For example you might have your own custom made tilemap generator and you need to pass that data to the grid graph.
Here's how you get nodes
There are also cases where you want to get only certain nodes, such as "What is the closest *Walkable* node to this position?". This can be accomplished using the Pathfinding.NNConstraint. For this case the Default NNConstraint (it is called default, because it is used for path calls if nothing else is specified)
The search range of these constraints is not unlimited, but quite large. The maximum distance can be set in A* Inspector -> Settings -> Max Nearest Node Distance or AstarPath.maxNearestNodeDistance.
You may have noticed above that to get the node from the GetNearest call we had to access the node field. The GetNearest method returns an NNInfo struct which contains two fields. The first one is the node field which contains the best node (or null if no node could be found). The second one is the position field which contains the closest point on that node to the query point. On grid graphs, the nodes are thought of as squares so the position field will then contain the closest point inside that square to the query point. On navmesh based graphs (RecastGraph and NavMeshGraph) the position field will contain the closest point on the closest triangle. Point nodes do not have a surface so the position will just be set to the node's position.
All graphs are stored in the Pathfinding.AstarData class. It contains an array with all the graphs and there are a bunch of methods for finding graphs in it. The quickest way however is to use the shortcuts that are provided. For each type of built in graph there is a field which points to the first graph of that type.
The different graphs types store their nodes in different ways. The grid graph for example stores all nodes in a huge array which can be indexed to easily get a node at a specific cell index. The recast graph stores all nodes in arrays in separate tiles.
The generic very high-level way to get all nodes in a graph is by using the GetNodes method which exists on all types of graphs. It takes a callback which will be invoked for each node. The callback should return true if the graph should continue to call it with the rest of the nodes in the graph and false if it should stop. The reason it is a callback instead of an iterator is because after profiling I found this to be significantly faster and for large graphs that does make a difference.
Grid graph nodes are stored in a large array. It is indexed by the coordinates of the node so they can be accessed easily.
There are some cases where you want to change the size of a grid graph during runtime. Then you can modify either the unclampedSize field. Which is the size of the grid in world units. Or you can modify the width and depth fields. But then you need to call the UpdateSizeFromWidthDepth method afterwards. After you have changed the width or depth of the graph you need to recalculate it using AstarPath.Scan.
It is also possible to move the grid graph without recalculating it using the RelocateNodes method. The same method is also available for other graphs, but then you have to calculate the necessarily matrix yourself.
The layered grid graph works almost like the grid graph. However the nodes are not ordered in exactly the same way. Since layered grid graphs can contain several layers. An additional layer coordinate is needed.
Recast graphs divide the nodes into a number of tiles. The individual tiles are stored in an array in the same way as the grid graph stores its nodes. Inside each tile, the nodes are stored in an array without any inherent order. However all nodes are also added to a axis aligned bounding box tree AABB Tree in order to be able to query for the closest node to a point in an efficient manner.
Point graphs simply store the nodes in an array without any inherent order.
Point graph nodes also contain a field for the GameObject they were created from (if any) which can be useful for all kinds of purposes.