I'm trying to find an algorithm to fit a predefined rectangle in a grid (2D array), where the rectangle does not intersect any cells marked as "blocked." For example, below is a grid of empty (white) and blocked (blue) cells. One solution for fitting a 3x3 rectangle is shown in red.




The following assumptions hold:
1. The grids can be various sizes, but are always rectangular with borders (no wrapping)
2. The grid may be filled with "blocked" cells randomly, and may be sparse or dense.
3. It only needs to be reasonably time efficient (will not be per-frame)
4. It does not need to be perfect (guaranteed to find a solution), but it should find most (with a time-out or other cheat to halt the algorithm)

I've come up with the following two methods (in concept, not in code):
1. Randomly choose (or enumerate through) empty cells and try and fit the rectangle there. Cells can be flagged as they are checked to reduce repeat checks. I'm not sure, however, how to do the fit-check step, except the naive way of trying every combination.
2. Some form of "falling block" process, where rectangles are moved inward from the edges until colliding with a blocked cell. Some sort of provision would have to be made to check interior voids in the grid.

Out of these, #1 seems the possible better solution (and it seems like it would even find all solutions?). However, I'm sure this is a solved problem, so I figured I should give it some research. Unfortunately, I don't really know what keywords to search for.

Can anyone point me in a direction, or other ideas to try?

Thanks

Use brute force, traverse from left to right, top to bottom, but whenever a square is found inside the rectangle, skip forward a number of x positions depending on which part was obstructed. So if the rectangle is obstructed on it's right column, skip forward 3. If it's obstructed on the middle, skip 2. Skip 1 if it's left column is obstructed.

Thanks for the replies.

I will try the brute force and see how it works, skipping unnecessary checks is a good idea. It seems simple enough, and I like simple

In case anyone has further input, here are few more details about the problem:

1. The grid will typically have less than 10,000 cells, but I'd like to support up to 40-50k (say 200x200)
2. This is for procedural generation (which is why the solution does not need to be perfect), so randomness will be introduced into the system
3. There will be multiple passes, each pass using a different sized rectangle region. Cells are marked off as blocked as each rect is positioned, thus the density of blocked cells will increase each pass.
4. While the process does not need to be real-time, it should complete a run of passes in a reasonable amount of time. However, I don't see brute force taking too long on a modern system (I'll just have to try it and find out).

Here's another idea if you want something more efficient than brute force (this is completely speculative - I haven't tried any of this myself).

Let's say you have a fixed range of 'query block' sizes, e.g. 2x2 to 5x5 (all square).

For each cell in the grid, store a bit flag (for example) indicating whether, for each rect size, a block could be placed there originating at one of its corners. These flags would initially be set as a preprocessing step, and would involve (at most) checking each of the rect sizes for each cell and setting the flags appropriately.

Then, create dynamic containers, one for each query rect size. These containers will hold references to the cells that are currently valid positions for that rect size. As part of the first pass, you would then add each cell to the containers corresponding to the flags that are set for that cell. (Note that if the grid is initially empty, this preprocessing step becomes trivial.)

When it comes time to place a rect, randomly choose a cell from the 'available cells' container for that rect. Then place the rect at that location.

Placing the rect will potentially affect the flags for all cells within a specified range of that rect. You would then need to iterate over these cells, adjusting the flags and removing/adding them from the corresponding containers as necessary.

I would definitely stick with brute force until and unless you run into performance problems; only then would I pursue something like the above.

(Again, the above is all completely speculative. Also, I imagine other broad-phase-like methods could be brought to bear on this problem as well.)

@jyk:

Interesting idea, thanks. I'm definitely going the brute force approach first, but I may try to do something like you described just because it sounds fun

I had a vague notion of storing run-lengths (starting position and number of empty consecutive spaces) for each row and column, and using those to narrow down the search, comparing the rectangle's width or height with each run. I have the feeling such an approach is related somehow to what you are describing at some basic level. Although your idea is more concrete and sounds like something I could actually figure out...

p.s. this is partly a learning/self-challenge project, so I'd love to hear other interesting ideas even if they are overkill/unnecessary for my goals.

You can partition your empty space into a series of rectangles. You just then need to iterate thru the rects to find which one that can contain the red rect wholly.

You have to be really careful however in how you partition it. It has to be optimal.