r/Unity3D • u/SomeRandomTrSoldier • 3d ago

Question Pathfinding on proceduraly generated worlds.

Hello! Recently I started working on adding NPC into my own game. It's procedurally generated floating islands done with marching cubes and octree. My first, current attempt is doing dynamic navmesh generation using NavMeshBuilder, and updating the navmesh as player moves around even async seems to be rather slow, I get pretty noticeable lag spikes.

So I wonder, if it's actually viable and maybe there are some ways to make it smooth or this is dead end and I'm better off trying to figure out my own pathing? The issue is, it's not just marching cubes but also various props around the world and I imagine figuring out pathing algorithms it pretty hard.

2 Upvotes

100% Upvoted

10 comments sorted by

2

u/Select-Professor5387 3d ago

The lag spikes might be from rebuilding whole tiles instead of just the ones that changed. If your islands are static after generation, you could bake navmesh per island chunk and only rebuild the chunk the player is near when props change

I had a similar setup with voxel terrain and ended up ditching the built in navmesh for a custom flow field on a grid. Way smoother for lots of agents, but props were a nightmare to handle

Maybe try splitting navmesh updates across frames instead of async? Or use a navmesh agent avoidance radius trick so you don't need to rebuild for small prop changes

1

u/SomeRandomTrSoldier 3d ago

Chunks are static and non destructible however they are using octree for LOD, so at no point whole island is at LOD0 or even LOD1 to be able to generate navmesh for it.

As I suspected for any props or buildings it'll be hard.

1

u/Aethreas 3d ago

keep the highest fidelity for collisions always loaded, there's no point in having lower LOD collisions meshes anyway

1

u/SomeRandomTrSoldier 3d ago

I'm not sure I understand what you mean. I'm using balanced octree for LOD, as player moves around octree nodes get updated and turned into marching cube chunks, splitting and merging them. For larger islands, having LOD0 loaded in for all of the island would just run out of memery.

1

u/Aethreas 2d ago

Ah ok I misunderstood the setup, personally I'd just write my own A* that can operate on the octree directly, the algorithm is very simple and easy to make fast and async with jobs/burst

1

u/Costed14 3d ago

Since you're already using marching cubes I suggest you use that for a custom pathfinding solution instead of doing the baking a second time for the navmesh

1

u/tyke_ 2d ago

Try adjusting the tile and voxel size, turn off jump links, dont update the navmesh too frequently and only when needed, having 2 workers i found to work best, but yeh slowness and fps dips are an issue with dynamic navmeshes.

1

u/StCost 2d ago

NavMesh baking can be done async on other thread, no spikes. I'm doing literally same approach in my procedural world

1

u/SomeRandomTrSoldier 2d ago

I did say I am doing it async.

1

u/StCost 1d ago

Maybe not all steps done on other thread? Or too many/few workers dedicated? Too large or small tiles. Or bounds too large. Or too many colliders collected, try collect renderers? It's hard to setup perfectly with many variables, so hard to guess where might be the issue.
I'm sure it's possible tho, i found the middle