Class RecastGraph Extends NavmeshBase, IUpdatableGraph

Public

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.

How a recast graph works

When generating a recast graph what happens is that the world is voxelized. You can think of this as constructing an approximation of the world out of lots of boxes. If you have played Minecraft it looks very similar (but with smaller boxes).

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

Inner Types

Public Methods

CalculateTransform ()

Returns a new transform which transforms graph space to world space.

Public
ClosestPointOnNode (node, pos)

Returns the closest point of the node.

Public
ContainsPoint (node, pos)

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

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

Public

Public Variables

cellSize

Voxel sample size (x,z).

Public
characterRadius

Radius of the agent which will traverse the navmesh.

Public
colliderRasterizeDetail

Controls detail on rasterization of sphere and capsule colliders.

Public
contourMaxError

Max distance from simplified edge to real edge.

Public
editorTileSize

Size in voxels of a single tile.

Public
forcedBounds

World bounds for the graph.

Public
forcedBoundsCenter

Center of the bounding box.

Public
mask

Layer mask which filters which objects to include.

Public
maxEdgeLength

Longer edges will be subdivided.

Public
maxSlope

Max slope in degrees the character can traverse.

Public
minRegionSize

Minumum region size.

Public
rasterizeColliders

Use colliders to calculate the navmesh.

Public
rasterizeMeshes

Use scene meshes to calculate the navmesh.

Public
rasterizeTerrain

Include the Terrain in the scene.

Public
rasterizeTrees

Rasterize tree colliders on terrains.

Public
relevantGraphSurfaceMode

Require every region to have a RelevantGraphSurface component inside it.

Public
rotation

Rotation of the graph in degrees.

Public
scanEmptyGraph

If true, scanning the graph will yield a completely empty graph.

Public
tagMask

Objects tagged with any of these tags will be rasterized.

Public
terrainSampleSize

Controls how large the sample size for the terrain is.

Public
tileSizeX

Size of a tile along the X axis in voxels.

Public
tileSizeZ

Size of a tile along the Z axis in voxels.

Public
TileWorldSizeX
Public
TileWorldSizeZ
Public
useTiles

If true, divide the graph into tiles, otherwise use a single tile covering the whole graph.

Public
walkableClimb

Height the character can climb.

Public
walkableHeight

Character height.

Public

Public Static Variables

BorderVertexMask
Public Static
BorderVertexOffset
Public Static

Public Enums

RelevantGraphSurfaceMode
Public

Inherited Public Members

active

Reference to the AstarPath object in the scene.

Public
CountNodes ()

Number of nodes in the graph.

Public
drawGizmos

Enable to draw gizmos in the Unity scene view.

Public
enableNavmeshCutting

Should navmesh cuts affect this graph.

Public
EndBatchTileUpdate ()

End batch updating of tiles.

Public
forcedBoundsSize

Size of the bounding box.

Public
GetNearest (position)

Returns the nearest node to a position.

Public
GetNearest (position, constraint)

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

Public
GetNearest (position, constraint, hint)

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

Public
GetNearestForce (position, constraint)

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

Public
GetNodes (action)

Calls a delegate with all nodes in the graph until the delegate returns false.

Public
GetNodes (action)

Calls a delegate with all nodes in the graph.

Public
GetTile (x, z)

Tile at the specified x, z coordinate pair.

Public
GetTileBounds (rect)

Returns a bounds object with the bounding box of a group of tiles.

Public
GetTileBounds (x, z, width=1, depth=1)

Returns a bounds object with the bounding box of a group of tiles.

Public
GetTileBoundsInGraphSpace (rect)
Public
GetTileBoundsInGraphSpace (x, z, width=1, depth=1)

Returns an XZ bounds object with the bounds of a group of tiles in graph space.

Public
GetTileCoordinates (position)

Returns the tile coordinate which contains the specified position.

Public
GetTileCoordinates (tileIndex, x, z)

Tile coordinates from a tile index.

Public
GetTileIndex (index)

Tile index from a vertex index.

Public Static
GetTiles ()

All tiles.

Public
GetTouchingTiles (bounds, margin=0)

Returns a rect containing the indices of all tiles touching the specified bounds.

Public
GetTouchingTilesInGraphSpace (rect)

Returns a rect containing the indices of all tiles touching the specified bounds.

Public
GetTouchingTilesRound (bounds)

Returns a rect containing the indices of all tiles by rounding the specified bounds to tile borders.

Public
GetVertex (index)

Vertex coordinate for the specified vertex index.

Public
GetVertexArrayIndex (index)
Public
GetVertexInGraphSpace (index)

Vertex coordinate in graph space for the specified vertex index.

Public
graphIndex

Index of the graph, used for identification purposes.

Public
guid

Used as an ID of the graph, considered to be unique.

Public
infoScreenOpen

Used in the editor to check if the info screen is open.

Public
initialPenalty

Default penalty to apply to all nodes.

Public
inverseMatrix

Inverse of matrix.

Public
Linecast (origin, end)

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

Public
Linecast (origin, end, hint)

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

Public
Linecast (origin, end, hint, hit)

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

Public
Linecast (origin, end, hit, trace, filter)

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

