Init 1

Small project idea to have some fun with C, a micro multiplayer classic game with as less dependencies as possible. I’ve always been curious about the challenges of game development so I started from one of the simplest ideas. The latest update of the code can be found in the repository codepr/battletank.git.

The game

It’s about a best effort terminal based implementation of the classic battle-tank, starting from a single player single tank and extending it to work as a multiplayer server with sockets to sync the game state across players. To begin with, the only dependency is ncurses, later on, if I get confident enough, I will consider something fancier such as Raylib.

Why

To have some fun, small old school programs are fun to mess with. In addition, although I worked for a brief stint for an AAA gaming company, I was mainly developing on the back-end side of the product, pre-game lobbies, chat rooms and game server deployments; but didn’t really know much about the inner logic of the game itself. This was a good opportunity to try and learn something about game development starting from the basics.

Ideas

In no particular order, and not necessarily mandatory:

• Implement a very simple and stripped down game logic ✅
  • 1 player, 1 tank, 1 bullet ✅
  • Handle keyboard input ✅
  • Design a better structured game state, multiple tanks, each tank loaded with bullets
• Multiplayer through TCP sockets
  • Implement a TCP server ✅
  • Implement a TCP client ✅
  • Implement a network protocol (text based or binary) ✅
  • The clients will send their input, server handle the game state and broadcasts it to the connected clients ✅
  • Heartbeat server side, drop inactive clients
  • Small chat? Maybe integrate chatlite
  • Ensure screen size scaling is maintained in sync with players
• Walls
• Life points
• Bullets count
• Recharge bullets on a time basis
• Power ups (faster bullets? Larger hit box? Mines?)
• Explore SDL2 or Raylib for some graphic or sprites

Main challenges

The game is pretty simple, the logic is absolutely elementary, just x, y axis as direction for both the tank and the bullets. The main challenges are represented by keeping players in sync and ensure that the battlefield size is correctly scaled for each one of them (not touched this yet).

For the communication part I chose the simplest and ubiquitous solution, a non-blocking server on select (yikes, maybe at least poll) and a timeout on read client, this way the main loops are not blocked indefinitely and the game state can flow. There are certainly infinitely better ways to do it, but avoiding threading and excessive engineered solutions was part of the scope. There is not plan to make anything more than have some fun out of this project, one simple upgrade would be to migrate the server implementation to epoll or kqueue, however it’s definitely not a game to be expected to have a sufficiently high number of players to prove problematic to handle for the good old select call.

Something I find more interesting is delving a little more into graphics, I literally don’t know anything about it but I can see libraries such as Raylib seem to make it simple enough to generate some basic animations and sprites, the program is sufficiently simple to try and plug it in, hopefully without too much troubles.

Implementation

I won’t go deep in details, some parts are to be considered boilerplate, such as serialization, TCP helpers and such. To get into details of those parts, the repository is codepr/battletank.git.

The game can be divided in the main modules:

• The game state
  • Tank
  • Bullet
• A game server, handles the game state and serves as the unique authoritative source of truth.
• A game client, connects to the server, provides a very crude terminal based graphic battlefield and handles input from the player.
• A protocol to communicate. Initially I went for a text-based protocol, but I’m not very fond of them, so I decided for a binary one eventually, a very simple one.

The game state

The game state is the most simple I could imagine to begin with

• An array of tanks
• Each tank has 1 bullet

Short and sweet, to keep in sync, the server is only required to update the coordinates of each tank and bullet and send them to the clients. This structure is probably where additional improvements mentioned in the intro paragraph could live, power ups, walls, bullets and their kinds, mines etc.

game_state.h

// Possible directions a tank or bullet can move.
typedef enum { IDLE, UP, DOWN, LEFT, RIGHT } Direction;

// Only fire for now, can add something else such as
// DROP_MINE etc.
typedef enum {
    FIRE = 5,
} Action;

// Represents a bullet with its position, direction, and status.
// Can include bullet kinds as a possible update for the future.
typedef struct {
    int x;
    int y;
    Direction direction;
    bool active;
} Bullet;

// Represents a tank with its position, direction, and status.
// Contains a single bullet for simplicity, can be extended in
// the future to handle multiple bullets, life points, power-ups etc.
typedef struct {
    int x;
    int y;
    Direction direction;
    bool alive;
    Bullet bullet;
} Tank;

typedef struct {
    Tank *players;
    size_t players_count;
    size_t player_index;
} Game_State;

// General game state managing
void game_state_init(Game_State *state);
void game_state_free(Game_State *state);
void game_state_update(Game_State *state);

// Tank management
void game_state_spawn_tank(Game_State *state, size_t index);
void game_state_dismiss_tank(Game_State *state, size_t index);
void game_state_update_tank(Game_State *state, size_t tank_index,
                            unsigned action);

Tanks and bullets

