I'm working on some 2D games with Pygame. I need to place several objects at the same time randomly without them intersecting. I have tried a few obvious methods but they didn't work.
Obvious methods follow (in pseudo):
create list of objects
for object in list:
for other object in list:
if object collides with other object:
create new list of objects
That method took forever.
Other method I tried:
create list of objects
for object in list:
for other object in list:
if object collides with other object:
remove object from list
That method returned near empty lists.
I'm dealing with a list that is anywhere from 2 - 20 objects large. Any suggestions?
EDIT: The rectangles are all random different sizes.
In my case I had a similar problem except that I had some pre-exiting rectangles inside the overall rectangle. So new rectangles had to be placed around those existing ones.
I used a greedy approach:
This requires a conversion from your original coordinate space to/from the grid space but straightforward to do.
(Note that running Kadene directly on the original, global rectangle takes to long. Going via a grid approximation is plenty fast for my application)
Did you try:
No sense recreating the entire list, or taking out everything that's involved in a collision.
Another idea is to "fix" collisions by either of the following approaches:
1) Find the center of the region of intersection, and adjust the appropriate corner of each intersecting rect to that point, such that they now touch on corner/edge instead of intersecting.
2) When a rectangle collides with something, randomly generate a sub-region of that rectangle and try that instead.
an alternative pseudocode, to those already mentioned:
Or something like that.
But this has the advantage of possibly creating some smaller objects than you intended, and creating objects which almost intersect (i.e. touch).
If it's a map for the player to traverse, they may still not be able to traverse it because their path could be blocked.
I've changed my answer a bit to address your follow-up question about whether it could be modified to instead generate random non-colliding squares rather than arbitrarily rectangles. I did this in the simplest way I could that would work, which was to post-process the rectangular output of my original answer and turn its contents into square sub-regions. I also updated the optional visualization code to show both kinds of output. Obviously this sort of filtering could be extended to do other things like insetting each rectangle or square slightly to prevent them from touching one another.
My answer avoids doing what many of the answers already posted do -- namely randomly generate rectangles while rejecting any that collide with those already created -- because it sounds inherently somewhat slow and computationally wasteful. Instead it concentrates on only generating ones that don't overlap in the first place.
That makes what needs to be done relatively simple by turning it into a area subdivision problem which can be done very quickly. Below is one implementation of how this could be done. It starts with a rectangle defining the outer boundary which it divides into four smaller non-overlapping rectangles. That is accomplished by choosing a semi-random interior point and using it along with the four existing corner points of the outer rectangle to form the four subsections.
Most of the action take place in the
quadsect()
function. The choice of the interior point is crucial in determining what the output looks like. You can constrain it any way you wish, such as only selecting one that would result in sub-rectangles of at least a certain minimum width or height or no bigger than some amount. In the sample code in my answer, it's defined as the center point ± 1/3 of the width and height of the outer rectangle, but basically any interior point would work to some degree.Since this algorithm generates sub-rectangles very rapidly, it's OK to spend some computational time determining the interior division point.
To help visualize the results of this approach, there's some non-essential code at the very end that uses the
PIL
(Python Imaging Library) module to create an image file displaying the rectangles generated during some test runs I made.Anyway, here's the latest version of the code and output samples:
Output Sample 1
Output Sample 2
There is a very simple approximation to your problem which worked fine for me:
I used this to randomly generate a 2D map (Zelda like). My objects' images are smaller than <100*100>, so I used grid of size <500*500> and allowed for 1-6 objects in each grid.
I assume you already have the
create_object()
andcollides()
functionsYou may also need to decrease the size of the rects if this loops too many times