r/Unity3D • u/SomeRandomTrSoldier • 12h 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.

1 Upvotes

100% Upvoted

6 comments sorted by

2

u/Select-Professor5387 12h 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 12h 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 10h ago

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

1

u/SomeRandomTrSoldier 10h 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 9h 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 12h 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