Although the structures introduced are trivial, some helper functions to manage tanks and bullets can come handy; when the server starts, the first thing will be to init a global game state. When a new player connects, a tank will be spawned in the battlefield, I opted for a random position spawning in a small set of coordinates. In hindsight, I could’ve easily set a fixed number of players such as 10, I went for a dynamic array on auto-pilot basically. To be noted that as of now I’m not really correctly freeing the allocated tanks (these are the only structure that is heap allocated) as it’s not really necessary, the memory will be released at shutdown of the program anyway and the number of expected players is not that big. That said, it’s definitely best practice to handle the case correctly, I may address that at a later stage.

game_state.c

void game_state_init(Game_State *state) {
    state->players_count = 2;
    state->players = calloc(2, sizeof(Tank));
    for (size_t i = 0; i < state->players_count; ++i) {
        state->players[i].alive = false;
        state->players[i].bullet.active = false;
    }
}

void game_state_free(Game_State *state) { free(state->players); }

void game_state_spawn_tank(Game_State *state, size_t index) {
    // Extend the players pool if we're at capacity
    if (index > state->players_count) {
        state->players_count *= 2;
        state->players = realloc(state->players, state->players_count);
    }
    if (!state->players[index].alive) {
        state->players[index].alive = true;
        state->players[index].x = RANDOM(15, 25);
        state->players[index].y = RANDOM(15, 25);
        state->players[index].direction = 0;
    }
}

void game_state_dismiss_tank(Game_State *state, size_t index) {
    state->players[index].alive = false;
}

And here to follow the remaining functions needed to actually update the state of the game, mainly manipulation of the X, Y axis for the tank and bullet directions based on actions coming from each client.

To check collision initially I just check that the coordinates of a given tank collide with those of a given bullet. Admittedly I didn’t focus much on that (after all there isn’t even a score logic yet), for a first test run I was more interested into seeing actually tanks moving and be in sync with each other through the network, but check_collision still provides a good starting point to expand on later.

game_state.c

static void fire_bullet(Tank *tank) {
    if (!tank->bullet.active) {
        tank->bullet.active = true;
        tank->bullet.x = tank->x;
        tank->bullet.y = tank->y;
        tank->bullet.direction = tank->direction;
    }
}

void game_state_update_tank(Game_State *state, size_t tank_index,
                            unsigned action) {
    switch (action) {
        case UP:
            state->players[tank_index].y--;
            state->players[tank_index].direction = UP;
            break;
        case DOWN:
            state->players[tank_index].y++;
            state->players[tank_index].direction = DOWN;
            break;
        case LEFT:
            state->players[tank_index].x--;
            state->players[tank_index].direction = LEFT;
            break;
        case RIGHT:
            state->players[tank_index].x++;
            state->players[tank_index].direction = RIGHT;
            break;
        case FIRE:
            fire_bullet(&state->players[tank_index]);
            break;
        default:
            break;
    }
}

static void update_bullet(Bullet *bullet) {
    if (!bullet->active) return;
    switch (bullet->direction) {
        case UP:
            bullet->y--;
            break;
        case DOWN:
            bullet->y++;
            break;
        case LEFT:
            bullet->x -= 2;
            break;
        case RIGHT:
            bullet->x += 2;
            break;
        default:
            break;
    }
    if (bullet->x < 0 || bullet->x >= COLS || bullet->y < 0 ||
        bullet->y >= LINES) {
        bullet->active = false;
    }
}

static void check_collision(Tank *tank, Bullet *bullet) {
    if (bullet->active && tank->x == bullet->x && tank->y == bullet->y) {
        tank->alive = false;
        bullet->active = false;
    }
}

/**
 * Updates the game state by advancing bullets and checking for collisions
 * between tanks and bullets.
 *
 * - Creates an array of pointers to each player's bullet for easy access during
 *   collision checks.
 * - For each player:
 *   - Updates their bullet by calling `update_bullet`.
 *   - Checks for collisions between the player's tank and every other player's
 *     bullet using `check_collision`.
 * - Skips collision checks between a player and their own bullet.
 */
void game_state_update(Game_State *state) {
    Bullet *bullets[state->players_count];
    for (size_t i = 0; i < state->players_count; ++i)
        bullets[i] = &state->players[i].bullet;

    for (size_t i = 0; i < state->players_count; ++i) {
        update_bullet(&state->players[i].bullet);
        for (size_t j = 0; j < state->players_count; ++j) {
            if (j == i) continue;  // Skip self collision
            check_collision(&state->players[i], bullets[j]);
        }
    }
}

The client side

The client is the main entry point for each player, once started it connects to the battletank server and provides a very crude terminal based graphic battlefield and handles input from the player:

• upon connection,it syncs with the server on the game state, receiving an index that uniquely identifies the player tank in the game state
• the server continually broadcasts the game state to keep the clients in sync
• clients will send actions to the servers such as movements or bullet fire
• the server will update the general game state and let it be broadcast in the following cycle

Out of scope (for now)

The points above provide a very rudimentary interface to just see something work, there are many improvements and limitations to be overcome in the pure technical aspect that are not yet handled, some of these in no particular order:

• screen size scaling: each client can have a different screen size, this makes it tricky to ensure a consistent experience between all the participants, in the current state of things, a lot of glitches are likely to happen due to this fact.
• clients disconnections and re-connections, reusing existing tanks if already instantiated
• heartbeat logic to ensure clients aliveness

