Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 Elements, 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?

share|improve this question
    
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) –  thorsten müller Jul 28 '13 at 7:09
2  
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. –  thorsten müller Jul 28 '13 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. –  Schoolboy Jul 28 '13 at 7:53
2  
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. –  Martijn Pieters Jul 28 '13 at 8:34
add comment

1 Answer

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
        seen.add((x, y))
        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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.