roguelike-tutorial

Roguelike Tutorial Revised ported to C

View on GitHub

Chapter 03: Go Forth And Dungeon

What’s a good roguelike without a dungeon? In this chapter we’re going to focus on building the basics of a map. Let’s start by creating two new files, include/map.h and src/map.c.

Cartography 101

For our map design, we will define a struct Map that holds an array of struct Tile. The map will also need to know it’s own width and height. Each struct Tile will hold information about that tile on the map. We need to know if it is a wall or floor, if it blocks or allows player movement, and if the player has seen it yet.

Let’s begin implementing map.h. Start with our header guards and includes:

#ifndef RTUT_MAP_H
#define RTUT_MAP_H

#include "BearLibTerminal.h"

Under The C: Enums and Bitflags

Next, we will face our first new concept for this chapter, enum. Enums are a special type in C that signify named values. They have several uses, but a major one is to use them for flags. Flags are a quick and efficient way to set on/off properties without making a big struct filled with int or bool values for each property. Instead, we make an enum. Add our new enum to map.h:

enum TileProperties {
    TILE_NONE       = 0,
    TILE_WALKABLE   = 1,
    TILE_VISIBLE    = 2,
    TILE_DISCOVERED = 4
};

We use TileProperties to define a set of properties that a tile in a map can have. By convention, each member of an enum is in all caps, similar to #define macros. Now we can use TileProperties as a type, just like when we define a struct.

Normally, a variable of type enum can hold a single value. In other words, a TileProperties can only be one of its members at any time. So at first glance an enum seems like a poor decision as a tile in a map can be both walkable and visible, but perhaps not discovered yet. That’s where bitflag enums come in.

Under the hood, an enum is just an int. They’re what we call “syntactical sugar”, syntax that provides a shortcut for the programmer. Normally, each member of an enum is an incremented number. So TILE_NONE would be 0, TILE_WALKABLE would be 1, etc. However, you’ll notice that we’re explicitly defining the number that each setting of TileProperties represents. And you may have noticed that TILE_DISCOVERED is 4, not 3. Why did we do this?

Let’s say there was a few more settings in TileProperties. We very well may add more in a later chapter. Here’s a mockup of what that might look like:

enum TileProperties {
    TILE_NONE       = 0,
    TILE_WALKABLE   = 1,
    TILE_VISIBLE    = 2,
    TILE_DISCOVERED = 4,
    TILE_A          = 8,
    TILE_B          = 16,
    TILE_C          = 32,
};

Notice anything interesting? Our numbers are counting in powers of 2. The reason for that is that we’re tracking the binary representation of each possible TileProperties value. So if we translate to binary, here’s how our mockup version of TileProperties would look:

enum TileProperties {
    TILE_NONE       = 00000000,
    TILE_WALKABLE   = 00000001,
    TILE_VISIBLE    = 00000010,
    TILE_DISCOVERED = 00000100,
    TILE_A          = 00001000,
    TILE_B          = 00010000,
    TILE_C          = 00100000,
};

So we can see that each enum represents a single bit in an byte. This allows us to use the individual bits that our TileProperties is made up of to flag properites of a struct Tile. That’s why we call them bitflags!

Now we just need to learn how to use bitflags. we will cover that in a later section.

Cartography 102

Let’s continue map.h:

struct Tile {
    char symbol;
    color_t bg;
    color_t fg;
    enum TileProperties prop;
};

struct Map {
    struct Tile *grid;
    int width;
    int height;
};

Now we define our two structs. struct Tile represents an individual tile on our map. symbol, like struct Player defines that ASCII character that we will actually write to the screen. You may notice that it’s just a char and not a C string, or char * like in struct Player. That’s because I wanted to teach the basics of C strings at the same time as pointers, and it was a good spot in the last chapter to do so. In a bit, we will go back to player.h and update the design of struct Player.

color_t is a typedef provided by BearLibTerminal to represent a color. Since we’re not working with colors yet, we will add them now and implement later. bg is the background color behind the ASCII character, fg is the foreground, or the actual color of the ASCII symbol. prop is the TileProperties that will hold the tile’s flags.

struct Map’s width and height are self-explanatory. struct Tile *grid however is not. I said earlier that we will use an array to hold our grid of tiles, but we’re using a pointer inside struct Map instead of an array. Let’s discover why.

