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.
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?
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
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.
