Procedural Dungeon Generation Part3

During the Part2, we updated the dungeonMap to have all coordinates in the same room share the same numerical value. However, all rooms are unconnected and that would make a pretty boring dungeon. We’ll correct that!

Add corridors
The goal of this step is to add corridor and make sure that all rooms are connected together and are all accessible. In the following image, you can see an updated version of the previously created dungeon with corridors. Each room now have a corridor starting from a random position in it(C#_Start) going to another random position in a random room/corridor(C#_End).

PDG Step3

Procedural Dungeon Generation – Step 3

Here is the whole CreateDungeonHalls() method that update the dungeonMap with added corridors. The code below will be split in 3 part below and explained individually.

// Create a hall starting from each room, connecting to another room or corridor
static private int[,] CreateDungeonHalls(int[,] _dungeonMap, int _sizeX,int _sizeZ, int nbrRoom)
{
	int _x1; // x coordinate of the starting position
	int _z1; // z coordinate of the starting position
	int _x2; // x coordinate of the ending position
	int _z2; // z coordinate of the ending position

	// Start a corridor from each room
	for(int _curRoomNbr = 1; _curRoomNbr <= nbrRoom; _curRoomNbr++)
	{
		int nbrRoomsTry = 0; // Counter is used to avoid looping forever if there is a bug in the program.
		int _nbrRoomsTryMax = 5000;

		// Find a random coordinate in the room with number _curRoomNbr
		_x1 = Random.Range (1, _sizeX-1);
		_z1 = Random.Range (1, _sizeZ-1);

		// Find a random position with the current room number
		while(_dungeonMap[_x1,_z1] != _curRoomNbr && nbrRoomsTry < _nbrRoomsTryMax)
		{
			_x1 = Random.Range (1, _sizeX-1);
			_z1 = Random.Range (1, _sizeZ-1);
			nbrRoomsTry++;
		}
		nbrRoomsTry = 0;

		// Find a random coordinate in any room/corridor that isn't the first room
		_x2 = Random.Range (1, _sizeX-1);
		_z2 = Random.Range (1, _sizeZ-1);

		// Find a random position in a different room or corridor created from a previous room
		while((_dungeonMap[_x2,_z2] == 0 || _dungeonMap[_x2,_z2] == _curRoomNbr) && nbrRoomsTry < _nbrRoomsTryMax)
		{
			_x2 = Random.Range (1, _sizeX-1);
			_z2 = Random.Range (1, _sizeZ-1);
			nbrRoomsTry++;
		}

		// Difference between both coordinates on each axis. This is used to find direction of corridor to create
		int _diffX = _x2 - _x1;
		int _diffZ = _z2 - _z1;

		int _xDirection = 1; // Coefficient used to loop in the right direction on x axis(-1 or 1)
		int _zDirection = 1; // Coefficient used to loop in the right direction on z axis(-1 or 1)

		// Evaluate direction of the corridor on the X and Z axis
		if(_diffX != 0)
		{
			_xDirection = _diffX/Mathf.Abs(_diffX); // 1 = Left to Right (->) ... -1 =  Right to Left (<-)
		}
		else
		{
			_xDirection = 0; // No horizontal corridor if they are aligned on X axis
		}

		if(_diffZ != 0)
		{
			_zDirection = _diffZ/Mathf.Abs(_diffZ); // 1 = Top to Bottom( \/ ) ... -1 = Bottom to Top ( /\ )
		}
		else
		{
			_zDirection = 0; // No vertical corridor if they are aligned on Z axis
		}

		// randomize corridor portion and height
		int _hallWidth  = Random.Range (4,10);
		int _hallHeight = Random.Range (4,10);

		//Create vertical part of the hall
		for(int i = _x1; i != _x1 + _xDirection*_hallWidth; i += _xDirection)
		{
			for(int j = _z1; j != _z2; j += _zDirection)
			{
				if(i >= 0 && i < _sizeX && j >= 0 && j < +_sizeZ) // Make sure that the index is within the map range
				{
					if(_dungeonMap[i,j] == 0) // Only modify empty position, not rooms position
					{
						_dungeonMap[i,j] = -1; // Write corridor as -1 in the dungeonMap
					}
				}
			}
		}

		//Create horizontal portion of the hall
		for(int i = _x1; i != _x2; i += _xDirection)
		{
			for(int j = _z2; j != _z2 + _zDirection*_hallHeight; j += _zDirection)
			{
				if(i >= 0 && i < _sizeX && j >= 0 && j < +_sizeZ) // Make sure that the index is within the map range
				{
					if(_dungeonMap[i,j] == 0) // Only modify empty position, not rooms position
					{
						_dungeonMap[i,j] = -1; // Write corridor as -1 in the dungeonMap
					}
				}
			}
		}
	}
	return _dungeonMap; // The _dungeonMap contains 0 for non-room, -1 for corridor and N for rooms
}

¸
First part of the method (line 10-38) simply find a random position to start a corridor from each room and an ending position in another room or in a previously added corridor.

// Start a corridor from each room
	for(int _curRoomNbr = 1; _curRoomNbr <= nbrRoom; _curRoomNbr++)
	{
		int nbrRoomsTry = 0; // Counter is used to avoid looping forever if there is a bug in the program.
		int _nbrRoomsTryMax = 5000;

		// Find a random coordinate in the room with number _curRoomNbr
		_x1 = Random.Range (1, _sizeX-1);
		_z1 = Random.Range (1, _sizeZ-1);

		// Find a random position with the current room number
		while(_dungeonMap[_x1,_z1] != _curRoomNbr && nbrRoomsTry < _nbrRoomsTryMax)
		{
			_x1 = Random.Range (1, _sizeX-1);
			_z1 = Random.Range (1, _sizeZ-1);
			nbrRoomsTry++;
		}
		nbrRoomsTry = 0;

		// Find a random coordinate in any room/corridor that isn't the first room
		_x2 = Random.Range (1, _sizeX-1);
		_z2 = Random.Range (1, _sizeZ-1);

		// Find a random position in a different room or corridor created from a previous room
		while((_dungeonMap[_x2,_z2] == 0 || _dungeonMap[_x2,_z2] == _curRoomNbr) && nbrRoomsTry < _nbrRoomsTryMax)
		{
			_x2 = Random.Range (1, _sizeX-1);
			_z2 = Random.Range (1, _sizeZ-1);
			nbrRoomsTry++;
		}

Second part of the method (line 40-64) calculate the difference between the start/end position on the X and Z axis. It also calculate a coefficient to increment in the good direction while creating the corridor.

		// Difference between both coordinates on each axis. This is used to find direction of corridor to create
		int _diffX = _x2 - _x1;
		int _diffZ = _z2 - _z1;

		int _xDirection = 1; // Coefficient used to loop in the right direction on x axis(-1 or 1)
		int _zDirection = 1; // Coefficient used to loop in the right direction on z axis(-1 or 1)

		// Evaluate direction of the corridor on the X and Z axis
		if(_diffX != 0)
		{
			_xDirection = _diffX/Mathf.Abs(_diffX); // 1 = Left to Right (->) ... -1 =  Right to Left (<-)
		}
		else
		{
			_xDirection = 0; // No horizontal corridor if they are aligned on X axis
		}

		if(_diffZ != 0)
		{
			_zDirection = _diffZ/Mathf.Abs(_diffZ); // 1 = Top to Bottom( \/ ) ... -1 = Bottom to Top ( /\ )
		}
		else
		{
			_zDirection = 0; // No vertical corridor if they are aligned on Z axis
		}

Last part of the method (line 66-101) start by calculating a random width and height for the new corridor. The map is then updated with the vertical portion of the corridor first and the horizontal portion of the corridor second. Corridor are a simple corner for now. It would be possible to add randomness/more corner or connect them in a different way by modifying this part. It would also be possible to customize the corridors width/height depending on the room size/distance between rooms and such.

To create the corridors, we take the previously evaluated direction on the X axis and step toward that direction with the corridor width. This corridor is filled on the Z axis from z1 to z2. Same thing is done with the horizontal part of the corridor.

		// randomize corridor portion and height
		int _hallWidth  = Random.Range (4,10);
		int _hallHeight = Random.Range (4,10);

		//Create vertical part of the hall
		for(int i = _x1; i != _x1 + _xDirection*_hallWidth; i += _xDirection)
		{
			for(int j = _z1; j != _z2; j += _zDirection)
			{
				if(i >= 0 && i < _sizeX && j >= 0 && j < +_sizeZ) // Make sure that the index is within the map range
				{
					if(_dungeonMap[i,j] == 0) // Only modify empty position, not rooms position
					{
						_dungeonMap[i,j] = -1; // Write corridor as -1 in the dungeonMap
					}
				}
			}
		}

		//Create horizontal portion of the hall
		for(int i = _x1; i != _x2; i += _xDirection)
		{
			for(int j = _z2; j != _z2 + _zDirection*_hallHeight; j += _zDirection)
			{
				if(i >= 0 && i < _sizeX && j >= 0 && j < +_sizeZ) // Make sure that the index is within the map range
				{
					if(_dungeonMap[i,j] == 0) // Only modify empty position, not rooms position
					{
						_dungeonMap[i,j] = -1; // Write corridor as -1 in the dungeonMap
					}
				}
			}
		}
	}
	return _dungeonMap; // The _dungeonMap contains 0 for non-room, -1 for corridor and N for rooms
}

