Category Archives: Voxel Games

The World Stands Still
Partially-Homomorphic Compression for Voxel Games

Minecraft world slice
Credit: Minecraft Wiki

One of the things that makes voxel-based games really interesting is the challenge of storing the procedurally-generated terrain efficiently. A big problem is that the number of voxels grows cubically (or quadratically, if you cap the world height) with the distance that you allow the player to walk in any direction. What this means is that compact world storage is critical to be able to create massive-world experiences.

Usually the dynamically-sized world is cut up into fixed-size chunks which are then stored as an integer array. Each integer within the array represents the type of the voxel at that location. For instance, in the game Minecraft, the bottom-most layer of the world is usually bedrock, then mostly stone with ore veins sprinkled in, followed by a few layers of dirt, a grass layer and finally air—you can see this on the image on the right. Given such an array you can then throw any generic compression algorithm at it to get a pretty decent compression ratio. It’s a simple way to take advantage of the fact that the generated terrain often contains repeating patterns.1There are some tricks you can play to improve the compression ratio further, such as applying a scheme similar to indexed color to reduce the number of bits needed for each voxel.

If you are familiar with Minecraft, you may have noticed that if you walk far enough away from an area, the crops suddenly stop growing—until you come back. This is not a bug. In order to save on precious memory, Minecraft unloads regions that don’t have any players within view distance. If it didn’t, the amount of data simply would not fit into RAM once the world gets sufficiently large.2This can get out of hand pretty quickly on a multiplayer server with 100+ players and a world size in the thousands. It is not uncommon to see worlds with over 10.000 blocks in any direction from the spawn point. Assuming a world height of 128 blocks and 2 bytes per block this amounts to over 95 GiB of data. To process world updates like crops growing the data needs to be mutable. Compression turns nicely mutable data into an immutable black box and thus cannot be used for in-memory storage.3You could of course decompress on-the-fly, but that would be pretty expensive just to update a single voxel.

Continue reading
  • 1
    There are some tricks you can play to improve the compression ratio further, such as applying a scheme similar to indexed color to reduce the number of bits needed for each voxel.
  • 2
    This can get out of hand pretty quickly on a multiplayer server with 100+ players and a world size in the thousands. It is not uncommon to see worlds with over 10.000 blocks in any direction from the spawn point. Assuming a world height of 128 blocks and 2 bytes per block this amounts to over 95 GiB of data.
  • 3
    You could of course decompress on-the-fly, but that would be pretty expensive just to update a single voxel.