Under The C: Decay That Array!

C’s arrays are implemented as contiguous blocks of memory that hold the same type. When we declare something like

int nums[3];

The C compiler creates a block of memory big enough to fit 3 int and points nums to it. That’s right, points. While arrays are not exactly pointers, they are implemented as such. That’s why you can do this:

#include <stdio.h>

int main(void) {
	int nums[3];
    nums[0] = 1;
	printf("%d\n", nums[0]);
	printf("%d\n", *nums);
	return 0;
}

Both printf() statements will print 1 to the terminal. In the first printf() we use the array operator [] to access the first element of nums. In the second printf(), we treat nums like a pointer and dereference it. The C compiler will then find the memory address of nums and treat it like a pointer to an int. Since arrays are just a block of memory holding the type you specifiy, the program reads an int at that address.

This is called array decay. When we talk about how arrays decay into pointers, we mean that they can be represented as a pointer because the compiler treats them in a similar fashion. Likewise, we can use pointer representation for an array as well.

Now in the real world, I would never suggest you do the above. Array decay is a tool to be used in specific scenarios. If you can use the array operator [] to access an array member, then do it. However, one of the most common uses of treating a pointer like an array is for when we do not know the size of an array until runtime. Since we want our struct Map to be able to represent a map of any size, we need to dynamically allocate it.

we will cover the implementation details of dynamic memory later in this chapter. For now, let’s get back to map.h.

Finishing map.h

All we have left is our function definitions.

void init_map(struct Map *map, int w, int h);
void destroy_map(struct Map *map);

Like struct Player, we will start with a function that takes a struct Map and sets it up for use. Because struct Map has dynamic memory, it is good practice to also create a destroy function that will cleanup the dynamic memory.

struct Tile *get_tile(struct Map *map, int x, int y);

int is_walkable(struct Tile *t);
int is_visible(struct Tile *t);
int is_discovered(struct Tile *t);

Now we have four helper functions. get_tile() will return a pointer to a tile in the map based on its x and y coordinates. Since struct Tile does not know its own x and y coordinate, we need this helper function. The other three functions will return a 1 if the tile pointed to by t has that bitflag set, or a 0 otherwise. Remember that 1 is a true value and 0 is a false value.

void draw_map(struct Map *map);

#endif

Lastly, we will need a function that will draw our map. As our map gets more complicated, the drawing will get more complicated as well. Instead of putting all that logic into main(), we should have it in its own function. we will be doing the same in player.h later. We end map.h with our header guard’s closing #endif.

Implementing Our Map

Lets start writing map.c

#include <stdlib.h>
#include <stdio.h>

#include "map.h"

