dual pass cave generation algorithm

local CHANCE_TO_START_ALIVE = 480
local BIRTH_LIMIT = 5
local DEATH_LIMIT = 5
-- in phase 2 there's more death than birth in order to widen paths
local BIRTH_LIMIT_PHASE2 = 5
local DEATH_LIMIT_PHASE2 = 6
local STEPS = 3 -- per phase

local distance = 64
local pointSize = 11

local lastx
local lasty
-- function for updating last possible x and y indexes
function updateLastXY()
  -- +1 to make sure we touch the walls
  lastx = math.floor(4096/distance) + 1
  lasty = math.floor(2048/distance) + 1
end
-- initialize
updateLastXY()


function generateCave()

  local world = {}

  -- PHASE 1

  -- generate low resolution world
  initializeWorld(world)

  for i=1, STEPS do
    world = simulationStep(world)
  end

  -- PHASE 2

  -- okay, we got a rough cave shape now
  -- double its resolution and simulate again to refine shape
  world = doubleWorldResolution(world)

  DEATH_LIMIT = DEATH_LIMIT_PHASE2
  BIRTH_LIMIT = BIRTH_LIMIT_PHASE2

  for i=1, STEPS do
    world = simulationStep(world)
  end

  -- DRAWING

  local realx = 0
  for x=1, lastx do

    local realy = 0
    for y=1, lasty do

      if world[x][y] then
        AddPoint(realx, realy, pointSize)
      end

      realy = realy + distance
    end
    realx = realx + distance
  end

  FlushPoints()
end

-- doubles the world resolution in both x and y direction
-- causing every cell/space become 4 cells/spaces each
function doubleWorldResolution(world)

  -- update distance to reflect the change
  distance = math.floor(distance / 2)
  updateLastXY()

  local world2 = {}

  -- generate 2 lines at once, because they are identical
  for x=1, lastx, 2 do
    local oddcol = {}
    local evencol = {}

    -- generate 2 cells per column at once, because they are identical
    for y=1, lasty, 2 do
      local wx = math.floor(x/2)+1
      local wy = math.floor(y/2)+1
      local cell = world[wx][wy]
      -- add 2 cells in both columns
      table.insert(oddcol, cell)
      table.insert(oddcol, cell)
      table.insert(evencol, cell)
      table.insert(evencol, cell)
    end

    -- add the two columns
    table.insert(world2, oddcol)
    table.insert(world2, evencol)
  end

  return world2
end

function initializeWorld(world)
  for x=1, lastx do
    table.insert(world, {})
    local borderx = (x == 1) or (x == lastx)

    for y=1, lasty do
      local border = borderx or ((y == 1) or (y == lasty))
      if border or GetRandom(1000) < CHANCE_TO_START_ALIVE then
        table.insert(world[x], true)
      else
        table.insert(world[x], false)
      end
    end
  end
end

function simulationStep(world)
  world2 = {}

  for x=1, lastx do
    table.insert(world2, {})

    for y=1, lasty do
      local count = countNeigbours(world, x, y)

      if world[x][y] then
        if count < DEATH_LIMIT then
          table.insert(world2[x], false)
        else
          table.insert(world2[x], true)
        end
      else
        if count > BIRTH_LIMIT then
          table.insert(world2[x], true)
        else
          table.insert(world2[x], false)
        end
      end
    end
  end

  return world2
end

function countNeigbours(world, x, y)
  count = 0

  for dx=-1, 1 do
    for dy=-1, 1 do
      local x2 = x+dx
      local y2 = y+dy

      if x2 == 0 or x2 > lastx or y2 == 0 or y2 > lasty or world[x2][y2] then
        count = count + 1
      end
    end
  end

  return count
end

function onGameInit()
    MapGen = mgDrawn
    TemplateFilter = 0
    generateCave()
end

function onPreviewInit()
    onGameInit()
end