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.

Advertisements

One thought on “Procedural Dungeon Generation Part2

  1. Pingback: Dungeon Grind – Procedural Dungeon Generation Tutorial | LearningGeek Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s