Custom Navmesh Generation

This section gives an overview of how to support navmesh pathfinding with procedurally generated game levels.

Quantum does not have a complete deterministic navmesh baking tool but there are a few alternatives to support generated navmeshes.

Two approaches are feasible:

• Generate the navmesh on one client and share with others
• Deterministically generate BakeData on each client and bake the navmesh locally

As a reminder: When the expected agent count is high (>100) a different pathfinding solution might be better and even more compatible with procedural level generation: E.g. tile based pathfinder, flow fields.

We previously recommended Asset Injection and DynamicAssets as a tool to customize and share navmeshes, but this puts too much pressure on the sensible Quantum realtime protocol.

Generating And Sharing A Navmesh

This solution lets one client bake the navmesh using the Unity tools and then share it with each other client. Because of its lengthy and impactful process it is best to synchronize this before any client started the Quantum simulation.

Lacking an API to safely add Quantum assets to the Quantum DB before loading anything a NavMeshAsset and its BinaryDataAsset content are simply replaced.

• Bake Unity Navmesh
• MapNavMesh.ImportFromUnity()
• MapNavMeshBaker.BakeNavMesh()
• Upload To File Server
• Download From File Server
• Replace Navmesh
• Start Quantum

Selecting the client to generate the navmesh can be done by using the admin Photon client or utilizing a custom backend.

Sample to replace the navmesh binary data

C#

// Make sure to dispose the UnityDB after each game
UnityDB.Dispose();

// Load the pre-existing navmesh data asset
var navmeshData = UnityDB.FindAsset<BinaryDataAsset>(4350045557267041182).Settings;

// This would need to be replaced by download the file from a server
var newNavmeshData = UnityEngine.Resources.Load<BinaryDataAsset>("NewNavmeshData");

// Replace the navmesh data that is loaded with the pre-existing navmesh asset
// Grid and world sizes etc must match, regions will be added to the map correctly
navmeshData.Data = newNavmeshData.Settings.Data;

// QuantumRunner.StartGame()

Deterministically Generating Navmesh BakeData

This approach does not require the Unity navmesh baking instead it works with parts of the navmesh being procedurally generated and then baked into a Quantum navmesh. Because the input data (BakeData) is already a navmesh and not a collection of colliders (as used by the Unity navmesh generation) this solution works well when it can be stitched together from pre-generated navmesh parts or triangles can be generated with a simple pattern. See section below about the internals of the BakeData object.

Requirements:

• navmesh-deterministic-baking branch for SDK 2.1 (please contact us)
• MapNavMesh.BakeData creation needs to be deterministic

The BakeData is generated by each client individually in a deterministic way which removes the necessity to share it with others but late-joiners also have to go through this process.

The completed BakeData will be used to generate a Quantum navmesh.

C#

// Bake navmesh asset
var navmesh = NavmeshBaker.BakeNavMesh(f.Map, bakeData);

The result can also replaces a dummy navmesh data asset like in the section before or it could replace an existing navmesh with a runtime navmesh.

Sample to replace the runtime navmesh before start

Replacing the asset this way must be done before the navmesh is loaded through the UnityDB and before the simulation has started. The Unity navmesh asset is loaded to replace the Quantum asset inside it (.Settings) and the Guid and Path values are copied. Invalidating the .DataAsset will prevent the deserialization of the binary navmesh asset (_data asset) when it is finally loaded by Quantum.

C#

// BakeData needs to be procedurally generated
var bakeData = default(NavmeshBakeData);
var newNavmesh = NavmeshBaker.BakeNavMesh(map, bakeData);

// Load navmesh asset to replace
var navmeshAsset = UnityEngine.Resources.Load<NavMeshAsset>("DB/TestNavMeshAgents/NavMeshToReplace");

// Replace the navmesh content
newNavmesh.Guid = navmeshAsset.Settings.Guid;
newNavmesh.Path = navmeshAsset.Settings.Path;
navmeshAsset.Settings = newNavmesh;

