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.

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.

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