Generating a Dungeon (part 1)

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.

I did some research before I started to see what methods other people have used and what kinds of dungeons they’ve yielded.

Binary Space Partition (BSP)

Here and here are a couple of pages with pictures and code.

This is the first method I looked at and it involves recursively dividing a rectangle into sub-rectangles, taking portions of those and turning them into rooms. It’s definitely a good way to generate a map, but I didn’t quite like the look of the result. I didn’t really want long corridors in my dungeons, and I wanted them to have a more grid-like feel, similar to a 2D Zelda game.

Cellular Automata

This page has a good explanation and interactive demo on generating maps using cellular automata.

This method was pretty interesting in that it’s pretty simple and the maps are very un-grid-like in appearance. Which unfortunately isn’t what I was looking for. The maps it generates look more like cave systems than man-made dungeons. However, if I want to add a second dungeon “type” at some point I’ll definitely give the cellular automata method some consideration.

After a bit more searching I failed to find anything that looked like what I was imagining my dungeons would look like, so I decided to take a stab at creating it myself.

Defining the style

Before I could start writing code to create the dungeons first I would have to figure out exactly what went into making them.

  1. The dungeon size is defined in two dimensions with numbers, for example “20×15”. I ended up calling these “cells”.
  2. There needs to be some empty cells in the dungeon.
  3. 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
  4. The start and ending rooms in the dungeon need to be some minimum distance from each-other.
  5. The pathways between rooms should be short, no long corridors are desired
  6. 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.

Here’s a quick image I drew up as an example of what I was looking for:

paintdungeon

Item 1 was quite easy. I chose to store the grid of cells as a 2D-array of chars. I used a vector of vectors instead of a char[][] because I was having trouble declaring it in the header file without defining the size. They can still be accessed like an array anyway. In the grid periods are used as unassigned cells.

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

The next thing I added in was item 2, empty cells. The plan was to pick a random sized “empty room” between 1×1 and 3×3 cells in size, pick a random location for it in the map, and place it if it fits. Cells designated as being empty are denoted with an ‘X’.

void GeneratedMap::createEmptyCells()
{
	std::vector<Room> emptyRooms;
	int numEmpties = (myWidth * myHeight) * 0.20; //20% of cells are empty
	while (true)
	{
		//empty vector of rooms
		emptyRooms.clear();
		int emptyCellCount = 0;
		while (emptyCellCount < numEmpties)
		{
			//randomly pick a size
			int width = 0;
			int num = rand() % 100;
			if (num < 40)
				width = 0;
			else if (num >= 40 && num < 80)
				width = 1;
			else
				width = 2;

			int height = 0;
			num = rand() % 100;
			if (num < 40)
				height = 0;
			else if (num >= 40 && num < 80)
				height = 1;
			else
				height = 2;

			//randomly pick location
			int xpos = rand() % (myWidth - (width)); 
			int ypos = rand() % (myHeight - (height));

			//randomly pick a size
			Vector2i topLeft(xpos, ypos);
			Vector2i bottomRight(xpos + width , ypos + height);
			
			if (canPlaceRoom(topLeft, bottomRight))
			{
				//if it fits then add it to the list
				Room emptyRoom(topLeft, bottomRight);
				emptyRooms.push_back(emptyRoom);

				//fill cells in map
				replacePeriods(topLeft, bottomRight, 'X');

				//recalculate number of empty cells
				emptyCellCount = 0;
				for (int i = 0; i < emptyRooms.size(); i++)
					emptyCellCount += emptyRooms[i].getArea();
			}				
		}

		if (allUnassignedReachable())
			break;
		else
			removeEmpties();
	}
}

Then once the desired number of empty cells have been reserved, test to see that all of the other unassigned cells are still reachable by picking one of them then flood filling the map from that location. If the empty cells have been placed correctly the map should now consist of empty cells (‘X’) and test (‘T’) cells, no unassigned (‘.’) cells should remain. If there are unassigned cells left, that means that the empty cell placement has partitioned the dungeon into two separate parts. This is bad because it could result in orphaned rooms, large chunks of the dungeon not being generated, or the end room being unreachable. In such a case the cells all get reset to unassigned and it tries to randomly place empty cells again.

The code that floods the map to check if all unassigned cells are reachable is below. It works by randomly picking cells until it finds an unassigned one (it could have just checked in a linear fashion for the first empty cell and went from there but I had been generating a lot of random numbers before then so I guess I was just in the frame of mind). It then adds that cell’s location to a queue. While there are locations in the queue the program will dequeue the first item, mark any unassigned neighbors in the up/down/left/right directions with a ‘T’, and enqueue all of the locations it marked. It then dequeues the next item and repeats the process until there are no locations left in the queue.

When the flooding is done it checks the map by removing all the ‘T’ characters, if it runs into a ‘.’ unassigned cell while doing that then the map is bad and generation must start over.

bool GeneratedMap::allUnassignedReachable()
{
	std::queue<Vector2i> queue;
	Vector2i start(0, 0);
	while (myMapCells[start.y][start.x] != '.')
	{
		start.x = rand() % myWidth;
		start.y = rand() % myHeight;
	}
	queue.push(start);

	while (queue.size() > 0)
	{
		Vector2i cell = queue.front();
		queue.pop();

		//left
		if (cell.x > 0 && myMapCells[cell.y][cell.x - 1] == '.')
		{
			Vector2i newCell(cell.x - 1, cell.y);
			myMapCells[newCell.y][newCell.x] = 'T';
			queue.push(newCell);
		}

		//right
		if (cell.x < myWidth - 1 && myMapCells[cell.y][cell.x + 1] == '.')
		{
			Vector2i newCell(cell.x + 1, cell.y);
			myMapCells[newCell.y][newCell.x] = 'T';
			queue.push(newCell);
		}

		//top
		if (cell.y > 0 && myMapCells[cell.y - 1][cell.x] == '.')
		{
			Vector2i newCell(cell.x, cell.y - 1);
			myMapCells[newCell.y][newCell.x] = 'T';
			queue.push(newCell);
		}

		//bottom
		if (cell.y < myHeight - 1 && myMapCells[cell.y + 1][cell.x] == '.')
		{
			Vector2i newCell(cell.x, cell.y + 1);
			myMapCells[newCell.y][newCell.x] = 'T';
			queue.push(newCell);
		}
	}

	//make sure no unassigned cells remain
	bool result = true;
	for (int y = 0; y < myHeight; y++)
	{
		for (int x = 0; x < myWidth; x++)
		{
			if (myMapCells[y][x] == '.')
				result = false;
			else if (myMapCells[y][x] == 'T')
				myMapCells[y][x] = '.';
		}
	}
	return result;
}

Once that’s done and returns true we have a map that contains unassigned cells and reserved empty cells. Which admittedly isn’t much to look at, but it’s definitely progress towards a dungeon. I added in some code to print out the unassigned/empty cell map to the console once the empty cells are successfully placed, here’s an example output:

withempties

After that the next step is “flooding” the map with rooms. I’ll write that bit up in another post. This one is starting to get a little lengthy. I’ve put all the source files containing the progress I’ve made into a .zip file that you can download here. I also have a GitHub repo for the work in progress, which may or may not be significantly different from the point in time I am writing this post.

The code requires SDL2 to work. Shoutout to Lazy Foo for creating this extremely helpful tutorial on getting an SDL2 project compiled and running.

Leave a Reply

Your email address will not be published. Required fields are marked *