DevLog #001 – Let’s Build a Voxel Engine

Part of a series of posts in which we write a voxel engine from scratch for Android.

In-between projects, we like to experiment with new tech to further enhance our in-house graphics engine (deepScene) and come up with new game ideas. Although we’ve only used our deepScene engine for 2D games so far, it’s actually a fully-featured 3D engine with 2D capabilities. In this series of developer logs, we’ll be taking you through the process as we push our engine to its limits, by writing a highly optimized ‘mining and crafting-style’ voxel engine using our existing tech as a base.

Although we store our block data as voxels, we’ll be using good old-fashioned triangles and vertices to render them. The term ‘voxel’ is used loosely to describe a rendering technique (volumetric pixels) or in our case, how blocks are stored in memory before being converted to 3D geometry.

Despite the blocky nature of voxel-based games, they’re suprisingly challenging to develop from the ground-up, due to the potentially massive memory requirements of storing millions of blocks, and the performance bottle-neck of pushing that data to the graphics card – and we’re going to do it all on mobile, a platform with severe technical restrictions – and it’s all going to run at a silky-smooth 60fps on a humble phone.

What are Chunks and why are they important?

You can think of a chunk as a collection of data (such as blocks) that has a position in 3D space, and a bounding-box, allowing for fast-traversal of smaller collections of data without having to check everything at once – so for example, if you want to check if there’s a block in-front of you; instead of cycling through millions of blocks, you only have to know which chunk you’re inside (via the bounding-box), to know which blocks to check.

Chunks are not only useful for CPU operations like collision-checking, but also vastly improve rendering speed by culling entire chunks of blocks that can’t be seen before sending only visible ones to the GPU.

In our engine, we’re going to have BIGCHUNKS, each of which contains 8 chunks – this will allow us to further optimize the process by first checking a larger area for chunks, before checking the blocks in each chunk.

Even cycling through a small subset of blocks is a slow operation – if our chunks contain 16x16x16 blocks each, that’s 4096 blocks to check, but we can remove the need for cycling through blocks at all with lookup-tables.

A lookup-table is an array of short integers (2 bytes each) describing the type of block at every position in the chunk (e.g: -1 is empty, 0=dirt, 2=grass etc..) – and with a bit of simple math, we can access any block in the array directly without looping through them all…

//Define the array used for our lookup-table..
final int blocksMax=blocksTall*blocksTall*blocksTall;
this.blockTable=new short[blocksMax];

//Get the array lookup-value via an x,y,z position in the world
//We use a modulo operation (%) to wrap the x,y,z values to fit the array dimensions 
int lookup=((int)((x-Chunk.x)/blockScale) % blocksWide)+
(((int)((z-Chunk.z)/blockScale) % blocksWide)*blocksWide)+
(((int)((y-Chunk.y)/blockScale) % blocksWide)*blocksWide*blocksWide);

//Access the array with our lookup value to get the block-type at our x,y,z position
short blocktype=this.blockTable[lookup];

Just like magic, we can now access any block in the world, by first knowing its position,  then finding the containing chunk and checking a lookup-table. It’s lightning-fast, and removes the need for slow loops.

The last element of our data structure is Blocklists – which differ from the lookup-table, in that they contain only blocks which need to be built into a batched mesh during the terrain building, discarding any that can’t be seen. Each chunk contains 8 Blocklists which are immediately discarded from memory once the terrain is built.

Blocklists are an intermediate step between our voxel data (lookup-tables, which contain no positional information) and our 3D models, which need to know the x,y,z position of visible blocks.

We will use these Blocklists to build the terrain for each chunk into a statically batched mesh to reduce draw-calls. We do this because every instruction to the GPU (to draw something, or change a texture) counts as a draw-call, and we need to keep these to around 60-100 draw calls per frame for faster performance – so we batch blocks together into a single instruction wherever possible.