I’ve been doing a lot of thinking about my game’s design. It consists of several different systems that need to work together.

• Physics
• Tilemap drawing and collisions
• Individual sprites
• Managing multiple sprites and their collisions
• Allowing each sprite to run some code of its own

Conceptually this isn’t difficult to understand. There are individual sprites, each one is able to run some code to determine what it should be doing. All the sprites are managed by an entity manager, and a physics system and collision system are used to move the sprites around the screen, checking for and resolving collisions. However, making this work together is a Hard Problem.

Thinkers

Currently I’m trying to fix two problems with my code. The first one is how to give entities in my game the ability to run pieces of code by themselves to control their behaviour. So far I have been doing this by using function pointers in a kind of callback system.

Each entity is defined like this, with a function that’s called when a collision happens called collision_func() and one that is run every frame called update_func()

typedef struct Sprite {
    uint16_t id;
    Point position;                         // Position in Object Space - See docs
    Point_int last_screen_position;         // Actual previous physical position on the screen in screen space
    Point_int screen_position;              // Actual physical position on the screen in screen space
    SpriteDef *sprite_def;
    PhysicsBody *physics_body;
    SpriteAnimationState animation_state;
    uint8_t current_behaviour;
    uint8_t is_active;
    uint8_t is_visible;
    uint8_t dirty_buffer;
    uint8_t is_dirty;
    CollisionFuncPtr collision_func;
    UpdateFuncPtr update_func;
    void *user_data;
} Sprite;

A typical update function would look something like this, with a *this pointer so the function can access the data from that specific sprite instance

void player_update(Sprite *this)
{
    move_amount.x = 0;
    move_amount.y = 0;

    if (IS_KEY_HELD(KEY_LEFT)) {
        move_amount.x = float_to_fixed(-1);
        facing_dir = move_amount;

    } else if (IS_KEY_HELD(KEY_RIGHT)) {
        move_amount.x = float_to_fixed(1);
        facing_dir = move_amount;
    }

    if (IS_KEY_HELD(KEY_UP)) {
        move_amount.x = 0;
        move_amount.y = float_to_fixed(-1);
        facing_dir = move_amount;

    } else if (IS_KEY_HELD(KEY_DOWN)) {
        move_amount.x = 0;
        move_amount.y = float_to_fixed(1);
        facing_dir = move_amount;
    }

    sprite_set_behaviour(this, lookup_direction(facing_dir));

    move_amount = vector2_scale(move_amount, float_to_fixed(5));
    sprite_apply_force(this, move_amount);

    if (IS_KEY_PRESSED(KEY_Z)) {
        debug_print_sprite(this);
        //Sprite *bullet = bullet_instantiate((SpriteDef*)asset_registry_get("bullet"), facing_dir, this);
    }
}

This method is fine, and works reasonably well but I am finding problems trying to program more complex behaviour. Also it is getting messy trying to execute the update functions. I have this code that goes through every entity in the game and checks whether it has an update function to execute.

for (int x = 0; x < MAX_SPRITES; x++) {
        if (sprites[x].is_active == 1) {
            // If there is an update func, run it
            if (sprites[x].update_func)
                sprites[x].update_func(&sprites[x]);

It is part of a giant function called sprite_system_update() which is so long it’s hard to follow the logic. I need to prune this function down and make things more simple. Part of making this code more simple is to separate out running of the sprite logic. At the moment this is inside the sprite manager because that’s the code that understands what a “sprite” is.

There is a better way though, let’s go look at how others have done this.

Doom

iD Software released the source to Doom on Github and it’s freely available for people to poke around in. As a result, some very helpful people created the Doom Wiki which attempts to document how the source of Doom works. It makes interesting reading when combined with the Game Engine Black Book - Doom.

In Doom each entity can be assigned something known as a “thinker”, as the Doom Wiki explains

A thinker is an instance of a large number of diverse structures in the Doom engine which are used to implement per-tic scheduled actions within the game world. Thinkers are linked into a global double-linked list which is iterated down once per tic, giving each object a turn at running its logic for that time slice. This is a very basic implementation of a cooperative multitasking system.

The idea is that each game object has a C struct used to store all the data about it, with the first item in the struct being a thinker_t struct, defined in d_think.h

typedef struct thinker_s
{
    struct thinker_s*	prev;
    struct thinker_s*	next;
    think_t		function;
    
} thinker_t;

Each item that appears in the game is called a “map object” or “mobj” and has a structure to store all the data about it relevant to drawing it on the screen and managing which part of the game it is in.

// Map Object definition.
typedef struct mobj_s
{
    // List: thinker links.
    thinker_t		thinker;

    // Info for drawing: position.
    fixed_t		x;
    fixed_t		y;
    fixed_t		z;

The first item is the thinker_t struct. This allows a mobj_s to be cast as a thinker_t where needed. The player is derived from a mobj_s and has its own struct with relevant data stored inside it. Since the first element in the struct is a mobj_t which has a thinker_t as its first element, a player_s can be cast down to a thinker_t.

typedef struct player_s
{
    mobj_t*		mo;
    playerstate_t	playerstate;
    ticcmd_t		cmd;

    // Determine POV,
    //  including viewpoint bobbing during movement.
    // Focal origin above r.z
    fixed_t		viewz;
    // Base height above floor for viewz.
    fixed_t		viewheight;
    // Bob/squat speed.
    fixed_t         	deltaviewheight;
    // bounded/scaled total momentum.
    fixed_t         	bob;	

    // This is only used between levels,
    // mo->health is used during levels.
    int			health;	
    int			armorpoints;
    // Armor type is 0-2.
    int			armortype;	

    // Power ups. invinc and invis are tic counters.
    int			powers[NUMPOWERS];
    boolean		cards[NUMCARDS];
    boolean		backpack;
    
    // Frags, kills of other players.
    int			frags[MAXPLAYERS];
    weapontype_t	readyweapon;

This emulation of basic C++ inheritance and subclassing means the logic for “running” entities doesn’t need to know or care what kind of entity it is running. It just needs to accept any struct cast as a thinker_t and execute the think_t function function.

Doom doesn’t iterate through every single instanced sprite trying to execute this function, instead it maintains a linked list of thinkers and just iterates through that once a frame.

Stealing Doom’s Thinkers

I am trying to implement something similar to this in my game code now. Partially because it is a fun programming challenge to make this work, but also because it’ll uncouple different types of sprite from each other while still allowing one generic system to manage and run their code.

What I need to do is plan out what kind of entities my game will contain, the data they need to store and then create a flexible system that allows me to create and define entities without needing to modify any of the management code.