These are all interesting challenges (well, probably the heartbeat and proper client tracking are less exciting, but the screen scaling is indeed interesting) and some of these limitations may be address in an hypothetical battletank v0.0.2 depending on inspiration.

Moving on with the code, the first part of the client side requires some helpers to handle the UI, as agreed, this is not gonna be a graphical game (yet?) so ncurses provides very handy and neat functions to draw something basic on terminal. I don’t know much about the library itself but by the look of the APIs and their behaviour, from my understanding of the docs it provides some nice wrappers around manipulation of escape sequences for VT100 terminals and compatibles, similarly operating in raw mode allowing for a fine-grained control over the keyboard input and such.

battletank_client.c

static void init_screen(void) {
    // Start curses mode
    initscr();
    cbreak();
    // Don't echo keypresses to the screen
    noecho();
    // Enable keypad mode
    keypad(stdscr, TRUE);
    nodelay(stdscr, TRUE);
    // Hide the cursor
    curs_set(FALSE);
}

static void render_tank(const Tank *const tank) {
    if (tank->alive) {
        // Draw the tank at its current position
        mvaddch(tank->y, tank->x, 'T');
    }
}

static void render_bullet(const Bullet *const bullet) {
    if (bullet->active) {
        // Draw the bullet at its current position
        mvaddch(bullet->y, bullet->x, 'o');
    }
}

static void render_game(const Game_State *state) {
    clear();
    for (size_t i = 0; i < state->players_count; ++i) {
        render_tank(&state->players[i]);
        render_bullet(&state->players[i].bullet);
    }
    refresh();
}

static unsigned handle_input(void) {
    unsigned action = IDLE;
    int ch = getch();
    switch (ch) {
        case KEY_UP:
            action = UP;
            break;
        case KEY_DOWN:
            action = DOWN;
            break;
        case KEY_LEFT:
            action = LEFT;
            break;
        case KEY_RIGHT:
            action = RIGHT;
            break;
        case ' ':
            action = FIRE;
            break;
    }
    return action;
}

In the last function handle_input the unsigned action returned will be the main command we send to the server side (pretty simple huh? Ample margin to enrich this semantic).

Next in line comes the networking helpers, required to manage the communication with the server side, connection, send and receive:

battletank_client.c

static int socket_connect(const char *host, int port) {
    struct sockaddr_in serveraddr;
    struct hostent *server;
    struct timeval tv = {0, 10000};

    // socket: create the socket
    int sfd = socket(AF_INET, SOCK_STREAM, 0);
    if (sfd < 0) goto err;

    setsockopt(sfd, SOL_SOCKET, SO_RCVTIMEO, &tv, sizeof(struct timeval));
    setsockopt(sfd, SOL_SOCKET, SO_SNDTIMEO, &tv, sizeof(struct timeval));

    // gethostbyname: get the server's DNS entry
    server = gethostbyname(host);
    if (server == NULL) goto err;

    // build the server's address
    bzero((char *)&serveraddr, sizeof(serveraddr));
    serveraddr.sin_family = AF_INET;
    bcopy((char *)server->h_addr, (char *)&serveraddr.sin_addr.s_addr,
          server->h_length);
    serveraddr.sin_port = htons(port);

    // connect: create a connection with the server
    if (connect(sfd, (const struct sockaddr *)&serveraddr, sizeof(serveraddr)) <
        0)
        goto err;

    return sfd;

err:

    perror("socket(2) opening socket failed");
    return -1;
}

static int client_connect(const char *host, int port) {
    return socket_connect(host, port);
}

static int client_send_data(int sockfd, const unsigned char *data, size_t datasize) {
    ssize_t n = network_send(sockfd, data, datasize);
    if (n < 0) {
        perror("write() error");
        close(sockfd);
        exit(EXIT_FAILURE);
    }
    return n;
}

static int client_recv_data(int sockfd, unsigned char *data) {
    ssize_t n = network_recv(sockfd, data);
    if (n < 0) {
        perror("read() error");
        close(sockfd);
        exit(EXIT_FAILURE);
    }
    return n;
}

All simple boilerplate code mostly, to handle a fairly traditional TCP connection, the only bit that’s interesting here is represented by the lines

setsockopt(sfd, SOL_SOCKET, SO_RCVTIMEO, &tv, sizeof(struct timeval));
setsockopt(sfd, SOL_SOCKET, SO_SNDTIMEO, &tv, sizeof(struct timeval));

These two lines ensure that the read system call times out after a certain period, seemingly simulating a non-blocking socket behaviour (not really, but the part that’s interesting for us). This is the very first solution and the simplest that came to mind but it allows to run a recv loop without blocking indefinitely, as the server will constantly push updates, the client wants to be as up-to-date as possible to keep rendering an accurate and consistent game state.

This part happens in the game_loop function, a very slim and stripped down client-side engine logic to render and gather inputs from the client to the server:

battletank_client.c