Now that the map dungeonMap is updated with all the rooms and corridors, we need to find a list of all wall to create and instantiate them in the dungeon scene. This will be the topic of the next 2 posts.

Update : I’m currently updating the way I do part 4 and 5. They are accessible on the Dungeon Grind repository on GitHub but, they can’t be buggy or in an imperfect state. You can however look for inspiration on how to continue. The most important file is DungeonGenerator.cs and DungeonManager.cs can be useful.

Advertisements

Procedural Dungeon Generation Part2

Now that we filled the array with squares(1), we need to find every independent room so we can make sure they are connected by corridors. The rooms are identified by looping through the whole array dungeonMap. Every time a square(1) is encountered, an algorithm find all the adjacent cells that are part of the same room. The algorithm work like a minesweeper game when you hit an empty area and it crawls around to open it.

Find Rooms
The goal of this step is to identify all independent room and modify the dungeonMap with a different value for each room as presented in the next picture.

PDG Step2

PDG Step 2 – Find Rooms

The method FindRooms() take as input the dungeonMap and its size. The first step of the algorithm is to create a copy of the dungeonMap. Then, we loop through the map searching the square(1) that were created by the previous step. The first encountered square is added to a list of coordinate to test.

Every time a coordinate is tested, the 8 coordinate around it are evaluated. Each coordinate that are also a square(1) are added to the list of coordinate to test. They are also put as 0 in the modifiedMap to make sure we don’t add them to the list again. The algorithm then try the next cell on the list until there are no more cell to test. This ensure that all cell are tested and the whole room is identified.

