How do I find the optimal wall to tear down in a maze to generate the largest area?

Question

I have a maze represented by a two dimensional array.

bool[][] maze = ...

where maze[row][column] is True if there is a wall at that location, or False if there is no wall at that location. The perimeter is always surrounded by walls.

The goal is to identify the largest room and then find one cut point in the maze that, if you break down the wall at that point, will create the new largest room.

Is there an algorithm that will find the wall to break that will create the largest room?

Should this be modeled as a graph?

EDIT:

I was haphazardly throwing around the word room. A room is one or more non-walls, connected together.

----------
|   |    |
|   |----|
|   |    |
----------

maze = { {True, True, True, True, True},
         {True, False, True, False, True},
         {True, False, True, True, True},
         {True, False, True, False, True},
         {True, True, True, True, True} }

This diagram contains three rooms. Their areas are 3, 1, and 1. The optimal cut points would be either (1,2) or (3, 2). Either of these would generate a room with an area of 5.

Answer 1

Union-find seems like an appropriate algorithm here.

Just loop through the grid and union each non-wall cell with its non-wall neighbours.

Then loop through the sets to find the biggest one (this is the biggest room).

Then loop through the grid again and, for each wall, check the size of union-ing the different sides of the wall together (just record the size, don't actually perform the union). The biggest recorded union would indicate the wall to break down to create the biggest room.

The running time of using known optimizations to union-find would be, for all remotely practical sizes of the grid, O(rowCount*columnCount) (linear).

Answer 2

The approach that comes to mind immediately is brute force, which isn't too inefficient in this case because it only takes polynomial time. Just try removing each section and see which one creates the largest room.

Here is some pseudo-code that uses this approach

int[] removeBestWall(maze) {
  int maxSize = 0;
  int[] bestWall = [0, 0]
  for(int i = 1; i < maze.width - 1; i++) {
    for(int j = 1; j < maze.height - 1; j++) {
      int size = getRoomSize(maze, i, j);
      if(size > maxSize) {
        maxSize = size;
        bestWall = [i, j];
      }
    }
  }
  return bestWall;
}

int getRoomSize(maze, i, j) {
  if(maze[i][j] == True) return 0;
  int size = 1;
  bool[][] newMaze = make;
  newMaze[i][j] = True;
  return size + 
   getRoomSize(newMaze, i, j + 1) +
   getRoomSize(newMaze, i, j - 1) +
   getRoomSize(newMaze, i + 1, j) +
   getRoomSize(newMaze, i - 1, j);
}

Answer 3

I agree that the data structure you've shown is ambiguous. You really want two arrays: one for horizontal walls and one for vertical. Another way to lay it out is as an array of cell structs where each struct holds a Boolean value for its right and bottom walls.

Since you are always looking for one wall between two rooms, this amounts to finding two adjacent rooms with the largest total area. Start by identifying the rooms and making a list. This is by depth or breadth first search of the forest of open squares. Each connected component of the forest is a room. The area is the number of squares in the component.

Next you need to know which rooms share each wall. This is just a matter of looping through all internal walls and finding the rooms adjacent to it. You'll then have a list of walls and two associated rooms for each.

Finally, traverse this list and pick the wall with adjacent rooms totaling to the largest area.

There are various ways to make this computation fast, but unless brute force benchmarks as too slow, this is premature optimization. I'm sure this will work fine on a 500x500 maze in a fraction of a second.