17th May 2012

Creating a world

So now we have a nice grid, some axes, and can navigate around with the keyboard and mouse - result! It's all a bit dull though, time to start building our world.

As I mentioned before our world will be built from a 3D grid of cells (similar to Minecraft in that respect). Each cell is a one-metre cube of space in the world be it air, ground, water, whatever.

The naive approach would be to define a big three-dimensional array that is the largest size we want our world to be and store all of the cells and their attributes within it.

Unfortunately, however, this isn't realistic even on modern hardware as three-dimensional data gets big very very quickly! Let's say for example we want our world to be 1024 metres square, and 256 metres high:

1024 metres * 1024 metres * 256 metres = 268,435,456 cells

Woha! We'd need an array with space to store over two hundred and fifty million cells. Even if each cell only needed a single byte of data to represent all of its state and attributes that's two hundred and sixt-eight megabytes of data.

It's likely, though, that we'll potentially want to store quite a bit of metadata about each cell:

This information could easily take over two hundred bytes per cell to store:

268,435,456 cells * 200 bytes = 53,687,091,200 bytes = 53 gigabytes!

And that's just for a world that's limited to slightly over one kilometre squared!

Clearly we need to find a more efficient approach than this...

So, what can we do?

Large portions of our world will be pretty uninteresting, huge swathes of it will just be air or solid stone underground. This suggests our world data should be very compressable.

Let's imagine a really boring world:

The only feature in this world is the boundary between land and air.

Most worlds will look something like this with details like hills, caves, and rivers at the boundary. If we can find a way to only store the information about our interesting areas then we could save ourselves a lot of space!

There are many ways we could compress this data (run-length encoding, octrees) but we need a system that allows fast random access and the ability to manipulate any part of the world without having to rebuild and time-consuming data structures.

If we were to split our world into smaller chunks:

We could save space in situations where an entire chunk is air or ground as there would be no need to store any information about the cells within the chunk.

We'll make each chunk 16 metres squared so that they contain 16 * 16 * 16 (4,096) cells each. Now our kilometre squared map is 64 * 64 * 16 chunks in size (65,536 chunks).

For our really boring map only the centre two layers (64 chunks * 64 chunks * 2 chunks = 8,192) of chunks contain any detail, the rest are either completely air or ground:

So we have 8,192 detail chunks and 57,344 simple chunks in our world, we've just reduced the amount of data we need to store by 86%!

Urgh, we've not written any code at all this time. Next time we'll see how it works in practise...

pretell
(778) 773-9594