Here is the code for the FindRoom() function:

// Loop through the dungeon map and find rooms created by touching squares
static int FindRooms(int[,] _dungeonMap, int _sizeX, int _sizeZ)
{
	
	List<Vector2> ListCoordToTest = new List<Vector2>(); // List of all coordinate that need to be evaluated for the current room.
	int[,] _modifiedMap  = new int[_sizeX,_sizeZ]; // This array will be a copy of _modifiedMap where all known room cell are set as 0 to be ignored by the next steps
	int    _nbrRoomFound = 0;
	
	System.Array.Copy(_dungeonMap,_modifiedMap, _sizeX*_sizeZ); // Create a copy of the _dungeonMap in _modifiedMap
	
	//Loop through all position of the map
	for(int i = 0; i < _sizeX; i++)
	{
		for(int j = 0; j < _sizeZ; j++)
		{
			// If a room is found
			if(_modifiedMap[i,j] == 1)
			{
				ListCoordToTest.Add(new Vector2(i, j)); // Add the coordinate to the list to test
				
				while(ListCoordToTest.Count > 0) // Loop while there are coordinates to test
				{	
					int _x = (int)ListCoordToTest[0].x; // Find x value of coordinate to test
					int _z = (int)ListCoordToTest[0].y; // Find y value of coordinate to test
					ListCoordToTest.RemoveAt (0); // Remove the currently tested coordinate
					
					_dungeonMap[_x,_z] = _nbrRoomFound + 1; // Update the _dungeonMap with the current number of room found
					
					// Look the 8 coordinate around the current coordinate to find for connected rooms
					for(int _xAround = _x - 1; _xAround <= _x + 1; _xAround++)
					{
						for(int _zAround = _z - 1 ; _zAround <= _z + 1; _zAround++)
						{
							// Test if evaluated coordinate is a square and need to be added to the room
							if(_modifiedMap[_xAround,_zAround] == 1)
							{
								ListCoordToTest.Add(new Vector2(_xAround, _zAround)); // Add it to the list of coordinates to test
								_modifiedMap[_xAround,_zAround] = 0; // Remove the room position from the modified map so we don't step on it again
							}
						}
					}
				}
				_nbrRoomFound++;
			}
		}
	}
	return _nbrRoomFound;
}

