I heard recently about an interview problem involving matching braces in a string. Checking to see if all the braces in a string are paired up in the proper order. Seemed like an interesting, and short, challenge.
Examples of strings with proper brace matching: "()", "(){}[]", "([{}])"
Examples of strings without proper brace matching: "(", "[]]", "([)]"
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++;
}
}
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.
I’ve been wanting to create a game that uses randomly generated dungeons for a while now but didn’t have a good idea about what kind of game to make. Recently though I decided “so what if I don’t have an idea for what to DO with the dungeons, I can figure that out after I make them.” So I set out to make some code that will generate random dungeons.
In my last post I talked about finding the number of zeroes at the end of 
The first has to do with the relationship between the quantity of fives and the quantity of twos. The lower quantity in the prime factorization of
Even the prime factorization of 
This means that all we really need to keep track of is the quantity of fives in the prime factorization of