// Main game loop, capture input from the player and communicate with the game
// server
static void game_loop(void) {
    int sockfd = client_connect("127.0.0.1", 6699);
    if (sockfd < 0) exit(EXIT_FAILURE);
    Game_State state;
    game_state_init(&state);
    unsigned char buf[BUFSIZE];
    // Sync the game state for the first time
    int n = client_recv_data(sockfd, buf);
    protocol_deserialize_game_state(buf, &state);
    unsigned action = IDLE;

    while (1) {
        action = handle_input();
        if (action != IDLE) {
            memset(buf, 0x00, sizeof(buf));
            n = protocol_serialize_action(action, buf);
            client_send_data(sockfd, buf, n);
        }
        n = client_recv_data(sockfd, buf);
        protocol_deserialize_game_state(buf, &state);
        render_game(&state);
    }
}

int main(void) {
    init_screen();
    game_loop();
    endwin();
    return 0;
}

The main function is as light as it gets, just initializes the ncurses screen to easily calculate COLS and LINES the straight to the game loop, with the flow being:

• Connection to the server
• Sync of the game state, including other possibly already connected players
• Non blocking wait for input, if made, send it to the server to update the game state for everyone connected
• Receive data from the server, i.e. the game state, non blocking.

The server

The server side handles the game state and serves as the unique authoritative source of truth.

• clients sync at their first connection and their tank is spawned in the battlefield, the server will send a unique identifier to the clients (an int index for the time being, that represents the tank assigned to the player in the game state)

As with the client, a bunch of communication helpers to handle the TCP connections. The server will be a TCP non-blocking server (man select / poll / epoll / kqueue), relying on select call to handle I/O events. Select is not the most efficient mechanism for I/O multiplexing, it’s in fact quite dated, the first approach to the problem, it’s a little quirky and among other things it requires to linearly scan over all the monitored descriptors each time an event is detected, it’s also an user-space call, which adds a minor over-head in context switching and it’s limited to 1024 file descriptor in total but:

• It’s ubiquitous, basically every *nix system provides the call
• It’s very simple to use and provides everything required for a PoC
• It’s more than enough for the use case, even with tenth of players it would handle the load very well, poll and epoll are really designed towards other scales, in the order of 10K of connected sockets.

battletank_server.c

// We don't expect big payloads
#define BUFSIZE 1024
#define BACKLOG 128
#define TIMEOUT 30000 // 30 ms

// Generic global game state
static Game_State game_state = {0};

/* Set non-blocking socket */
static int set_nonblocking(int fd) {
    int flags, result;
    flags = fcntl(fd, F_GETFL, 0);

    if (flags == -1) goto err;

    result = fcntl(fd, F_SETFL, flags | O_NONBLOCK);
    if (result == -1) goto err;

    return 0;

err:

    fprintf(stderr, "set_nonblocking: %s\n", strerror(errno));
    return -1;
}

static int server_listen(const char *host, int port, int backlog) {
    int listen_fd = -1;
    const struct addrinfo hints = {.ai_family = AF_UNSPEC,
                                   .ai_socktype = SOCK_STREAM,
                                   .ai_flags = AI_PASSIVE};
    struct addrinfo *result, *rp;
    char port_str[6];

    snprintf(port_str, 6, "%i", port);

    if (getaddrinfo(host, port_str, &hints, &result) != 0) goto err;

    /* Create a listening socket */
    for (rp = result; rp != NULL; rp = rp->ai_next) {
        listen_fd = socket(rp->ai_family, rp->ai_socktype, rp->ai_protocol);
        if (listen_fd < 0) continue;

        /* set SO_REUSEADDR so the socket will be reusable after process kill */
        if (setsockopt(listen_fd, SOL_SOCKET, SO_REUSEADDR, &(int){1},
                       sizeof(int)) < 0)
            goto err;

        /* Bind it to the addr:port opened on the network interface */
        if (bind(listen_fd, rp->ai_addr, rp->ai_addrlen) == 0)
            break;  // Succesful bind
        close(listen_fd);
    }

    freeaddrinfo(result);
    if (rp == NULL) goto err;

    /*
     * Let's make the socket non-blocking (strongly advised to use the
     * eventloop)
     */
    (void)set_nonblocking(listen_fd);

    /* Finally let's make it listen */
    if (listen(listen_fd, backlog) != 0) goto err;

    return listen_fd;
err:
    return -1;
}

static int server_accept(int server_fd) {
    int fd;
    struct sockaddr_in addr;
    socklen_t addrlen = sizeof(addr);

    /* Let's accept on listening socket */
    fd = accept(server_fd, (struct sockaddr *)&addr, &addrlen);
    if (fd <= 0) goto exit;

    (void)set_nonblocking(fd);
    return fd;
exit:
    if (errno != EWOULDBLOCK && errno != EAGAIN) perror("accept");
    return -1;
}

static int broadcast(int *client_fds, const unsigned char *buf, size_t count) {
    int written = 0;
    for (int i = 0; i < FD_SETSIZE; i++) {
        if (client_fds[i] >= 0) {
            // TODO check for errors writing
            written += network_send(client_fds[i], buf, count);
        }
    }

    return written;
}

