Posts Blok (Part 1)
Post
Cancel

Blok (Part 1)

This post is about Blok, a Minecraft-style 3D game, written in C++ with OpenGL.

I hope to keep my blog updated with my progress as it develops! I’ve spent the last 3 days programming an early demo, and now I am writing it from scratch, documenting all my progress and decisions. Time to delve in!

You can find all the source for this here: Blok

1. Choosing Libraries and Setting Up Env

I want this application to be cross-platform, somewhat easy to rewrite and maintain, and eventually, be able to pull segments of the code out (such as the renderer, mesh loading, input control, etc) for use in other projects.

So, I am choosing to write this in C++ (specifically, C++11 standard, no boost or other libraries), but use a fair amount of C idioms for efficiency in some key areas. I use CMake 3.1 as my build system, so google how to install that for your platform

I am planning to use the OpenGL graphics framework, GLFW for events, and gl3w for loading OpenGL.

I am also going to use Assimp for model loading, although we won’t be loading many models. This may be replaced by a manual .obj reader, as I don’t plan to have many high-poly meshes. In either case, we will start with it for simplicity.

All of these libraries should be cross platform, although I haven’t been compiling on Windows or MacOS. Eventually, once the project has matured, I’ll make sure those platforms are supported. But, for development, I will be running on Ubuntu Linux.

I’ve included a script (./build_libs.sh) that will statically build the requirements. Just run this script once when you clone the repository, and you’re good to go!

2. Overall Goals

Now, we need to define our goals for this project, specifically the game aspect. Here is what I want to accomplish:

  • Dynamic world generation, with interesting foundations, cave systems, structures, biomes, etc
  • Mining, building, many different block types
  • Multiplayer/server capabilities (will be a good bit in the future, but we will design with this use case in mind)
  • Interesting/kinda crazy enemy mob behavior (I’m thinking all sorts of monsters)
  • More hostile/badlands style biomes
  • More visual effects

Alright, seems like a lot. Can we do it? Lets find out!

3. Starting Out

This first blog post will consider setting up the general datastructures in the Blok game.

For consistency, let’s define our coordinate system. We will use a left hand coordinate system:

LHCS

All this means is that X means right, Z means forward, and Y means up

And, for now, we’ll just add a few block types. Eventually, we’ll add more, but first, let’s just get the basics working

Start Coding!

The first file is going to be Blok/Blok.hh, a C++ header.

The important data specification comes here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    // ID - describes a numeric identifier for the type of block
    enum ID : uint8_t {

        // AIR - an empty block, is transparent, and non-physical
        //   basically just a placeholder block
        AIR        = 0,

        // DIRT - a cube made of dirt, with identical textures on all sides
        //   is completely opaque, and is physical
        DIRT       = 1,

        // DIRT_GRASS - a cube made of dirt, with grass on the top side
        //   is completely opaque, and is physical
        DIRT_GRASS = 2,

        // STONE - a cube of stone, same on all sides
        //   is completely opaque, and is physical
        STONE      = 3,

    };

