roguelike-tutorial

Roguelike Tutorial Revised ported to C

View on GitHub

Chapter 04: If You Build It, They Will Come

In this chapter we will finally be building a map for your player to explore. We will learn about procedural generation and get our player moving properly through our generated dungeons. This chapter is quite long and has a lot of coding.

First, let’s get our walls working. Right now the player can step through walls. Open player.c and look at handle_input_player(). Since this function handles the player’s movement through the dungeon, it looks like a good place to check if a move is valid.

Open player.h as well and change handle_input_player() to the following

int handle_input_player(struct Player *player, struct Map *map);

Since we are adding the map as an argument, we will need to include map.h at the top of player.h, like so:

#ifndef RTUT_PLAYER_H
#define RTUT_PLAYER_H

#include "map.h"

struct Player {
/* rest of player.h */

Now we will need to rewrite handle_player_input(). Since we took the key argument out of the function’s parameter list, we will need to call terminal_read() here instead of in main().

int handle_input_player(struct Player *player, struct Map *map)
{
    while (1) {
        int key = terminal_read();

The majority of this function is wrapped in a while loop, as we need to be able to test again for input when the player tries to hit a wall. If we do not do this, then an invalid move will still count as a turn, which is not the desired behavior.

        /* Player movement */
        if (key >= TK_RIGHT && key <= TK_UP) {
            int dx = player->x, dy = player->y;
            switch (key) {
            case TK_UP:
                --dy;
                break;

            case TK_DOWN:
                ++dy;
                break;

            case TK_LEFT:
                --dx;
                break;

            case TK_RIGHT:
                ++dx;
                break;
            }

TK_RIGHT is defined to 0x4F, or 79. TK_UP is defined to 0x52, or 82. Between these are TK_LEFT and TK_DOWN. Because our input’s define directives are sequential, we use the if statement to see if the input falls between TK_RIGHT and TK_UP, meaning movement was entered.

dx and dy are set to the player’s coordinates, then modified based on the input. This means that dx and dy represent where the player wants to go.

            struct Tile *t = get_tile(map, dx, dy);
            if (is_walkable(t)) {
                set_pos_player(player, dx, dy);
                break; /* Made a move, break from the loop */
            } else {
                continue; /* Hit a wall, restart input loop */
            }

t points to the target tile. We use the handy is_walkable() function to see if it’s ok for the player to step onto the tile. If so, we set the player’s position and break from the while loop. If is_walkable() returns 0, then we know that the move is invalid and we restart our loop, testing for input again from the player.

As a side note, we’ve now seen a few good uses of pointers. Being able to quickly get an address to the memory of the tile instead of searching for it in a list or copying its data is a huge benefit of C, and a major part of writing good C code.

        } else if (key == TK_CLOSE || key == TK_ESCAPE) {
            return 0;
        }
    }

    return 1;
}

Here is the end of our function. If our input isn’t a move, then we test to see if it’s TK_CLOSE or TK_ESCAPE. If so, the function immediately returns 0.

When the while loop exits, the function returns 1, which is our true value we send to the primary game loop in main() to let it know that the game is still going.

Speaking of which, we will need to modify how handle_input_player() is being called in main(). Open main.c and change the game loop to the following:

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

We pass in map and do not worry about calling terminal_read() here since it’s now being called int handle_input_player().

Run make and test the game. Your player should no longer be able to walk through walls!

Dungeon Trek: Generations

Now we get to the fun part… math! It’s time to start building our dungeon. First, let’s close all our open files, then open map.h and map.c. we will start by adding an enum to map.h and modifying struct Map and the declaration of init_map()

enum MapType {
    MAPTYPE_RECT
};

struct Map {
    struct Tile *grid;
    enum MapType maptype;
    int width;
    int height;
    int start_x;
    int start_y;
};

void init_map(struct Map *map, int w, int h, enum MapType type);

After the declaration of struct Tile, add the above enum. We will use this enum MapType to signify different types of maps to generate. The first one we will start with is a basic dungeon made of rectangle shaped rooms and hallways that connect them, like the classic Rogue that this genre is named after.

We add an enum MapType to struct Map in case we need to query the map type sometime down the road. We also add two new variables to struct Map that track the starting position of the player when enterint the map.

The declaration of init_map() is also modified to take an enum MapType as a parameter.

Next, open map.c and modify the definition of init_map(). Here is the new version of it:

void init_map(struct Map *map, int w, int h, enum MapType type) {
    map->width = w;
    map->height = h;
    map->maptype = type;
    map->grid = malloc(sizeof(struct Tile) * w * h);
    if (map->grid == NULL) {
        printf("Failed to malloc map->grid\n");
        exit(1);
    }

    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;
        }
    }

    switch (map->maptype) {
    case MAPTYPE_RECT:
        generate_rect(map);
        break;
    }
}

