Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Let us consider the case: there is an overall bounding rectangle (call this Rb) which contains a number of rectangles within it (call this set SRo). Now I would like to randomly position a new rectangle with known bounds (call this Rn) within the bounds of Rb without intersecting any of the rectangles in the set SRo

My current approach is rather brute force:

  1. Generate random x-y coordinates for new rectangle
  2. Check Rb contains Rn if it is placed at intended coordinates
  3. Check Rn does not intersect any of rectangles inside set SRo

Anyone got any better idea?

share|improve this question
    
A couple questions: "known bounds" means that the size of Rn is fixed and you only have to randomly choose a point? Or does it mean that they will also be randomly generated but within some bounds? Question 2: Is it a pixel representation with integer coordinates or a vector representation where coordinates/sizes can be real values? –  CeeJay Dec 22 '10 at 14:34
    
1-known bounds mean size of Rn is fixed. 2-pixel representation with integer values –  codemonkey Dec 22 '10 at 14:59
add comment

5 Answers

up vote 2 down vote accepted

Recursive subdivision is one simple and guaranteed finite-time solution, though it tends to look a little... non-uniform. The end result is reminiscent a bit of a mondrian painting and doesn't look exactly like random scattered rectangles. If that's still good enough for you, the algorithm is:

makeRects(x, y, width, height)
    if shouldSubdivide(width * height) then
        // pick which way to split it, tend towards making
        // the resulting pieces closer to square
        if random(width + height) < width then
            // split vertically
            var split = random(width)
            makeRects(x, y, split, height)
            makeRects(x + split, y, width - split, height)
        else
            // split horizontally
            var split = random(height)
            makeRects(x, y, width, split)
            makeRects(x, y + split, width, height - split)
        end
    else
        // not splitting the box, so just draw a rectangle inside it
        randomRect(x, y, width, height)
    end
end

// randomly inset the rect within the given bounds
randomRect(x, y, width, height)
    var insetWidth = random(width)
    var insetHeight = random(height)
    var insetX = random(width - insetWidth)
    var insetY = random(height - insetHeight)
    placeRect(x, y, width, height)
end

// determine if a rect of the given area should be
// subdivided, or if its small enough that we should
// stop here
shouldSubdivide(area)
    // return true or false. the smaller the area, the more
    // likely to be false. tune to taste...
end

random(max)
    // generate random value between 0 and max...
end

placeRect(x, y, width, height)
    // do whatever you want here to place the rect...
end
share|improve this answer
add comment

This sounds similar to a collision-detection problem. Look at "spacial partitioning" to sub-divide Rb, and find the set of open spaces in which Rn would fit. Randomly select one of those spaces, and place Rn randomly within it.

share|improve this answer
    
definitely looking into it –  codemonkey Dec 22 '10 at 15:49
add comment

If don't run that algorithm too often (eg. just at startup-time) and there aren't thousands of rectangles, I'd probably just stick with the brute-force approach.

You could already eliminate a lot of unnecessary trial/error attempts, by combining step 1 and 2 into one step. To do this, just make sure you generate random x and y coordinates that are guaranteed to be inside Rb.

Example in pseudo-code, assumes that random() returns a value from 0-1 and that y-axis points down (screen-space).

y = Rb.minY + (random() * (Rb.height - Rn.height))
x = Rb.minX + (random() * (Rb.width - Rn.width))

Then check the rectangle position against all the already placed rectangles. If it intersects another rectangle, restart at step 1.

Depending on the generated random-values, this approach could need a lot of tries to be successful though. An optimization would be to divide your containing rectangle (Rb) into sections and increase a counter for each section that intersects a placed rectangle. Then pick random coordinates from sections with a low "rectangle-count" in step 1.

If you try to place a lot of rectangles into Rb (so that a big part of the area of Rb is covered), the brute-force approach is a very bad choice, since there's a very high probability that it will fail (endless loop).

Maybe also have a look at this answer over at stackoverflow for another approach.

share|improve this answer
add comment

Sounds like a fair implementation, there is no simple trick for avoiding doing a fair amount of checking. If you have got a performance problem then show us your code, otherwise just stick with it.

share|improve this answer
add comment

Depending on the layout of rectangles already inside, if you find that brute-force is taking too many iterations (i.e. that there are too few valid spaces to put a new rectangle after some point in time), an alternative might be to iterate through the entire bounding box, making a list of all valid positions where the new smaller box can go. Then, choose a random element from that list. Worst-case O(x*y) time, which is at least better than the random worst-case O(infinity).

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.