An Analysis of Minecraft-like Engines – 0 FPS does a breakdown into the conventional data structures used to represent the world of a 3D voxel game engine. In particular, they list the following:
- 1D array. Simple, most basic, easiest to implement. Also what we used in4600 .
- Octrees. On paper these might sound faster, but in reality they’re much slower than arrays because accessing neighbor chunks takes longer.
- Virtualized array. From what I can tell it’s like an array but we keep a hash map to various indexes in the array that we currently care about. Sort of like a sparse data structure.
We care about how fast we’re able to access world, chunk, and block information from within memory. Random and sequential read/writes are important to us. This article makes the claim that sequential queries matter significantly more and lists some heavy iterative operations:
- Placing and removing blocks
- Collision detection
- Picking/raytracing
- Lighting updates
- Physics updates
- Mesh generation
- Disk serialization
- Network serialization
Therefore, we want to focus on increasing sequential read/write speeds, even if it causes random accesses to be slower (nothing beats a linear array. Why?), because in the grand scheme of things most logic is being sequentially done and we get net positive performance boosts.
Interval trees and virtualization
They further argue that any operation being performed is local to the current chunk and its neighboring chunks, and that any operation is deterministic in the sense that e.g. applying a physics update to both voxels will produce the same result. If we can somehow group/batch these operations together, then we can update all the chunks at the same time.
To do this, they talk about using run-length encoding (which is apparently the same as an interval tree), which I don’t understand too much about and will need to revisit. In addition, we use this data structure for each chunk: store each chunk as an interval tree, and then furthermore add chunk virtualization via a hash map to the currently active/used chunks. So we’re combining interval trees and virtualization here.
Benchmark results
According to their benchmarks their interval tree + hashing method is roughly ~2 times slower than a flat array for random reads, but anywhere between ~10-59 times faster for sequential reads.
Interestingly, a virtual array performed worse for both metrics compared to a flat array, and the octree was several magnitudes slower than all three.
Caveats
For interval trees to work well, blocks of the same type must be grouped together for us to save space and to improve efficiency. If the world generation creates very small groups of the same block or is extremely random, then this data structure would not perform as well.
However, for games like Minecraft (and our own Mini Minecraft) our terrain generation carves out very large areas of land for biomes (which use the same block types), so this method generally works out.