This post may have a bit of repeated information for those that follow along closely. A whole lot of Chunk related refactoring happened because I had a new idea about how to do some things. Thus, to make sure everyone is on the same page, I’m going to explain the way it was, and the way it ended up, and why. Feel free to skip around if that suits you.
Chunks are collections of blocks that are 16x16x16 and before the refactoring there were three kinds of them in QubeKwest under the covers. The first is an EmptyChunk, it is a chunk where the whole thing is air. It gives the ability to represent vast empty sections of sky with virtually no storage space. The second is a UniformChunk, it is a chunk where the whole thing is made out of a single material. For example, under a mountain where the whole thing is rock or way underground where you might encounter all lava. Technically, there is nothing stopping you from using a UniformChunk full of air instead of an EmptyChunk but it will take a little more space, so it’s a bit of a waste. The third kind is called a FullChunk (formerly called just Chunk). It details every single block individually and can thus hold anything in any arrangement. All of these types of chunks extend ChunkParent as their base class so they can be treated as the same thing.
The basic concept behind all these different kinds of chunks was that they could be promoted to other types based on blocks being changed inside them. For example if you have an EmptyChunk or a UniformChunk and you change even a single block within it, you have to also change it into a FullChunk. One of the problems with this was that the space it takes to store a chunk has no middle ground. You go from just a few bytes for either an EmptyChunk or a UniformChunk to around 65,000 bytes for a FullChunk. The other problem is, where does this promotion occur so it’s easy to deal with?
The first problem inspired thought about how to make a chunk that can store somewhere between a single type of block and one that has all 4096 individually detailed. This got me thinking back to something I’d coded as a kid. The original Doom saved screen shots in the PCX graphics file format. This ancient format was both palettized and run-length encoded. I learned the inner workings of the PCX file format and coded a PCX decoder so I could make little stop motion movies using Doom screen shots. For QubeKwest, I’d originally considered run-length encoding for blocks in a chunk, but ruled it out because of the constant heavy updates to the encoding when changes are made. This left the idea of using a block palette to reduce the space needed to save a chunk. Basically it’s like an artist’s palette that has things like “1 = air” and “2 = granite” in it so I can reference all of the pieces of granite in a chunk just by using the number 2 instead of a whole block description.
The new PalettizedChunk was born. First, I considered using a palette that used a short (16-bit) index. This was a bad choice because it would actually allow enough entries in the palette to represent every single block in a chunk individually, and could thus result in chunks that take more storage than the original FullChunk did. Next, I considered using a byte (8-bit) index. This would limit the number of blocks in the palette pretty heavily, but it would drastically reduce the space needed to store a chunk. I further realized that because java uses stupid signed bytes, I decided to limit the indexes to 0 to 127. I could have applied a bit of math to the index to use all 256 possible spots in a byte, but I didn’t like all of the primitive type promotion it would involve so I didn’t end up doing it that way. This new version can store 128 kinds of blocks and only takes about 10% of the space as a FullChunk.
The promotion can now go from either EmptyChunk or UniformChunk to a PalettizedChunk when a single block is changed, and then to be promoted to a FullChunk only when the chunk has more than 128 different types of blocks in it. This still leaves the problem of where do the promotions between chunk types occur? And when they occur, how do the various references to chunks get updated without taking a lot of work? The answer to both questions is the idea of a ChunkProxy object (later renamed simply “Chunk” so I didn’t have to type “Proxy” in a million places in the code).
This new object wraps any child of the ChunkParent class (which all 4 types of chunk are) and provides access to the various methods that are actually on the chunk inside. This proxy knows which kind of chunk it is wrapping, and promotes it as needed automatically when an action performed on it requires it. Now the rest of the codebase can just use ChunkProxy objects where they previously used ChunkParent objects. If a chunk gets promoted, the proxy that wraps it stays the same. That means that other things that refer to it don’t actually need to change, and in fact have no idea the promotion has occurred. It’s the best of both worlds.