void init_map(struct Map *map, int w, int h) {
    map->width = w;
    map->height = h;

we will need stdlib.h and stdio.h from the standard library to implement our functions. stdlib.h provides the dynamic memory functions and stdio.h is used to print errors to the console. We also include map.h as we need access to struct Tile and struct Map.

In the beginning of init_map(), we will take in the values of our map size and set those in the struct Map.

    map->grid = malloc(sizeof(struct Tile) * w * h);

Now we need to setup our array of tiles. To do this, we will need to allocate a block of memory big enough to hold all the tiles. Dynamic memory means malloc(). Go ahead and add the above line of code and prepare for a long explanation.

Under The C: Malloc For Fun And Profit

Remember that C arrays are contiguous blocks of memory that hold the same type. One disadvantage of arrays is that they need to have their size stated at compile time. That way the compiler knows how much memory to allocate.

What about the times that we need an array, but do not know until runtime what size the map is? Or what if we have an array that needs to be different sizes at different times? For example, we could have one level of the dungeon be 80x25, and another level be a huge cave that’s 800x250. If we tried to use an array, we would need different arrays for different maps with different sizes. Clearly that’s not a workable solution.

Now you may be used to easily querying the size of an array in other languages. Python has len(), C# has Array.Length, etc. In C an array has no idea what size it is, it’s just a block of memory. When we need to dynamically set the size of an array, we need to allocate our own block of memory. That’s where C’s dynamic memory functions come into play.

map->grid = malloc(sizeof(struct Tile) * w * h);

Let’s start from the inside of the malloc() call and work our way out. sizeof() is a built-in function that looks at a type and returns how many bytes that type uses in memory. For the sake of argument, let’s pretend that sizeof(struct Tile) resolves to 10 bytes. If w is 10 and h is 5, we multiply them together to discover that we need 50 tiles for this map. We then multiply 50 by the size of struct Tile, which we are pretending is 10. That means in order to build an array that holds 50 tiles, we need to malloc() 500 bytes. So, our line of code resolves in this pattern:

map->grid = malloc(sizeof(struct Tile) * w * h);
map->grid = malloc(10 * 10 * 5);
map->grid = malloc(500);

These 500 bytes will be allocated in memory at runtime. This means that the next time we need a new map, our function will do the math and allocate the proper amount of bytes. If the map is 20x10, then our function will ask for 2000 bytes instead, which will hold 200 tiles.

Now, we can access map->grid as though it’s an array. map->grid[5] will be the fifth struct Tile in the array. If you’re wondering why we’re storing a two-dimensional map in a single-dimension array, it makes handling the memory and usage much easier. Dynamic two-dimensional arrays require some tricky syntax and frankly I do not think it’s worth it. A single-dimension array with a helper function is much easier to use.

Forging Ahead

    if (map->grid == NULL) {
        printf("Failed to malloc map->grid\n");
        exit(1);
    }

Here’s the thing about malloc(): It can fail to get the requested block of memory. It happens very rarely, but it can happen. Perhaps your PC is out of memory and can’t handle the request. Perhaps an antivirus or malware is interfering with the OS’s ability to hand out memory. Whatever the reason, we need to check and see if malloc() was succesful. We do this by seeing if our freshly allocated pointer equals NULL.

NULL is a macro in several C standard library headers that is used to represent a null value. In this case, we’re checking to see if the pointer we just allocated memory to still points to nothing. If it does, that means malloc() has failed and we need to exit the program after printing an error message to the console.

    for (int x = 0; x < map->width; x++) {
        for (int y = 0; y < map->height; y++) {
            struct Tile *t = get_tile(map, x, y);
            t->symbol = '.';
            t->bg = 0;
            t->fg = 0;
            t->prop = TILE_VISIBLE | TILE_DISCOVERED | TILE_WALKABLE;
        }
    }

Now we need to loop through the map and set the default values of each tile. We use get_tile() to get a pointer to the tile based on its x and y coordinate within the map. We then set symbol to a period, which will represent an empty floor tile in our game. The settings for bg and fg are just placeholders until we implement color in our game.

Setting prop has some interesting new syntax. Remember that our new enum TileProperties is using bitflags. The | operator, known as the OR bitwise operator, compares the bits of two values and selects any bits that are set to 1, or true, in either value. Here’s a representation of how that works:

TILE_WALKABLE   = 00000001 = 1
TILE_VISIBLE    = 00000010 = 2
TILE_DISCOVERED = 00000100 = 4

t->prop         = 00000111 = 7

By ORing the three values together, we create a new value that holds a 1 in each bit that represents the value. Therefore, a value of 7 in t->prop means that TILE_WALKABLE, TILE_VISIBLE, and TILE_DISCOVERED are all true for this tile. Pretty slick, huh?

    /* TEMP walls */
    for (int y = 0; y < map->height; y++) {
        struct Tile *t = get_tile(map, 0, y);
        t->symbol = '#';
        t->prop = TILE_VISIBLE | TILE_DISCOVERED;
        t = get_tile(map, map->width - 1, y);
        t->symbol = '#';
        t->prop = TILE_VISIBLE | TILE_DISCOVERED;
    }

    for (int x = 0; x < map->width; x++) {
        struct Tile *t = get_tile(map, x, 0);
        t->symbol = '#';
        t->prop = TILE_VISIBLE | TILE_DISCOVERED;
        t = get_tile(map, x, map->height - 1);
        t->symbol = '#';
        t->prop = TILE_VISIBLE | TILE_DISCOVERED;
    }
    /* END walls */
}

We finish off init_map() by adding a quick map generator. This will select every edge tile in our map and set its symbol to #, which represents our dungeon walls. We also change the tile’s properties to remove TILE_WALKABLE, as our player shouldn’t be able to walk through walls. That won’t change anything yet, we will implement the wall logic in the next chapter.

