Dungeon_Generator/DungeonGenerator.lua

local Bresenham = require("bresenham/bresenham")
local Delaunay = require("delaunay/delaunay")
local Point    = Delaunay.Point
local Map = require("Map")
local Room = require("Room")

local Node = require("Graph/Node")
local Graph = require("Graph/Graph")
local MST = require("Graph/MST")

require("func")

local Generator = {
  _VERSION = "0",

  DIMENSION=64,
  NB_ROOMS = 400

}



function roundm(n, m) return math.floor(((n + m - 1)/m))*m end

function getRandomPointInCircle(radius)
  local t = 2*math.pi*math.random()
  local u = math.random()+math.random()
  local r = nil
  if u > 1 then r = 2-u else r = u end
  return radius*r*math.cos(t), radius*r*math.sin(t)
end

function trim_table(t, indices)
  function reverse(tbl)
    local r = {}
    for i=1, math.floor(#tbl / 2) do
      r[i], r[#tbl - i + 1] = tbl[#tbl - i + 1], tbl[i]
    end
    return r
  end

  -- We're reversing the indcies to avoid removing the wrong rooms by popping the items.
  for _,i in pairs(reverse(indices)) do
    table.remove(t, i)
  end
end


-- Dirty and unoptimized room generation
function generate_rooms()
  local rooms = {}
  for i=1, Generator.NB_ROOMS do 
    width,height = roundm(math.pow(math.random(), 2)*10+2,1), roundm(math.pow(math.random(), 2)*10+2,1)
    local x,y= getRandomPointInCircle(16-math.max(width, height))
    x = x+Generator.DIMENSION/2
    y = y+Generator.DIMENSION/2
    local r = Room(x, y, width, height)
    table.insert(rooms, r)
  end

  local done = false
  local pass = 0
  while not done do
    -- Repulsion calculation
    for a_i, a in pairs(rooms) do
      a.vx, a.vy = 0,0
      for b_i, b in pairs(rooms) do
        if (a_i ~= b_i) and a:intersects(b) then
          local dx = a.x - b.x
          local dy = a.y - b.y
          local l = math.sqrt(dx*dx + dy*dy)
          a.vx = a.vx + dx/l
          a.vy = a.vy + dy/l
          break
        end
      end
    end

    -- Repulsion applicaiton and room carving
    for _, room in pairs(rooms) do
      local l = math.sqrt(room.vx*room.vx + room.vy*room.vy)
      if l >= 0.01 then
        room.x = room.x + room.vx/l
        room.y = room.y + room.vy/l
      end
    end

    -- triming out of bounds rooms
    for i=#rooms,1,-1 do
       local room = rooms[i]
        if room.x < 1 or room.y < 1 or room.x >= Generator.DIMENSION-room.width-1 or room.y >= Generator.DIMENSION-room.height-1 then
         table.remove(rooms, i)
       end
    end     

    -- Exit check
    done = true
    for a_i, a in pairs(rooms) do
      for b_i, b in pairs(rooms) do
        if a_i ~= b_i and a:intersects(b) then
          done = false
          break
        end
      end
      if not done then break end
    end
    pass = pass+1
  end
  return rooms
end


function Generator.generate(seed)
    math.randomseed(seed) 

    local rooms = generate_rooms()
    -- Keeping the biggest rooms
    local biggest_rooms = filter(function(r) return r.width >= 4 and r.height >= 4 end, rooms)

    -- Generating their centers
    local centers = map(function(r) return Point(r.x+r.width/2, r.y+r.height/2) end, biggest_rooms)



    local triangles = Delaunay.triangulate(unpack(centers))
    local edges = {}
    for i, triangle in ipairs(triangles) do
      for _,edge in pairs({triangle.e1, triangle.e2, triangle.e3}) do
        local found = false
        for _,v in pairs(edges) do
          if v == edge then
            found = true
            break
          end
        end
        if not found then
          table.insert(edges, edge)
        end
      end
    end

    local graph = Graph(centers, edges)
    local res = graph
    if #edges > 3 then
      res = MST.search(graph,
        function(edge)
          local dx = edge.p1.x - edge.p2.x
          local dy = edge.p1.y - edge.p2.y
          return math.sqrt(dx*dx+dy*dy)
        end
        )
    end

    local m = Map(Generator.DIMENSION, Generator.DIMENSION)
    for _, r in pairs(biggest_rooms) do
      m:carve(r)
    end

    for _,edge in pairs(res.edges) do
      local vertices_ok = 0
      for _,c in pairs(centers) do
        if edge.p1.id ==c.id or edge.p2.id == c.id then
          vertices_ok = vertices_ok + 1
        end 
      end
      if vertices_ok == 2 then
        Bresenham.los(math.floor(edge.p1.x), math.floor(edge.p1.y), math.floor(edge.p2.x), math.floor(edge.p2.y),
          function(x, y) 
            m.tiles[y][x] = 0 
            return true 
          end
          )
      end
    end
    return m
end
return Generator