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

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.

MapNavMeshVertex Class

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

MapNavMeshLink Class

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

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 }
  }
};