TIGSource Forums

(http://i.imgur.com/pKGLRW8.png)

What's the best way to accomplish rectangles like in right side from squares in left side

Not sure of the best way, but I'd do it hierarchically and approximately.

1st pass:
Start by subdividing the grid into 4x4 squares, and identify any full 4x4 blocks. Then subdivide into 2x2, and find the 2x2 blocks. Then identify the remaining 1x1 blocks. So for a 16x4 map you might end up with:


..11221.444422..
...122..44442211
.11.....4444.122
111.....4444..22


2nd pass:
Join adjacent squares that share an edge of the same length. Starting small and going up. E.g., two adjacent 1x1 blocks can become a 2x1 block. This'll give you rectangles, but they will have power of 2 length.

If you just want to minimize the number of rectangles, you could just use horizontal strips one square in width. That is, in each row, start at the first square on the left, then move to the right, adding squares to your rectangle when you reach a gap. The first square to the right of the gap, start again.

On your picture this method would give you 20 rectangles, where what you have now gives maybe 23. I think the reason is that when you start making big rectangles, you end up with lots of single squares that you can't fit into them.

Pishtaco's is good, but certainly not the minimal number of rectangles. 
A better alternative would be do what he said for each row.  Then do it for each column.  Choose the orientation that has fewer rectangles.

There are algorithms that can guarantee the minimal number, but that's overkill.  The above algorithm should get you most of the way there. 

However, here's how I do it:
1) find all corners
2) pick a corner (can be in order, or at random, or whatever)
3) depending on the type of corner, expand in the proper direction (e.g. upper left corner, expand to the right and down)
4) if you can no longer expand in one of the directions (e.g. can't expand down), expand only in the other
5) when you can no longer expand in either direction, go back to 2

If you expect mostly rectangular sections this should probably do better than Pishtaco's.  If you expect something like your original image, then the bi-directional Pishtaco is probably a better bet.

Pick a corner on the exterior, expand it horizontally or vertically until it can't anymore, repeat.

EDIT: Yeah what Fallsburg said. Only, finding all the corners at the beginning won't cover everything as you'll occasionally create new corners near the interior.

Assuming your goal is procedural level generation, there are a bunch of different ways you could go about inflating the rectangles.

• Each step, randomly choose one of the two directions. Stop when both directions are exhausted.
• Each step, expand in both directions according to a randomly picked ratio. Stop when EITHER direction is exhausted
• Randomly pick a direction and expand as far as possible, then do likewise for the other.
• Unnecessary genetic algorithm that combines all of the above.

Also, inflating the rectangles one-at-a-time or doing a few in parallel would produce different results.

Sounds like a fun idea to play around with :)

I'm attempting to reduce vertex count in a voxel map, but procedural generation could work as well I'd suppose

Quadtree is definitely the way to go then.

Edit: Assuming you want it to be dynamic... I am making a lot of assumptions today.

Here is a Stack Overflow thread that mostly links to research papers:
http://stackoverflow.com/questions/8639154/algorithm-to-find-the-minimum-number-of-rectangles-covering-certain-elements-in

There appears to be an algorithm that gets you optimal results in O(n^(3/2)logn) time. But it's behind a stupid pay-wall, because hosting a pdf obviously costs lots of money.
http://dx.doi.org/10.1137/0215033

Holy Jesus, $25

Fuck academics.

It should be noted that no money goes to the researcher or the scientists involved in the peer-review. It's (mostly) not the academics' fault, just as it (mostly) isn't the game-developers' fault that EA are assholes.

It's just another example of an old-fashioned, corrupt, capitalistic publishing industry that has failed to move into the Internet era. Thankfully there is a movement among academics that's pushing for open publishing and it seems to be moving forward.

Also Belimoth, do you seriously mean that corporations make their research available in a better way?

We need a wikipedia article named just like that.

Oh, then you don't need rectangles, so you can just do the first stage of what I suggested. Which is just building a quadtree.

I was/will need to do something like this too, and I was thinking of a nice solution for it, but havent implemented it yet.

This is for just a 2d grid of squares, but Im sure you can can get the idea to extend it to work on a 3d volume.

-Start with a list of all squares, the "open list", probably in a hashset format or something.
-Select the first square in the in the list and create a rectangle out of it.
-Expand this rectangle north, and check if any squares in the newly expanded area are empty, do not exist in the open list (already removed), or otherwise undesirable for grouping. If any are undesirable dont apply the expansion.
-Do this for south, east, and west.
-Keep doing this until it cant expand anymore.
-Remove all the squares bounded by this rectangle from the open list.
-You have a rectangle you can convert to a quad.
-If open list length > 0 goto step 1.

I have no idea if this is the fastest or best way to do it but it seemed pretty elegant and id imagine the results would be pretty optimized.

Not sure I can give you the fastest or most optimal way, but this problem somewhat resembles a procedural generation issue I worked on - I had an irregular shaped region and I needed to fill it completely with rooms of various sizes, and I wanted to get it right the first time.

Basically, what I did was:

- For each cell in the region, I kept a set of every possible rectangular room contained that cell.

- I'd start with a single cell and randomly select a room. Then I'd add the entire set of every cell that room touched to the invalid room set.

- Before selecting a new room from a new cell, I'd subtract the invalid set from that room's current set, leaving me with a set of only valid potential rooms (since a 1x1 room was always possible, there was never any empty sets to contend with).

I wrote a more detailed page on the subject (http://www.squidi.net/three/entry.php?id=163).

This approach was designed around filling a region with rooms, with some control over making sure specific rooms appeared. It didn't try to find the best solution, or the quickest. However, using sets of rooms, you could come up with an approach that could quickly give you "good enough" by prioritizing large rooms or using a stack to iterate through solutions until you've found a solution within a certain threshold.