# How do I randomly position objects without overlap?

I'm studying a little about procedurally generating levels and decided to start with a vertical scrolling game.

I would like to position some platforms vertically in my scene. So far, I've used a basic method: Random positions, with some maximum `y`-distance between them. However, that means platforms at the same height can still overlap. I would like to be able to have more than one platform at each height:

I thought about using sets of platforms including unique platforms, combined platforms (2 or 3 per `y`, and so on), and randomly position those sets. However, this would not prevent the overlapping and I really would like to do it properly procedurally.

Even so, I cannot guarantee that each platform is accessible by the player character from the previous one.

How can I proceed?

-
Randomly generating reachable platforms is already covered, so I think answers ought to focus on the overlap problem. – Anko Aug 9 '14 at 15:03

I'd try something like this:

• Go from the start to the end and place the platforms at semi-random positions.
• Ensure this basic level is solvable, i.e. the end may be reached.
• Once that's done, use additional iterations to add more optional platforms. When placing those, you can verify that they're not too close or don't overlap for example.

As an alternative:

• Rather than placing random platforms, create "screens" with fixed platform layouts (or possibly optional platforms).
• Instead of placing platforms randomly, you now pick the order of screens randomly.
• You can add constants identifying the left/right border setup to ensure levels may be solved (e.g. a very low platform can't transition to a very high platform unless there's some kind of ladder or catapult).
-

Before randomly placing the platforms you need to take into consideration some important values:

1. Character's height
2. Character's width
3. Jump's maximum height
4. Jump's maximum distance
5. Minimum distance to run for optimal jump between platforms at the same level

With that in mind you craft your platform generator floor by floor, starting by the ground floor and taking it as a platform.

Basic rules

• Character's height < vertical distance < jump's maximum height
• Character's width < horizontal distance < jump's maximum distance
• Character's width < platform width < (max horizontal space - character's width)

• If maximum horizontal distance in same floor > threshold, ensure one of the platforms complies with the minimum distance to run for taking that optimal jump
• If maximum horizontal distance in previous floor > threshold, don't place a platform above the gap in order to avoid a jump collision that disables the player to properly jump that gap

There would be more rules and considerations (e.g. placing spikes), but those are what comes to mind right now for starters.

Note: I'm not taking into account the height of the platforms just to make the rules cleaner.

Take into consideration that depending on the approach rules addition, this could be a complex problem in terms of computational theory, making it CPU-intensive. In that case, it could be seen as a CSP problem, but this first approach look suitable because the computations are bond to same-level platform and two floors at the same time (current and previous).

Just like Mario said, the approach of making hand-crafted platform blocks is less CPU-intensive and making it easier to place random platforms in real time. However, the trade-off would be to invest time creating and tuning those platform blocks (considering the rules above).

-
Interesting, however i don't agree with your fear of too much CPU computations: When creating a new platform, one must ask : where should i put the next tile in a 'possible' location ? So it's a computation involving many parameters ( horizontal and vertical distance between tiles, ... and the parameters you explained well), but there's no 'complexity' involved : compute the area(s) where a tile should be there, then depending on difficulty, put it randomly in the area, the more difficulty we have, the more the highest position in the possible area is likely. – GameAlchemist Aug 9 '14 at 23:32
@GameAlchemist You're right, because we're not comparing every platform to one another, but rather just the new set against the previous one. – pctroll Aug 9 '14 at 23:48