Navmesh "Chunks"

General Recast graph
1

Hello friends :slight_smile:

After quite a bit of experimentation , I don’t think building navmeshes during runtime will be a good idea for my game. I need a high level of precision (.1 or smaller cell size), and a pretty large area to map at a time… it ends up taking around 30 seconds or so, which isn’t too surprising.

The sad thing is I don’t even want to build navmeshes at runtime… my world is pretty static in this way, and if I could build the navmesh in editor that would be the best bet, since it would mean no recasting needed at all!

Of course, the problem is I can’t just build a massive navmesh of my entire world, that would be ridiculous. My original solution was going to be to build a chunk of navmesh at a time, since my world is split into “chunks” / scenes… however, using Unity’s base navmesh system, of course this results in separate, detached navmeshes.

And of course, the problem is the same with A* Pathfinding project. However, this code is “open”, so I think finding a solution here would be easier…

SO.

Let’s say I have a bunch of navmesh chunks. I need to stitch these together. Problem is, it won’t be easy, since there will be overlapping bits and alll sorts of other junk… for example, a rock may overlap onto another cell, so when the stitching happens, this would need to be accounted for…

Any thoughts? Ideas? Other solutions that don’t involve super complex mesh stitching? xD

Josh

EDIT: A 500x100x500 area (which is still too small, since I need npc’s to be able to walk pretty far) takes 39 seconds to scan. Makes sense since it’s a complex world, so I am going to go towards the idea of building it during edit time.

2

Here’s a visual that might help aid what I’m going for:

Essentially, in editor, I have a script that goes through each scene and builds lighting, one scene at a time. It would make sense to implement building navigation at the same time.

The reason for this is because I don’t think loading the entire world and building a massive navmesh is a good idea. Hence, per chunk.

HOLD UP, I HAVE AN IDEA:

What if these chunk navmeshes AS MESHES? Then load them up into the scene, then use the navmesh builder to generate a new navmesh based on these pre-created navmeshes? (Basically put these “pre-created meshes” onto a special layer for the Recaster to collect)

EDIT 2: Alright, I tried exporting the navmesh data to a mesh, and then tried using that as a basis for another navmesh calculation.

Problems:

  1. On edges of terrain chunks, the navmesh is not calculated to the edge, so there are gaps between navmesh meshes
    2: Since navmeshes are simplified, running a navmesh on a navmesh causes simplification + simplification, which results in many problems. Example: https://i.imgur.com/nIOGO8K.png (Orange line is pre-generated navmesh, navmesh is the navmesh built of this. Naturally, this doesn’t end up really working)
    3: It still takes 19 seconds to run the navmesh on this, so clearly this direction is not a good one. I’m assuming the bottleneck has little to do with collecting the meshes and such.

SO, I guess this is a dud solution… too bad :frowning:

3

Hi

Is there any reason your cells cannot be perfect squares? If they could be perfect squares then you could simplify everything immensely.

Having a massive navmesh loaded at the same time isn’t actually a big deal if it is completely static. It just contributes to additional memory usage, but for just pathfinding (no updates) it should be just as fast.

1 Like
4

Ahh I see. I think I could redesign my stuff to only be perfect squares, what are my options if I do this?

And oh, I see! I guess that is a possible route, although it means rebuilding the entire world at once in editor, which isn’t the best imo… but hey, it’s an option!

5

There is this sort of undocumented API which allows you to save and load individual tiles in a recast graph.

var graph = AstarPath.active.recastGraph;
var tile = graph.GetTile(0,0);
var tris = tile.tris;
var verts = tile.vertsInGraphSpace;
// ...maybe save verts and tris to a file or something
// then later when you load the graph you can do:
graph.ReplaceTile(0, 0, verts, tris);


// If you do many tile replacements at the same time you probably want to batch the update together though.
// Also you need to do it when it is safe to do so (i.e pathfinding is not running at the same time). Here is the full code:
AstarPath.active.AddWorkItem((context) => {
     var graph = AstarPath.active.recastGraph;
     graph.StartBatchTileUpdate();
     graph.ReplaceTile(0, 0, verts, tris);
     // ... additional tile replacements
     graph.EndBatchTileUpdate();

    // Flood fill everything to make sure graph areas are still valid
     context.QueueFloodFill();
});

So you would be able to scan your individual world chunks and then load them all up in the same world. Or you could load them when they are needed if necessary.

When you scan the tiles there is one important thing you need to do though. The tiles will only line up well if it knows a small region around the tile. So I recommend that you load the world up in 3x3 tiles (or more) and then only save the tiles in the middle.

1 Like
6

This looks brilliant!!! Somehow I never thought about loading just the neighbor tiles… HOW DID I NOT THINK OF THIS.

