When I last left off I had the rooms (or data equivalent of rooms) created, the last thing that needed to be done was add in cycles so that the dungeon layout is not a tree. That’s what I’ll be tackling in this post.

I’ve updated the generateMap() function and added a call to the new function fixTree() at the end:

fixTree()

void GeneratedMap::fixTree()
{
//get all dead ends
std::vector<Room*> deadEnds;
for (unsigned int i = 0; i < rooms.size(); i++)
{
if (rooms[i]->isDeadEnd())
deadEnds.push_back(rooms[i]);
}
std::random_shuffle(deadEnds.begin(), deadEnds.end());

unsigned int i = 0;
int addedCount = 0;
int cyclesToAdd = (deadEnds.size() * CYCLE_PERCENT) / 100;
//keep adding cycles until the quantity is met or we run out of
//dead ends to try
while (i < deadEnds.size() && addedCount < cyclesToAdd)
{
Room* de = deadEnds[i++];
std::vector<Room*> adjacentRooms = getAdjacentRooms(de);
if (adjacentRooms.size() <= 0)
{
adjacentRooms.clear();
continue;
}
std::random_shuffle(adjacentRooms.begin(), adjacentRooms.end());

unsigned int j = 0;
Room* aj = nullptr;
//find first non-connected room
do
{
if (!de->areConnected(adjacentRooms[j]))
aj = adjacentRooms[j];
j++;
} while (j < adjacentRooms.size() && aj == nullptr);

//if no non-connected room is found try the next dead-end
if (aj == nullptr)
{
adjacentRooms.clear();
continue;
}

aj->hasSecondEntrance = true;

//rooms are adjacent, but not connected, now we connect them... with
//wizardry...
int directionOfOther = de->directionOfOtherRoom(aj);
int miny = 0, minx = 0, shift = 0;
if (directionOfOther == Room::LEFT || directionOfOther == Room::RIGHT)
{
miny = std::max(de->topLeft.y, aj->topLeft.y);
int maxy = std::min(de->bottomRight.y, aj->bottomRight.y);
int dy = std::abs(maxy - miny);
shift = dy <= 0 ? 0 : rand() % (dy + 1);
}
else if (directionOfOther == Room::UP || directionOfOther == Room::DOWN)
{
minx = std::max(de->topLeft.x, aj->topLeft.x);
int maxx = std::min(de->bottomRight.x, aj->bottomRight.x);
int dx = std::abs(maxx - minx);
shift = dx <= 0 ? 0 : rand() % (dx + 1);
}

switch (directionOfOther)
{
case Room::LEFT:
aj->startingCell2 = Vector2i(aj->bottomRight.x, miny + shift);
aj->previousCell2 = Vector2i(de->topLeft.x, miny + shift);
break;
case Room::RIGHT:
aj->startingCell2 = Vector2i(aj->topLeft.x, miny + shift);
aj->previousCell2 = Vector2i(de->bottomRight.x, miny + shift);
break;
case Room::UP:
aj->startingCell2 = Vector2i(minx + shift, aj->bottomRight.y);
aj->previousCell2 = Vector2i(minx + shift, de->topLeft.y);
break;
case Room::DOWN:
aj->startingCell2 = Vector2i(minx + shift, aj->topLeft.y);
aj->previousCell2 = Vector2i(minx + shift, de->bottomRight.y);
break;
}

addedCount++;
}
}

Continue reading Generating a Dungeon (part 3) →