My Take on an Infinite Voxel Engine

I am using some sort of navigation structure, which splits the world into areas and maintains links to every connected area - this results in a smaller graph and works as abstraction layer for the world (and even allows for detecting rooms and dynamic doors) - this graph is used for early pathing checks mainly. For actual pathfinding a modified A* is used on block-level which runs in a separate thread.

Currently the graph does not find the shortest path as it does not provide any heursistics over its nodes. But the early checks help a lot

The way this is all connected to the main thread is basically some “messaging queue”. For example, when an entity get’s an order to build something, it first issues a search (message to thread) which then finds the closest item of the specified type which has a path to the target and then returns the actual path - the agent then walks this path and so on - so the other thread is basically a task/msg handler. And because all this happens in the other thread I can mostly eliminate syncronization issues and don’t need to “lock” everything.

there is a LOT of optimization in there :smiley:

Thats very clever. When I implemented A* on larger worlds (4000x4000 tiles), i ran it on a separate thread using a queue system. It generated large amounts of garbage and gc spikes when moving a couple hundred units at once. I ended up trying to get the algorithm as memory efficient as possible and doing jump searches and did get rid of the GC spikes

But I think I might have to try your idea of dividing the world into smaller areas. Im guessing the pathing won’t be as ‘best possible’ but will be a lot faster and easier on the garbage collector.

Are you going to be making some kind of needs based ai tree for your agents to do things?

Love your work mate

I basically try to avoid dynamic lists whereever possible. My a* information sits directly in the datagrid portions and for finding out if a block was already visited I just set an integer which is incremented each run. Of course that means I cannot do concurrent path searches but that doesn’t matter for me.

It’s basically optimized for performance on every possible location, I am actually quite impressed how fast you can make .Net

I’ve always been curious about this Minecraft style voxel. Is it related to old MSDOS games that also used voxels. Is this the same technology?


the second one does not relate to the first screenshot - but no, that was a bit differently. In the first screenshot (which was originally called “voxel”) - you actually plotted lines from back to front to make the illusion of 3D - this was mainly used for heighmaps - that was appears to be pixels are alway axis align to the monitor.

in the second screenshot, the “pixels” are not screen aligned, so I guess that’s something else.

The Voxels in Exipelago … are actually a representation of big cubes (in Exipelago - which is what this engine transformed into) there is all sorts of shapes, each representing a differnt type of “voxel” - ultimately this all is generated into an optimzed mesh for performance reasons and then sent to the GPU as geometry.

A “true” Voxel engine nowadays does more send data to the GPU and builds geometrical information there on the fly - which is different again but allows for all kinds of cool stuff.

In my game, I do need proper information about the geometry created (for game mechanics) so that is all stored and created on the CPU side

The second screen shot is from a Build Engine game. During the 90’s when it was created, they said it supported voxels. That cross was an example of voxels in their engine. It seems the term is used very loosely.

Look into The Making of Desert Strike, I believe it was called, will explain that technique in detail as it was what it was known for…