Resolved Any tips on coding a Dots NavMesh?

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.

 

Have you tried use Unity na mesh? If I remember correctly, there are few discussion on the topic, here in DOTS forum.

 

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
https://forum.unity.com/threads/navmeshsurface-updatenavmesh-with-a-entity.766148/#post-5110340

Using the NavMeshQuery api
https://docs.unity3d.com/ScriptReference/Experimental.AI.NavMeshQuery.html

You can see an example in Unitys first demo
https://github.com/Unity-Technologies/UniteAustinTechnicalPresentation



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)

 

This looks a little bit complicated, but I want to give it a try before rolling my own since it looks like there aren't many guides on this subject.

 

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 value your and @tertle 's experiences, I'll make it work with Unity NavMesh

 

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?

 

1. yes you need read access because you need to be able to read them on cpu
2. 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
3. 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:

 

Hey.

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

 

I realized this problem isn't related to NavMesh at all, it happens if I try to convert cubes when they have Static ticked.

Edit: I solved this by disabling Static batching.

 

@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?

Code (CSharp):

1. using System.Collections.Generic;
2. using Unity.Entities;
3. using UnityEngine;
4. using UnityEngine.AI;
5.  
6. public class TestNavSys : SystemBase
7. {
8.     protected override void OnUpdate()
9.     {
10.         var agentID = 0;
11.         var navMeshData = new NavMeshData(agentID);
12.         var navMeshBuildSettings = NavMesh.GetSettingsByID(agentID);
13.         var buildSources = new List<NavMeshBuildSource>();
14.         var center = Vector3.zero;
15.         var size = new Vector3(10000, 10000, 10000);
16.         var bounds = new Bounds(center, size);
17.  
18.         // Give me a single box please?
19.         buildSources.Add(new NavMeshBuildSource
20.         {
21.             area = 0,
22.             component = null,
23.             shape = NavMeshBuildSourceShape.Box,
24.             size = new Vector3(10, 10, 10),
25.             sourceObject = null,
26.             transform = Matrix4x4.TRS(Vector3.zero, Quaternion.identity, new Vector3(10, 10, 10))
27.         });
28.  
29.         var operation = NavMeshBuilder.UpdateNavMeshDataAsync(navMeshData, navMeshBuildSettings, buildSources, bounds);
30.         operation.completed += OnCompleted;
31.         Enabled = false;
32.  
33.         Debug.Log("TestSys Run.");
34.     }
35.  
36.     void OnCompleted(AsyncOperation obj)
37.     {
38.         Debug.Log("Done Building NavMesh.");
39.     }
40. }

Edit: I found it. I needed to call
NavMeshBuilder.BuildNavMeshData and
NavMesh.AddNavMeshData to build the NavMesh

 

Anyone done binaryheaps in jobs for this?

Oh, mind the never, I found this, which seems promising: https://forum.unity.com/threads/pri...implementation-with-native-containers.569161/

(Still would like to know, though...)

 

hi there,

has anyone used the new function "NavMeshBuildSettings.preserveTilesOutsideBounds"?

i want to ask if its possible to provide a new smaller bounding box because when im providing the original bounds its taking a toll on performance

 

I don't suppose there's an more up to date simpler method of using the Navmesh in Dots, because this does not seem easy to use this way to me.

 

Any reason why NavMeshQuery is sitll in experimental namespace in 2022 and 2023? Quick search of issues shows only this one https://issuetracker.unity3d.com/is...aned-up-but-not-deregistered-from-the-navmesh

 

Probably because they haven't brought the full API. I needed to bring some code from their Austin presentation in order to construct path etc.