Again, the main just initializes the ncurses screen (this is the reason why the PoC will assume that the players will play from their own full size terminal, as currently there is no scaling mechanism in place to ensure consistency) and run the main select loop waiting for connections. Clients are tracked in the simplest way possible by using an array and each new connected client will be assigned its index in the main array as the index for his tank in the game state.

battletank_server.c

static void server_loop(int server_fd) {
    fd_set readfds;
    int client_fds[FD_SETSIZE];
    int maxfd = server_fd;
    int i = 0;
    unsigned char buf[BUFSIZE];
    struct timeval tv = {0, TIMEOUT};
    unsigned long long current_time_ns = 0, remaining_us = 0,
                       last_update_time_ns = 0;

    // Initialize client_fds array
    for (i = 0; i < FD_SETSIZE; i++) {
        client_fds[i] = -1;
    }

    while (1) {
        FD_ZERO(&readfds);
        FD_SET(server_fd, &readfds);

        for (i = 0; i < FD_SETSIZE; i++) {
            if (client_fds[i] >= 0) {
                FD_SET(client_fds[i], &readfds);
                if (client_fds[i] > maxfd) {
                    maxfd = client_fds[i];
                }
            }
        }
        memset(buf, 0x00, sizeof(buf));
        int num_events = select(maxfd + 1, &readfds, NULL, NULL, &tv);

        if (num_events == -1) {
            perror("select() error");
            exit(EXIT_FAILURE);
        }

        if (FD_ISSET(server_fd, &readfds)) {
            // New connection request
            int client_fd = server_accept(server_fd);
            if (client_fd < 0) {
                perror("accept() error");
                continue;
            }

            for (i = 0; i < FD_SETSIZE; i++) {
                if (client_fds[i] < 0) {
                    client_fds[i] = client_fd;
                    game_state.player_index = i;
                    break;
                }
            }

            if (i == FD_SETSIZE) {
                fprintf(stderr, "Too many clients\n");
                close(client_fd);
                continue;
            }

            printw("[info] New player connected\n");
            printw("[info] Syncing game state\n");
            printw("[info] Player assigned [%ld] tank\n",
                   game_state.player_index);

            // Spawn a tank in a random position for the new connected
            // player
            game_state_spawn_tank(&game_state, game_state.player_index);

            // Send the game state
            ssize_t bytes = protocol_serialize_game_state(&game_state, buf);
            bytes = network_send(client_fd, buf, bytes);
            if (bytes < 0) {
                perror("network_send() error");
                continue;
            }
            printw("[info] Game state sync completed (%d bytes)\n", bytes);
        }

        for (i = 0; i < FD_SETSIZE; i++) {
            int fd = client_fds[i];
            if (fd >= 0 && FD_ISSET(fd, &readfds)) {
                ssize_t count = network_recv(fd, buf);
                if (count <= 0) {
                    close(fd);
                    game_state_dismiss_tank(&game_state, i);
                    client_fds[i] = -1;
                    printw("[info] Player [%d] disconnected\n", i);
                } else {
                    unsigned action = 0;
                    protocol_deserialize_action(buf, &action);
                    printw(
                        "[info] Received an action %s from player [%d] (%ld "
                        "bytes)\n",
                        str_action(action), i, count);
                    game_state_update_tank(&game_state, i, action);
                    printw("[info] Updating game state completed\n");
                }
            }
        }

        // Send update to the connected clients, currently with a TIMEOUT of
        // 16ms is roughly equal to 60 FPS. Checks for the last update sent and
        // adjust the select timeout so to make it as precise and smooth as
        // possible and respect the deadline
        current_time_ns = get_microseconds_timestamp();
        remaining_us = current_time_ns - last_update_time_ns;
        if (remaining_us >= TIMEOUT) {
            // Main update loop here
            game_state_update(&game_state);
            size_t bytes = protocol_serialize_game_state(&game_state, buf);
            broadcast(client_fds, buf, bytes);
            last_update_time_ns = get_microseconds_timestamp();
            tv.tv_sec = 0;
            tv.tv_usec = TIMEOUT;
        } else {
            tv.tv_sec = 0;
            tv.tv_usec = TIMEOUT - remaining_us;
        }
        // We're using ncurses for convenience to initialize ROWS and LINES
        // without going raw mode in the terminal, this requires a refresh to
        // print the logs
        refresh();
    }
}

int main(void) {
    srand(time(NULL));
    // Use ncurses as its handy to calculate the screen size
    initscr();
    scrollok(stdscr, TRUE);

    printw("[info] Starting server %d %d\n", COLS, LINES);
    game_state_init(&game_state);

    int server_fd = server_listen("127.0.0.1", 6699, BACKLOG);
    if (server_fd < 0) exit(EXIT_FAILURE);

    server_loop(server_fd);

    return 0;
}

An interesting bit is the syncing of the framerate client-side with the udpates coming from the server, the initial implementation relies on select timing out every at 30ms, that means that the game will update consistently when there is not input from any client (e.g. every one is not moving), but realistically, all the players will be moving frequently, resulting in the select call to detect I/O events on the observed sockets before the TIMEOUT deadline.

