Quick Links: Download Gideros Studio | Gideros Documentation | Gideros community chat | DONATE
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.
circles.png
2305 x 1656 - 281K
My Gideros games: www.totebo.com

Comments

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

    my games:
    https://play.google.com/store/apps/developer?id=razorback456
    мій блог по гідерос https://simartinfo.blogspot.com
    Слава Україні!
  • keszeghkeszegh Member
    edited 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.
  • Just make the radius of the circles more than what it really is then check for circle collision.
    Coder, video game industry veteran (since the '80s, ❤'s assembler), arrested - never convicted hacker (in the '90s), dad of five, he/him (if that even matters!).
    https://deluxepixel.com
  • 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.
    Coder, video game industry veteran (since the '80s, ❤'s assembler), arrested - never convicted hacker (in the '90s), dad of five, he/him (if that even matters!).
    https://deluxepixel.com
  • 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?
    Coder, video game industry veteran (since the '80s, ❤'s assembler), arrested - never convicted hacker (in the '90s), dad of five, he/him (if that even matters!).
    https://deluxepixel.com
  • 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 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
  • 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
  • I also think this could be solved with Perlin Noise but it would be overly complex IMHO ;)
  • 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
  • antixantix Member
    edited 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

    Likes: MoKaLux

    +1 -1 (+1 / -0 )Share on Facebook
Sign In or Register to comment.