Under The C: Let My Memory Go

void destroy_map(struct Map *map) {
    free(map->grid);
    map->grid = NULL;
}

When we allocated dynamic memory earlier with malloc(), that memory is assigned by the OS to our program. The program only has two ways of telling the OS that it’s done with that memory. When the program ends and the OS takes all memory the program was using, dynamic or otherwise. The other method is having our program tell the OS that we’re done with that memory. If we do not tell the OS that we’re done with the memory and the program is still running, then it will hold it for us indefinitely.

So, what happens if we do this:

int *p;
p = malloc(sizeof(int));
p = malloc(sizeof(int));

We declare an int * named p, then dynamically allocate a block of memory that can hold a single int to it. Then we malloc() another block of memory to p. What do you think happens to the first block of memory? p no longer points to the old block, as malloc() returns the address of the second block.

That first block of memory is what we call a memory leak. The OS is still holding onto the memory, but the program no longer has any pointers pointing to it. This means the memory is in limbo until the program exits and the OS does cleanup. For a small program and a few bytes, probably not a big deal. But if you’re allocating large chunks of memory and letting them hang around without cleanup, you can cause all kinds of memory problems for the program and the OS.

Good stewardship of memory is important, so we use the free() function from stdlib.h to cleanup memory when we’re done. free() deallocates memory that a pointer points to. After it is called, your pointer will still point to the old address. That address may still have our data in it, or the OS may have cleaned it up and used it in another program. That’s why we always set a pointer to NULL after freeing its memory. The pointer’s memory isn’t valid, so we set it to point to nothing.

Finishing Our Map

struct Tile *get_tile(struct Map *map, int x, int y) {
    return &(map->grid[x + (map->width * y)]);
}

Let’s break this one down into pieces. grid[x + (map->width * y)] is how we change two coordinates into a position on our array. Let’s say that x is 2 and y is 1. Because our map start at 0,0 this means we want the third tile on the second row. So our code resolves like this:

map->grid[x + (map->width * y)]
map->grid[2 + (map->width * 1)]
map->grid[2 + (80 * 1)] /* assume our map's width is 80 for this example */
map->grid[82]

Now we know which tile we want. We wrap the tile in parenthesis and put the & operator at the beginning so that our return sends the address of the tile and not the tile itself. If we returned struct Tile instead of struct Tile *, we would return a copy of the tile instead of a pointer to the tile that’s inside map->grid. This lets us use the returned pointer to edit the tile’s data.

int is_walkable(struct Tile *t) {
    if (t->prop & TILE_WALKABLE) {
        return 1;
    }
    return 0;
}

int is_visible(struct Tile *t) {
    if (t->prop & TILE_VISIBLE) {
        return 1;
    }
    return 0;
}

int is_discovered(struct Tile *t) {
    if (t->prop & TILE_DISCOVERED) {
        return 1;
    }
    return 0;
}

These are helper functions that return if a tile has the requested property set. The interesting part is the if statement. The & operator when put between two values performs a bitwise AND operation. This is like the bitwise OR we saw earlier, execept it only sets the bit to 1 if both sides have it.

Let’s go back to our example of t->prop being set to 7 aka 00000111, and look at is_walkable(). The if statement will look like this after converting the numbers to binary:

if (00000111 & 00000001)

which looks like

  00000111
& 00000001
  --------
  00000001

Therefore the AND operation results in a value of 1. If t->prop only had TILE_VISIBLE set, then the operation would look like

  00000010
& 00000001
  --------
  00000000

Since 0 is a false value, is_walkable() returns a false value of 0.

void draw_map(struct Map *map) {
    for (int x = 0; x < map->width; x++) {
        for (int y = 0; y < map->height; y++) {
            struct Tile *t = get_tile(map, x, y);
            if (is_discovered(t)) {
                terminal_printf(x, y, "%c", t->symbol);
            }
        }
    }
}

Our last function in map.c is draw_map(). This should all look pretty straightforward. Notice that we’re using is_discovered() to check each tile’s properties. While it doesn’t matter yet, eventually we will only want to print tiles that the player has explored. We do have one new feature in terminal_printf(). This is an alternate drawing function for BLT that uses a format string.

