How do I efficiently simulate a grid of static rectangles in a physics engine?

Question

I'm making a space shooter which takes place in a big dungeon, which consists of large rectangles to define walls. Everything in the game is physically simulated using Farseer Physics. There's one problem though: I want the dungeon to look sufficiently large, but that requires me to have at least 80x80 rectangles in my grid, which means that I have, in the worst case scenario, 6400 physically simulated bodies, which isn't exactly performance friendly, as you can guess.

My temporary solution was to divide the grid in vertical slices, so that, for every column, all rectangles are added using a boolean add operation, and then a body is created, using the resulting concave polygon. It increases performance a bit, but the polygons have a tendency to mess up, become non-existent, block ways that should normally be traversable or even become invalid and cause Farseer to crash.

I've been thinking about making some kind of algorithm that somehow finds the biggest areas of walls and merges them together into one big rectangle, and keeps doing this for smaller rectangles until all holes are filled, but I have no idea how to implement this. It seems like the perfect solution because it'd solve the performance problems and also the concave polygon mess I have right now. Does anyone have a clue on how to implement something like this?

It is not a solution to stop using a physics engine altogether, because a lot of things in my game rely on it.

EDIT: Here's a little example of how the bodies look like right now: (every number is a body)

And this is how I want them to be:

Answer 1

I might not understand the question correctly, but let me propose an algorithm that I think kinda hints at solving your problem.

Your problem starts with a rectangular greed where squares are free and non-free. From start the free squares are the ones we are going to build walls with, and the non-free squares are the hollow spaces.

1. Foreach free square do an expansion around that square, and see what is the biggest area that that square can belong to. By expansion I mean going in all directions from that square whilst it's possible to build an area out of free squares. Associate this largest area with the given free square.
2. Select the square that has the largest associated area, and build your merged wall by expanding around that square. Squares that belong to this merge are marked as non-free. If there are no more free squares you are done, else go to step 1.

After you are done, you should have the largest possible blocks of wall grouped together.

To clarify, by expansion around a free square I mean taking the hypothetical largest rectangle that can be built starting from the given square in all available directions.

The complexity of this algorithm for a rectangle n*m matrix is intuitively around O(n*n*m*m). In practice i think it'll be quite quick with your data. Note that this algorithm doesn't provide the fewest number of objects, but rather maximizes the sum of all areas (as per your question). I intune that the problem of minimizing the total number of bodies is much more difficult in terms of complexity.