Large Scale Voxel Plugin World?

[ICanDoThings2]

Is this performant at all with large voxel plugin worlds? I'm working on a game where that's a worthwhile question and wondered.

[darbycostello]

TBH, I think it's overkill for many use cases, including my own. I have a full PCG city-based environment which this solution was initially intended for. I even implemented a full chunking strategy to allow for fine rasterisation over large distances (bearing in mind that all Nav3D volumes are cubic by their nature, so you often end up with a good bit of redundancy in anything but space game scenarios).

But in the end I built a lightweight multiple-height nav grid instead, so agents can simply pathfind through three different planes. Storage is minimal versus a sparse octree and A* pathfinds are lightning-fast. The only justification for going back to an SVO for this use case would be if I had subterranean cavern networks to path through.

One other thing to note for my use case is that it's built entirely at runtime. The Nav3D solution is build-time only and bake times can run into several minutes for complex environments. So my advice is to tread carefully. Nav3D as you can see has been quite popular with devs working in this space but a lot of people are reaching for it as a panacea. But the inverse is true: It's a highly-specific solution and one that even I'm not using in my current commercial project. For coarse pathfinding one can simply use waypoints or my example above. Nav3D could then be useful when applied to a constrained, high-detail environment.

[ICanDoThings2]

I see, I am trying to make something for an open world simulation. Is your solution available anywhere? Does it use hierarchical pathfinding too? I am trying to achieve pathing over quite significant distances, aiming for 2KM away, that may be unfeasible however. I would be interested in studying yours if it is even more performant than Nav3D. I may however still want Nav3D as you said, since it has support for caves and such.

[darbycostello]

No, my solution is just three standard 2d grid-based pathfinding solutions. No quadtree representation so no hierarchical pathfinding - but I suppose I would do that for a larger game world. To be clear, my custom solution here covers 5km, which really isn't that far at all. The cell size you're seeing in the image is 16 metres, which is my max agent size. Some quick math:

N ≈ 98k cells → ~782 Kb baked for the full three-tier nav grid - not even a megabyte.
Point query → O(1)
LOS → O(cells crossed)
A* → O(A²) worst case per search; tier choice mostly controls how often you pay it

At this scale the grid is memory-trivial and CPU-modest; tier choice affects how often you pay A* vs a single LOS sweep, not how much you store.

So if I were pathing over tens of kilometers then I'd probably want to optimise with heirarchical (e.g. use different grid sizes per height) and potentially move to quad tree storage. But honestly, at 5km this stuff is trivial for modern processors and I wrote my system in an afternoon last week.

I have my own solution for working out what's occluded in my nav grid planes, because I'm building the entire thing at runtime therefore I can register the collision with the nav grids as I go. For a voxel-based solution YMMV. If the open world plugin you're using doesn't provide all the voxels within a given plane via a query, then the brute force method is just to perform an AABB collision box check at every nav grid position in a loop for your entire collision plane.

The one thing I've learned in the years I've spent building pathfinding solutions is that no off-the-shelf solution compares to a half-decent one that you can build yourself that meets the precise needs of the use case.

[ICanDoThings2]

5KM is probably fine for me too. I just wondered if you were willing to share the solution source you mentioned. I'm certainly not as heavy a programmer as you. I was looking into using UE5's built in recast but subdividing them into sectors and using hierarchical A* between them, but your system does sound better. Is there a link to it anywhere?

[darbycostello]

I can't share the code as it's a) commercial and b) not generic enough for your likely use case. However I had Claude attempt a one-shot to re-use the Nav3D plugin structure and tools to build you a brand new plugin which does most of what you probably need.

https://claude.ai/share/e6a48e6a-a47c-4c67-a479-9878fd6f4761

NavGrid_Files.zip

You'll need to read the Readme, organise the files in folders as described there and compile it yourself. Good luck.

[ICanDoThings2]

Thanks. I'll try it. Is your commercial code part of an upcoming game then, or sold somewhere as a plugin? Just thought I'd keep an eye out.

[darbycostello]

It's a game and it's a way off yet. Solo dev is hard, even for an old timer like me!

[ICanDoThings2]

I understand completely being a solo indie dev myself. I hope the stripped down plugin you gave will work with world partition, but I will check it out. Thanks! Also does it work at runtime instead of in editor, like you said? With World Partition too?

[darbycostello]

If you're world-partitioning navigation as well as world geometry, then you can't pathfind to a distant position because it wouldn't be loaded into memory. Thus the solution would be to use multiple NavGrid volumes - one per world partition cell - and then simply pathfind through them in the large-scale direction that your agents want to travel. Nav3D supports world partitioning in the same way. If you want to build the grid at runtime like my own project, it is a simple fix.