Random distribution of objects in space, with no overlap


#1

Do you guys know any math theory that allows you to fill a space with random objects, so that they don’t overlap?


#2

fill the space entirely or?


#3

I remember 2 threads on kirupa recently, however I only managed to find one:


#4

What kind of shape ? It’s quite impossible if you place object with random shape …


#5

Ok, here is another one:


#6

On a rectangle. Not fill it, but place the objects so that they don’t overlap, and so that it looks organic (not all put evenly, nor in a corner).


#7

I did that once, a long time ago. What I did was create a grid to place the items on, mathematically.

First you get the square root of the number of items you have, and Math.ceil() that. That number you have now is the number of rows as well as number of columns.

This means you have created yourself a grid with those rows and columns, which you can use to place your item in a certain cell somewhere in that grid.

Using Math.random() you can randomly chose a cell to add a little randomness.

The only problem is when the items are not equal size, then my solution wont really work that well… But it might help you out a bit :slight_smile:


#8

may be http://www.box2dflash.org/?

I did the following project using http://www.box2dflash.org/ in which bubbles collide with each other but they don’t overlap:
http://www.luftforalle.no/

Learning box2d flash is a bit pain but its a nice library.

Following website has one of the best tutorials/articles on box2dflash:
http://www.emanueleferonato.com/


#9
I did that once, a long time ago. What I did was create a grid to place the items on, mathematically.

First you get the square root of the number of items you have, and Math.ceil() that. That number you have now is the number of rows as well as number of columns.

This means you have created yourself a grid with those rows and columns, which you can use to place your item in a certain cell somewhere in that grid.

Using Math.random() you can randomly chose a cell to add a little randomness.

The only problem is when the items are not equal size, then my solution wont really work that well… But it might help you out a bit :slight_smile:

Yep, I know I can use a grid, but I want a more organic solution, not evenly positioned elements. There must be some math theories to do that. :frowning:


#10

my guess is you’re building a gallery of some kind so can we assume the objects are of four sides or are they totally random?


#11

what about using a for loop to place each item, and making sure when an item is placed it does not overlap anything else, otherwise move it away and try again… i guess you could use a hitTest on the container clip to check if the placed item is touching any other object before placing it… simple solution, but it could work…


#12

Hmm, I see. Well, another solution would be to stop thinking that you have to place them on a 2D space immediately. Because you can also first place them on a random X first, and see if there are any objects along the Y path that go with that X. You could do hitTests to make sure it doesnt hit anything too. If there is no place for that object on any Y on that X, move to another random X.

A bit like what LucidStudios showed, but then you calculate where they are going to be, instead of animating them to a position.


#13
what about using a for loop to place each item, and making sure when an item is placed it does not overlap anything else, otherwise move it away and try again.. i guess you could use a hitTest on the container clip to check if the placed item is touching any other object.

it will work if the area is large and number of object and their size are reasonable.

Complicated case you can run into is that you can’t fit a large object in remaining space since there are just not enough space for it.


#14
what about using a for loop to place each item, and making sure when an item is placed it does not overlap anything else, otherwise move it away and try again.. i guess you could use a hitTest on the container clip to check if the placed item is touching any other object before placing it... simple solution, but it could work...

Try that with a few large items, your code would crash 90% of the time. Thats because when a few items are placed, the ones that are left keep calculating for a spot, but might not be able to find anything soon, and crash the app. Happened to me, so I used the grid solution, back then.


#15
what about using a for loop to place each item, and making sure when an item is placed it does not overlap anything else, otherwise move it away and try again.. i guess you could use a hitTest on the container clip to check if the placed item is touching any other object before placing it... simple solution, but it could work...

Unfortunately this wouldn’t be optimal, as there are several hundred of objects.

This is what I’m trying to achieve, and before using the grid solution, I want to make sure the organic positioning of elements is impossible, or too difficult to bother.

http://drp.ly/1mz22L


#16
what about using a for loop to place each item, and making sure when an item is placed it does not overlap anything else, otherwise move it away and try again.. i guess you could use a hitTest on the container clip to check if the placed item is touching any other object.

it will work if the area is large and number of object and their size are reasonable.

Complicated case you can run into is that you can’t fit a large object in remaining space since there are just not enough space for it.

lol yeh true… depends if it just has to be random items and not a specific amount, then it should be fine. But if you must have 20 items on screen scattered and not touching each other, thats gonna be tricky.


#17
may be http://www.box2dflash.org/?

I did the following project using http://www.box2dflash.org/ in which bubbles collide with each other but they don’t overlap:
http://www.luftforalle.no/

Learning box2d flash is a bit pain but its a nice library.

Following website has one of the best tutorials/articles on box2dflash:
http://www.emanueleferonato.com/

Tree map is something different, I posted a link above of what I need to do.


#18
This is what I'm trying to achieve, and before using the grid solution, I want to make sure the organic positioning of elements is impossible, or too difficult to bother.

How about using the grid solution first, then apply a random x and y for the item inside the cell it is in? It wouldnt go outside its cell then, so wont touch others. But in the mean time itll be random, as it has been placed randomly in its own area.


#19

@bobocel : Is it really a few hundred object ? That screenshot doesn’t show over 100 objects I believe


#20
This is what I'm trying to achieve, and before using the grid solution, I want to make sure the organic positioning of elements is impossible, or too difficult to bother.

How about using the grid solution first, then apply a random x and y for the item inside the cell it is in? It wouldnt go outside its cell then, so wont touch others. But in the mean time itll be random, as it has been placed randomly in its own area.

You mean something like this: http://reclipse.net/kirupa/randomPlacementGrid.swf

But the issue is that I would still not position the elements organically.