// Invalidate the navmesh data (because it has been generated during runtime it's already loaded)
navmeshAsset.Settings.DataAsset.Id = AssetGuid.Invalid;
navmeshAsset.Settings.Name = "MyNavmesh";

// QuantumRunner.StartGame()

Sample to replace the runtime navmesh during start

In this code sample an already loaded dummy navmesh is replaced with a runtime generated navmesh during the OnGameStart and OnGameResync callbacks.

Replacing a navmesh during the game is also possible this way:

• Only during a verified frame
• All information and parameters to bake the navmesh have to be available on the frame (e.g. Singleton component or globals) for late-joiners to be able to generate the correct navmesh when resyncing.

C#

namespace Quantum {
  using Quantum.Experimental;

  public class RuntimeNavmeshBaking : QuantumCallbacks {
    public override void OnGameStart(QuantumGame game) {
      // In this sample the bake data has already been created, but it should be assembled during runtime
      var bakeData = UnityEngine.Resources.Load<BakeDataSO>("BakeData");
      ReplaceNavmesh(game.Frames.Verified.Map, 1356438205741681193, bakeData.BakeData);
    }

    public override void OnGameResync(QuantumGame game) {
      var bakeData = UnityEngine.Resources.Load<BakeDataSO>("BakeData");
      ReplaceNavmesh(game.Frames.Verified.Map, 1356438205741681193, bakeData.BakeData);
    }

    private static void ReplaceNavmesh(Map map, AssetGuid navmeshGuid, NavmeshBakeData bakeData) {
      var newNavmesh = NavmeshBaker.BakeNavMesh(map, bakeData);
      var navmeshAsset = UnityDB.FindAsset<NavMeshAsset>(navmeshGuid);
      // cannot change name or regions without manipulating the map too
      navmeshAsset.Settings.GridSizeX = newNavmesh.GridSizeX;
      navmeshAsset.Settings.GridSizeY = newNavmesh.GridSizeY;
      navmeshAsset.Settings.GridNodeSize = newNavmesh.GridNodeSize;
      navmeshAsset.Settings.WorldOffset = newNavmesh.WorldOffset;
      navmeshAsset.Settings.MinAgentRadius = newNavmesh.MinAgentRadius;
      navmeshAsset.Settings.Triangles = newNavmesh.Triangles;
      navmeshAsset.Settings.TrianglesGrid = newNavmesh.TrianglesGrid;
      navmeshAsset.Settings.Vertices = newNavmesh.Vertices;
      navmeshAsset.Settings.BorderGrid = newNavmesh.BorderGrid;
      navmeshAsset.Settings.TrianglesCenterGrid = newNavmesh.TrianglesCenterGrid;
      navmeshAsset.Settings.Borders = newNavmesh.Borders;
      navmeshAsset.Settings.Links = newNavmesh.Links;
    }
  }
}

namespace Quantum {
  using Quantum.Experimental;
  using UnityEngine;

  public class BakeDataSO : ScriptableObject {
    public NavmeshBakeData BakeData;
  }
}

MapNavMesh.BakeData

The MapNavMesh.BakeData is a complete mesh that is then further processed and converted to a Quantum navmesh. The mesh is build in the way of a triangle strip.

The recommended process is to generate the intermediate navmesh format MapNavMesh.BakeData and run this through MapNavMeshBaker.BakeNavMesh(MapData data, MapNavMesh.BakeData navmeshBakeData) which uses the triangle information from the BakeData to fill out all required data structures of a Quantum navmesh.

MapNavMeshBaker.BakeNavMesh() was developed to be used during edit time and replacing it entirely could yield performance improvements, but also would be a much more elaborate task.

MapNavMesh.BakeData Class