Public
Linecast (origin, end, hint, hit, trace)

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

Public
Linecast (graph, origin, end, hint, hit)

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

Public Static
Linecast (graph, origin, end, hint, hit, trace, filter=null)

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

Public Static
matrix

A matrix for translating/rotating/scaling the graph.

Public
name

Name of the graph.

Public
nearestSearchOnlyXZ

Perform nearest node searches in XZ space only.

Public
OnDrawGizmos (gizmos, drawNodes, redrawScope)

Draw gizmos for the graph.

Public
OnRecalculatedTiles

Called when tiles have been completely recalculated.

Public
open

Is the graph open in the editor.

Public
PointOnNavmesh (position, constraint)

Finds the first node which contains position.

Public
RelocateNodes (deltaMatrix)

Moves the nodes in this graph.

Public
RelocateNodes (newTransform)

Moves the nodes in this graph.

Public
RelocateNodes (oldMatrix, newMatrix)

Moves nodes in this graph.

Public
ReplaceTile (x, z, verts, tris)

Replace tile at index with nodes created from specified navmesh.

Public
Scan ()

Scan the graph.

Public
ScanGraph ()

Scan the graph.

Public
SetMatrix (m)

Use to set both matrix and inverseMatrix at the same time.

Public
showMeshOutline

Show an outline of the polygons in the Unity Editor.

Public
showMeshSurface

Show the surface of the navmesh.

Public
showNodeConnections

Show the connections between the polygons in the Unity Editor.

Public
StartBatchTileUpdate ()

Start batch updating of tiles.

Public
TileIndexMask
Public Static
TileIndexOffset
Public Static
tileXCount

Number of tiles along the X-axis.

Public
tileZCount

Number of tiles along the Z-axis.

Public
transform

Determines how the graph transforms graph space to world space.

Public
VertexIndexMask
Public Static

Private/Protected Members

BuildTileMesh (vox, x, z, threadIndex=0)
Protected
CalculateTileBoundsWithBorder (x, z)
Private
CanUpdateAsync (o)
Private
CellHeight
Private
CharacterRadiusInVoxels

Convert character radius to a number of voxels.

Private
ClearTile (x, z)

Clear the tile at the specified coordinate.

Protected
CollectMeshes (bounds)
Private
ConnectTiles (tile1, tile2, tileWorldSizeX, tileWorldSizeZ, maxTileConnectionEdgeDistance)

Generate connections between the two tiles.

Protected Static
ConnectTileWithNeighbours (tile, onlyUnflagged=…)
Protected
ConvertUnsafeBufferToArray< T > (src)
Private Static
CreateNodeConnections (nodes)

Create connections between all nodes.

Protected Static
CreateNodes (tile, tris, tileIndex, graphIndex, tags, astar, initialPenalty, recalculateNormals)
Protected Static
CreateTile (mesh, x, z, threadIndex)

Create a tile at tile index x, z from the mesh.

Private
DeserializeExtraInfo (ctx)

Deserializes graph type specific node data.

Protected
DeserializeSettingsCompatibility (ctx)

An old format for serializing settings.

Protected
DestroyAllNodes ()

Destroys all nodes in the graph.

Protected
DisposeUnmanagedData ()

Cleans up any unmanaged data that the graph has.

Protected
DrawUnwalkableNodes (gizmos, size, redrawScope)
Protected
exists

True if the graph exists, false if it has been destroyed.

Package
FillWithEmptyTiles ()

Fills graph with tiles created by NewEmptyTile.

Protected
InitializeTileInfo ()
Private
MaxTileConnectionEdgeDistance
Protected
navmeshUpdateData

Handles navmesh cutting.

NewEmptyTile (x, z)

Creates a single new empty tile.

Protected
OnDestroy ()

Function for cleaning up references.

Protected
pendingGraphUpdatePromise
Private
pendingGraphUpdateRect
Private
PostDeserialization (ctx)

Called after all deserialization has been done for all graphs.

Protected
PutMeshesIntoTileBuckets (meshes, tileBuckets)

Creates a list for every tile and adds every mesh that touches a tile to the corresponding list.

Private
RecalculateNormals
Protected
RemoveConnectionsFromTile (tile)
Protected
RemoveConnectionsFromTo (a, b)
Protected
ScanAllTiles ()
Protected
ScanAllTilesBurst (async)
Protected
ScanInternal ()

Internal method to scan the graph.

Protected
ScanInternal (async)

Internal method to scan the graph.

Protected
SerializeExtraInfo (ctx)

Serializes Node Info.

Protected
stagingTiles

List of tiles that have been calculated in a graph update, but have not yet been added to the graph.

Private
TileBorderSizeInVoxels

Number of extra voxels on each side of a tile to ensure accurate navmeshes near the tile border.

Private
TileBorderSizeInWorldUnits
Private
tiles

All tiles.

Protected
UpdateArea (o)

Updates an area using the specified #GraphUpdateObject.

Private
UpdateAreaInit (o)

May be called on the Unity thread before starting the update.

Private
UpdateAreaPost (guo)

Called on the Unity thread to complete a graph update.

Private