A* Pathfinding Project  3.6
The A* Pathfinding Project for Unity 3D
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Events Macros Groups Pages
NavMeshGraph Class Reference

Generates graphs based on navmeshes. More...

Detailed Description

Generates graphs based on navmeshes.

Navmeshes are meshes where each polygon define a walkable area. These are great because the AI can get so much more information on how it can walk. Polygons instead of points mean that the funnel smoother can produce really nice looking paths and the graphs are also really fast to search and have a low memory footprint because of their smaller size to describe the same area (compared to grid graphs).

See Also
Pathfinding.RecastGraph

Public Member Functions

void AddPortal (GraphNode n1, GraphNode n2, List< Vector3 > left, List< Vector3 > right)
 
void BuildFunnelCorridor (List< GraphNode > path, int startIndex, int endIndex, List< Vector3 > left, List< Vector3 > right)
 
GraphUpdateThreading CanUpdateAsync (GraphUpdateObject o)
 
bool ContainsPoint (TriangleMeshNode node, Vector3 pos)
 Returns if the point is inside the node in XZ space.
 
override void CreateNodes (int number)
 Creates a number of nodes with the correct type for the graph.
 
override void DeserializeExtraInfo (GraphSerializationContext ctx)
 Deserializes graph type specific node data.
 
void GenerateMatrix ()
 
override NNInfo GetNearest (Vector3 position, NNConstraint constraint, GraphNode hint)
 Returns the nearest node to a position using the specified NNConstraint.
 
override NNInfo GetNearestForce (Vector3 position, NNConstraint constraint)
 This performs a linear search through all polygons returning the closest one.
 
override void GetNodes (GraphNodeDelegateCancelable del)
 Calls a delegate with all nodes in the graph.
 
void GetTileCoordinates (int tileIndex, out int x, out int z)
 
Int3 GetVertex (int index)
 
int GetVertexArrayIndex (int index)
 
bool Linecast (Vector3 origin, Vector3 end)
 Returns if there is an obstacle between origin and end on the graph.
 
bool Linecast (Vector3 origin, Vector3 end, GraphNode hint, out GraphHitInfo hit)
 Returns if there is an obstacle between origin and end on the graph.
 
bool Linecast (Vector3 origin, Vector3 end, GraphNode hint)
 Returns if there is an obstacle between origin and end on the graph.
 
bool Linecast (Vector3 origin, Vector3 end, GraphNode hint, out GraphHitInfo hit, List< GraphNode > trace)
 Returns if there is an obstacle between origin and end on the graph.
 
override void OnDestroy ()
 Function for cleaning up references.
 
override void OnDrawGizmos (bool drawNodes)
 
void PostProcess ()
 
override void RelocateNodes (Matrix4x4 oldMatrix, Matrix4x4 newMatrix)
 Relocates the nodes to match the newMatrix.
 
void ScanInternal (string objMeshPath)
 Scans the graph using the path to an .obj mesh.
 
override void ScanInternal (OnScanStatus statusCallback)
 Scans the graph, called from AstarPath.ScanInternal Override this function to implement custom scanning logic The statusCallback may be optionally called to show progress info in the editor
 
override void SerializeExtraInfo (GraphSerializationContext ctx)
 Serializes graph type specific node data.
 
void Sort (Vector3[] a)
 
void UpdateArea (GraphUpdateObject o)
 
void UpdateAreaInit (GraphUpdateObject o)
 
- Public Member Functions inherited from NavGraph
virtual void Awake ()
 This will be called on the same time as Awake on the gameObject which the AstarPath script is attached to.
 
virtual int CountNodes ()
 Count nodes in the graph.
 
NNInfo GetNearest (Vector3 position)
 Returns the nearest node to a position using the default NNConstraint.
 
NNInfo GetNearest (Vector3 position, NNConstraint constraint)
 Returns the nearest node to a position using the specified NNConstraint.
 
virtual Color NodeColor (GraphNode node, PathHandler data)
 
virtual void PostDeserialization ()
 Called after all deserialization has been done for all graphs.
 
void SafeOnDestroy ()
 SafeOnDestroy should be used when there is a risk that the pathfinding is searching through this graph when called.
 
void Scan ()
 
void ScanGraph ()
 Consider using AstarPath.Scan () instead since this function might screw things up if there is more than one graph.
 
void ScanInternal ()
 
void SetMatrix (Matrix4x4 m)
 Use to set both matrix and inverseMatrix at the same time.
 
- Public Member Functions inherited from INavmesh
void GetNodes (GraphNodeDelegateCancelable del)
 
- 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)
 
- Public Member Functions inherited from IFunnelGraph
void AddPortal (GraphNode n1, GraphNode n2, List< Vector3 > left, List< Vector3 > right)
 Add the portal between node n1 and n2 to the funnel corridor.
 
void BuildFunnelCorridor (List< GraphNode > path, int sIndex, int eIndex, List< Vector3 > left, List< Vector3 > right)
 
- Public Member Functions inherited from INavmeshHolder
void GetTileCoordinates (int tileIndex, out int x, out int z)
 
Int3 GetVertex (int i)
 
int GetVertexArrayIndex (int index)
 
- 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 void BuildFunnelCorridor (INavmesh graph, List< GraphNode > path, int startIndex, int endIndex, List< Vector3 > left, List< Vector3 > right)
 
static Vector3 ClosestPointOnNode (TriangleMeshNode node, Int3[] vertices, Vector3 pos)
 Returns the closest point of the node.
 
static bool ContainsPoint (TriangleMeshNode node, Vector3 pos, Int3[] vertices)
 Returns if the point is inside the node in XZ space.
 
static void DeserializeMeshNodes (NavMeshGraph graph, GraphNode[] nodes, byte[] bytes)
 
static NNInfo GetNearest (NavMeshGraph graph, GraphNode[] nodes, Vector3 position, NNConstraint constraint, bool accurateNearestNode)
 
static NNInfo GetNearestForce (NavGraph graph, INavmeshHolder navmesh, Vector3 position, NNConstraint constraint, bool accurateNearestNode)
 This performs a linear search through all polygons returning the closest one.
 
static NNInfo GetNearestForceBoth (NavGraph graph, INavmeshHolder navmesh, Vector3 position, NNConstraint constraint, bool accurateNearestNode)
 This performs a linear search through all polygons returning the closest one.
 
static bool Linecast (INavmesh graph, Vector3 tmp_origin, Vector3 tmp_end, GraphNode hint, out GraphHitInfo hit)
 Returns if there is an obstacle between origin and end on the graph.
 
static bool Linecast (INavmesh graph, Vector3 tmp_origin, Vector3 tmp_end, GraphNode hint, out GraphHitInfo hit, List< GraphNode > trace)
 Returns if there is an obstacle between origin and end on the graph.
 
static void RebuildBBTree (NavMeshGraph graph)
 Rebuilds the BBTree on a NavGraph.
 
static void UpdateArea (GraphUpdateObject o, INavmesh graph)
 
- Static Public Member Functions inherited from NavGraph
static bool InSearchTree (GraphNode node, Path path)
 Returns if the node is in the search tree of the path.
 

Public Attributes

bool accurateNearestNode = true
 More accurate nearest node queries.
 
TriangleMeshNode[] nodes
 
Vector3 offset
 Offset in world space.
 
Vector3 rotation
 Rotation in degrees.
 
float scale = 1
 Scale of the graph.
 
Mesh sourceMesh
 Mesh to construct navmesh from.
 
int[] triangles
 
- Public Attributes inherited from NavGraph
byte[] _sguid
 Used to store the guid value.
 
AstarPath active
 Reference to the AstarPath object in the scene.
 
bool drawGizmos = true
 
uint graphIndex
 Index of the graph, used for identification purposes.
 
bool infoScreenOpen
 Used in the editor to check if the info screen is open.
 
uint initialPenalty = 0
 
Matrix4x4 inverseMatrix
 Inverse of matrix.
 
Matrix4x4 matrix
 A matrix for translating/rotating/scaling the graph.
 
string name
 
bool open
 Is the graph open in the editor
 

Properties

BBTree bbTree [get, set]
 
TriangleMeshNode[] TriNodes [get]
 
Int3[] vertices [get, set]
 
- Properties inherited from NavGraph
Guid guid [get, set]
 Used as an ID of the graph, considered to be unique.
 

Private Member Functions

void GenerateNodes (Vector3[] vectorVertices, int[] triangles, out Vector3[] originalVertices, out Int3[] vertices)
 Generates a navmesh.
 

Private Attributes

BBTree _bbTree
 Bounding Box Tree.
 
Int3[] _vertices
 
Vector3[] originalVertices
 

Member Function Documentation

void AddPortal ( GraphNode  n1,
GraphNode  n2,
List< Vector3 >  left,
List< Vector3 >  right 
)
void BuildFunnelCorridor ( List< GraphNode path,
int  startIndex,
int  endIndex,
List< Vector3 >  left,
List< Vector3 >  right 
)
static void BuildFunnelCorridor ( INavmesh  graph,
List< GraphNode path,
int  startIndex,
int  endIndex,
List< Vector3 >  left,
List< Vector3 >  right 
)
static
GraphUpdateThreading CanUpdateAsync ( GraphUpdateObject  o)
static Vector3 ClosestPointOnNode ( TriangleMeshNode  node,
Int3[]  vertices,
Vector3  pos 
)
static

Returns the closest point of the node.

bool ContainsPoint ( TriangleMeshNode  node,
Vector3  pos 
)

Returns if the point is inside the node in XZ space.

static bool ContainsPoint ( TriangleMeshNode  node,
Vector3  pos,
Int3[]  vertices 
)
static

Returns if the point is inside the node in XZ space.

override void CreateNodes ( int  number)
virtual

Creates a number of nodes with the correct type for the graph.

This should not set the nodes array, only return the nodes. Called by graph generators and when deserializing a graph with nodes. Override this function if you do not use the default Pathfinding.Node class.

Reimplemented from NavGraph.

override void DeserializeExtraInfo ( GraphSerializationContext  ctx)
virtual

Deserializes graph type specific node data.

See Also
SerializeExtraInfo

Reimplemented from NavGraph.

static void DeserializeMeshNodes ( NavMeshGraph  graph,
GraphNode[]  nodes,
byte[]  bytes 
)
static
void GenerateMatrix ( )
void GenerateNodes ( Vector3[]  vectorVertices,
int[]  triangles,
out Vector3[]  originalVertices,
out Int3[]  vertices 
)
private

Generates a navmesh.

Based on the supplied vertices and triangles. Memory usage is about O(n)

static NNInfo GetNearest ( NavMeshGraph  graph,
GraphNode[]  nodes,
Vector3  position,
NNConstraint  constraint,
bool  accurateNearestNode 
)
static
override NNInfo GetNearest ( Vector3  position,
NNConstraint  constraint,
GraphNode  hint 
)
virtual

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

Parameters
positionThe position to try to find a close node to
hintCan be passed to enable some graph generators to find the nearest node faster.
constraintCan 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.

override NNInfo GetNearestForce ( Vector3  position,
NNConstraint  constraint 
)
virtual

This performs a linear search through all polygons returning the closest one.

This is usually only called in the Free version of the A* Pathfinding Project since the Pro one supports BBTrees and will do another query

Reimplemented from NavGraph.

static NNInfo GetNearestForce ( NavGraph  graph,
INavmeshHolder  navmesh,
Vector3  position,
NNConstraint  constraint,
bool  accurateNearestNode 
)
static

This performs a linear search through all polygons returning the closest one.

static NNInfo GetNearestForceBoth ( NavGraph  graph,
INavmeshHolder  navmesh,
Vector3  position,
NNConstraint  constraint,
bool  accurateNearestNode 
)
static

This performs a linear search through all polygons returning the closest one.

This will fill the NNInfo with .node for the closest node not necessarily complying with the NNConstraint, and .constrainedNode with the closest node complying with the NNConstraint.

See Also
GetNearestForce(Node[],Int3[],Vector3,NNConstraint,bool)
override void GetNodes ( GraphNodeDelegateCancelable  del)
virtual

Calls a delegate with all nodes in the graph.

This is the primary way of "looping" through all nodes in a graph.

This function should not change anything in the graph structure.

Implements NavGraph.

void GetTileCoordinates ( int  tileIndex,
out int  x,
out int  z 
)
Int3 GetVertex ( int  index)
int GetVertexArrayIndex ( int  index)
bool Linecast ( Vector3  origin,
Vector3  end 
)

Returns if there is an obstacle between origin and end on the graph.

This is not the same as Physics.Linecast, this function traverses the graph and looks for collisions instead of checking for collider intersection.

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
bool Linecast ( Vector3  origin,
Vector3  end,
GraphNode  hint,
out GraphHitInfo  hit 
)

Returns if there is an obstacle between origin and end on the graph.

Parameters
[in]originPoint to linecast from
[in]endPoint to linecast to
[out]hitContains info on what was hit, see GraphHitInfo
[in]hintYou need to pass the node closest to the start point This is not the same as Physics.Linecast, this function traverses the graph and looks for collisions instead of checking for collider intersection.
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
bool Linecast ( Vector3  origin,
Vector3  end,
GraphNode  hint 
)

Returns if there is an obstacle between origin and end on the graph.

