The past two weeks have mostly been spent on refactoring and restructuring a lot of Skycraft, so there won’t be a new version just yet. But this might be a good time to give you another peek down the rabbit hole: let’s look at how the world of Skycraft is stored.
Let’s first look at the smallest single unit of the world of Skycraft: A block. Each block is stored as a 32-bit integer:
The lower 10 bits denote the type of the block, in other words whether it is grass, air, water, dirt, marble, or something else. This allows for 1024 different blocks, which shoooould be enough. I hope.
The remaining 22 bits are block data. These 22 bits are entirely at the blocks disposal to store all kinds of state the block can have. For instance, because air blocks propagate lighting, they have 6 bits dedicated to the storage of light, because there are 64 different levels of light. Water also propagates light, but in addition stores one of 128 different water levels, so it currently uses 6 + 7 = 13 bits of data.
At this point, 32 seems large enough that all block types and most block data will fit comfortably, while still keeping the memory footprint manageable; As I will adress further down, memory is very much a limiting factor.
So each block is 32 bit. But we have to store it somehow, and so we divide the world into chunks of blocks, that are 32 blocks wide, 32 blocks high and 32 blocks deep. Why exactly 32? There are a few considerations to make when coming up with this number:
The chunks should be as large as possible for efficient storage and compression. And there is only a certain number of chunks we can send to the GPU for rendering, so the fewer chunks, the better.
The chunks should be small enough to be redrawn in just a few milliseconds. When you remove or place a block, the whole chunk has to be rebuilt and sent to the GPU. This takes time, and the larger the chunk, the longer time it will take.
The number should preferably be a power of two, as certain calculations can be done with bitshifts instead of multiplication and division. Bitshifts are great because they automaticly cast the operands to ints1, which saves us doing that in a separate operation.
After some quick experimentation, 32x32x32 quickly proved to be the sweet spot: As large as possible, but still small enough to rerender quickly, and it’s a power of 2. 64x64x64 is 8 times larger, and is only really an option if the chunk rendering gets a lot faster.
I am not the only one to find 32x32x32 a sweet spot. Even Minecraft’s chunks used to be this exact number, but due to the static height of the world, each chunk covers the whole height of the world from top to bottom, so the chunks were 16x16x128. At some point Notch doubled the height though, to 256.
Let’s do some math: Let’s say we want to make an island which is 500x500x500 meters. Skycraft has 4 blocks per meter, so that’s equivelant to 2000x2000x2000 blocks. Each block is 32 bits, or 4 bytes. This amounts to 32 000 000 000 bytes, otherwise known as 32 gigabytes.
Well that clearly doesn’t work. So what do we do? We compress. Everything. and only uncompress it right before we actually need it. Currently this is done by a simple Run Length Encoding (RLE) algorithm: If you have a string “A A A C C B B B A A A A A C C A”, RLE will convert this to “3A 2C 3B 5A 2C 1A”, which is intuitively shorter for data which has a lot of repetition in it. This yields pretty nice results for Skycraft, compressing it down to 3-8% of the original size, allowing the 32 gigabytes to come close to a more manageable 1 gigabyte.
Certain chunks are used all the time (the ones around the player), and will be uncompressed most of the time. The rest of the world will stay compressed almost all the time, except for when something happens to it, for instance that water moves, or grass grows. Without compression we could only ever show a bit over 500x500x500 blocks at any time.
And of course there’s a ton of other reasons to make a game like this in the browser, which we’ll talk about later! But until then, keep asking me questions at @haeric, and feel free to bug me about when the next update is coming…
Speaking of crazy: I just watched Indie Game: The Movie, and I loved it, but the common theme seemed to be “you will get crazy making an indie game”… Here’s hoping insanity is not a success criteria! ↩