Optimizing Random Placement

[Kwing]

Continuously, not discreetly.

Suppose I want to spawn 10 circles on a 500x500 map without any intersection. I can do this...

array of circles
for(i to 10){
  x and y random 0-499
  for(c in circles){
    while (x, y) lies within circle c
    x and y random 0-499
  }
  create circle at point (x, y)
  push circle to array
}

However, this doesn't seem optimal. At high numbers of circles or on small map sizes there's a risk of an infinite loop, or at the very least unnecessary computation. That said, it's also a bad idea to create a 500x500 array of pixels and mark them off as available or taken because we're looking at a huge amount of memory (which is also being accessed repeatedly.) Is there a better method?

[GeoKureli]

At 5/9/17 10:08 PM, Kwing wrote: Suppose I want to spawn 10 circles on a 500x500 map without any intersection.

It depends what your end pattern should look like, and what kind of volatility in grouping you want. can they end up neatly packed side by side or should it be more organic and chaotic looking? do all the circles share the same radius, or can they be anything?

Edit:

At 5/9/17 10:08 PM, Kwing wrote: Continuously, not discreetly.

...I'm guessing this means you don't want a grid-like final result for a "full" room. it would still help to know more about the purpose of this, and whether the radius is constant

[Kwing]

At 5/9/17 11:23 PM, GeoKureli wrote: ...I'm guessing this means you don't want a grid-like final result for a "full" room. it would still help to know more about the purpose of this, and whether the radius is constant

I'm supposed to design a test where the user is picking out a circle that's slightly larger than the rest among a large and chaotic group. The circles are scattered around the screen randomly but don't overlap. The number of circles and how much bigger the odd one is are both variable. That said I've run into similar problems in games also so I think whatever algorithm can be used for this will be applicable in other situations too.

[GeoKureli]

At 5/10/17 12:43 AM, Kwing wrote: I'm supposed to design a test where the user is picking out a circle that's slightly larger than the rest among a large and chaotic group. The circles are scattered around the screen randomly but don't overlap. The number of circles and how much bigger the odd one is are both variable. That said I've run into similar problems in games also so I think whatever algorithm can be used for this will be applicable in other situations too.

What kind of values are you going for with small/large radius, and min/max number of circles? Without knowing much I can only guess

1 approach is to first disperse them evenly, so there's an equal spacing between each adjacent one, and then randomly offset each by some random safe amount

another approach is to just to place them in, and when there's an overlap, get all the nearest circles and determine the least amount of nudging needed to resolve the overlap, and when the initial random placement has no overlaps, look at the nearest ones and close the gap, or if it's too far, nudge it so that another circle can be placed between them.

[GeoKureli]

another idea is to use any lazy, non-intensive method that doesn't check overlap, and then reduce the size of the circles until it all fits, so long as it's within a certain threshold, if they end up too small, redo it. The ratio between the big/small circle can stay the same

Also, I googled it. some interesting solutions there

[egg82]

QuadTrees will give you fast collision checking and might help if you want a lazy, easy, and effective way out.

A cheap (and mostly-random) way of doing this is by dividing the area into quadrants and using those.

int columns = canvasWidth / circleWidth
int rows = canvasHeight / circleHeight

array quads
for (x in columns) {
  for (int y in rows) {
    quads.add(new Point(x, y))
  }
}

for (i in 0..9) {
  int index = Math.round(Math.random() * (quads.length - 1))
  Point p = quads[index]
  quads.removeAt(index)
}

if you want to go all fancy with it:

float budgeDeltaPositive = circleWidth / 2
float budgeDeltaNegative = - (circleWidth / 2)

for (i in 0..9) {
  int index = Math.round(Math.random() * (quads.length - 1))
  Point p = quads[index]
  quads.removeAt(index)
  
  p.x += Math.random() * (budgeDeltaPositive - budgeDeltaNegative) + budgeDeltaNegative
  p.y += Math.random() * (budgeDeltaPositive - budgeDeltaNegative) + budgeDeltaNegative
}

admittedly there's better ways of influencing "randomness" into an otherwise-standard pattern, but that's what I came up with off the top of my head.

[Gimmick]

At 5/11/17 08:35 PM, egg82 wrote: QuadTrees will give you fast collision checking and might help if you want a lazy, easy, and effective way out.

Beat me to it! Yes, quad trees would be a good way to subdivide the circles. The maximum number of levels you'll need for the quadtree are lg_4(numCircles); alternatively a generic n-ary tree would work too, although it's easiest with powers of 2 as you get a neat rectangle - large circles taking up a spot in the tree leaves a known rectangle of size which can be used to distribute the smaller circles (although you would get clumping of small near large this way). See image below - if the circle takes up a lot of space (1st quadrant, bottom right) then the rest of the three 'cells' could be resized to fit, whereas if it takes up an entire cell's space then the cells would have to be subdivided further in other quadrants.

Afterwards you could shift the circles' x and y by a random amount based on the space remaining within the cell (which is why there's a small amount of padding between the circles and their cell's borders)