Under the hood of Skycraft: Part II

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.

Blocks & bits

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.

Chunks

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:

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.

Compression

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.

Uh-oh.

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.

Crazy?

At this point, a few of you may wonder why someone would be insane enough to create a memory-intensive and computation-heavy game like this in javascript. It’s just not something you’re supposed to do, it’s crazy 2. So of course I had to do it, where’s the fun if there’s no challenge? :)

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…

  1. It might seem weird that I care about data types in Javascript. But the browsers try to figure out all they can about the different variables to be able to optimize better, so the more type info you can give them, the better they can optimize, and the faster things get.

  2. 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!

06 Aug 2013