This may generate weird and funny bugs, such as bullets flying much faster than expected when tanks are moving. A naive but simple approach to solve the problem is to track the timestamp in nanoseconds of each update and update the select timeout accordingly.

• check for remaining us (microseconds) left to reach the TIMEOUT deadline in the current cycle, if we’re already beyond, send a gamestate update, record the last update us and reset the select timeout
• if the remaining us have not yet reached the deadline, update the select timeout to TIMEOUT - remaining

This way, the update frequency is ensured to be mostly consitent at roughly the same time each cycle.

That’s all folks, an extremely small and simple battletank should allow multiple players to join and shoot single bullets. No collisions nor scores or life points yet, but it’s a starting point, in roughly 600 LOC:

battletank (main) $ ls *.[c,h] | xargx cloc
       8 text files.
       8 unique files.
       0 files ignored.

github.com/AlDanial/cloc v 2.02  T=0.02 s (521.2 files/s, 61767.2 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C                                5            134            172            563
C/C++ Header                     3             17             10             52
-------------------------------------------------------------------------------
SUM:                             8            151            182            615
-------------------------------------------------------------------------------

References

• ncurses
• Raylib
• SDL2
• setsockopt
• select
• Select is fundamentally broken
• beej.us - serialization techniques

Databases, how they interact with the filesystem at low-level, have always represented a fascinating topic for me. I implemented countless in-memory key-value stores at various level of abstraction and various stages of development; with multiple languages, Scala, Python, Elixir, Go. Gradually going more and more in details, it was finally time to try and write something a bit more challenging.

A relational database was too big of a step to begin with and being the persistence the very first big problem I could think of facing almost immediately, I wanted something that could be implemented based on a simple but extremely versatile and powerful structure, the log. I wanted something that could be implemented on top of a this simple concept, in my mind the system should’ve basically been a variation of a Kafka commit log, but instead of forwarding binary chunks to connected consumers (sendfile and how Kafka works internally is another quite interesting topic I explored and I’d like to dig into a bit more in the future); a time-series seemed interesting and fitting my initial thoughts.

The programming language to write it in was the next decision to make, I considered a couple of choices:

• Elixir/Erlang - a marvel, fantastic back-end language, the BEAM is a piece of art, I use Elixir daily at work though so I craved for something of a change my scenery
• Go - great design, simplicity and productivity like no others, also a bit boring too
• Rust - different beast from anything else, requires discipline and perseverance to retain productivity, I like it, but for it’s very nature and focus on safety, I always feel kinda constrained and fighting the compiler more than the problem I’m solving (gotta put some more effort into it to make it click completely). Will certainly pick it up again for something else in the future.
• C++ - Nope, this was a joke, didn’t consider this at all

Eventually I always find myself coming back to a place of comfort with C. I can’t really say the reason, it’s a powerful tool with many dangers and when I used it for my toy projects in the past, I almost never felt enough confidence to say “this could to be used in a prod environment”. I fought with myself on it for many years, learning Rust, flirting with Go, but I eventually gave up and embraced my comfort place. They’re great languages, I used Go for work for a while and Rust seems a good C++ replacement most of time, provided you use it with consistency (borrow checker and lifetimes can be hellish to deal and re-learn if out of shape).

With C, I reckon it all boils down to it’s compactness, conceptually simple and leaving very little to imagination of what’s happening under the hood. I’m perfectly conscious how easy it is to introduce memory-related bugs, and implementing the same dynamic array for each project can get old pretty fast; but what matters to me, ultimately, is having fun, and C provides me with that. Timeseries have always been a fascinating topic for me

Design

Conceptually it’s not really an efficient or particularly smart architecture, I approached the implementation on a best-effort way, the idea being to delay as much as possible the need of non-basic data-structures such as arrays.

The two main segments are just fixed size arrays where each position stores a pointer to the first position of a dynamic array. This to be able to store all the data points included in the time range that the segment covers

Each time a new record is to be inserted, first it is appended as a new entry in the Write-Ahead-Log (WAL) and only then it is store in the in-memory segment where it belongs. The WAL acts as a disaster recovery policy, it is solely responsible for storing incoming records in order to be able to read them and re-populate the segment on restarts.

In short:

• two segments of 15 minutes each
  • each position represents a second, so 900 is the length of the segments
  • each second points to a dynamic array storing positions based on the microsecond portion of the timestamp of the point
• each time a new point is inserted, it is first stored on a WAL on disk in order to be able to recover in case of crash
• once the main segment is full, or a timestamp too far in the future is received (i.e. more than 15 minutes past the 1st point store)
  • the tail segment gets persisted on disk and becomes immutable, WAL is cleared
  • the head segment gets persisted on disk and becomes immutable, WAL is cleared
  • the head segment becomes the new tail segment
  • a new head in-memory segment is generated
• immutable segments on disk are paired with an index file to read records from the past

Although there are plenty of improvements, fixes and other things to take care of, this function is roughly at the heart of the logic (there is a secondary logic in here for which we flush on disk also based on the WAL size, nothing of interest for the purpose of simplicity)

/*
 * Set a record in a timeseries.
 *
 * This function sets a record with the specified timestamp and value in the
 * given timeseries. The function handles the storage of records in memory and
 * on disk to ensure data integrity and efficient usage of resources.
 *
 * @param ts A pointer to the Timeseries structure representing the timeseries.
 * @param timestamp The timestamp of the record to be set, in nanoseconds.
 * @param value The value of the record to be set.
 * @return 0 on success, -1 on failure.
 */
int ts_insert(Timeseries *ts, uint64_t timestamp, double_t value) {
    // Extract seconds and nanoseconds from timestamp
    uint64_t sec = timestamp / (uint64_t)1e9;
    uint64_t nsec = timestamp % (uint64_t)1e9;

    char pathbuf[MAX_PATH_SIZE];
    snprintf(pathbuf, sizeof(pathbuf), "%s/%s/%s", BASE_PATH, ts->db_data_path,
             ts->name);

    // if the limit is reached we dump the chunks into disk and create 2 new
    // ones
    if (wal_size(&ts->head.wal) >= TS_FLUSH_SIZE) {
        uint64_t base = ts->prev.base_offset > 0 ? ts->prev.base_offset
                                                 : ts->head.base_offset;
        size_t partition_nr = ts->partition_nr == 0 ? 0 : ts->partition_nr - 1;

        if (ts->partitions[partition_nr].clog.base_timestamp < base) {
            if (partition_init(&ts->partitions[ts->partition_nr], pathbuf,
                               base) < 0) {
                return -1;
            }
            partition_nr = ts->partition_nr;
            ts->partition_nr++;
        }

        // Dump chunks into disk and create new ones
        if (partition_flush_chunk(&ts->partitions[partition_nr], &ts->prev) < 0)
            return -1;
        if (partition_flush_chunk(&ts->partitions[partition_nr], &ts->head) < 0)
            return -1;

        // Reset clean both head and prev in-memory chunks
        ts_deinit(ts);
    }
    // Let it crash for now if the timestamp is out of bounds in the ooo
    if (sec < ts->head.base_offset) {
        // If the chunk is empty, it also means the base offset is 0, we set
        // it here with the first record inserted
        if (ts->prev.base_offset == 0)
            ts_chunk_init(&ts->prev, pathbuf, sec, 0);

        // Persist to disk for disaster recovery
        wal_append_record(&ts->prev.wal, timestamp, value);

        // If we successfully insert the record, we can return
        if (ts_chunk_record_fit(&ts->prev, sec) == 0)
            return ts_chunk_set_record(&ts->prev, sec, nsec, value);
    }

    if (ts->head.base_offset == 0)
        ts_chunk_init(&ts->head, pathbuf, sec, 1);

    // Persist to disk for disaster recovery
    wal_append_record(&ts->head.wal, timestamp, value);
    // Check if the timestamp is in range of the current chunk, otherwise
    // create a new in-memory segment
    if (ts_chunk_record_fit(&ts->head, sec) < 0) {
        // Flush the prev chunk to persistence
        if (partition_flush_chunk(&ts->partitions[ts->partition_nr],
                                  &ts->prev) < 0)
            return -1;
        // Clean up the prev chunk and delete it's WAL
        ts_chunk_destroy(&ts->prev);
        wal_delete(&ts->prev.wal);
        // Set the current head as new prev
        ts->prev = ts->head;
        // Reset the current head as new head
        ts_chunk_destroy(&ts->head);
        wal_delete(&ts->head.wal);
    }
    // Insert it into the head chunk
    return ts_chunk_set_record(&ts->head, sec, nsec, value);
}

The current state

At the current stage of development, it’s still a very crude core set of features but it seems to be working as expected, with definitely many edge cases and assertions to solve; the heart of the DB is there, and can be built into a dynamic library to be used on a server. The repository can be found at https://github.com/codepr/roach.

Main features

• Fixed size records: to keep things simple each record is represented by just a timestamp with nanoseconds precision and a double
• In memory segments: Data is stored in time series format, allowing efficient querying and retrieval based on timestamp, with the last slice of data in memory, composed by two segments (currently covering 15 minutes of data each)
  • The last 15 minutes of data
  • The previous 15 minutes for records out of order, totaling 30 minutes
• Commit Log: Persistence is achieved using a commit log at the base, ensuring durability of data on disk.
• Write-Ahead Log (WAL): In-memory segments are managed using a write-ahead log, providing durability and recovery in case of crashes or failures.

What’s in the road map

• Duplicate points policy
• CRC32 of records for data integrity
• Adopt an arena for memory allocations
• Memory mapped indexes, above a threshold enable binary search
• Schema definitions

Timeseries library APIs

• tsdb_init(1) creates a new database
• tsdb_close(1) closes the database
• ts_create(3) creates a new Timeseries in a given database
• ts_get(2) retrieve an existing Timeseries from a database
• ts_insert(3) inserts a new point into the Timeseries
• ts_find(3) finds a point inside the Timeseries
• ts_range(4) finds a range of points in the Timeseries, returning a vector with the results
• ts_close(1) closes a Timeseries

Writing a Makefile

A simple Makefile to build the library as a .so file that can be linked to any project as an external lightweight dependency or used alone.

CC=gcc
CFLAGS=-Wall -Wextra -Werror -Wunused -std=c11 -pedantic -ggdb -D_DEFAULT_SOURCE=200809L -Iinclude -Isrc
LDFLAGS=-L. -ltimeseries

LIB_SOURCES=src/timeseries.c src/partition.c src/wal.c src/disk_io.c src/binary.c src/logging.c src/persistent_index.c src/commit_log.c
LIB_OBJECTS=$(LIB_SOURCES:.c=.o)

libtimeseries.so: $(LIB_OBJECTS)
	$(CC) -shared -o $@ $(LIB_OBJECTS)
%.o: %.c
	$(CC) $(CFLAGS) -fPIC -c $< -o $@
clean:
	@rm -f $(LIB_OBJECTS) libtimeseries.so

Building the library is a simple thing now, just a single command make, to link it to a main, just a one liner

gcc -o my_project main.c -I/path/to/timeseries/include -L/path/to/timeseries -ltimeseries

LD_LIBRARY_PATH=/path/to/timeseries.so ./my_project to run the main, a basic example of interaction with the library

#include "timeseries.h"

int main() {
    // Initialize the database
    Timeseries_DB *db = tsdb_init("testdb");
    if (!db)
        abort();
    // Create a timeseries, retention is not implemented yet
    Timeseries *ts = ts_create(db, "temperatures", 0, DP_IGNORE);
    if (!ts)
        abort();
    // Insert records into the timeseries
    ts_insert(&ts, 1710033421702081792, 25.5);
    ts_insert(&ts, 1710033422047657984, 26.0);
    // Find a record by timestamp
    Record r;
    int result = ts_find(&ts, 1710033422047657984, &r);
    if (result == 0)
        printf("Record found: timestamp=%lu, value=%.2lf\n", r.timestamp, r.value);
    else
        printf("Record not found.\n");
    // Release the timeseries
    ts_close(&ts);
    // Close the database
    tsdb_close(db);

    return 0;
}

A server draft

Event based server (rely on ev at least initially), TCP as the main transport protocol, text-based custom protocol inspired by RESP but simpler:

• $ string type
• ! error type
• # array type
• : integer type
• ; float type
• \r\n delimiter

With the following encoding:

<type><length>\r\n<payload>\r\n

For example a simple hello string would be

$5\r\nHello\r\n

Simple query language

Definition of a simple, text-based format for clients to interact with the server, allowing them to send commands and receive responses.

Basic outline

• Text-Based Format: Use a text-based format where each command and response is represented as a single line of text.
• Commands: Define a set of commands that clients can send to the server to perform various operations such as inserting data, querying data, and managing the database.
• Responses: Define the format of responses that the server sends back to clients after processing commands. Responses should provide relevant information or acknowledge the completion of the requested operation.

Core commands

Define the basic operations in a SQL-like query language

• CREATE creates a database or a timeseries

  CREATE <database name>

  CREATE <timeseries name> INTO <database name> [<retention period>] [<duplication policy>]

• INSERT insertion of point(s) in a timeseries

  INSERT <timeseries name> INTO <database name> <timestamp | *> <value>, ...

• SELECT query a timeseries, selection of point(s) and aggregations

  SELECT <timeseries name> FROM <database name> AT/RANGE <start_timestamp> TO <end_timestamp> WHERE value [>|<|=|<=|>=|!=] <literal> AGGREGATE [AVG|MIN|MAX] BY <literal>

• DELETE delete a timeseries or a database

  DELETE <database name> DELETE <timeseries name> FROM <database name>

Flow:

1. Client Sends Command: Clients send commands to the server in the specified text format.

2. Server Parses Command: The server parses the received command and executes the corresponding operation on the timeseries database.

3. Server Sends Response: After processing the command, the server sends a response back to the client indicating the result of the operation or providing requested data.

4. Client Processes Response: Clients receive and process the response from the server, handling success or error conditions accordingly.

UPDATE: 2020-02-07

In the previous 6 parts we explored a fair amount of common CS topics such as networks and data structures, the little journey ended up with a bugged but working toy to play with.

This part will focus on the implementation of the handlers, they will be mapped one-on-one with MQTT commands in an array, indexed by command type, making it trivial to call the correct function depending on the packet type.

In the Part 4 we explored some useful concepts and implemented two data structures on top of those concepts.

Before proceeding to the implementation of all command handlers, we’re going to design and implement some of the most common data structures needed to the correct functioning of the server, namely hashtable, list and a trie.

This part deal with the implementation of the server part of our application, by using the network module we drafted on part-2 it should be relative easy to handle incoming commands from a MQTT clients respecting 3.1.1 standards as we defined on part 1.

Let’s continue from where we left, in the part 1 we defined and roughly modeled the MQTT v3.1.1 protocol and our src/mqtt.c module has now all unpacking functions, we must add the remaining build helpers and the packing functions to serialize packet for output.

It’s been a while that for my daily work I deal with IoT architectures and research best patterns to develop such systems, including diving through standards and protocols like MQTT;