To start with, we need to break down what is meant by room or cave. With respect to the 2D array in the problem description, a room is a collection of elements that are 'connected'. For any given starting point, we can identify all the elements of a connected region using a flood fill algorithm.
The flood fill algorithm presented below works as follows:
- tag the starting point
- place a starting point in the work queue
- while the work queue isn't empty
- remove an element from the queue
- get the neighbors of the current element
- for each valid neighbor (meaning it's not a wall & hasn't already been tagged)
- tag it (the neighbor) & add it to the queue
When the work queue is empty, all of the elements that are reachable from the starting point will have been visited and tagged. Because the problem description requests a list of all the element locations, whenever an element is tagged, it will also be added to a list.
Flood fill alone isn't quite enough to solve the problem though. We still need a way to find the starting point of the largest room. Since we don't necessarily know where the largest room is, we'll need to iterate over the 2D array and look for it. If we encounter an element isn't open or has already been tagged, we can skip over it. If we encounter an open element that hasn't previously been identified as belonging to a region, we flood fill starting at that location.
There are a couple of options regarding what to do each time the flood fill finishes with a region:
- Compare the most recently found region against the largest know region & only keep track of the largest.
- Keep track of all the regions and then find the largest.
The second option requires a bit more memory, but also provides some extra benefits that might be useful when dealing with procedurally generated caves. Also, after seeing the solution for the second, it's pretty trivial to trim it back down it the first option. Since the second option provides more flexibility and isn't significantly more complex, it's the solution we will examine.
Here's the code:
using System.Collections;
using System.Collections.Generic;
using System.Numerics;
namespace LargestRoomProject
{
public class CaveGridManager
{
public int[,] regionID;
public List<List<Vector2>> regionCoords;
// helper class for dealing with a map
// assumes 0 == wall & 1 == open
public CaveGridManager(int[,] data)
{
regionID = new int[data.GetLength(0), data.GetLength(1)];
for(int x=0; x<regionID.GetLength(0); x++)
{
for(int y=0; y<regionID.GetLength(1); y++)
{
regionID[x,y] = -1;
}
}
regionCoords = new List<List<Vector2>>();
for(int x=0; x<data.GetLength(0); x++)
{
for(int y=0; y<data.GetLength(1); y++)
{
if(data[x,y] == 1 && regionID[x,y] == -1)
{
regionCoords.Add(FillNewRegion(data, x, y));
}
}
}
}
// start a new region at the x,y coords, fill it with the next available regionID and
// return a list of the x,y coords of that regions
private List<Vector2> FillNewRegion(int[,] data, int x, int y)
{
int ID = regionCoords.Count;
List<Vector2> coords = new List<Vector2>();
regionID[x, y] = ID;
Queue queue = new Queue();
coords.Add(new Vector2(x, y));
queue.Enqueue(new Vector2(x, y));
while (queue.Count > 0)
{
Vector2 curr = (Vector2)queue.Dequeue();
foreach (Vector2 neighbor in (ValidNeighbors(curr)))
{
if (data[(int)neighbor.X, (int)neighbor.Y] == 1 && regionID[(int)neighbor.X, (int)neighbor.Y] == -1)
{
regionID[(int)neighbor.X, (int)neighbor.Y] = ID;
coords.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
return coords;
}
// returns a list of the valid cardinal direction neighbors for the given location on the grid
private List<Vector2> ValidNeighbors(Vector2 v)
{
List<Vector2> neighbors = new List<Vector2>();
if (v.X - 1 > 0)
{
neighbors.Add(new Vector2(v.X - 1, v.Y));
}
if (v.Y - 1 > 0)
{
neighbors.Add(new Vector2(v.X, v.Y - 1));
}
if (v.X + 1 < regionID.GetLength(0))
{
neighbors.Add(new Vector2(v.X + 1, v.Y));
}
if (v.Y + 1 < regionID.GetLength(1))
{
neighbors.Add(new Vector2(v.X, v.Y + 1));
}
return neighbors;
}
// convenience method to get the coords of the largest room on the map
// assumes 0 == wall & 1 == open
public static List<Vector2> GetLargestRoom(int[,] data)
{
CaveGridManager mgr = new CaveGridManager(data);
List<Vector2> largest = new List<Vector2>();
foreach (List<Vector2> list in mgr.regionCoords)
{
if (list.Count > largest.Count)
{
largest = list;
}
}
return largest;
}
}
}
The class above can be used a couple of different ways. The simplest to pass a rectangular int[,] to the static method & get back a list of coords as described in the original problem statement:
List<Vector2> coordList = CaveGridManager.GetLargestRoom(map);
For any given x,y location on the map, we can immediately see which room (if any) it belongs to by checking regionID[x,y]. Assuming there's a room there (that is to say regionID[x,y] >= 0) we can then immediately get all of the coords for that room by checking regionCoords[n] (where n is the ID of the room. If desired, these features can help us use the class in other ways. For instance, we could find rooms that are below a certain threshold & fill them. Or include some methods for connecting separate rooms with tunnels.
The flood fill algorithm used here is the four-way stack/queue based non-recursive implementation. It has the advantage of being relatively easy to understand and it has been optimized to check elements before committing them to the queue. It's likely to be fine for most cases, but if profiling the application reveals a problematic bottle in the flood fill code, there are some known optimizations that may help. For instance, it could be optimized further to take advantage of span filling.