Note that we’ve modified the function’s signature to match map.h. We’re also setting map->maptype in line 3.

The most important change is when setting t->prop for each tile. I’ve noted it with a comment in the above code, you do not need to add that comment to your version. We are removing TILE_WALKABLE from all tiles. That’s because procedural map generation is much, much easier to do if we start with a dungeon of walls and then carve our rooms and hallways out. Starting with a big empty room and adding walls is way more difficult, and you’ll find that most roguelikes do the “carving” method.

Since we’re making everything a wall, we also need to set t->symbol to #. This is an easy change to miss.

At the end of the function, we build a switch for the different map types and call the proper generation function. Right now there’s only MAPTYPE_RECT, but later we can add new types and generator functions.

Next we will need to build generate_rect(). Because no external functions need to use a generator function, there’s no need to put it in map.h as we do not want it to be part of the interface. However, there is another thing we need to be aware of.

Under The C: Reading Top To Bottom

When the C compiler does a pass over a source file, it starts at the top and reads down. For example, we have a set of a source file and a header that looks like so:

/* file.h */

void do_thing();
/* file.c */

void do_thing() {
    /* do stuff */
    other_thing();
}

void other_thing() {
    /* do other stuff! */
}

file.h provides do_thing() as part of its interface to other code. Since nothing provided in file.h is required for file.c, like a struct or enum definition, we do not need to include it. The compiler will figure out how to hook the function declaration in file.h to the function definition in file.c.

However, when we try to compile file.c the compiler will say that it can’t find other_thing(). The reason is that after the preprocessor is finished, the compiler reads the processed source file from top to bottom. That means that it starts with do_thing(), but when it hits the call to other_thing() inside do_thing(), the compiler has not seen any information about other_thing() and errors out.

There are several ways to fix this. The easiest is to add other_thing() to file.h. However, we do not want users of file.h to be able to call other_thing(), so that’s not an option.

We could rearrange file.c so that other_thing() comes first, and that would solve our problem:

/* file.c */

#include "file.h"

void other_thing() {
    /* do other stuff! */
}

void do_thing() {
    /* do stuff */
    other_thing(); /* Now it works! */
}

Now the compiler knows what other_thing() is and can wire up the call to it in do_thing(). That’s great, but let’s say that file.c grows and now has dozens of functions. Keeping track of where to move functions in a file so that the compiler reads them correctly is extremely tedious. Thankfully there is a saner way to do this. Going back to our unfixed version of file.c, where other_thing() is below do_thing(), we can also do this to fix the problem:

/* file.c */

#include "file.h"

void other_thing();

void do_thing() {
    /* do stuff */
    other_thing();
}

void other_thing() {
    /* do other stuff! */
}

By placing a function declaration at the top of the file, we are telling the compiler to not worry when it hits the call to other_thing() inside of do_thing(). Because there is a declaration available, the compiler sees that there will be a function named other_thing() and that its definition will come later. Of course, if we do not provide a definition then the compiler will error out.

Which method to use is up to you. Some people hate putting function definitions at the top and reorder the code to make sure it compiles. While I understand the reasoning behind that method, I personally do not agree and will put declarations at the top of a file if it makes sense. It makes sense for init_map() to be the first function of map.c, as it starts the interaction with struct Map. If map.c starts with all our generator functions, it lowers readability.

Choosing how to structure your code depends on many factors, so there is no “one true answer”. Pick what you like and what works best for you.

Preparing map.c

Here is the modified beginning of map.c

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

#include "map.h"

#define MIN_RECT_SIZE 5
#define MAX_RECT_SIZE 10

/* Generator declarations */
void generate_rect(struct Map *map);

