Quick Links: Download Gideros Studio | Gideros Documentation | Gideros Development Center | Gideros community chat
Procedural map of non-overlapping circles - Gideros Forum

Procedural map of non-overlapping circles

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:

image

How would you approach creating this? Ideally supporting a large number of circles, say 1,000,000 or so.
My Gideros games: www.totebo.com
circles.png
2305 x 1656 - 281K

Comments

  • olegoleg Member
    edited February 1
    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

  • keszeghkeszegh Member
    edited February 1
    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.
  • Just make the radius of the circles more than what it really is then check for circle collision.
  • hgy29hgy29 Maintainer
    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

    Likes: SinisterSoft

    +1 -1 (+1 / -0 ) Share on Facebook
  • 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.
    My Gideros games: www.totebo.com
  • Don't bother with box2d, circle collision is fairly easy.
  • 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.
    My Gideros games: www.totebo.com
  • 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?
  • 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!
    My Gideros games: www.totebo.com
  • antixantix Member
    edited February 2
    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
    Follow me on FaceBook Check out my DevBlog, my GitHub, and try my games...
    Falling Animals | Breaky Wall | Exetor | Mini Putt Golfing
  • antixantix Member
    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
    Follow me on FaceBook Check out my DevBlog, my GitHub, and try my games...
    Falling Animals | Breaky Wall | Exetor | Mini Putt Golfing
  • antixantix Member
    I also think this could be solved with Perlin Noise but it would be overly complex IMHO ;)
    Follow me on FaceBook Check out my DevBlog, my GitHub, and try my games...
    Falling Animals | Breaky Wall | Exetor | Mini Putt Golfing
  • 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.
    My Gideros games: www.totebo.com
  • Maybe that will help:

    Likes: antix

    +1 -1 (+1 / -0 ) Share on Facebook
  • Thanks @rrraptor !
    My Gideros games: www.totebo.com
  • antixantix Member
    edited February 3
    @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
    Follow me on FaceBook Check out my DevBlog, my GitHub, and try my games...
    Falling Animals | Breaky Wall | Exetor | Mini Putt Golfing
Sign In or Register to comment.