Skip to content

Instantly share code, notes, and snippets.

@vlat456
Created July 9, 2016 17:59
Show Gist options
  • Save vlat456/3867c2a1045020c507586d35ae6eb8c3 to your computer and use it in GitHub Desktop.
Save vlat456/3867c2a1045020c507586d35ae6eb8c3 to your computer and use it in GitHub Desktop.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment