Automatically generates navmesh graphs based on world geometry.
The recast graph is based on Recast (http://code.google.com/p/recastnavigation/).
I have translated a good portion of it to C# to run it natively in Unity. The Recast process is described as follows:
- The voxel mold is build from the input triangle mesh by rasterizing the triangles into a multi-layer heightfield. Some simple filters are then applied to the mold to prune out locations where the character would not be able to move.
- The walkable areas described by the mold are divided into simple overlayed 2D regions. The resulting regions have only one non-overlapping contour, which simplifies the final step of the process tremendously.
- The navigation polygons are peeled off from the regions by first tracing the boundaries and then simplifying them. The resulting polygons are finally converted to convex polygons which makes them perfect for pathfinding and spatial reasoning about the level.
It works exactly like that in the C# version as well, except that everything is triangulated to triangles instead of n-gons. The recast generation process usually works directly on the visiable geometry in the world, this is usually a good thing, because world geometry is usually more detailed than the colliders. You can however specify that colliders should be rasterized, if you have very detailed world geometry, this can speed up the scan.
Check out the second part of the Get Started Tutorial which discusses recast graphs.
Exporting for manual editing
In the editor there is a button for exporting the generated graph to a .obj file. Usually the generation process is good enough for the game directly, but in some cases you might want to edit some minor details. So you can export the graph to a .obj file, open it in your favourite 3D application, edit it, and export it to a mesh which Unity can import. You can then use that mesh in a navmesh graph.
Since many 3D modelling programs use different axis systems (unity uses X=right, Y=up, Z=forward), it can be a bit tricky to get the rotation and scaling right. For blender for example, what you have to do is to first import the mesh using the .obj importer. Don't change anything related to axes in the settings. Then select the mesh, open the transform tab (usually the thin toolbar to the right of the 3D view) and set Scale -> Z to -1. If you transform it using the S (scale) hotkey, it seems to set both Z and Y to -1 for some reason. Then make the edits you need and export it as an .obj file to somewhere in the Unity project. But this time, edit the setting named "Forward" to "Z forward" (not -Z as it is per default).
- 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 GraphTransform | CalculateTransform () |
| Returns a new transform which transforms graph space to world space.
|
|
Vector3 | ClosestPointOnNode (TriangleMeshNode node, Vector3 pos) |
| Returns the closest point of the node.
|
|
bool | ContainsPoint (TriangleMeshNode node, Vector3 pos) |
| Returns if the point is inside the node in XZ space.
|
|
void | SnapForceBoundsToScene () |
| Changes the bounds of the graph to precisely encapsulate all objects in the scene that can be included in the scanning process based on the settings.
|
|
void | EndBatchTileUpdate () |
| End batch updating of tiles.
|
|
override NNInfoInternal | GetNearest (Vector3 position, NNConstraint constraint, GraphNode hint) |
| Returns the nearest node to a position using the specified NNConstraint.
|
|
override NNInfoInternal | GetNearestForce (Vector3 position, NNConstraint constraint) |
| Returns the nearest node to a position using the specified constraint .
|
|
override void | GetNodes (System.Action< GraphNode > action) |
| Calls a delegate with all nodes in the graph.
|
|
NavmeshTile | GetTile (int x, int z) |
| Tile at the specified x, z coordinate pair.
|
|
Bounds | GetTileBounds (IntRect rect) |
| Returns an XZ bounds object with the bounds of a group of tiles.
|
|
Bounds | GetTileBounds (int x, int z, int width=1, int depth=1) |
| Returns an XZ bounds object with the bounds of a group of tiles.
|
|
Bounds | GetTileBoundsInGraphSpace (IntRect rect) |
|
Bounds | GetTileBoundsInGraphSpace (int x, int z, int width=1, int depth=1) |
| Returns an XZ bounds object with the bounds of a group of tiles in graph space.
|
|
void | GetTileCoordinates (int tileIndex, out int x, out int z) |
| Tile coordinates from a tile index.
|
|
Int2 | GetTileCoordinates (Vector3 position) |
| Returns the tile coordinate which contains the specified position.
|
|
NavmeshTile[] | GetTiles () |
| All tiles.
|
|
IntRect | GetTouchingTiles (Bounds bounds) |
| Returns a rect containing the indices of all tiles touching the specified bounds.
|
|
IntRect | GetTouchingTilesInGraphSpace (Rect rect) |
| Returns a rect containing the indices of all tiles touching the specified bounds.
|
|
IntRect | GetTouchingTilesRound (Bounds bounds) |
| Returns a rect containing the indices of all tiles by rounding the specified bounds to tile borders.
|
|
Int3 | GetVertex (int index) |
| Vertex coordinate for the specified vertex index.
|
|
int | GetVertexArrayIndex (int index) |
|
Int3 | GetVertexInGraphSpace (int index) |
| Vertex coordinate in graph space for the specified vertex 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 | OnDrawGizmos (Pathfinding.Util.RetainedGizmos gizmos, bool drawNodes) |
|
GraphNode | PointOnNavmesh (Vector3 position, NNConstraint constraint) |
| Finds the first node which contains position.
|
|
override void | RelocateNodes (Matrix4x4 deltaMatrix) |
| Moves the nodes in this graph.
|
|
void | RelocateNodes (GraphTransform newTransform) |
| Moves the nodes in this graph.
|
|
void | ReplaceTile (int x, int z, Int3[] verts, int[] tris) |
| Replace tile at index with nodes created from specified navmesh.
|
|
void | ReplaceTile (int x, int z, int w, int d, Int3[] verts, int[] tris) |
| Replaces a tile with a new mesh.
|
|
void | StartBatchTileUpdate () |
| Start batch updating of tiles.
|
|
virtual int | CountNodes () |
| Number of nodes in the graph.
|
|
NNInfoInternal | GetNearest (Vector3 position) |
| Returns the nearest node to a position using the default NNConstraint.
|
|
NNInfoInternal | GetNearest (Vector3 position, NNConstraint constraint) |
| Returns the nearest node to a position using the specified NNConstraint.
|
|
void | GetNodes (System.Func< GraphNode, bool > action) |
| Calls a delegate with all nodes in the graph until the delegate returns false.
|
|
virtual void | OnDrawGizmos (RetainedGizmos gizmos, bool drawNodes) |
| Draw gizmos for the graph.
|
|
void | RelocateNodes (Matrix4x4 oldMatrix, Matrix4x4 newMatrix) |
| Moves nodes in this graph.
|
|
void | Scan () |
| Scan the graph.
|
|
void | ScanGraph () |
| Scan the graph.
|
|
void | SetMatrix (Matrix4x4 m) |
| Use to set both matrix and inverseMatrix at the same time.
|
|
void | DeserializeExtraInfo (GraphSerializationContext ctx) |
|
void | DeserializeSettingsCompatibility (GraphSerializationContext ctx) |
|
void | DestroyAllNodes () |
|
void | OnDestroy () |
|
void | PostDeserialization (GraphSerializationContext ctx) |
|
IEnumerable< Progress > | ScanInternal () |
|
void | SerializeExtraInfo (GraphSerializationContext ctx) |
|
void | GetNodes (System.Action< GraphNode > del) |
|
void | GetTileCoordinates (int tileIndex, out int x, out int z) |
| Transforms coordinates from graph space to world space.
|
|
Int3 | GetVertex (int i) |
| Position of vertex number i in the world.
|
|
int | GetVertexArrayIndex (int index) |
|
Int3 | GetVertexInGraphSpace (int i) |
| Position of vertex number i in coordinates local to the graph.
|
|
GraphUpdateThreading | CanUpdateAsync (GraphUpdateObject o) |
|
void | UpdateArea (GraphUpdateObject o) |
| Updates an area using the specified GraphUpdateObject.
|
|
void | UpdateAreaInit (GraphUpdateObject o) |
| May be called on the Unity thread before starting the update.
|
|
void | UpdateAreaPost (GraphUpdateObject o) |
| May be called on the Unity thread after executing the update.
|
|
|
NavmeshTile | BuildTileMesh (Voxelize vox, int x, int z, int threadIndex=0) |
|
override void | DeserializeSettingsCompatibility (GraphSerializationContext ctx) |
| An old format for serializing settings.
|
|
IEnumerable< Progress > | ScanAllTiles () |
|
override IEnumerable< Progress > | ScanInternal () |
| Internal method to scan the graph.
|
|
void | ClearTiles (int x, int z, int w, int d) |
| Clear all tiles within the rectangle with one corner at (x,z), width w and depth d.
|
|
void | ConnectTiles (NavmeshTile tile1, NavmeshTile tile2) |
| Generate connections between the two tiles.
|
|
void | ConnectTileWithNeighbours (NavmeshTile tile, bool onlyUnflagged=false) |
|
TriangleMeshNode[] | CreateNodes (int[] tris, int tileIndex, uint graphIndex) |
|
override void | DeserializeExtraInfo (GraphSerializationContext ctx) |
| Deserializes graph type specific node data.
|
|
void | FillWithEmptyTiles () |
| Fills graph with tiles created by NewEmptyTile.
|
|
NavmeshTile | NewEmptyTile (int x, int z) |
| Creates a single new empty tile.
|
|
override void | OnDestroy () |
| Function for cleaning up references.
|
|
override void | PostDeserialization (GraphSerializationContext ctx) |
| Called after all deserialization has been done for all graphs.
|
|
void | RemoveConnectionsFromTile (NavmeshTile tile) |
|
void | RemoveConnectionsFromTo (NavmeshTile a, NavmeshTile b) |
|
override void | SerializeExtraInfo (GraphSerializationContext ctx) |
| Serializes Node Info.
|
|
virtual void | DestroyAllNodes () |
| Destroys all nodes in the graph.
|
|
void | DrawUnwalkableNodes (float size) |
|
|
void | BuildTiles (Queue< Int2 > tileQueue, List< RasterizationMesh >[] meshBuckets, ManualResetEvent doneEvent, int threadIndex) |
|
Bounds | CalculateTileBoundsWithBorder (int x, int z) |
|
GraphUpdateThreading
IUpdatableGraph. | CanUpdateAsync (GraphUpdateObject o) |
|
List< RasterizationMesh > | CollectMeshes (Bounds bounds) |
|
void | ConnectTiles (Queue< Int2 > tileQueue, ManualResetEvent doneEvent, bool xDirection, bool zDirection) |
| Connects all tiles in the queue with the tiles to the right (x+1) side of them or above them (z+1) depending on xDirection and zDirection.
|
|
NavmeshTile | CreateTile (Voxelize vox, VoxelMesh mesh, int x, int z, int threadIndex) |
| Create a tile at tile index x, z from the mesh.
|
|
void | InitializeTileInfo () |
|
List< RasterizationMesh >[] | PutMeshesIntoTileBuckets (List< RasterizationMesh > meshes) |
| Creates a list for every tile and adds every mesh that touches a tile to the corresponding list.
|
|
void IUpdatableGraph. | UpdateArea (GraphUpdateObject guo) |
|
void IUpdatableGraph. | UpdateAreaInit (GraphUpdateObject o) |
|
void IUpdatableGraph. | UpdateAreaPost (GraphUpdateObject guo) |
| Called on the Unity thread to complete a graph update.
|
|
Require every region to have a RelevantGraphSurface component inside it.
A RelevantGraphSurface component placed in the scene specifies that the navmesh region it is inside should be included in the navmesh.
If this is set to OnlyForCompletelyInsideTile a navmesh region is included in the navmesh if it has a RelevantGraphSurface inside it, or if it is adjacent to a tile border. This can leave some small regions which you didn't want to have included because they are adjacent to tile borders, but it removes the need to place a component in every single tile, which can be tedious (see below).
If this is set to RequireForAll a navmesh region is included only if it has a RelevantGraphSurface inside it. Note that even though the navmesh looks continous between tiles, the tiles are computed individually and therefore you need a RelevantGraphSurface component for each region and for each tile.
In the above image, the mode OnlyForCompletelyInsideTile was used. Tile borders are highlighted in black. Note that since all regions are adjacent to a tile border, this mode didn't remove anything in this case and would give the same result as DoNotRequire. The
RelevantGraphSurface component is shown using the green gizmo in the top-right of the blue plane.
In the above image, the mode RequireForAll was used. No tiles were used. Note that the small region at the top of the orange cube is now gone, since it was not the in the same region as the relevant graph surface component. The result would have been identical with OnlyForCompletelyInsideTile since there are no tiles (or a single tile, depending on how you look at it).
The mode RequireForAll was used here. Since there is only a single
RelevantGraphSurface component, only the region it was in, in the tile it is placed in, will be enabled. If there would have been several
RelevantGraphSurface in other tiles, those regions could have been enabled as well.
Here another tile size was used along with the OnlyForCompletelyInsideTile. Note that the region on top of the orange cube is gone now since the region borders do not intersect that region (and there is no
RelevantGraphSurface component inside it).
- Note
- When not using tiles. OnlyForCompletelyInsideTile is equivalent to RequireForAll.