Procedural map of non-overlapping circles

totebo · February 2018

Question to the floor!

Is there a way to procedurally create a map of circles that don't overlap? See handy sketch for The Ultimate Function to grab a segment of the map:

How would you approach creating this? Ideally supporting a large number of circles, say 1,000,000 or so.

oleg · February 2018

variant 1
put a point, with the help of "line"
randomly increase the point
randomly move point

variant 2

http://docs.giderosmobile.com/reference/gideros/Particles#Particles

grab the required area
http://docs.giderosmobile.com/reference/gideros/Viewport#Viewport

variant 3
Make 10 Random Tiles with Cargues and a Transparent Background
Randomly arrange tiles with overlapping each other 10-20 pixels

ps/ English is not my language

keszegh · February 2018

you can always randomize a new position and radius and check if the new point is far enough from all the earlier points one by one. if yes, good, if not, randomize another point and radius.

SinisterSoft · February 2018

Just make the radius of the circles more than what it really is then check for circle collision.

hgy29 · February 2018

Nice idea @SinisterSoft ! Make several randomly sized circles with box2d, let them fall in place, then fetch the position of each circle and use a smaller radius when rendering

totebo · February 2018

Thanks for the ideas!

I like the Box2D variant. Probably won't work with too many circles though. Ideally I'd like to avoid a two dimensional array, because it would take time to process and create. I'd like to solve it with perlin noise or another formula which is infinite. But I'm probably dreaming!

Maybe the best thing to do is to create the map offline, then just save the coordinates and radiuses of each circle. Then load that massive file on startup.

SinisterSoft · February 2018

Don't bother with box2d, circle collision is fairly easy.

totebo · February 2018

That's true. Would probably take quite a while to calculate many circles (because each circle needs to check all other circles at least once), but if I create a "circle creator" app separate to the game it doesn't really matter.

SinisterSoft · February 2018

A circle won't need to be checked for collision if it's already done it's collision check loop, as it would already have been checked. It might be faster than you think. You could also somehow divide them into integer rows and columns - so you know to not bother doing collision if there is a 2 column or 2 row gap?

totebo · February 2018

I meant all already existing circles, so only the last circle placed would need to check through all circles (minus itself). But yeah, that's probably the way to go!

antix · February 2018

Something like this might work...

WORLD_WIDTH = 2048
WORLD_HEIGHT = 2048
 
NUMCIRCLES = 256
 
MINRADIUS = 16
MAXRADIUS = 64
 
local bump = require("bump").newWorld(32)
 
local random = math.random
 
-- create n circles
for i = 1, NUMCIRCLES do
 
  local r = random(MINRADIUS, MAXRADIUS)
 
  local placed = false
  repeat
    local x = random(MAXRADIUS, WORLD_WIDTH - MAXRADIUS)
    local y = random(MAXRADIUS, WORLD_HEIGHT - MAXRADIUS)
 
    local items, len = bump:queryRect(x - r, y - r, r * 2, r * 2) -- check for overlap
 
    if len == 0 then
      bump:add({}, x, y, r * 2, r * 2)
 
      -- do your object placing here
 
      placed = true
    end
  until placed
end
 
-- cleanup
local items, len = bump:queryRect(0, 0, WORLD_WIDTH, WORLD_HEIGHT)
for i = 1, len do
  bump:remove(items[i])
end

Of course there is a chance of infinite recursion built in but it is highly unlikely that it would happen :d

antix · February 2018

Or you could opt to use a grid system to place objects. Whilst this could possibly look a little griddy it is guaranteed to never recurse and of course never overlap

WORLD_WIDTH = 2048
WORLD_HEIGHT = 2048
 
NUMCIRCLES = 256
 
MINRADIUS = 16
MAXRADIUS = 64
 
local random, remove = math.random, table.remove
 
-- generate a grid of equal sized cells
local rows = {}
for r = 1, WORLD_HEIGHT / MAXRADIUS do
  local row = {}
  for c = 1, WORLD_WIDTH / MAXRADIUS do
    row[#row + 1] = {x = c - 1, y - r - 1}
  end
  rows[#rows + 1] = row -- save row
end
 
-- generate a list of unallocated cells
local free = {}
for i = 1, #rows do
  free[#free + 1] = i
end
 
-- place objects
for i = 1, #NUMCIRCLES do
  local c = remove(free[random(1, #free)]) -- get a random cell number
  local cell = rows[c]
  local x, y = cell.x, cell.y
 
  -- place your object into your world here
end

antix · February 2018

I also think this could be solved with Perlin Noise but it would be overly complex IMHO

totebo · February 2018

Two good solutions there! The bump one is clean and nice. And would probably work, even though it's dealing with squares rather than circles.

The beauty of a perlin noise solution would be that no pre-generation would be needed and the map of circles would in theory be infinite.

rrraptor · February 2018

Maybe that will help:

totebo · February 2018

Thanks @rrraptor !

antix · February 2018

@totebo, you use squares because it's faster and more efficient, then plop your circle in the center of the rectangle

If you want to allow things to be a bit closer than rectangle bounds you can query the rectangle and check for circle overlaps between any items returned by the query. Here is a messy example that may or may not work (untested but you should get the gist of it)

WORLD_WIDTH = 2048
WORLD_HEIGHT = 2048
 
NUMCIRCLES = 256
 
MINRADIUS = 16
MAXRADIUS = 64
 
local bump = require("bump").newWorld(32)
 
local random = math.random
 
-- create n circles
for i = 1, NUMCIRCLES do
 
  local r = random(MINRADIUS, MAXRADIUS)
 
  local xA, yA, rA, xB, yB, rB
 
  local placed = false
 
  repeat
    local x = random(MAXRADIUS, WORLD_WIDTH - MAXRADIUS)
    local y = random(MAXRADIUS, WORLD_HEIGHT - MAXRADIUS)
 
    local items, len = bump:queryRect(x - r, y - r, r * 2, r * 2) -- check for overlap
 
    if len == 0 then
 
      -- 
      -- no overlap so you are good to add your circle to the world
      -- 
 
      bump:add({x = x, y = y, r = r}, x, y, r * 2, r * 2)
      placed = true
    else
 
      local overlap = false
 
      for i = 1, len do
        local function overlaps() local r = rA + rB local dx, dy = xA - xB, yA - yB return r * r > (dx * dx + dy * dy) end
 
        local other = items[i]
        xA, yA, rA, mA = other.x + other.r, other.y + other.r, other.r
        xB, yB, rB, mB = x, y, r
 
        if overlaps() then
          overlap = true
        end
      end
 
      if not overlap then
        -- 
        -- no overlap so you are good to add your circle to the world
        -- 
 
        bump:add({x = x, y = y, r = r}, x, y, r * 2, r * 2)
        placed = true
      end
 
    end
  until placed
end
 
-- cleanup
local items, len = bump:queryRect(0, 0, WORLD_WIDTH, WORLD_HEIGHT)
for i = 1, len do
  bump:remove(items[i])
end

Howdy, Stranger!

Categories

In this Discussion

Top Posters

Procedural map of non-overlapping circles

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

Procedural map of non-overlapping circles

Comments