And,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

    // BlockData - data for a single block in the world, which includes the type of
    //   block, as well as room for meta data
    struct BlockData {

        // the block ID for this current block
        ID id;

        // various metadata
        uint8_t meta;

        // construct a BlockData from parameters, defaulting to an empty block
        BlockData(ID id=ID::AIR, uint8_t meta=0) {
            this->id = id;
            this->meta = meta;
        }

    };

    // ChunkXZ - type defining the Chunk's macro coordinates world space
    // The actual world XZ is given by CHUNK_SIZE_X * XZ[0] and CHUNK_SIZE_Z * XZ[1]
    using ChunkXZ = glm::vec<2, int>;

    // Chunk - represents a vertical column of data of size:
    //   CHUNK_SIZE_X*CHUNK_SIZE_Y*CHUNK_SIZE_Z
    // This should extend from the bottom of the physical world to the top,
    //   and is indexed starting at 0 in all local directions (x, y, z)
    // There are also the macro coordinates (type: ) (X, Z), which describe
    //   the overall position in the 2D lattice on the XZ plane:
    // view the chunk as top down, with +X being right, +Z being up, etc
    // like so:
    // +-----+-----+-----+
    // |     |  T  |     |
    // |     |     |     |
    // +-----+-----+-----+
    // |  L  | cur |  R  |
    // |     |     |     |
    // +-----+-----+-----+
    // |     |  B  |     |
    // |     |     |     |
    // +-----+-----+-----+
    //
    // (Z)
    //  ^
    //  + > (X)
    //
    // If the macro coordinates for 'cur' are X=0,Z=0, then that means the back left bottom
    //   blocks are 0,0,0 in world space
    // The back left bottom of a chunk is given by: (CHUNK_SIZE_X*X, 0, CHUNK_SIZE_Z*Z)
    //   and it extends through: (CHUNK_SIZE_X*(X+1), CHUNK_SIZE_Y, CHUNK_SIZE_Z*(Z+1))
    //
    class Chunk {
        public:

        // the macro coordinates, i.e. 2D lattice index of the Chunk
        ChunkXZ XZ;

        // the array of blocks that make up the chunk, they are ordered in XZY order,
        // i.e. the the Y coordinates are the fastest changing
        // The index (x, y, z) maps to the linear index (CHUNK_SIZE_Y * (CHUNK_SIZE_Z * x + z) + y)
        //  so, for loop iteration should be like:
        // for (int x = 0; x < CHUNK_SIZE_X; ++x) {
        //   for (int z = 0; z < CHUNK_SIZE_Z; ++z) {
        //     for (int y = 0; y < CHUNK_SIZE_Y; ++y) {
        //       chunk->set(x, y, z, ...);
        //     }
        //   }
        // }
        BlockData* blocks;

        // rcache - the render cache, meant to be mainly managed by the rendering engine
        //   to improve efficiency
        // all 'cur' values mean current as of this frame, and
        // 'last' values mean the values for last frames
        struct {

            // keep track of hashes, to check if anything changed
            uint64_t curHash, lastHash;

            // pointers to other chunks that are spacially touching this chunk
            // NOTE: see the diagram above the definition for 'class Chunk' for a visual
            //   diagram of these
            // if one is NULL, that means that Chunk is not in the rendering engine currently,
            //   so the chunk is 'open'
            Chunk *cL, *cT, *cR, *cB;

        } rcache;

        // get the linear index into 'blocks' array, given the 3D local coordinates
        // i.e. 0 <= x < BLOCK_SIZE_X
        // i.e. 0 <= y < BLOCK_SIZE_Y
        // i.e. 0 <= z < BLOCK_SIZE_Z
        int getIndex(int x=0, int y=0, int z=0) const {
            return CHUNK_SIZE_Y * (CHUNK_SIZE_Z * x + z) + y;
        }
    ...
    }

These block comments describe how the data structures will work, and how we should access them.

The general idea is to divide the world into chunks. In Blok, they will have the size 16x256x16, which means there will be 65536 blocks per chunk (this includes the AIR block, which isn’t really a “block”).

That means that each chunk takes 65536 * 2==128kb of RAM (the 2 comes from the fact that 2 bytes are used for each BlockData). This is not bad at all!

If we have a 15x15 grid of chunks loaded at one time, that means we have 128kb * 15 * 15 == 28mb. So, 28 megabytes of memory, not too bad, huh?

This isn’t counting any caching, optimized render datastructures, etc, which will end up taking up more ram, but not many times more than this. So, this seems like a feasible amount of ram to require for the game.

The memory layout of the chunks is like this:

I’m going to refer to a ‘column’ as any 1x256x1 size. Internally, the memory is stored:

Column @ x=0,z=0 then Column @ x=0,z=1 then Column @ x=0,z=2Column @ x=0,z=15, then Column @ x=1,z=0 then Column @ x=1,z=1 then Column @ x=1,z=2Column @ x=1,z=15, then …

Column @ x=15,z=0 then Column @ x=15,z=1 then Column @ x=15,z=2Column @ x=15,z=15

So, you can also think of a chunk as a 16x16 matrix of columns of blocks. And, this matrix is stored in row-major order, so all the elements are just jammed together in memory.

Check out the getIndex() function in the above code snippet to see how an index into this array is calculated, for our local x, y, and z coordinates

Graphics

OpenGL is a beast on its own. I recommend following a tutorial (like here). My blog is not meant to be an introduction to OpenGL entirely, but I’ll try to explain things at a high level, and how we’ll use them

A Texture is just a 2D image (well, there can be 3D textures, but we’re keeping it simple for now). It’s just a 2D array of pixels, like this image:

PIXELS

This is a grass block texture I’m making for the game (in GIMP). You can see the axis of 0-64 for both the length and width. So, at position (31, 31) is the middle of the image. If you have never dealth with or learned about representing images on computers, this is a pretty good simple link on the issue: https://teachwithict.weebly.com/binary-representation-of-images.html.

So, a texture is any picture, or 2D image.

A Mesh is just another name for a 3D model, which is a bunch of faces (in our case, all the faces are triangles, for simplicity). A mesh can represent any kind of 3D object we want, for this game, so all objects being rendered will effecively just be a bunch of triangles put together.

A Mesh’s vertices (the points on the mesh) all have data, like what the color/coordinates are. We won’t dive too deep on this yet, but just know that pretty much all of the useful rendering information will be baked into the mesh itself.

Now, will some of these basics out of the way, we can finally move on to making something render!

This post is licensed under CC BY 4.0 by the author.

Contents