Parameters
[in]originPoint to linecast from
[in]endPoint to linecast to
[in]hintYou need to pass the node closest to the start point This is not the same as Physics.Linecast, this function traverses the graph and looks for collisions instead of checking for collider intersection.
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
bool Linecast ( Vector3  origin,
Vector3  end,
GraphNode  hint,
out GraphHitInfo  hit,
List< GraphNode trace 
)

Returns if there is an obstacle between origin and end on the graph.

Parameters
[in]originPoint to linecast from
[in]endPoint to linecast to
[out]hitContains info on what was hit, see GraphHitInfo
[in]hintYou need to pass the node closest to the start point
traceIf a list is passed, then it will be filled with all nodes the linecast traverses This is not the same as Physics.Linecast, this function traverses the graph and looks for collisions instead of checking for collider intersection.
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
static bool Linecast ( INavmesh  graph,
Vector3  tmp_origin,
Vector3  tmp_end,
GraphNode  hint,
out GraphHitInfo  hit 
)
static

Returns if there is an obstacle between origin and end on the graph.

Parameters
[in]graphThe graph to perform the search on
[in]tmp_originPoint to start from
[in]tmp_endPoint to linecast to
[out]hitContains info on what was hit, see GraphHitInfo
[in]hintYou need to pass the node closest to the start point, if null, a search for the closest node will be done This is not the same as Physics.Linecast, this function traverses the graph and looks for collisions instead of checking for collider intersection.
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
static bool Linecast ( INavmesh  graph,
Vector3  tmp_origin,
Vector3  tmp_end,
GraphNode  hint,
out GraphHitInfo  hit,
List< GraphNode trace 
)
static

Returns if there is an obstacle between origin and end on the graph.

Parameters
[in]graphThe graph to perform the search on
[in]tmp_originPoint to start from
[in]tmp_endPoint to linecast to
[out]hitContains info on what was hit, see GraphHitInfo
[in]hintYou need to pass the node closest to the start point, if null, a search for the closest node will be done
traceIf a list is passed, then it will be filled with all nodes the linecast traverses This is not the same as Physics.Linecast, this function traverses the graph and looks for collisions instead of checking for collider intersection.
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
override void OnDestroy ( )
virtual

Function for cleaning up references.

This will be called on the same time as OnDisable on the gameObject which the AstarPath script is attached to (remember, not in the editor). Use for any cleanup code such as cleaning up static variables which otherwise might prevent resources from being collected. Use by creating a function overriding this one in a graph class, but always call base.OnDestroy () in that function. All nodes should be destroyed in this function otherwise a memory leak will arise.

Reimplemented from NavGraph.

override void OnDrawGizmos ( bool  drawNodes)
virtual

Reimplemented from NavGraph.

void PostProcess ( )
static void RebuildBBTree ( NavMeshGraph  graph)
static

Rebuilds the BBTree on a NavGraph.

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
See Also
NavMeshGraph.bbTree
override void RelocateNodes ( Matrix4x4  oldMatrix,
Matrix4x4  newMatrix 
)
virtual

Relocates the nodes to match the newMatrix.

The "oldMatrix" variable can be left out in this function call (only for this graph generator) since it is not used

Reimplemented from NavGraph.

void ScanInternal ( string  objMeshPath)

Scans the graph using the path to an .obj mesh.

override void ScanInternal ( OnScanStatus  statusCallback)
virtual

Scans the graph, called from AstarPath.ScanInternal Override this function to implement custom scanning logic The statusCallback may be optionally called to show progress info in the editor

Implements NavGraph.

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

void Sort ( Vector3[]  a)
void UpdateArea ( GraphUpdateObject  o)
static void UpdateArea ( GraphUpdateObject  o,
INavmesh  graph 
)
static
void UpdateAreaInit ( GraphUpdateObject  o)

Member Data Documentation

BBTree _bbTree
private

Bounding Box Tree.

Enables really fast lookups of nodes.

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
Int3 [] _vertices
private
bool accurateNearestNode = true

More accurate nearest node queries.

When on, looks for the closest point on every triangle instead of if point is inside the node triangle in XZ space. This is slower, but a lot better if your mesh contains overlaps (e.g bridges over other areas of the mesh). Note that for maximum effect the Full Get Nearest Node Search setting should be toggled in A* Inspector Settings.

TriangleMeshNode [] nodes
Vector3 offset

Offset in world space.

Vector3 [] originalVertices
private
Vector3 rotation

Rotation in degrees.

float scale = 1

Scale of the graph.

Mesh sourceMesh

Mesh to construct navmesh from.

int [] triangles

Property Documentation

BBTree bbTree
getset
TriangleMeshNode [] TriNodes
get
Int3 [] vertices
getset

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