I want to roll my own NavMesh for my prototype, I think it would be good to know how NavMesh works and I need it to be flexible and high performance. However, I couldn’t find much resources for a NavMesh implementation, mostly on how to build the NavMesh.
Features I need:
-NavMesh depends on agent radius and max slope
-NavMesh can be updated at runtime
-Off-mesh links
-Different movement costs for different surfaces
-A* pathfinding on NavMesh
The algorithm I can currently think of, but don’t know if it’s the right way to go:
1- Collect all meshes that contribute to NavMesh.
2- Get all vertices of the meshes and convert to the world coordinates.
3- Somehow get walkable border vertices applying radius and slope to the world vertices.
4- Somehow create 2D convex polygons, in which an agent can safely move inside, from the vertex data.
5- Create a graph from the polygons and define neighbor relationships.
6- Run A* on graph to find paths.
7- Profit…
I have no clue how I’d implement 3-4. Hope you guys have some ideas.
You can just use unitys existing pathfinding. It’s actually fully job compatible.
I wrote a big post about this a year or so ago
Using the NavMeshQuery api
You can see an example in Unitys first demo
That all said, I’m currently in the process this weekend of porting Recast to hpc# with burst specific optimizations to roll my own implementation (mostly as a learning exercise)
It’s actually pretty easy and quite fast and has the benefit of getting full editor support already
in this pure entities test scene (random asset from asset store) the entire town only took 30ms asynchronously to generate navmeshes for. This picture is from like 6+ months ago, but if i recall correctly it’s around 8,000 meshes.
Navigation mesh is the canonical term and gives better search results.
recastnavigation is what every engine uses, with their own modifications here and there.
It’s way too complex an area to learn how it works by rolling your own.
Rolling your own from square one not having used recast or any other navmesh in an actual game setting so you understand the full scope of the problem, that’s months of work. I rolled our own based on wrappers around recast which is significantly less work then even a straight port. And it took probably 4-6 weeks all told counting all the refining/bug fixing that happened over time. The wrappers were just a day or so and once done basically never touched. But the complete scope here is far larger.
There are only a few edge cases where Unity’s navmesh isn’t sufficient.
I have a few questions
1- I’m getting RuntimeNavMeshBuilder: Source mesh Combined Mesh (root: scene) does not allow read access. This will work in playmode in the editor but not in player error. I just tried to work with default Cube. Do I need to make my meshes readable?
2- What do I use for the Bounds parameter (or how do I make sure it’s big enough)?
3- I’m a little bit confused by your code example. Shouldn’t I always use NavMeshBuildSourceShape.Mesh if I’m collecting geometry from the scene?
yes you need read access because you need to be able to read them on cpu
figure out it however it suits your game. if you break your world up into 64x64 navmesh regions then thats your bounds. if its much more dynamic you can just get the individual bounds of every mesh and use encapsulate to find the combined bounds of them all
if you’re only using your meshes sure. however for performance you can optimize this by using approximations for performance. replace plane meshes with cubes, or a bush might only need to be a capsule etc. same as you do with physics.
I don’t get it. I’m trying to convert 6 cubes to entity and adding them to the NavMesh, but all cubes get combined into a single mesh for some reason? Also all entities have the same position, render bounds etc… Is this how it’s supposed to work? I used NavMeshBuildSourceShape.Box with size (1,1,1) as input.
This is before conversion:
After conversion and calling
NavMeshBuilder.UpdateNavMeshDataAsync:
A while ago I made my own navmesh solution from the ground up. The generation isn’t bursted but path queries are (A* and Funnel).
It was 2d so for your point 2 and 3 you can use a 2d library like Clipper to combine meshes and then triangulate it. This also supports holes, layer costs and agent radia. For 3d this doesn’t work and you would have to look at recast how it does this with voxelization.
All that said, this is all not trivial at all and unless you want a learning project you’re much better off using an existing solution (as the others said… :))
@tertle I’m trying a very simple setup but I can’t see any NavMesh gizmos (blue) at runtime. Do I need to do extra setup for gizmos to work?
using System.Collections.Generic;
using Unity.Entities;
using UnityEngine;
using UnityEngine.AI;
public class TestNavSys : SystemBase
{
protected override void OnUpdate()
{
var agentID = 0;
var navMeshData = new NavMeshData(agentID);
var navMeshBuildSettings = NavMesh.GetSettingsByID(agentID);
var buildSources = new List<NavMeshBuildSource>();
var center = Vector3.zero;
var size = new Vector3(10000, 10000, 10000);
var bounds = new Bounds(center, size);
// Give me a single box please?
buildSources.Add(new NavMeshBuildSource
{
area = 0,
component = null,
shape = NavMeshBuildSourceShape.Box,
size = new Vector3(10, 10, 10),
sourceObject = null,
transform = Matrix4x4.TRS(Vector3.zero, Quaternion.identity, new Vector3(10, 10, 10))
});
var operation = NavMeshBuilder.UpdateNavMeshDataAsync(navMeshData, navMeshBuildSettings, buildSources, bounds);
operation.completed += OnCompleted;
Enabled = false;
Debug.Log("TestSys Run.");
}
void OnCompleted(AsyncOperation obj)
{
Debug.Log("Done Building NavMesh.");
}
}
Edit: I found it. I needed to call
NavMeshBuilder.BuildNavMeshData and
NavMesh.AddNavMeshData to build the NavMesh