void init_map(struct Map *map, int w, int h, enum MapType type) {

Notice that we’ve added time.h to the include list. This is a standard library header containing functions around time. We will use the current time as a seed for our random number generator later.

The two define macros set constants for how big and small our rectangular rooms can be.

Now you have a place to put new generator function declarations. One last thing before we get started is to build a few helper functions for our generator. Go to the bottom of map.c and add the following:

void set_walkable_on(struct Tile *t) {
    t->prop |= TILE_WALKABLE;
}

void set_visible_on(struct Tile *t) {
    t->prop |= TILE_VISIBLE;
}

void set_discovered_on(struct Tile *t) {
    t->prop |= TILE_DISCOVERED;
}

void set_walkable_off(struct Tile *t) {
    t->prop &= ~(TILE_WALKABLE);
}

void set_visible_off(struct Tile *t) {
    t->prop &= ~(TILE_VISIBLE);
}

void set_discovered_off(struct Tile *t) {
    t->prop &= ~(TILE_DISCOVERED);
}

We’ve got some fun bit fiddling going on here. |= and &= are shorthand operators.

t->prop |= TILE_WALKABLE;
t->prop &= ~(TILE_WALKABLE);

becomes

t->prop = t->prop | TILE_WALKABLE;
t->prop = t->prop & ~(TILE_WALKABLE);

The on functions are similar to the earlier discussion we had on bitflags. We OR the desired property with the current setting which makes sure that the bit representing our property is set.

The off functions are a little trickier. If we turn it into pseudocode, set_walkable_off() turns into

t->prop = t->prop AND the bitwise inverse of TILE_WALKABLE

Here’s how that looks in binary.

t->prop          = 00000111 /* t->prop is discovered, visible, and walkable */

TILE_WALKABLE    = 00000001
~(TILE_WALKABLE) = 11111110

  00000111 /* t->prop */
& 11111110 /* The bitwise inverse of TILE_WALKABLE */
  --------
  00000110 /* TILE_WALKABLE is unset */

Bitwise inverse is also known as the “unary not” or bitwise NOT operator, represented in C by the tilde character ~. If your head is spinning, fear not. This is an advanced subject and requires some practice to get down. I have to lookup bitwise tricks all the time. A great resource if you want to dig in much deeper than we need is Bit Twiddling Hacks

We need code for carving a room into our map. As we come up with more room types, we can add more room building functions, but for now we just need the ability to create a rectangle

void create_room_rect(struct Map *map, int x1, int y1, int w, int h) {
    for (int x = x1 + 1; x < x1 + w - 1; x++)  {
        for (int y = y1 + 1; y < y1 + h - 1; y++) {
            struct Tile *t = get_tile(map, x, y);
            if (t != NULL) {
                t->symbol = '.';
                set_walkable_on(t);
            }
        }
    }
}

What is with the +1 and -1 ? Think about what we’re saying when we tell our program that we want a room at coordinates (1, 1) that goes to (6, 6). You might assume that would carve out a room like this one (remember that lists are 0-indexed, so (0, 0) is a wall in this case):

  0 1 2 3 4 5 6 7
0 # # # # # # # #
1 # . . . . . . #
2 # . . . . . . #
3 # . . . . . . #
4 # . . . . . . #
5 # . . . . . . #
6 # . . . . . . #
7 # # # # # # # #

That’s all fine and good, but what happens if we put a room right next to it? Let’s say this room starts at (7, 1) and goes to (9, 6)

  0 1 2 3 4 5 6 7 8 9 10
0 # # # # # # # # # # #
1 # . . . . . . . . . #
2 # . . . . . . . . . #
3 # . . . . . . . . . #
4 # . . . . . . . . . #
5 # . . . . . . . . . #
6 # . . . . . . . . . #
7 # # # # # # # # # # #

There’s no wall separating the two! That means that if two rooms are one right next to the other, then there won’t be a wall between them! So long story short, our function needs to take the walls into account when digging out a room. So if we have a rectangle with coordinates x1 = 1, x2 = 6, y1 = 1, and y2 = 6, then the room should actually look like this:

  0 1 2 3 4 5 6 7
0 # # # # # # # #
1 # # # # # # # #
2 # # . . . . # #
3 # # . . . . # #
4 # # . . . . # #
5 # # . . . . # #
6 # # # # # # # #
7 # # # # # # # #

This ensures that we will always have at least a one tile wide wall between our rooms, unless we choose to create overlapping rooms. In order to accomplish this, we add +1 to x1 and y1.

The other new feature of this function is checking the return value of get_tile() for NULL. What if we accidently ask for a tile off the side of the map? Without some error handling code, the program will compile just fine but crash at runtime with an arcane SIGSEV or segfault error, which means “I screwed up accessing a memory address and had to crash”. SIGSEV and segfault can be extremely hard to debug, so let’s add a little protection. This means we also need to modify get_tile() and add some error handling. Here is the new version of get_tile()

struct Tile *get_tile(struct Map *map, int x, int y) {
    if (x < 0 || x >= map->width || y < 0 || y >= map->height) {
        return NULL;
    }
    return &(map->grid[x + (map->width * y)]);
}

We check to see if x or y is out of bounds for the map, and return NULL if they are. The adding and subtracting of 1 from each side is to account for the double walls we talked about earlier.

Also, we need to be able to set the start points in the map. Here’s a quick pair of functions to do so:

void get_center_rect(int *cx, int *cy, int x, int y, int w, int h) {
    *cx = (x + x + w) / 2;
    *cy = (y + y + h) / 2;
}

void set_start_rect(struct Map *map, int x, int y, int w, int h) {
    get_center_rect(&(map->start_x), &(map->start_y), x, y, w, h);
}

get_center_rect() is the first time we’ve used pointers for assignments for a function. Since we can’t return two int from a function but need to provide both an x and y coordinate, we will use 2 pointers to int instead. Remember that that *cx and *cy are using the dereference operator, and as such are setting the value that they point to. We will see how to use this function in a moment.

set_start_rect() will be used on our first generated room to get the center position and set map->start_x and map->start_y. We will use those values to place the player in the relative middle of the first room.

Strike The Earth!

Now that we’ve got our helper functions built, lets start writing generate_rect()

void generate_rect(struct Map *map) {
    create_room_rect(map, 1, 1, 10, 10);
    set_start_rect(map, 1, 1, 10, 10);
    create_room_rect(map, 30, 15, 14, 5);
}

We will start with two hard-coded rooms as a demonstration. After building the first room, we set start_x and start_y to be the middle of that room.

Lastly, we need to modify the call to init_map() in main() and set our player’s starting position. Open main.c and change the call to init_map() to the following:

    struct Map map;
    init_map(&map, MAP_WIDTH, MAP_HEIGHT, MAPTYPE_RECT);
    set_pos_player(&player, map.start_x, map.start_y);

With that, run make and start your game. You should see a similar room layout:

We Are All Slaves to Armok

Now let’s actually get our dwarf on and start digging some real rooms. We also need to dig tunnels to connect our rooms, and we will start with those functions first. Be sure to either place these above generate_rect() or add function declarations at the top of map.c. Since these tunnel functions are directly related to create_room_rect(), I’m going to put them between create_room_rect() and get_center_rect().

int int_max(int a, int b) {
    return a > b ? a : b;
}

int int_min(int a, int b) {
    return a < b ? a : b;
}

void create_h_tunnel(struct Map *map, int x1, int x2, int y) {
    for (int x = int_min(x1, x2); x <= int_max(x1, x2); x++) {
        struct Tile *t = get_tile(map, x, y);
        if (t != NULL) {
            t->symbol = '.';
            set_walkable_on(t);
        }
    }
}

void create_v_tunnel(struct Map *map, int x, int y1, int y2) {
    for (int y = int_min(y1, y2); y <= int_max(y1, y2); y++) {
        struct Tile *t = get_tile(map, x, y);
        if (t != NULL) {
            t->symbol = '.';
            set_walkable_on(t);
        }
    }
}

int_max and int_min are helper functions to determine the maximum and minimum of two int. We will use them in our tunnel creation.

The tunnel creation methods both use the same algorithm. Let’s use create_h_tunnel() as an example. It chooses a starting point that is the lower of the two x values and then carves each space out up to and including the higher x value. We use <= because we want the tunnel to break through that extra wall in the destination room.

We also need to check when two generated rooms are intersecting on top of each other:

void set_start_rect(struct Map *map, int x, int y, int w, int h) {
    map->start_x = ((x + 1 + w) - (x - 1)) / 2;
    map->start_y = ((y + 1 + h) - (y - 1)) / 2;
}

void set_center_rect(int *cx, int *cy, int x, int y, int w, int h) {
    *cx = (x + x + w) / 2;
    *cy = (y + y + h) / 2;
}

int intersects(struct Map *map, int x1, int y1, int w, int h) {
    for (int x = x1 + 1; x < x1 + w; x++)  {
        for (int y = y1 + 1; y < y1 + h; y++) {
            struct Tile *t = get_tile(map, x, y);
            if (t != NULL && t->symbol == '.') {
                return 1;
            }
        }
    }
    return 0;
}

intersects() is placed after set_center_rect() from earlier. It looks over the floor space of a generated room and sees if there’s already open floor space there. We will use this to throw away rectangles that end up on top of each other.

Time to start on generate_rect(). Remove the code inside it and start over.

void generate_rect(struct Map *map) {
    srand(time(NULL));
    rand();

    int num_room = 0, px = 0, py = 0, pw = 0, ph = 0;

srand() sets a seed for our random number generator. time(NULL) selects the current time according to the system clock, down to the second. Therefore we are setting the current time as the seed for the dungeon, which means we will get a different dungone as long as we’re not generating more than one a second.

rand() returns a random int between 0 and INT_MAX, which depends on your system but is usually 2^32, or 2,147,483,647. Convention is to call rand() once without using it after seeding. Due to the way rand() is implemented, it has a bias on what number is made the first time you call it. Therefore, we call and ignore the return value once.

num_room will keep track of how many rooms we have successfully generated, and the other int variables will keep track of the previous room we have made. This will help when we draw our tunnels from room to room.

    for (int i = 0; i < 200; i++) {
        int x = rand() % (map->width - 1);
        int y = rand() % (map->height - 1);
        int w = rand() % (MAX_RECT_SIZE - MIN_RECT_SIZE + 1) + MIN_RECT_SIZE;
        int h = rand() % (MAX_RECT_SIZE - MIN_RECT_SIZE + 1) + MIN_RECT_SIZE;

Since we’re going to throw away any room that overlaps another, we’re going to try generating 200 rooms. Feel free to adjust this as you wish, but 200 seems to be a nice balance between speed and a good sample of rooms.

rand() returns a number between 0 and 2.1 billion, so we will need to use modulo division against it. This is a quick and effective way to clamp our randomly generated number between 0 and an upper bound, like map->width - 1 for x.

With w and h, we want our lower bound to be MIN_RECT_SIZE, not 0. Here’s how the expression evaluates for w:

/* In this example, rand() returns 200 */
int w = rand() % (MAX_RECT_SIZE - MIN_RECT_SIZE + 1) + MIN_RECT_SIZE;
int w = 200 % (10 - 5 + 1) + 5;
int w = 200 % 6 + 5;
int w = 2 + 5;
int w = 7;

This algorithm keeps our random number between MIN_RECT_SIZE and MAX_RECT_SIZE. let’s continue writing the generator.

        if (x + w >= map->width || y + h >= map->height) {
            continue;
        }

It’s entirely possible that we generate a room whose x or y value would make it go off the side of the map. Instead of tweaking our random number generation algorithm, we will just throw away any results that would overflow off the side. This keeps our random number generation simple.

        if (!intersects(map, x, y, w, h)) {
            create_room_rect(map, x, y, w, h);

We use intersects() to make sure that the room isn’t overlapping one we’ve already set. If not, create the new room.

            ++num_room;
            if (num_room == 1) {
                set_start_rect(map, x, y, w, h);

Increment num_room to keep track of how many rooms we have. If it’s our first, we do not need to create any tunnels. However, we need to set the player’s start position. Using set_start_rect(), we will set the start positions in our struct Map.

            } else {
                int prev_cx = 0;
                int prev_cy = 0;
                get_center_rect(&prev_cx, &prev_cy, px, py, pw, ph);

                int cur_cx = 0;
                int cur_cy = 0;
                get_center_rect(&cur_cx, &cur_cy, x, y, w, h);

If it’s not the first room, then we need to make some tunnels. We start by getting the center coordinates of the previous room and the current room. Since get_center_rect() sets the respective cx and cy of each room’s center, we create variables before calling the function then pass their addresses with the & operator. This lets get_center_rect() effectively “return” two int.

                if (rand() % 2 == 0) {
                    create_h_tunnel(map, prev_cx, cur_cx, prev_cy);
                    create_v_tunnel(map, cur_cx, prev_cy, cur_cy);
                } else {
                    create_v_tunnel(map, prev_cx, prev_cy, cur_cy);
                    create_h_tunnel(map, prev_cx, cur_cx, cur_cy);
                }
            }

By calling rand and modulo dividing by 2, we basically flip a coin. The result determines if we start with a horizontal or vertical tunnel. This gives more elements of randomness to our map generation.

            px = x;
            py = y;
            pw = w;
            ph = h;
        }
    }
}

Lastly, we will take our current room’s coordinates and set them as the previous room. This way we always know the dimensions of the last room and can draw our tunnels.

Darkest Dungeons

Run make and fire up your game. Quit and restart the game a few times to see how the dungeons look. It’s pretty basic, but there are tons of dungeon generation algorithms that you can discover and implement. Since we built a way to select dungeon generation types in init_map(), it should be very simple to add a new generator!

Next time we will spend some time prettying up our ASCII by adding a nice looking font and color. Then we will dig deep into some math and build our field of view system. It is going to be a lot of work, but the game will look better and start to play like a real roguelike!

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.