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