Type	Field	Description
String	Name	The name of the navmesh accessible inside the simulation by f.Map.NavMeshes[name]
Vector3	Position	The position of the navmesh. Final navmesh vertices are stored in global space and their positions are translated by this during baking.
FP	AgentRadius	The radius of the largest agents that the navmesh is created for. Older versions of Quantum were permitting different agent radii, but that has been abolished. Now, agents can walk up until their pivot is on the edge of the navmesh. This way the margin agents should keep away from walls is baked into the triangles. This value is only used to render debug graphics.
List<string>	Regions	All regions ids that are used in this navmesh. During baking the region ids will be added to the Region list of the Map asset and their index is baked into the navmesh triangles region mask (NavMeshTriangle.Regions). The regions are aggregated on the map because a map can have multiple navmeshes that share the region ids.
MapNavMeshVertex[]	Vertices	The vertices of the navmesh.
MapNavMeshTriangle[]	Triangles	The triangle of the navmesh. This is a regular mesh data structure where the triangles and vertices are kept in two separate arrays and the triangle points into the vertex array to mark their 3 vertices.
MapNavMeshLink[]	Links	Link between positions on the same navmesh.
enum	ClosestTriangleCalculation	The Quantum navmesh uses a grid for spatial partitioning. Each grid cell will have a fallback triangle assigned. The default search is quite slow (BruteForce) while SpiralOut more efficient is but it could result in empty fallback triangles.
int	ClosestTriangleCalculationDepth	The number of grid cells to expand the SpiralOut search.
bool	EnableQuantum_XY	When enabled the navmesh baking will flip Y and Z components of the vertex positions to support navmeshes generated in the XY plane.
bool	LinkErrorCorrection	Automatically correct navmesh link positions to the closest triangle during baking.

MapNavMeshTriangle Class

Triangles are expected to have clock-wise winding order.
Not all fields have to be filled out. Some of them are only needed for the legacy navmesh drawing tool.

Type	Field	Description
String	Id	Not required
String[]	VertexIds	Must have length of 3. The referenced vertices as ids. Required for SDK 2.1. or earlier.
Int32[]	VertexIds2	Must have length of 3. The referenced vertices as indices into the vertex array. Required for SDK 2.2.
Int32	Area	Not required
String	RegionId	The region that this triangle belongs to. Default is null.
FP	Cost	The cost of the triangle. Default should be FP._1.

MapNavMeshVertex Class

The types of Position has been replaced by FPVector3 SDK 2.2.

Type	Field	Description
String	Id	Required for SDK 2.1 or earlier
Vector3	Position	The position of the vertex
List<Int32>	Neighbors	Not required
List<Int32>	Triangles	Not required

MapNavMeshLink Class

The types of Start, End and CostOveride have been replaced by FPVector3 and FP respectively in SDK 2.2.

Type	Field	Description
Vector3	Start	Start position of the link. Must be on the same navmesh.
Vector3	End	End position of the link. Must be on the same navmesh.
bool	Bidirectional	Can the link be traversed from both directions.
float	CostOverride	The cost of the connection.
String	RegionId	The region id that the link belongs to. Default is null.
String	Name	The name of the link. Can be queried by navmesh.Links[NavMeshPathfinder.CurrentLink()].Name.

Snippet

C#

// Generate simple navmesh BakeData
var bakeData = new MapNavMesh.BakeData() {
  AgentRadius = FP._0_20,
  ClosestTriangleCalculation = MapNavMesh.FindClosestTriangleCalculation.SpiralOut,
  ClosestTriangleCalculationDepth = 1,
  Name = "DynamicNavmesh",
  PositionFP = FPVector3.Zero,
  Regions = new System.Collections.Generic.List<string>(),
  Vertices = new MapNavMeshVertexFP[] {
    new MapNavMeshVertexFP { Position = FPVector3.Forward },
    new MapNavMeshVertexFP { Position = FPVector3.Right },
    new MapNavMeshVertexFP { Position = -FPVector3.Forward},
    new MapNavMeshVertexFP { Position = -FPVector3.Right},
  },
  Triangles = new MapNavMeshTriangle[] {
    new MapNavMeshTriangle { VertexIds2 = new int[] { 0, 1, 2}, Cost = FP._1 },
    new MapNavMeshTriangle { VertexIds2 = new int[] { 0, 2, 3}, Cost = FP._1 }
  }
};

Back to top