Under The C: Format String

Format strings are a deep topic, and we’re only going to scratch the surface here. The most common place you’ll see them is in printf(). Let’s say we want to print a line to the terminal that outputs two int variables and a message, like Coord: x, y. The call to printf() would look like this:

int x = 3;
int y = 4;
printf("Coord: %d, %d\n", x, y); /* prints "Coord: 3, 4" to the console */

%d is a format token that will be replaced by a digit, aka an int. printf() looks at the format string we pass in and replaces each token with the next argument down the line. So the first %d is replaced by the value in x, and the second is replaced with the value in y.

The %c that we use in draw_map() is the format token for a char, which is the type that a tile’s symbol uses. BLT’s terminal_printf() uses the same format string syntax that printf() uses, which makes sense as C developers already know the syntax.

Consistency in player.c

So now that our basic map is setup, let’s do some quick cleanup on player.h and player.c. Since we’re using a char to represent tiles in struct Map, we should do the same in struct Player. Change the definition of struct Player to the following:

struct Player {
    int x;
    int y;
    char symbol;
};

We will then need a draw_player() function, similar to our draw_map(). Add the function declaration in player.h:

void draw_player(struct Player *player);

And then define the function at the bottom of player.c:

void draw_player(struct Player *player) {
    terminal_printf(player->x, player->y, "%c", player->symbol);
}

Refactoring main.c… Again!

Last, but not least, we need to get our map into main(). Before we do so, let’s take some time and clean up main.c. I like to keep my main() function as light as possible, so let’s take code that works together and break it into functions.

#include "BearLibTerminal.h"
#include "player.h"
#include "map.h"

#define WINDOW_WIDTH 100
#define WINDOW_HEIGHT 35
#define MAP_WIDTH 80
#define MAP_HEIGHT 25

First, We will define a set of constants. We want our game’s window to be a larger size than our map as we need space for UI components like player stats and messages. For now We will define a standard size for our map as well.

void setup_game() {
    terminal_open();
    terminal_setf("window.title='roguelike-tutorial'; window.size=%dx%d;",
        WINDOW_WIDTH, WINDOW_HEIGHT);
}

We will move our setup code into its own function. terminal_setf() is a BLT function that sets options for our game window. This is easily the most complicated part of using BLT and has an entire page dedicated just to it in the documentation.

We set the window’s title to “roguelike-tutorial”, though you should change it to whatever you want to name your game. The size uses a format string to set the size of the game window.

void end_game(struct Map *map) {
    destroy_map(map);
    terminal_close();
}

Since we have a setup function, we should also have an end function. We call destroy_map() to cleanup our dynamically allocated map data and close the terminal.

void update() {

}

void draw(struct Player *player, struct Map *map) {
    terminal_clear();

    draw_map(map);
    draw_player(player);

    terminal_refresh();
}

We will setup two functions for our game loop. update() will hold game logic code in it, which we haven’t implemented yet. draw() will hold any code that draws to the screen.

int main(int argc, char** argv)
{
    setup_game();

    struct Player player;
    init_player(&player);

    struct Map map;
    init_map(&map, MAP_WIDTH, MAP_HEIGHT);

    do {
        update();
        draw(&player, &map);
    } while (handle_input_player(&player, terminal_read()));

    end_game(&map);
    return 0;
}

Now we have our cleaned up main(). We setup the game, init our player and map, then start the game loop. Instead of a while loop we use a do while, which ensures that our game will at least run one game iteration. This also means that we do not have to keep track of an exit variable anymore.

If you’ve never seen a do while loop, the syntax may look a little odd to you. Our conditional goes at the end of the loop instead of the beginning. Also, in C a do while loop requires a semicolon at the end of the while statement.

Run make and start up your freshly compiled game. It should look something like this:

We’ve got walls and player that can move around inside them. We haven’t implemented move checking yet, so you can still walk through walls and outside the game window. Next time we will start with fixing that, then move onto generating a real dungeon to explore.

If you’re stuck or getting weird issues, compare your code to the code above. A missing line of code could cause all kinds of weird behavior. You can also visit the git branch for this chapter and compare your code to the tutorial’s.