Complete roguelike tutorial using C++ and libtcod - part 3: dungeon building

Complete roguelike tutorial using C++ and libtcod -originally written by Jice Text in this tutorial was released under the Creative Commons Attribution-ShareAlike 3.0 Unported and the GNU Free Documentation License (unversioned, with no invariant sections, front-cover texts, or back-cover texts) on 2015-09-21.

part 1: setting up part 2: map and actors part 3: dungeon building part 4: field of view part 5: preparing for combat part 6: going berserk! part 7: the GUI part 8: items and inventory part 9: spells and ranged combat part 10.1: persistence part 10.2: game menu part 11: dungeon levels and character progression extra 1: about editors and IDE extra 2: debugging extra 3: scent tracking extra 4: makefiles extra 5: more generic items

In this article, we will improve the Map class to generate a real dungeon with rooms and corridors. We'll use a very simple dungeon generator, using a straightforward way to connect rooms together. This will result in "winnable" dungeons (no room disconnected) but with a slightly chaotic look. For a better corridor connection, check the libtcod C++ samples in the libtcod/samples/ directory.

View source here

libtcod functions used in this article

TCODRandom::getInstance

TCODRandom::getInt

TCODBsp::TCODBsp

TCODBsp::splitRecursive

TCODBsp::traverseInvertedLevelOrder

A hole digging map

Whereas we were adding walls in an empty map in the last article, this time, we will dig holes in a map full of walls. We need to change the Map class declaration for that :

Tile() : canWalk(false) {}

Tiles default to non-walking.

protected :
    Tile *tiles;
    friend class BspListener;

    void dig(int x1, int y1, int x2, int y2);
    void createRoom(bool first, int x1, int y1, int x2, int y2);
};

We replace the setWall function by a function that digs a rectangular zone. We also make a declaration that will allow some BspListener class to use the protected dig function. The BspListener class is not declared in the header because it's private to the Map class. The createRoom function will dig the room and populate it with actors.

The implementation

We define some constants for the room size range :

static const int ROOM_MAX_SIZE = 12;
static const int ROOM_MIN_SIZE = 6;

The static keyword, when used on a global variable means that the variable is not visible from outside the .cpp file.

The digging function

void Map::dig(int x1, int y1, int x2, int y2) {
    if ( x2 < x1 ) {
        int tmp=x2;
        x2=x1;
        x1=tmp;
    }
    if ( y2 < y1 ) {
        int tmp=y2;
        y2=y1;
        y1=tmp;
    }
    for (int tilex=x1; tilex <= x2; tilex++) {
        for (int tiley=y1; tiley <= y2; tiley++) {
            tiles[tilex+tiley*width].canWalk=true;
        }
    }
}

The only subtlety here is that we allow x2 to be smaller than x1 and y2 to be smaller than y1. That's why we swap the variables first to put them back in the right order. Being able to dig with *2 coordinates smaller than *1 will be handy for corridor digging.

The room creation

void Map::createRoom(bool first, int x1, int y1, int x2, int y2) {
    dig (x1,y1,x2,y2);
    if ( first ) {
        // put the player in the first room
        engine.player->x=(x1+x2)/2;
        engine.player->y=(y1+y2)/2;
    } else {
        TCODRandom *rng=TCODRandom::getInstance();
        if ( rng->getInt(0,3)==0 ) {
            engine.actors.push(new Actor((x1+x2)/2,(y1+y2)/2,'@',
                TCODColor::yellow));
        }
    }
}

First we dig the room, then put either the player in its center (only for the first room) or some NPC in 25% of other rooms. We're using here libtcod's random number generator.

The new constructor : where the BSP magic resides

Map::Map(int width, int height) : width(width),height(height) {
    tiles=new Tile[width*height];
    TCODBsp bsp(0,0,width,height);
    bsp.splitRecursive(NULL,8,ROOM_MAX_SIZE,ROOM_MAX_SIZE,1.5f,1.5f);
    BspListener listener(*this);
    bsp.traverseInvertedLevelOrder(&listener,NULL);
}

