gistfile1.txt

local class = require("middleclass")

local Maze = class('Maze')

Maze.directions = 
  {
    north = { x = 0, y = -1 },
    east = { x = 1, y = 0 },
    south = { x = 0, y = 1 },
    west = { x = -1, y = 0 }
  }

function Maze:initialize(width, height)
  self.obj = {}
   
  local function createDoor()
    local door = {}
    door.closed = true
    
    function door:open()
      door.closed = false
    end
    
    function door:isClosed()
      return door.closed
    end
    
    function door:isOpen()
      return not door.closed
    end
    
    return door
  end

  for y = 1, height do
    self.obj[y] = {}
    for x = 1, width do
      self.obj[y][x] = { east = createDoor(), south = createDoor() }
      
      if x~=1 then self.obj[y][x].west = self.obj[y][x-1].east 
      else self.obj[y][x].west = createDoor() end
      
      if y~=1 then self.obj[y][x].north = self.obj[y-1][x].south
      else self.obj[y][x].north = createDoor() end      
    end
  end
  
  self:backtrack(math.random(width),math.random(height))
end

function Maze:directionsFrom(x, y, predicate)
  local directions = {}
  
  for name, shift in pairs(Maze.directions) do
    local _x, _y = x+shift.x, y+shift.y
    if self.obj[_y] and self.obj[_y][_x] and predicate(self.obj[_y][_x], x, y)
    then
      directions[#directions+1] = { name = name, x = _x, y = _y }
    end
  end
  return directions
end

function Maze:backtrack(x, y)
  self.obj[y][x].visited = true
  local directions = self:directionsFrom(x, y, function(cell, _x, _y) if cell.visited then return false else return true end end)
  while #directions ~= 0 do
    local rand_i = math.random(#directions)
    local dirn = directions[rand_i]
    
    directions[rand_i] = directions[#directions]
    directions[#directions] = nil -- remove last one
    
    if not self.obj[dirn.y][dirn.x].visited then 
      self.obj[y][x][dirn.name].open()
      self:backtrack(dirn.x, dirn.y)
    end 
  end
end

function Maze:mazeWidth()
  return #self.obj[1]
end

function Maze:mazeHeight()
  return #self.obj
end

function Maze:adjacentRooms(x, y)
  local rooms = {}
  if self.obj[y][x].north:isOpen() then rooms[#rooms+1] = self.obj[y-1][x]  end
  if self.obj[y][x].south:isOpen() then rooms[#rooms+1] = self.obj[y+1][x]  end
  if self.obj[y][x].east:isOpen() then rooms[#rooms+1] = self.obj[y][x+1]  end
  if self.obj[y][x].west:isOpen() then rooms[#rooms+1] = self.obj[y][x-1]  end
  return rooms
end

function Maze:solve(x, y, xf, yf) 
  local N = 1
  
  for y=1,self:mazeHeight() do    -- fill marks with 0, also index x and y . Ugly, but simple
    for x=1,self:mazeWidth() do
      self.obj[y][x].x = x
      self.obj[y][x].y = y
      self.obj[y][x].N = 0
    end
  end
  
  self.obj[y][x].N = 1               -- start position is 1
  
  while (true) do
    for y=1,self:mazeHeight() do
      for x=1,self:mazeWidth() do
        if self.obj[y][x].N == N then
          local rooms = self:adjacentRooms(x, y)
          for i=1, #rooms do
            if rooms[i].N == 0 then rooms[i].N = N + 1 end
            if rooms[i] == self.obj[yf][xf] then      -- we're at finish
              local x, y = xf, yf
              self.obj[y][x].footprint = true         -- hack, last(first) item
              for N = self.obj[yf][xf].N, 1, -1 do
                local rooms = self:adjacentRooms(x, y)
                for i=1, #rooms do
                  if rooms[i].N == N-1 then 
                    x = rooms[i].x
                    y = rooms[i].y
                    rooms[i].footprint = true 
                  end
                end
              end
            return end
          end
        end
      end
    end
    N = N+1
  end
end

function Maze:drawMaze(scale)
  for y=1, self:mazeHeight() do
    for x=1, self:mazeWidth() do
      if self.obj[y][x].footprint == true then
        local circle = display.newCircle( (scale / 2) + x*scale, (scale / 2) + y*scale, 5 )
      end
      
      if self.obj[y][x].north.closed then
        local line = display.newLine(x*scale, y*scale, (x+1)*scale, y*scale) 
        line.strokeWidth = 2
      end
      if self.obj[y][x].west.closed then
        local line = display.newLine(x*scale, y*scale, x*scale, (y+1)*scale)
        line.strokeWidth = 2
      end
      if x == self:mazeWidth() then     -- draw right border
        local line = display.newLine((x+1)*scale, y*scale, (x+1)*scale, (y+1)*scale)
        line.strokeWidth = 2
      end
      if y == self:mazeHeight() then    -- draw bottom border
        local line = display.newLine(x*scale, (y+1)*scale, (x+1)*scale, (y+1)*scale)
        line.strokeWidth = 2
      end
    end
  end
end

local maze = Maze:new(10,10)
maze:solve(1,1,10, 10)
maze:drawMaze(50)