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.

Answer 2

Here's what I used in one of my games (not in C#, also):

First create an array with the solid walls, create a structure like Wall, with the intergers x, y, width and height, create lots of them, one for each block.

Then loop through them and merge the ones which have the same y and height, and are neighbors (x₁ + width₁ = x₂).

Then loop again, this time using x instead of y (and vice versa), and using width instead of height (and vice versa).

This is not optimized, but you can modify it to make it faster. This was the implementation that I used in my game, it may be too slow for you.

Running this generates 38 bodies (that's the same number of bodies as in the example your posted):

Reversing the order in the last two steps generates 36 bodies:

Answer 3

Using Farseer one should use EDGES instead of constructing your map/world/level with so many bodies, which could result in performance issues.

If you can find a way to convert your map into a list of sequential vertex coords, maybe an algorithm that traces the walls and generates the list, you could then do this...

Create 1 body and add FIRST edge:

Body dungeon = BodyFactory.CreateEdge(world, start, end);

Then loop through all other vertex coords in sequence and then attach each new edge to the previous edge end coordinate. (chaining edges together in sequence until done)

FixtureFactory.AttachEdge(start, end, dungeon);

This results in 1 body instead of having 35+.