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