LÖVE

Code: Select all

math.randomseed(require('socket').gettime())
local maze = {}
local W = 39
local H = 29
local tilesize = 20
local MW = W*2+1
local MH = H*2+1

for i = 1, MW*MH do
  maze[i] = 1
end

-- Kruskal's algorithm: assign different IDs to each vertex; pick up a random
-- edge and if the IDs on both sides are different, remove the edge and join
-- both sets. We use a flood fill algorithm for simplicity, but there are
-- faster variants.

do
  local function floodfill(x, y, target, new)
    if maze[y*MW + x + 1] ~= target then return end
    maze[y*MW + x + 1] = new
    if maze[y * MW + x] == 0 then
      floodfill(x-2, y, target, new)
    end
    if maze[y * MW + x + 2] == 0 then
      floodfill(x+2, y, target, new)
    end
    if maze[(y - 1) * MW + x + 1] == 0 then
      floodfill(x, y-2, target, new)
    end
    if maze[(y + 1) * MW + x + 1] == 0 then
      floodfill(x, y+2, target, new)
    end
  end

  -- Build a list of edges
  local edges = {}
  local nedges = 0
  -- Vertical edges
  for y = 1, MH - 2, 2 do
    for x = 2, MW - 3, 2 do
      nedges = nedges + 1
      edges[nedges] = y*MW + x + 1
    end
  end
  -- Horizontal edges
  for y = 2, MH - 3, 2 do
    for x = 1, MW - 2, 2 do
      nedges = nedges + 1
      edges[nedges] = y*MW + x + 1
    end
  end

  -- Step 1: Assign a different ID to each cell
  for y = 1, MH - 2, 2 do
    for x = 1, MW - 2, 2 do
      maze[y*MW + x + 1] = y*MW + x + 1
    end
  end

  while nedges ~= 0 do
    local samegroup = false
    local x1, y1, x2, y2 = 0, 0, 0, 0

    -- Step 2: Pick an edge at random
    local i = math.random(1, nedges)

    if edges[i] % MW % 2 == 0 then
      -- Vertical edge - check group of upper and lower vertices
      x1 = (edges[i] - 1) % MW
      y1 = (edges[i] - 1 - x1) / MW - 1
      x2 = x1
      y2 = y1 + 2
      if maze[edges[i] - MW] == maze[edges[i] + MW] then
        samegroup = true
      end
    else
      -- Horizontal edge - check left and right vertices
      x1 = (edges[i] - 1) % MW - 1
      y1 = (edges[i] - 2 - x1) / MW
      x2 = x1 + 2
      y2 = y1
      if maze[edges[i] - 1] == maze[edges[i] + 1] then
        samegroup = true
      end
    end

    -- Step 3: If they are not in the same group, add an edge and
    --         mark all connected cells with the same group.
    if not samegroup then
      -- Remove wall
      maze[edges[i]] = 0
      -- Flood fill one of the sides with the group number of the other
      floodfill(x1, y1, maze[y1 * MW + x1 + 1], maze[y2 * MW + x2 + 1])
    end

    -- Remove the edge from the list
    edges[i] = edges[nedges]
    edges[nedges] = nil
    nedges = nedges - 1

    -- Go to step 2 until there are no more edges
  end
end

local canvas = love.graphics.newCanvas()

-- Draw the maze on the canvas
love.graphics.setCanvas(canvas)
love.graphics.rectangle("fill", 0, 0, tilesize*W, 1)
love.graphics.rectangle("fill", 0, 0, 1, tilesize*H)
for y = 1, MH - 2, 2 do
  local yy = (y-1) * 0.5
  for x = 1, MW - 2, 2 do
    local xx = (x-1) * 0.5
    if maze[y*MW + (x+1) + 1] ~= 0 then
      love.graphics.rectangle("fill", (xx+1)*tilesize, yy*tilesize, 1, tilesize)
    end
    if maze[(y+1)*MW + x + 1] ~= 0 then
      love.graphics.rectangle("fill", xx*tilesize, (yy+1)*tilesize, tilesize+1, 1)
    end
  end
end
love.graphics.setCanvas()

function love.draw()
  love.graphics.setBlendMode("alpha", "premultiplied")
  love.graphics.draw(canvas, math.floor(tilesize*0.5), math.floor(tilesize*0.5))
  love.graphics.setBlendMode("alpha", "alphamultiply")
end