In fact, this brings up a new possibility… what if I loaded up 3x3 chunks, and then cut the navmesh from this? (In other words, not using the tile system in this case) I could then, during runtime, stitch these navmeshes together by finding duplicate vertices and attaching them…

EDIT: Regardless, one possible issue: since my world loads async as the player explores, these tiles would need to be replaced also during async… so pathfinding could be running… :confused: Is there a way to somehow pause the pathfinding and then continue after the replacement?

1 Like
7

Well, there is no guarantee that the navmesh vertices will line up perfectly. Even when using a normal tiled recast graph the tile vertices do not line up perfectly. There is some special code for handling connections across tile borders.

1 Like
8

Unless you can actually load the whole navmesh at once.
In any case, yes, if you use the AddWorkItem method as shown in the code sample above, that will take care of pausing pathfinding, applying the update and then resuming pathfinding once it is complete.

See AstarPath - A* Pathfinding Project

1 Like
9

Is there a way to convert a mesh to a navmesh? I wrote some code that can slice up a navmesh and then stitch it back together + wield it during runtime. If I can push this stitched mesh into the graph, this problem might be solved!

EDIT: I figured it out, very very simple to do. Here is what it looks like: (3x3 chunks)

It’s very strange, since it looks like a lot of the scene built correctly, but then a few of the chunks are completely disconnected somehow. I will be trying to figure this out now.

10

Hi

How are you doing the stiching? Using the ReplaceTile method as in the sample above?

The most likely cause is that while your tile’s border vertices may line up with each other, they need to line up with the expected tile borders for it to work. For debugging you could use the AstarPath.active.recastGraph.GetTileBounds(x,y) method to draw it in the scene view and see if it lines up with your tiles.

void OnDrawGizmos () {
    int x = 0;
    int y = 0;
    var bounds = AstarPath.active.recastGraph.GetTileBounds(x,y);
    Gizmos.DrawWireCube(bounds.center, bounds.size);
}
11

I’m currently trying a non replace tile approach, if this doesn’t work out I’ll try that out :slight_smile:

What I’m trying to do is actually stitch meshes, or weld them.

Here I used your navmesh builder, then tried my splitting/welding (originally I was using a mesh made by Unity’s built in navmesh triangulated mesh)

This time it makes sense… it looks like the edges aren’t connected? OR it’s almost as if there are extra vertices / edges floating around?

I’m using a welder from a script I found here: https://answers.unity.com/questions/228841/dynamically-combine-verticies-that-share-the-same.html

hmmm

EDIT 1: Also, after exporting a navmesh to a obj file, I imported it into blender and found something very strange… most of the vertices are not attached! Why is this? When I run “remove doubles” (which essentially does what I want Unity to do, welds any duplicate verts together) it finds 11k doubles…

This makes me question: why aren’t my chunks working? They should overlap exactly, since I’m using a tool that splits the mesh (https://github.com/DavidArayan/EzySlice) .

So if the mesh that is exported from A* works and has unattached/unwelded vertices and it works, why does my merged mesh with unattached/unwelded vertices not work? thinking emoji

EDIT 2: I imported my welded mesh into blender, and it’s welded correctly, far as I can tell… I am confused on why the A* navmesh has those colored lines on it :confused:

EDIT 3: Alright, I am officially confused. I re-exported that mesh from blender into Unity (The one that was stitched together in Unity, and exported to obj) and now… IT WORKS?

What this must mean is Blender must be doctoring the mesh somehow, or fixing it, or something… or perhaps the OBJ exporter is… I’m really not sure anymore.

12

If you export a tiled recast graph then all tiles are exported as is and different tiles do not share vertices. That’s probably why you are seeing duplicates. Connections between tiles are handled differently by the system and do not need to share vertices perfectly (the vertices do however need to lie exactly on the tile border for it to work).
If you import the mesh again as a navmesh graph then it will lose the tile information.

13

Oooh so the imported mesh thing in the picture above actually has no tiles, which is probably a problem…

So question. Say I have a mesh, I split it into 9 “tile” meshes. I then combine it into a single mesh, then plug it into the navmesh.

Why doesn’t this work?

This is strange since the splits should be EXACTLY the same as the tiles, and I’ve checked that this is true and it seems to fit exactly where the tiles would go… :confused:

EDIT: I think I am going to give up on the mesh thing, and go your way of doing tiles… it’s probably a LOT more easier heh heh

14

If you are using a navmesh graph to import this combined mesh, then it will just import it as if it were any other mesh. It will not recognize the tiles at all. It should work though if the vertices line up, not sure why it didn’t do that for you…

Yeah, if you do it using the ReplaceTile call, then the tiles should be recognized. One thing to note is that the ReplaceTile method takes the vertices in graph space, i.e they must be moved to where the tile is before you pass it to that function (the function RecastGraph.GetTileBoundsInGraphSpace may come in handy during testing).

1 Like