# Finding possible positions for rectangle in a 2-d array

Well, the title is not very appropriate, please read on (I couldn't get a better one).

Note: Using Python 2.7, but an algorithm will help too.

I'm making a side scroller game, in which I am generating the obstacles on the fly. The trouble I am having is figuring out how to generate the obstacles. o_O
I have a some kind of a logic, but then I'm having trouble in figuring out the entire logic.

So here's my problem from an implementation perspective :
I have a `Surface`, in which I have put some `Element`s, which are all rectangles.
Think of it like:

``````0 0 0 0 0 0 0
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 0 0 0 0 0 0
0 1 1 0 0 1 1
0 0 0 0 0 1 1
``````

As in the above structure, how can I determine if a `axb` rectangle can be added without overlapping another rectangle (of 1s), and where all. Also, that with maintaining a distance of x elements (even diagonally) from all the other objects, that means the entire rectangle is (x+3, x+4). Something like if `x=1, a=3, b=4`, there's only one possible arrangement:
(2s represent the new object)

``````2 2 2 0 0 0 0
2 2 2 0 1 1 0
2 2 2 0 1 1 0
2 2 2 0 1 1 0
0 0 0 0 0 0 0
0 1 1 0 0 1 1
0 0 0 0 0 1 1
``````

Basically, I need to find all the points, from which an rectangle of sides `a` and `b` can have it's, say, top-left corner. How this be achieved?

Note: Open to better ideas for generating the obstacles on the fly!

PS: Am I unclear?

• Would it be mandatory to have a path of zeros from top to bottom (or left to right) for moving? Any other restrictions like some kind of randomness? (a few very simple solutions would maybe generate rather boring levels) Jul 28, 2013 at 7:09
• btw: While it should be on topic here (algorithm problem), there would be gamedev.stackexchange.com. Or you could try to make codegolf.stackexchange.com throw any amount of very short solutions in your direction. Jul 28, 2013 at 7:13
• @thorstenmüller OOh, on re-reading your comment, no it isn't mandatory to have a path from top to bottom, but yes from left to right. A random choice from all possible locations will also help. Jul 28, 2013 at 7:53
• This question was cross-posted to Finding an appropriate rectange in a 2-d array As it is off-topic on Stack Overflow, I've voted to close there. Jul 28, 2013 at 8:34

The following should work fairly well:

``````def find_valid_locations(grid, z, a, b):
seen = set()
check = [(0, 0, 0, 0)]
w = z + b
h = z + a
while check:
x, y, ox, oy = check.pop()
if (x, y) in seen:
continue
if x + w >= len(grid) or y + h >= len(grid[0]):
continue
for i, row in enumerate(grid[x+ox:x+w+1], x+ox):
for j, val in enumerate(row[y+oy:y+h+1], y+oy):
if val:
break
else:
continue
check.extend([(i+1, y, 0, 0), (x, j+1, 0, 0)])
break
else:
yield (x, y)
check.extend([(x+1, y, w-1, 0), (x, y+1, 0, h-1)])
continue
``````

The brute force method here would be to check all positions in every potential rectangle location and only return locations where the rectange didn't encounter a non-zero position. This is essentially what we do here, with the following optimizations:

• If we have found a valid location (x, y), we can check locations (x+1, y) and (x, y+1) easily, by only checking the new positions added to the rectangle by shifting it down or to the right.
• If we encounter an obstacle at position (i, j) while checking location (x, y), we can skip checking any other location that includes (i, j) by starting our next checks at (i+1, y) and (x, j+1).

Note that I renamed the parameter `x` to `z` so that I could use `x` as a row index in the code.