Now that we have identified all the rooms, we can add corridors so all rooms are accessible.

Procedural Dungeon Generation Part1

Initialization

To generate my dungeons, I use 2 classes :

public class DungeonManager : MonoBehaviour{}
static class DungeonGenerator{}
  • DungeonManager is attached to a GameObject(“__DungeonMaster”) that is only instantiated when the Dungeon scene load. This class is responsible for finding the level information, spawn the dungeon with the DungeonGenerator static class, add monsters and test for victory.
  • DungeonGenerator is a static class that randomize dungeon configuration and instantiate the GameObject

The main method of DungeonGenerator is SpawnDungeon(). This method calculate the dungeon configuration and spawn the walls as GameObject. If you look the step-by-step graphic of the precedent post, you can see each step translated in functions.

// Randomize configuration of dungeon and instantiate it
static public int[,] SpawnDungeon(int _sizeX,int _sizeZ, int _nbrSquareForGeneration)
{
	int[,] _dungeonMap; // 2D Array of int that will hold the dungeon map information

	_dungeonMap = CreateDungeonSquares(_sizeX,_sizeZ, _nbrSquareForGeneration); // Fill the array with different squares of various size
	_nbrRoom = FindRooms (_dungeonMap,_sizeX, _sizeZ); // Loop through the dungeon map and find the square that form rooms together
	if(_nbrRoom &gt; 1)
	{
		_dungeonMap = CreateDungeonHalls(_dungeonMap, _sizeX,_sizeZ,_nbrRoom);  // Add halls between the created room
	}

	SpawnEnvironment(_dungeonMap, _sizeX, _sizeZ, _nbrRoom); // Create environment(Spider eggs for now)

	_ListOfWallsToCreate = EvaluateWallToBuild(_dungeonMap, _sizeX, _sizeZ); // Loop through the dungeon map to find all the wall that need to be created
	InstantiateDungeonWalls(_ListOfWallsToCreate); // Instantiate all the wall found by the EvaluateWallToBuild function

	return _dungeonMap;
}

The array int[,] _dungeonMap is the result of the SpawnDungeon() method.

Square creation
The goal of this step is to fill the array with various squares of different size/position. They are written as 1 in the array.

PDG - Step 1

Procedural Dungeon Generation – Step 1

The first function, CreateDungeonSquares(), fill the _dungeonMap with the inputted number of squares of random size at random position. It’s pretty straightforward and just make sure that all the rooms are on the map. It doesn’t matter if rooms overlap, that’s in fact what we want. This will leads to variously shaped room and more randomness.

// Create the inputted number of square on the map
static int[,] CreateDungeonSquares(int _sizeX, int _sizeZ, int _squareNbr)
{
	int[,] _newMap = new int[_sizeX,_sizeZ]; // Create empty map with imputted dimensions

	for(int i = 0; i &lt; _squareNbr; i++)
	{
		// Calculate random room size and position. Make sure the room is inside the map.
		int _roomSizeX = Random.Range (10,_sizeX/5);
		int _roomSizeZ = Random.Range (10,_sizeZ/5);
		int _roomPosX  = Random.Range (1,_sizeX-_roomSizeX);
		int _roomPosZ  = Random.Range (1,_sizeZ-_roomSizeZ);

		// Add the square to the map. Avoid making square on the external values of the map.
		for(int j = _roomPosX; j &lt; _roomPosX + _roomSizeX; j++)
		{
			for(int k = _roomPosZ; k &lt; _roomPosZ + _roomSizeZ; k++)
			{
				_newMap[j,k] = 1;
			}
		}
	}
	return _newMap;
}

Dungeon Grind – Procedural Dungeon Generation Tutorial

I decided to work on tutorials that explain how are generated the dungeon in my game, Dungeon Grind. The algorithm could be improved at various places and I still get some bugs(missing wall in some case) but it get the jobs done. I’ll update the post whenever i fix any bugs. Here is an example of a randomly generated dungeon with a size of 500×500.

Dungeon 500x500

Generated dungeon of size 500×500

The algorithm will be explained in greater detail in the following post.
Part 1 – Create squares
Part 2 – Find Rooms
Part 3 – Add Corridors
Part 4 – Evaluate walls to build (WIP)
Part 5 – Instantiate walls (WIP)

The basic idea can be understood with this graphic :

PDG Step by step graphic

Step-by-step tutorial for Procedurally generated dungeon