|
=={{header|Lua}}==
{{Works with|Lua|5.21}}
'''maze_generation.lua:'''
This is an implementation of the recursive backtracker maze generation algorithm found at [http://www.astrolog.org/labyrnth/algrithm.htm Think Labyrinth!] but without recursion :)
<lang Lua>
-- Fisher-Yates shuffle from http://santos.nfshost.com/shuffling.html
function shuffle(t)
for i = 1, #t - 1 do
local r = math.random(i, #t)
t[i], t[r] = t[r], t[i]
end
end
-- builds a width-by-height grid of falses
This solution consists of four files:
function initialize_grid(w, h)
local a = {}
for i = 1, h do
table.insert(a, {})
for j = 1, w do
table.insert(a[i], false)
end
end
return a
end
-- average of a and b
#stack.lua - very simple implementation of the LIFO container, used for stacking the travel path
function avg(a, b)
#maze.lua - simple maze implementation
return (a + b) / 2
#backtracker.lua - actual algorithm implementation
end
#demo.lua - some code to show off the functionality
function make_maze(w, h)
'''stack.lua:'''
w = w or 16
<lang Lua>Stack = {}
h = h or 8
local map = initialize_grid(w*2+1, h*2+1)
function Stack:Create()
local stack = {}
function stack:push(item)
self[#self + 1] = item
end
function stack:pop()
local item = self[#self]
self[#self] = nil
return item
end
return stack
end</lang>
function walk(x, y)
'''maze.lua:'''
map[y][x] = true
<lang Lua>require "stack"
Maze local d = {
{x = x, y = y-2}, -- north
{
{x = x+2, y = y}, -- east
directions =
{x = x-2, y = y}, -- west
{
north = { x = 0x, y = y+2}, -1- },south
}
east = { x = 1, y = 0 },
shuffle(d)
south = { x = 0, y = 1 },
for i, dir in ipairs(d) do
west = { x = -1, y = 0 }
local xx = dir.x
}
local yy = dir.y
}
if map[yy] == nil then
-- out of bounds north or south
elseif map[yy][xx] == nil then
-- out of bounds east or west
elseif map[yy][xx] then
-- already visited
else
if xx == x then
map[avg(y, yy)][x] = true
else -- by elimination, yy == y
map[y][avg(x, xx)] = true
end
walk(xx, yy)
end
end
end
walk(math.random(1, w)*2, math.random(1, h)*2)
function Maze:Create(width, height, closed)
-- Actual maze setup
local maze = {}
for y = 1, height do
maze[y] = {}
for x = 1, width do
maze[y][x] = { east = self:CreateDoor(closed), south = self:CreateDoor(closed)}
-- Doors are shared beetween the cells to avoid out of sync conditions and data dublication
if x ~= 1 then maze[y][x].west = maze[y][x - 1].east
else maze[y][x].west = self:CreateDoor(closed) end
if y ~= 1 then maze[y][x].north = maze[y - 1][x].south
else maze[y][x].north = self:CreateDoor(closed) end
end
end
function maze:resetDoors(close)
for y = 1, #self do
self[y][#self[1]].east:setOpened(not close)
for i, cell in ipairs(self[y]) do
cell.north:setOpened(not close)
cell.west:setOpened(not close)
end
end
for i, cell in ipairs(self[#self]) do
cell.south:setOpened(not close)
end
end
function maze:resetVisited()
for y = 1, #self do
for x = 1, #self[1] do
self[y][x].visited = nil
end
end
end
function maze:tostring(wall, passage)
wall = wall or "#"
passage = passage or " "
local result = ""
local verticalBorder = ""
for i = 1, #self[1] do
verticalBorder = verticalBorder .. wall .. (self[1][i].north:isClosed() and wall or passage)
end
verticalBorder = verticalBorder .. wall
result = result .. verticalBorder .. "\n"
local s = {}
for y, row in ipairs(self) do
for i = 1, h*2+1 do
local line = row[1].west:isClosed() and wall or passage
for j = 1, w*2+1 do
local underline = wall
if map[i][j] then
for x, cell in ipairs(row) do
table.insert(s, ' ')
line = line .. " " .. (cell.east:isClosed() and wall or passage)
else
underline = underline .. (cell.south:isClosed() and wall or passage) .. wall
table.insert(s, '#')
end
end
result = result .. line .. "\n" .. underline .. "\n"
end
table.insert(s, '\n')
end
return result
return table.concat(s)
end
return maze
end
print(make_maze())
'''
-- This function was designed to be easily replaced by the function generating Legend of Grimrock doors
function Maze:CreateDoor(closed)
local door = {}
door._closed = closed and true or false
function door:isClosed()
return self._closed
end
function door:isOpened()
return not self._closed
end
function door:close()
self._closed = true
end
function door:open()
self._closed = false
end
function door:setOpened(opened)
if opened then
self:open()
else
self:close()
end
end
return door
end</lang>
'''backtracker.lua:'''
<lang Lua>require "maze"
-- Backtracker algorithm (a variation of the recursive backtracker algorithm made without recursion)
function Maze:Backtracker(maze)
maze:resetDoors(true)
local stack = Stack:Create()
local cell = { x = 1, y = 1 }
while true do
maze[cell.y][cell.x].visited = true
-- Gathering all possible travel direction in a list
local directions = {}
for key, value in pairs(self.directions) do
local newPos = { x = cell.x + value.x, y = cell.y + value.y }
-- Checking if the targeted cell is in bounds and was not visited previously
if maze[newPos.y] and maze[newPos.y][newPos.x] and not maze[newPos.y][newPos.x].visited then
directions[#directions + 1] = { name = key, pos = newPos }
end
end
-- If there are no possible travel directions - backtracking
if #directions == 0 then
if #stack > 0 then
cell = stack:pop()
goto countinue
else break end -- Stack is empty and there are no possible directions - maze is generated
end
-- Choosing a random direction from a list of possible direction and carving
stack:push(cell)
local dir = directions[math.random(#directions)]
maze[cell.y][cell.x][dir.name]:open()
cell = dir.pos
::countinue::
end
maze:resetVisited()
end</lang>
'''demo.lua:'''
<lang Lua>require "maze"
require "backtracker"
maze = Maze:Create(30, 10, true)
--[[ Maze generation depends on the random seed, so you will get exactly
identical maze every time you pass exactly identical seed ]]
math.randomseed(os.time())
Maze:Backtracker(maze)
print(maze:tostring())</lang>
{{Out}}
<pre>#############################################################
# # # # # # # # # # # #
# # # ### ### ### ### # ### ### # # # # # ### ### # # # # # #
# # # # # # # # # # # # # # # # #
# ### ##### ####### ######### ##### ####### # # ### ####### #
# # # # # # # # # # # # # # #
### ##### ### # # ##### # ####### ####### # ### # ####### # #
# # # # # # # # # # # # # # # #
# # # ##### ### ### ##### ### ####### # ### # ### # # # ### #
# # # # # # # # # # # # # # # #
# ########### ### ### # ### ############# # # ### ### ### ###
# # # # # # # # # # # # #
##### # # ##### ### ####### ######### # ##### ######### ### #
# # # # # # # # # # # # # # # #
# ######### # # # # ### # # # # ##### ####### # ### # # ### #
# # # # # # # # # # # # # # # # #
# ### ########### ########### ######### ### # # # # # # # # #</pre>
# # # # # # # # # # # # # # # #
### ### # # # ##### ######### # # # # # # ##### # ####### # #
# # # # # # # # # #
#############################################################</pre>
=={{header|Mathematica}}==
|