Here we're using libtcod's BSP toolkit to easily create a dungeon using this algorithm. We create a bsp object the same size as our map

TCODBsp bsp(0,0,width,height);

and split it so that every node size is at least the maximum size of our rooms. The recursion level (8) is not very important because the splitting process stops as soon as the nodes reach the desired size. Every new recursion level, the nodes are split in 2.

bsp.splitRecursive(NULL,8,ROOM_MAX_SIZE,ROOM_MAX_SIZE,1.5f,1.5f);

The 1.5 coefficients are the maximum H/V and V/H ratio of the nodes. That means there will be rectangular nodes, but there won't be very flat nodes.

Finally we create the listener and traverse the BSP tree.

BspListener listener(*this);
bsp.traverseInvertedLevelOrder(&listener,NULL);

The BSP listener

All we have to do now is a class that implements libtcod ITCODBspCallback interface.

class BspListener : public ITCODBspCallback {
private :
    Map ↦ // a map to dig
    int roomNum; // room number
    int lastx,lasty; // center of the last room

Here we're creating a class that inherits a class declared in litbcod.hpp. This ITCODBspCallback class only has a single abstract virtual "visitNode" method. This is the method TCODBsp will call for every node in the BSP tree.

Concerning the fields, we need a reference to the map to dig (we could have used a pointer. A reference is just a hidden pointer that can't be null).

roomNum will contains the number of room. We're only using it to put the player in the first room.

lastx and lasty will store the coordinates of the center of the last created room. We need this to dig a corridor between the last room and the current one.

The constructor is straightforward :

public :
    BspListener(Map &map) : map(map), roomNum(0) {}

And now the node visiting function :

bool visitNode(TCODBsp *node, void *userData) {
    if ( node->isLeaf() ) {

We're only creating rooms in the BSP leafs.

int x,y,w,h;
// dig a room
TCODRandom *rng=TCODRandom::getInstance();
w=rng->getInt(ROOM_MIN_SIZE, node->w-2);
h=rng->getInt(ROOM_MIN_SIZE, node->h-2);
x=rng->getInt(node->x+1, node->x+node->w-w-1);
y=rng->getInt(node->y+1, node->y+node->h-h-1);
map.createRoom(roomNum == 0, x, y, x+w-1, y+h-1);

We're using libtcod's random number generator to get some random room size and position. We make sure the size is bigger than ROOM_MIN_SIZE and smaller than the node size (remember the nodes are bigger than ROOM_MAX_SIZE). We subtract 2 to the node size to ensure the room does not reach the node border. Thus we avoid joined rooms and more important, we avoid rooms reaching the map border. This way, no need to check if the player goes out of the map in the walking code because there will always be a wall on the map border.

if ( roomNum != 0 ) {
    // dig a corridor from last room
    map.dig(lastx,lasty,x+w/2,lasty);
    map.dig(x+w/2,lasty,x+w/2,y+h/2);
}

For other rooms, we dig a corridor from the center of the last room.

            lastx=x+w/2;
            lasty=y+h/2;
            roomNum++;
        }
        return true;
    }
};

Finally, we update the last room center coordinates and increase the room number. Returning true tells TCODBsp to keep traversing the tree. Returning false would allow to break from the traversal.

Since the Map implementation is now using the TCODBsp and Engine classes, we need to update the headers :

#include "libtcod.hpp"
#include "Map.hpp"
#include "Actor.hpp"
#include "Engine.hpp"

Finalizing

That's it. We only have to slightly change the Engine constructor to remove the NPC creation and we're done :

Engine::Engine() {
    TCODConsole::initRoot(80,50,"libtcod C++ tutorial",false);
    player = new Actor(40,25,'@',TCODColor::white);
    actors.push(player);
    map = new Map(80,45);
}

Let's compile the code with the same commands as in the previous articles :

Windows :

> g++ src/*.cpp -o tuto -Iinclude -Llib -ltcod-mingw -static-libgcc -static-libstdc++ -Wall

Linux :

> g++ src/*.cpp -o tuto -Iinclude -L. -ltcod -ltcodxx -Wl,-rpath=. -Wall

and enjoy our new dungeon !