A* Pathfinding Project
4.1.12
The A* Pathfinding Project for Unity 3D
|
Grid Graph, supports layered worlds. More...
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.
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< GraphNode > | GetNodesInRegion (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< 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. More... | |
List< GraphNode > | GetNodesInRegion (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< GraphNode > | GetNodesInRegion (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< 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 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... | |
string IGraphInternals. | SerializedEditorSettings [get, set] |
Properties inherited from IGraphInternals | |
string | SerializedEditorSettings [get, set] |
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... | |
|
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.
|
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.
|
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 |
Returns if node is connected to it's neighbour in the specified direction.
|
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.
|
protectedvirtual |
Deserializes graph type specific node data.
Reimplemented from GridGraph.
|
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.
|
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 GridGraph.
|
virtual |
Returns the nearest node to a position using the specified constraint .
Reimplemented from GridGraph.
|
private |
|
virtual |
GridNodeBase GetNode | ( | int | x, |
int | z, | ||
int | layer | ||
) |
Node in the specified cell.
|
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
Reimplemented from GridGraph.
|
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.
Reimplemented from GridGraph.
Get all nodes in a rectangle.
rect | Region in which to return nodes. It will be clamped to the grid. |
Reimplemented from GridGraph.
|
virtual |
Get all nodes in a rectangle.
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. |
Reimplemented from GridGraph.
|
protectedvirtual |
This function will be called when this graph is destroyed.
Reimplemented from GridGraph.
|
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.
|
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.
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). |
Reimplemented from GridGraph.
|
private |
|
private |
|
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.
|
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.
|
private |
Updates an area using the specified #GraphUpdateObject.
Notes to implementators. This function should (in order):
Implements IUpdatableGraph.
float characterHeight = 0.4F |
Nodes with a short distance to the node above it will be set unwalkable.
|
package |
|
package |
|
package |
Number of layers.
float mergeSpanRange = 0.5F |
If two layered nodes are too close, they will be merged.
new LevelGridNode [] nodes |
|
get |
|
get |