Decomposing a collision grid into a set of boxes

Question

I'm looking for a decent algorithm to decompose a collision grid (e.g. bool[w,h])...

...into a non-overlapping set of boxes (e.g. List<Rectangle>).

The solution does not have to be the best all the time, as long as it is simplified enough (otherwise I would just create one box per tile).

Answer 1

Perhaps you could check if there is a group of 4 tiles. For example the left top tile group is invalid because you have a passible tile. Then you check whether if there is a possible group in the vertical or horizontal alignment and keep resizing the box until no solid tile is found. In case there is a group of 4 you check in either direction whether 2 of those tiles can form another 4. If not then you stop looking in that direction and keep the rectangle as is.

For each grouped tileset you also mark them as checked to make sure your algorithm does not check them again.

So in sequence:

etc. Simply go from top left to bottom right one tile at a time. If its solid check the algorithm. If the tile is already checked we skip those till we reach the last tile. As long the rectangle can grow downwards and to the right equal in size you should cover it.

Answer 2

A simple algorithm I could think of (it won't optimize the distribution/coverage too well, but it will):

1. Have some kind of bitmask/array to mark boxes as "done".
2. From left to right top to bottom, pick the first box not marked as done.
3. From there on walk to the right as long as the boxes are filled and not yet "done".
4. Once you hit the end of the map or some not occupied box, go down as long as these rows are identical (i.e. same boxes filled).
5. Mark all boxes selected that way as "done" and store the rectangle.
6. Repeat starting with the step 2 till all boxes are "done".

This will essentially get you the exact same structure you've outlined in your image, with the slight difference that the bright green rectangle will be shorter by two boxes (as the blue and dark green ones take the first/last box).