Game Dev 2: Voxel Terrain Generation

Voxel terrain generation is all the rage these days. Specifically, building a world out of cubes (either textured or otherwise). There are a number of games doing this, with the most well-known being Minecraft. Games currently in development such as Cube World and Timber and Stone also use them. Thought I'm planning on a different graphical aesthetic as opposed to using cubes, I'm still quite interested in the idea of having volumetric data for my terrain. This enables destructible terrain and generally makes procedurally generated worlds a bit easier to think about.

Perhaps one of the most interesting design decisions with using voxel terrains relates to data storage. Specifically, how to design your worlds such that the save game (world save) files dont get too big.

After much reading, the general design of voxel worlds seems to be as follows:

• A Voxel: A cube, often of unit length (e.g. 1) on each side.
• A Chunk: A set of voxels in 3 dimensions. In Minecraft, a chunks is 16x256x16 (xyz) voxels.
• A Set of Displayed Chunks: The active chunks that should be displayed to the screen, which essentially sets how much of the world can be seen at any given point in time. The number of chunks is usually tailored to match the users GPU configuration.
• A Game Chunks: The set of all active chunks at which the world is "alive". Used for game logic, NPCs, etc. This is usually much larger than the number of chunks being displayed.
• A World file: The set of all chunks in the entire Map. This is usually the set of visited (or seen) chunks in Minecraft. When the player is exploring, new chunks are generated on the fly and put into the world file.

So this leads to a bunch of interesting design decisions that impact the world size (and file size)

• Big decision number 1: How big is a Voxel in game dimensions, really? Will it be 1 meter on a side? 2 meters? 4? 8? Minecraft chooses 1 meter on a side.
• Big decision number 2: What is the max height (Tallest mountain) and the lowest depth (lowest cavern) of the map? Typically, this means the chunk y-dimension. Minecraft is 128 voxels high for each chunk (256 meters). 
• Big decision number 3: What is the maximum area of each world map? Minecraft is unlimited (essentially), but realistically how big do we want it for a game file? This essentially means managing what the max number of chunks in the x and z dimensions is.

Now for a thought experiment about the feasibility of representing the entire earth in voxel terrain using actual sizes.

• Assume that each voxel is 1 meter long on each side and storage is 1 byte.
• Assume the tallest point in the world is Mt Everest (8900 meters) and deepest point is the Mariana Trench (10,911m) -> y dimension in voxel map should be ~20000 meters (voxels high).
• Assume that the Earth is 510,072,000,000,000 square meters. If turned into a square,  22,584,774 voxels long per side.
• Conclusion: representing the entire earth as a (22,584,774 x 20,000 x 22,584,774) voxels will take - 8.8 EXABYTES of memory (9278156 Gigabytes).

Wow! So what did we learn... other than it would be impossible given today's technology to ever create a scale model of planet earth with voxels? Well, if we think a bit more, we realize how silly the thought experiment is that a game would doesn't need that much realism. A player could never visit all of those places in the world (even in an MMO).

So how big do we need? Well I suggest reversing the problem and starting with our ideal file size. My opinion is that the file should be between 50MB to 5GB in size, with a target of 100-500MB. This is not unreasonable, as I've heard of Minecraft savefiles taking up to 2GB before. Keep in mind that we don't need to have that entire file loaded in RAM, only sitting on the hard drive.

So, if we stick with the 256 height (a la Minecraft), we end up with a 4,579m x 4,579m game world at 5GB (Roughly the size of Skyrim), or a 452m x 452m grid at 50MB. So, we can see that using 1m voxels can meet our needs just fine.

A final thought: Generally speaking, a lot of the world is filled with large regions of similar types of blocks. In other words, block types come in large groups. Many designs do not take advantage of this fact, when there is a great opportunity for optimization. The most straightforward optimization may very well be lossless compression. There are a number of options here, but I think that dictionary-based algorithms seems like a good start. It optimizes for the large regions of similar blocks. I may investigate these optimizations for myself later. If I do, expect a post here.