One big part of this game that will be very important is the fact the terrain is 100% modifiable (players should be able to destroy / add terrain arbitrarily).

In order to do this, we will be using a voxel system, along with a marching cubes algorithm-based method to generate the voxel meshes (instead of being blocks like in Minecraft, it would just be smooth meshes).

The basic idea is that each voxel holds a value, and depending on that value, and the values of the voxels surrounding it, a mesh will be created in that 2x2 little voxel cube.

Here is a link to a great video explaining the algorithm in detail.

Once the concept is understood, the implementation isn’t too difficult.

The more challenging part is structuring the voxel world in an optimal way that would work well for the game and here’s what’s currently going on in the engine.

Chunks

The most fundamental part of the voxel world is that it is split into 16x16x16 chunks.

Here is the chunk structure.

struct chunk_t {
    struct flags_t {
        uint32_t made_modification: 1;
        uint32_t active_vertices: 1;
    } flags;
    
    uint32_t chunk_stack_index;
    ivector3_t xs_bottom_corner;
    ivector3_t chunk_coord;

    uint8_t voxels[CHUNK_EDGE_LENGTH * CHUNK_EDGE_LENGTH * CHUNK_EDGE_LENGTH];

    chunk_render_t *render;
};

It is a pretty simple struct for now containing an array of 16x16x16 bytes (each byte is one voxel). Alongside that, it has a chunk coordinate, and some other data / flags. At the moment the size of one chunk in RAM is about 4136 bytes.

Now, how does the rendering work?

We must remember that this code will be used to compile both the server and client programs - server being windowless and the client being windowed with graphics drawn to it.

I made sure to isolate the rendering part of the structure as much as possible.

For now, data required to render the mesh is contained in the struct chunk_render_t.

// In case chunk_render_data_t may change
typedef mesh_render_data_t chunk_render_data_t;

struct chunk_render_t {
    mesh_t mesh;
    chunk_render_data_t render_data;
};

The mesh structure contains the VBO of the mesh and the render_data contains the push constant data (model matrix, PBR information, etc…)

Chunks not being rendered will have the render data pointer set to nullptr while the ones being rendered will have it set to some heap allocated render data. This makes it quite easy so that in the server program, we just set render to and ignore it.

Chunk world

struct chunk_world_t {
    uint32_t loaded_radius;

    // List of chunks
    // Works like a stack
    stack_container_t<chunk_t *> chunks;

    uint32_t render_count;
    chunk_t **chunks_to_render;

    hash_table_t<uint32_t, 100, 15, 5> chunk_indices;
};

The structure above contains the data for storing the chunks of the world. For now, it is quite simple and doesn’t have any sort of way to unload / load chunks that are not visible / too far, we will think of that later.

The basic functionality is the following:

When voxels get filled in chunks that are new / need to be loaded, a new chunk gets allocated on the heap and pushed onto the chunks stack (which is an array based container which can account for removal of object in a decent way). The only problem with this is that we would not be able to easily find a chunk’s data without knowing its index into the chunks stack container. It is essential, that just from it’s chunk coordinate, we can get the chunk’s data. For this, I added the hash table, which maps chunk coordinates (rather, its hash values) to the index of the chunk pointer.

Note: the index of the pointer never changes, even if chunks have been removed. The whole point of the stack container is that when chunks get removed, other chunks' indices don't get shifted. All that happens is that the index of the removed items gets pushed onto another stack, and when one wishes to add a new chunk, this stack of removed items gets popped, and the new chunk gets added at the index of the chunk that was removed previously.

And voila, we now have a system where we can easily find chunks given a chunk coordinate.

Rendering the chunks

The first part of rendering the chunks is generating the mesh of the voxels.

This is relatively simple with the marching cubes algorithm, and the implementation is in the following function, in w_chunk.cpp

static void s_update_chunk_mesh(
    VkCommandBuffer command_buffer,
    uint8_t surface_level,
    vector3_t *mesh_vertices,
    chunk_t *c,
    chunk_world_t *world);

Vertices are not stored permanently on RAM. Instead, when generating the meshes, a temporary array of positions is created (well, it exists for the lifetime of the program). Onces generating is done for one chunk, that data is sent to the GPU, and this same array is used to store the temporary vertices of the next chunk and etc…

That’s pretty much it for now!

In the next article, I will address the issue of integrating this system with the client / server architecture with the terraforming system implemented.

For now, enjoy this screenshot of a sphere generated with voxels!

photo