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.
Finding a Different Box
In cryptography there is a really fascinating concept called homomorphic encryption. The idea is fairly straightforward: You get an encrypted piece of data and perform a calculation on it in a special way. The result is equivalent to decrypting, calculating the result and encrypting it again, except you did it directly without having to decrypt and encrypt again.
If you mentally replace the words “encrypt” and “decrypt” by “compress” and “decompress” in the above description, this sounds just like what we need. If we had a scheme to perform operations on compressed data, we could keep everything in memory in compressed form while retaining the ability to make world updates. If you google the term “homomorphic compression” you won’t get many results however and the ones you do get don’t seem very promising.
A potential reason for this is that while similar on the surface, encryption and compression functions are actually different mathematically in an important way. Encryption is bijective—it creates a 1:1 mapping between bytes from the input and output. Now remember that the entire goal of a compression algorithm is to reduce the size of the data. Compression is therefore only surjective—an output byte may correspond to multiple input bytes and thus changing one such byte might end up affecting multiple locations after decompression.4Another way to think about this is to consider how a compression algorithm works: If it detects repetitions it can replace multiple occurrences of a pattern by references to a single instance.
Does this mean homomorphic compression fundamentally can’t work? Well, yes and no. What we are really after is a way to perform updates for those specific voxels that need updating. We won’t be able to do this for arbitrary voxels, but it is possible if we can restricts ourselves to specific instances, as we shall see.
Partially-Homomorphic Compression Using RLE
While it should be applicable to pretty much any generic compression algorithm, I’ll try to introduce the idea using what is probably the dumbest compression algorithm in existence: run-length encoding (RLE). In its simplest form RLE counts the number of consecutive occurrences of a value in the input sequence (this is called a “run”) and writes out the corresponding
(length, value) pairs, as seen in the following diagram:
Solid lines indicate uncompressed and dotted lines compressed data. In this example our input consists of runs of three 0’s, followed by three 1’s, followed by two 2’s. The run-length encoder simply converts this to the sequence
Now let’s suppose that we want to change the first 2 to a 3 without decompressing. If we were to make this modification here, it would end up affecting both 2’s after decompression, which is wrong:
The 2’s were part of the same initial run—however, if we split the run up we can establish a bijective mapping for 2’s:
Each 2 is now represented by its own, independent
(1,2) pair. We still have a valid run-length encoding, but it is no longer minimal. In exchange for giving up some compression ratio we are now free to modify the 2’s individually without affecting any other values.
How does the algorithm know that we want a bijective mapping for 2’s? We need to tell it using what I’ll call the bijectivity set. The bijectivity set represents all the voxels which need a bijective mapping and thus cannot be merged with others during compression. The exact form of this set does not really matter—it could just be a list of voxels, a list of concrete voxel types, or simply a predicate function to be evaluated for each voxel.
Once we have such a compression algorithm, how do we actually know where to find the 2’s in a given compressed array? If we’re using run-length encoding we can just perform a search (making sure to skip the run lengths within the data), but if we were to use more complicated algorithms, we would need to understand the structure of the compressed data to distinguish file content from metadata.
To solve this issue the compression algorithm needs to produce a list of offsets in addition to the compressed data:
I like to call this offset list the index, borrowing the term from databases.5Admittedly this is a bit confusing, given that array elements are also addressed using an index. I prefer the term offset for addressing here however, to emphasize that the compressed data is really just a byte array. The index contains the offsets 5 and 7, pointing to the 2’s that we can now change independently from any other values in the compressed array.
Interestingly, if you maintain such an index for uncompressed data as well, the pieces of game logic that work with compressed data can work with uncompressed data transparently—all that’s needed is an array and the corresponding index to find the values we care about.
As I already mentioned, this is not a general solution—only selected voxels can be made modifiable. Game logic of the type “for all voxels satisfying X, do Y” can be implemented with this technique in a straightforward manner and even made compression-agnostic.
Updating neighbors of such voxels is possible if we include them in the bijectivity set, but the complexity and overhead increases. Keep in mind that it is not enough to map these neighboring voxels bijectively, you also need a way to go from the offset of a voxel to the offset of its neighbor, which requires maintaining a bidirectional mapping between world coordinates and offsets in addition to the index.
While the scheme can work with any compression algorithm, the software interface needs to be extended by a bijectivity set and index—we saw this using RLE as an example.
Using this technique it is possible to perform selected world updates even though the data is compressed. Due to the reduced memory requirement compared to no compression at all there is potential to improve the player experience and make the world feel more alive.
In a future post I’ll look at different compression algorithms and provide some concrete numbers, stay tuned!
- 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.
- 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.
- 3You could of course decompress on-the-fly, but that would be pretty expensive just to update a single voxel.
- 4Another way to think about this is to consider how a compression algorithm works: If it detects repetitions it can replace multiple occurrences of a pattern by references to a single instance.
- 5Admittedly this is a bit confusing, given that array elements are also addressed using an index. I prefer the term offset for addressing here however, to emphasize that the compressed data is really just a byte array.