In my last post I started working on creating a randomly generated dungeon. At the end of the post there were cells that were marked as being reserved empty, ie: no rooms will be put there. In this post I’ll be adding in the rooms.
The way my code is setup the user must first create a GeneratedMap object, then call its generateMap() method.
void GeneratedMap::generateMap()
{
//create empty map
myMapCells = std::vector<std::vector<char>>();
for (int y = 0; y < myHeight; y++)
{
std::vector<char> row = std::vector<char>();
for (int x = 0; x < myWidth; x++)
row.push_back('.');
myMapCells.push_back(row);
}
printMap("Empty map:");
srand(time(0));
//add in purposely blank cells, so there's some emptiness
createEmptyCells();
printMap("with empty cells:");
//now to finally create rooms
fillRooms();
printMap("with rooms!");
}
I should note here that I’m using std::random_shuffle in my code, I learned after I wrote the code that when using C++11 std::random should be used because std::random_shuffle is to be deprecated in C++14
In the last post everything up to fillRooms() was covered, so let’s jump into that. It’s a really long method, and it should have been split out or better optimized, but it is what it is, and it works.
void GeneratedMap::fillRooms()
{
Vector2i startEnter, startFrom;
Room* seedRoom;
do
{
startEnter.x = rand() % myWidth;
startEnter.y = rand() % myHeight;
int dir = rand() % 4;
switch (dir)
{
case 0: //from left
startFrom.x = startEnter.x - 1;
startFrom.y = startEnter.y;
break;
case 1: //from right
startFrom.x = startEnter.x + 1;
startFrom.y = startEnter.y;
break;
case 2: //from top
startFrom.x = startEnter.x;
startFrom.y = startEnter.y - 1;
break;
case 3: //from bottom
startFrom.x = startEnter.x;
startFrom.y = startEnter.y + 1;
break;
}
if (startFrom.x < 0 || startFrom.x >= myWidth
|| startFrom.y < 0 || startFrom.y >= myHeight)
{
continue;
}
seedRoom = createRoom(startEnter, startFrom);
if (seedRoom != nullptr)
break;
} while (true);
rooms.push_back(seedRoom);
placeRoom(seedRoom);
roomStack.push_back(seedRoom);
while (roomStack.size() > 0)
{
//get the next room and remove it from the list/stack
Room* room = *roomStack.begin();
roomStack.erase(roomStack.begin());
//try to generate another room in each direction
if (room->topLeft.x > 0 && room->left == nullptr)
{
//to left
std::vector<Vector2i> possibleStarts;
for (int y = room->topLeft.y; y <= room->bottomRight.y; y++)
possibleStarts.push_back(Vector2i(room->topLeft.x - 1, y));
std::random_shuffle(possibleStarts.begin(), possibleStarts.end());
//try to find an unassigned adjacent cell to the left
Vector2i entrance;
bool validStart = false;
do
{
entrance = *possibleStarts.begin();
possibleStarts.erase(possibleStarts.begin());
if (myMapCells[entrance.y][entrance.x] == '.')
{
validStart = true;
break;
}
} while (possibleStarts.size() > 0);
if (validStart)
{
Vector2i from(entrance.x + 1, entrance.y);
Room* newroom = nullptr;
do {
newroom = createRoom(entrance, from);
} while (newroom == nullptr);
if (newroom != nullptr)
{
placeRoom(newroom);
room->left = newroom;
roomStack.push_back(newroom);
rooms.push_back(newroom);
}
}
}
if (room->bottomRight.x < myWidth - 1 && room->right == nullptr)
{
//to right
std::vector<Vector2i> possibleStarts;
for (int y = room->topLeft.y; y <= room->bottomRight.y; y++)
possibleStarts.push_back(Vector2i(room->bottomRight.x + 1, y));
std::random_shuffle(possibleStarts.begin(), possibleStarts.end());
//try to find an unassigned adjacent cell to the right
Vector2i entrance;
bool validStart = false;
do
{
entrance = *possibleStarts.begin();
possibleStarts.erase(possibleStarts.begin());
if (myMapCells[entrance.y][entrance.x] == '.')
{
validStart = true;
break;
}
} while (possibleStarts.size() > 0);
if (validStart)
{
Vector2i from(entrance.x - 1, entrance.y);
Room* newroom = nullptr;
do {
newroom = createRoom(entrance, from);
} while (newroom == nullptr);
if (newroom != nullptr)
{
placeRoom(newroom);
room->right = newroom;
roomStack.push_back(newroom);
rooms.push_back(newroom);
}
}
}
if (room->topLeft.y > 0 && room->top == nullptr)
{
//top
std::vector<Vector2i> possibleStarts;
for (int x = room->topLeft.x; x <= room->bottomRight.x; x++)
possibleStarts.push_back(Vector2i(x, room->topLeft.y - 1));
std::random_shuffle(possibleStarts.begin(), possibleStarts.end());
//try to find an unassigned adjacent cell to the top
Vector2i entrance;
bool validStart = false;
do
{
entrance = *possibleStarts.begin();
possibleStarts.erase(possibleStarts.begin());
if (myMapCells[entrance.y][entrance.x] == '.')
{
validStart = true;
break;
}
} while (possibleStarts.size() > 0);
if (validStart)
{
Vector2i from(entrance.x, entrance.y + 1);
Room* newroom = nullptr;
do {
newroom = createRoom(entrance, from);
} while (newroom == nullptr);
if (newroom != nullptr)
{
placeRoom(newroom);
room->top = newroom;
roomStack.push_back(newroom);
rooms.push_back(newroom);
}
}
}
if (room->bottomRight.y < myHeight - 1 && room->bottom == nullptr)
{
//bottom
std::vector<Vector2i> possibleStarts;
for (int x = room->topLeft.x; x <= room->bottomRight.x; x++)
possibleStarts.push_back(Vector2i(x, room->bottomRight.y + 1));
std::random_shuffle(possibleStarts.begin(), possibleStarts.end());
//try to find an unassigned adjacent cell to the bottom
Vector2i entrance;
bool validStart = false;
do
{
entrance = *possibleStarts.begin();
possibleStarts.erase(possibleStarts.begin());
if (myMapCells[entrance.y][entrance.x] == '.')
{
validStart = true;
break;
}
} while (possibleStarts.size() > 0);
if (validStart)
{
Vector2i from(entrance.x, entrance.y - 1);
Room* newroom = nullptr;
do {
newroom = createRoom(entrance, from);
} while (newroom == nullptr);
if (newroom != nullptr)
{
placeRoom(newroom);
room->bottom = newroom;
roomStack.push_back(newroom);
rooms.push_back(newroom);
}
}
}
//shuffle the remaining rooms
if (roomStack.size() > 0)
std::random_shuffle(roomStack.begin(), roomStack.end());
}
//pick a random two rooms as the start/finish rooms
Room* start;
Room* finish;
do
{
start = rooms[rand() % rooms.size()];
finish = rooms[rand() % rooms.size()];
int mindistance = (myWidth > myHeight) ? myWidth * 0.75 : myHeight * 0.75;
if (Vector2i::deltaDistance(start->topLeft, finish->topLeft) < mindistance)
continue;
if (start->isDeadEnd() || finish->isDeadEnd())
continue;
start->isStarting = true;
finish->isEnding = true;
startRoom = start;
endRoom = finish;
break;
} while (true);
}
The first do loop in fillRooms() tries to find an open and valid location that it can place the “seed” room for the dungeon. The seed room is the starting point of the “flooding” algorithm, that tries to fill in the map with rooms in much the same way that the allUnassignedReachable() function flooded the map with ‘T’s. The rooms in the dungeon are essentially a tree, which unfortunately was exactly what I said I didn’t want the dungeon to be. The plan is to remedy that by adding in room connections, and therefore cycles, after the dungeon is generated. However, creating the rooms themselves will already make for a fairly lengthy post, so I’ll have to do a part three.
Every room in the dungeon needs a startingCell, which we can think of as the first cell that we step on when we enter the room. Every room also needs a previousCell, which is the last cell of the previous room that we stepped on before we stepped on the startingCell of the current room. These two cells need to be side-by-side since the cells in the maps can only be designated (so far) as unassigned '.', empty 'X', and room 'R', there are no corridor or hallway cells, so we use these two cells to know where exactly the two rooms need to be connected.
So the do loop will randomly pick two side-by-side cell locations and call createRoom(), repeating until a non-null room is returned.
Room* GeneratedMap::createRoom(Vector2i entrance, Vector2i from)
{
//the entrance is the first cell of the room that the player enters from
//the previous room, this cell MUST be in the room. The from cell is the
//last cell of the previous room, adjacent to "entrance". It'll tell us
//which directions we're allowed to slide the room we're creating in.
if (myMapCells[entrance.y][entrance.x] != '.')
return nullptr;
int width = 0;
int num = rand() % 100;
if (num < 30)
width = 0;
else if (num >= 30 && num < 60)
width = 1;
else
width = 2;
int height = 0;
num = rand() % 100;
if (num < 30)
height = 0;
else if (num >= 30 && num < 60)
height = 1;
else
height = 2;
Vector2i topLeft, bottomRight;
if (entrance.y != from.y)
{
// up/down transition
//set left and right edges of room
int xmin = (entrance.x - width < 0) ? 0 : entrance.x - width;
int shiftHoriz = (width == 0 || entrance.x - xmin == 0) ? 0 : rand() % (entrance.x - xmin);// width;
topLeft.x = xmin + shiftHoriz;
bottomRight.x = topLeft.x + width;
if (bottomRight.x >= myWidth)
bottomRight.x = myWidth - 1;
if (entrance.y < from.y)
{
//set top and bottom bounds
bottomRight.y = entrance.y;
int top = entrance.y - height;
if (top < 0)
top = 0;
topLeft.y = top;
}
else
{
topLeft.y = entrance.y;
int bottom = entrance.y + height;
if (bottom >= myHeight)
bottom = myHeight - 1;
bottomRight.y = bottom;
}
}
else
{
// left/right transition
int ymin = (entrance.y - height < 0) ? 0 : entrance.y - height;
int shiftVert = (height == 0 || entrance.y - ymin == 0) ? 0 : rand() % (entrance.y - ymin);//height;
topLeft.y = ymin + shiftVert;
bottomRight.y = topLeft.y + height;
if (bottomRight.y >= myHeight)
bottomRight.y = myHeight - 1;
if (entrance.x < from.x)
{
bottomRight.x = entrance.x;
int left = entrance.x - width;
if (left < 0)
left = 0;
topLeft.x = left;
}
else
{
topLeft.x = entrance.x;
int right = topLeft.x + width;
if (right >= myWidth)
right = myWidth - 1;
bottomRight.x = right;
}
}
if (canPlaceRoom(topLeft, bottomRight))
{
Room* r = new Room(topLeft, bottomRight, entrance);
r->previousCell = from;
return r;
}
return nullptr;
}
The createRoom() function attempts to create a room of random size between 1×1 and 3×3. It gives preference to larger rooms because since there are reserved empty cells, and as the dungeon fills with rooms, it will be less likely that an attempt to place a large room will succeed, so it tries more times in order to compensate. Once the size of the room is picked it picks where in the dungeon the room will be placed. It will also attempt to “slide” the room randomly so that the entrance is not always on the top, bottom, or left cell. Since the room must contain the entrance position, and must not contain the from position, this means that if the room this one came from is on top or bottom of the current one, it can only slide left or right. And if the room this one came from is to the right or left that it can only slide up or down.
Once the size and position of the room have been decided it uses canPlaceRoom to make sure nothing else is using the cells that this room is going to take up.
bool GeneratedMap::canPlaceRoom(Vector2i &topLeft, Vector2i &bottomRight)
{
//makes sure x >=0, y < mapheight, etc
if (!isRoomInBounds(topLeft, bottomRight))
return false;
//assuming that the topLeft is indeed to the left and above bottomRight
for (int y = topLeft.y; y <= bottomRight.y; y++)
{
for (int x = topLeft.x; x <= bottomRight.x; x++)
{
if (myMapCells[y][x] != '.')
return false;
}
}
return true;
}
If there is something already in those cell(s), it returns null, otherwise it creates and returns the new room. The fillRooms() function continually calls createRoom() until it receives a non-null value.
Once the seed room is created it is put into the list of rooms as well as the roomStack. This collection contains rooms that have been created but have not had their neighbors created. It removes the first room in the list and attempts to make neighboring rooms for it, one in each direction up/down/left/right. Any rooms that are successfully created are added to the roomStack. Each attempt to create a neighboring room is contained in a fairly large if statement, all of which do essentially the same thing but have values changed slightly based on which direction the room is being created in.
The conditions on the if statement check to see if the new room would be within the bounds of the map. For example, to make a room to the left, the room it’s branching from must not be on the left edge of the map. Once that condition is satisfied it builds a list of cells directly adjacent to the current room and puts them into possibleStarts, it then goes through the list until it finds a cell that is unassigned. That cell is the startingCell of the new room. If an unassigned cell is not found, then a room cannot be placed in that direction, and is skipped.
If a valid starting cell has been found for the neighbor, createRoom() is called until a non-null value is returned. That room is added to the stack, and the process repeats. Once all four potential neighbors have been added, the stack is shuffled, and the next room is taken out of it.
After all of the rooms in the stack have been gone through, the fillRooms() function does one last thing. It picks “start” and “end” rooms. It does this by randomly selecting two rooms, checks if the distance between them is acceptable, and if it is, it marks them as such. Like the other pieces of code this will repeat until the desired conditions are met.
The dungeon is now filled with rooms! although it looks pretty unimpressive in the console :P
I created a method to draw the dungeon to the screen using SDL:
void DrawMap(GeneratedMap& map)
{
int tilesize = 5;
int tilesPerRoom = 10;
int roomBuffer = 1;//each room is 2 tiles from the edge of the cell
for (int i = 0; i < map.rooms.size(); i++)
{
Room* room = map.rooms[i];
if (room == map.startRoom)
SDL_SetRenderDrawColor(renderer, 0x00, 0x00, 0xFF, 0xFF);
else if (room == map.endRoom)
SDL_SetRenderDrawColor(renderer, 0x99, 0x00, 0xFF, 0xFF);
else
SDL_SetRenderDrawColor(renderer, 0xFF, 0x00, 0x00, 0xFF);
int horizCellCount = room->getWidth() + 1;
horizCellCount *= tilesPerRoom;
horizCellCount -= 2 * roomBuffer;
int vertCellCount = room->getHeight() + 1;
vertCellCount *= tilesPerRoom;
vertCellCount -= 2 * roomBuffer;
int startx = (room->topLeft.x * tilesize * tilesPerRoom);
startx += roomBuffer * tilesize;
int starty = (room->topLeft.y * tilesize * tilesPerRoom);
starty += roomBuffer * tilesize;
for (int y = 0; y < vertCellCount; y++)
{
for (int x = 0; x < horizCellCount; x++)
{
SDL_Rect rekt;
rekt.x = startx + (x * tilesize);
rekt.y = starty + (y * tilesize);
rekt.h = tilesize;
rekt.w = tilesize;
SDL_RenderFillRect(renderer, &rekt);
}
}
//draw connections
if (room->left != nullptr)
{
Vector2i startingCell = room->left->startingCell;
int startx = (startingCell.x + 1) * tilesize * tilesPerRoom;
startx -= (tilesize * roomBuffer);
int starty = (startingCell.y * tilesize * tilesPerRoom) + ((tilesPerRoom * tilesize) / 2);
for (int y = 0; y < 2; y++)
{
for (int x = 0; x < roomBuffer * 2; x++)
{
SDL_Rect rekt;
rekt.x = startx + (x * tilesize);
rekt.y = starty + (y * tilesize);
rekt.w = tilesize;
rekt.h = tilesize;
SDL_RenderFillRect(renderer, &rekt);
}
}
}
if (room->right != nullptr)
{
Vector2i startingCell = room->right->startingCell;
int startx = startingCell.x * tilesize * tilesPerRoom;
startx -= (tilesize * roomBuffer);
int starty = (startingCell.y * tilesize * tilesPerRoom) + ((tilesPerRoom * tilesize) / 2);
for (int y = 0; y < 2; y++)
{
for (int x = 0; x < roomBuffer * 2; x++)
{
SDL_Rect rekt;
rekt.x = startx + (x * tilesize);
rekt.y = starty + (y * tilesize);
rekt.w = tilesize;
rekt.h = tilesize;
SDL_RenderFillRect(renderer, &rekt);
}
}
}
if (room->top != nullptr)
{
Vector2i thisTopLeft = room->topLeft;
Room top = *map.rooms[i]->top;
Vector2i startingCell = room->top->startingCell;
int starty = (startingCell.y + 1) * tilesize * tilesPerRoom;
starty -= (tilesize * roomBuffer);
int startx = (startingCell.x * tilesize * tilesPerRoom) + ((tilesPerRoom * tilesize) / 2);
for (int y = 0; y < roomBuffer * 2; y++)
{
for (int x = 0; x < 2; x++)
{
SDL_Rect rekt;
rekt.x = startx + (x * tilesize);
rekt.y = starty + (y * tilesize);
rekt.w = tilesize;
rekt.h = tilesize;
SDL_RenderFillRect(renderer, &rekt);
}
}
}
if (room->bottom != nullptr)
{
Vector2i thisBottomRight = room->bottomRight;
Room* top = map.rooms[i]->top;
Vector2i startCell = room->bottom->startingCell;
int starty = startCell.y * tilesize * tilesPerRoom;
starty -= tilesize * roomBuffer;
int startx = (startCell.x * tilesize * tilesPerRoom) + ((tilesPerRoom * tilesize) / 2);
for (int y = 0; y < roomBuffer * 2; y++)
{
for (int x = 0; x < 2; x++)
{
SDL_Rect rekt;
rekt.x = startx + (x * tilesize);
rekt.y = starty + (y * tilesize);
rekt.w = tilesize;
rekt.h = tilesize;
SDL_RenderFillRect(renderer, &rekt);
}
}
}
}
}
It just uses rectangles of color to draw the rooms and their connections, but it’s still better than the console:
Going back to the list of requirements in the first post:
- The dungeon size is defined in two dimensions with numbers, for example “20×15”. I ended up calling these “cells”.
- There needs to be some empty cells in the dungeon.
- Rooms are rectangular and can occupy multiple cells. I chose room size ranges from 1-3 cells in both directions. This was an arbitrary choice and could easily be changed in the future
- The start and ending rooms in the dungeon need to be some minimum distance from each-other.
- The pathways between rooms should be short, no long corridors are desired
- The dungeon needs to not be a tree. i.e.: There should be some cycles in the dungeon. This should help reduce backtracking so the user spends more time in rooms that they haven’t been in yet.
Now all but the last requirement is met, which can be done in another post.
I left out quite a bit of code, like the implementation of Vector2i and Room, the contents of headers, the main method, etc. Those can be found in the .zip archive of this project (contains source code only). It requires SDL2 to compile, a tutorial for setting up an SDL2 environment can be found here on Lazy Foo’s site.