I'd put a recursive backtracker in the code doodles thread (viewtopic.php?p=258691#p258691)
The algorithm itself is really simple, though much of my implementation could probably be improved.
I was toying around with it this morning and below is a version that before generating the maze it puts in some blank spaces (rooms). The maze then fills in all the blanks and then checks where we've got sperate regions and punches holes through in suitable spots until all regions are connected in at least one spot.
Again the code could be neater. When it comes to generation and other one off things I tend to write a bit more verbosely since speed isn't always of the essence.
- Maze.png (10.37 KiB) Viewed 3388 times
Code: Select all
function love.load()
love.window.setTitle("Recursive Backtracking Maze")
math.randomseed(os.time())
math.random(); math.random(); math.random()
-- set map width and height, should be odd numbers
mapWidth = 201
mapHeight = 151
tileSize = 4
love.window.setMode((mapWidth+2)*tileSize,(mapHeight+2)*tileSize)
generateMap()
end
function love.keypressed(key)
if key=="f1" then
generateMap()
end
end
function generateMap()
-- make a map full of walls
finishedGen = false
finishedLoop = false
map = {}
for x = 1, mapWidth do
map[x] = {}
for y = 1, mapHeight do
map[x][y] = 0
end
end
-- add rooms
local numRooms = math.random(60,80)
local sx, sy, h, w
for i = 1, numRooms do
h = math.random(3,12) * 2 -- some math here so that all rooms have even boundaries
w = math.random(3,12) * 2
sx = math.floor(math.random(4, mapWidth - w - 2)/2) * 2
sy = math.floor(math.random(4, mapHeight - h - 2)/2) * 2
for x = sx, sx + w do
for y = sy, sy + h do
map[x][y] = 1
end
end
end
-- set a random starting space
local found = 1
while found > 0 do
cx, cy = math.random(1,math.floor(mapWidth/2)) * 2, math.random(1, math.floor(mapHeight/2)) * 2
found = map[cx][cy]
end
stack = {{cx, cy}}
map[cx][cy] = 1
end
function love.update()
if finishedGen then return end
for _ = 1, 10 do
if finishedLoop == false then
generateMaze()
else
-- check for new spots, just do this in map order
for x = 2, mapWidth - 1, 2 do
for y = 2, mapHeight - 1, 2 do
if map[x][y] == 0 then
finishedLoop = false
map[x][y] = 1
stack = {{x, y}}
goto done
end
end
end
-- if we got to here there are no spots, done
finishedGen = true
-- now do breakthroughs..
breakThrough()
break
end
::done::
end
end
function breakThrough()
-- set initial regions
local region = 2
for x = 2, mapWidth - 1, 2 do
for y = 2, mapHeight - 1, 2 do
-- only set a region if it's currently 1
if map[x][y] == 1 then
floodFill(x, y, region)
region = region + 1
end
end
end
local eligible = {}
-- get eligible spots to break through
for x = 3, mapWidth - 2 do
for y = 3, mapHeight - 2 do
-- check vertical breakthrough
if map[x][y-1] > 0 and map[x][y+1] > 0 then
if map[x][y-1] ~= map[x][y+1] then
table.insert(eligible,{x,y})
end
end
-- check horizontal breakthrough
if map[x-1][y] > 0 and map[x+1][y] > 0 then
if map[x-1][y] ~= map[x+1][y] then
table.insert(eligible,{x,y})
end
end
end
end
-- break through until we're all connected. Don't update eligible tiles though, this will give more interconnectivity
local numRegions = 2 -- doesn't matter what the start value is, we know it's more than one
while numRegions > 1 do
local num = math.random(#eligible)
x = eligible[num][1]
y = eligible[num][2]
map[x][y] = region
floodFill(x, y, region)
region = region + 1
numRegions = countRegions()
end
end
function countRegions()
local num = 0
local regions = {}
local newRegion, reg
for x = 1, mapWidth do
for y = 1, mapHeight do
reg = map[x][y]
if reg > 0 then
newRegion = true
for _, val in ipairs(regions) do
if reg == val then
newRegion = false
break
end
end
if newRegion then
table.insert(regions, map[x][y])
num = num + 1
end
end
end
end
return num
end
function floodFill(x, y, num)
-- fill an area with a number, ignoring zeroes
local frontier = {{x, y}}
local newFrontier = {}
while #frontier > 0 do
newFrontier = {}
-- check the tiles we have in the frontier
for _, val in ipairs(frontier) do
x, y = val[1], val[2]
-- check north
if map[x][y-1] > 0 and map[x][y-1] ~= num then
map[x][y-1] = num
table.insert(newFrontier, {x, y-1})
end
-- check east
if map[x+1][y] > 0 and map[x+1][y] ~= num then
map[x+1][y] = num
table.insert(newFrontier, {x+1, y})
end
-- check south
if map[x][y+1] > 0 and map[x][y+1] ~= num then
map[x][y+1] = num
table.insert(newFrontier, {x, y+1})
end
-- check west
if map[x-1][y] > 0 and map[x-1][y] ~= num then
map[x-1][y] = num
table.insert(newFrontier, {x-1, y})
end
end
frontier = newFrontier
end
end
function generateMaze()
-- make maze using the recursive backtracker algorithm
local neighbours, tx, ty
cx, cy = stack[#stack][1], stack[#stack][2]
neighbours = getEligibleNeighbours(cx, cy)
if #neighbours > 0 then
-- we've got moves, take the first and dig!
-- first the intermediate space
cx = cx + neighbours[1][1]
cy = cy + neighbours[1][2]
map[cx][cy] = 1
-- then the destination space
cx = cx + neighbours[1][1]
cy = cy + neighbours[1][2]
map[cx][cy] = 1
-- add the tile to the end of the stack
cx, cy = cx, cy
table.insert(stack, {cx, cy})
else
-- no moves, remove the last entry on the stack
table.remove(stack)
if #stack == 0 then
finishedLoop = true
cx, cy = -1, -1
else
cx, cy = stack[#stack][1], stack[#stack][2]
end
end
end
function getEligibleNeighbours(x, y)
-- gets if a space two spaces away is legal and if it's a wall
-- if both adds a dx, dy to neighbours (only +/-1 as we'll use it twice when we dig)
local neighbours = {}
-- north
if y > 2 then
if map[x][y-2] == 0 then
table.insert(neighbours, {0, -1})
end
end
-- east
if x < mapWidth - 1 then
if map[x+2][y] == 0 then
table.insert(neighbours, {1, 0})
end
end
-- south
if y < mapHeight - 1 then
if map[x][y+2] == 0 then
table.insert(neighbours, {0, 1})
end
end
-- west
if x > 2 then
if map[x-2][y] == 0 then
table.insert(neighbours, {-1, 0})
end
end
-- shuffle the array if we have more than one elgible
-- five times should be fine we're only going to have 2 or 3 entries at most
if #neighbours > 1 then
shuffleArray(neighbours, 5)
end
return neighbours
end
-- quick and dirty array shuffle
function shuffleArray(array, num)
local s1, s2
for _ = 1, num do
s1 = math.random(#array)
s2 = math.random(#array)
array[s1], array[s2] = array[s2], array[s1]
end
end
function love.draw()
for x = 1, mapWidth do
for y = 1, mapHeight do
if x == cx and y == cy then
love.graphics.setColor(0.7, 0.2, 0.2)
elseif map[x][y] == 0 then
love.graphics.setColor(0.2, 0.2, 0.2)
else
love.graphics.setColor(0.7, 0.7, 0.7)
end
love.graphics.rectangle("fill", x * tileSize, y * tileSize, tileSize, tileSize)
end
end
endCode: Select all
-- Disable output buffer so debug messages print in real time
io.stdout:setvbuf("no")
-- Load, called at game start
function love.load()
love.window.setTitle("Recursive Backtracking Maze")
math.randomseed(os.time())
math.random(); math.random(); math.random()
-- set map width and height, should be odd numbers
mapWidth = 201
mapHeight = 151
tileSize = 4
love.window.setMode((mapWidth+2)*tileSize,(mapHeight+2)*tileSize)
initMapGen()
end
function love.keypressed(key)
if key=="f1" then
initMapGen()
end
end
function love.update()
-- run the coroutine if it's alive
if coroutine.status(mapGenThread) ~= "dead" then
coroutine.resume(mapGenThread)
end
end
function initMapGen()
-- just a wrapper function for creating the coroutine
mapGenThread = coroutine.create(mapGen)
end
function mapGen()
clearMap()
makeRooms()
makeMaze()
fillGaps()
breakThrough()
end
function clearMap()
-- make a map full of walls
finishedGen = false
finishedLoop = false
map = {}
for x = 1, mapWidth do
map[x] = {}
for y = 1, mapHeight do
map[x][y] = 0
end
end
end
function makeRooms()
-- add rooms
local numRooms = math.random(60,80)
local sx, sy, h, w
for i = 1, numRooms do
h = math.random(3,12) * 2
w = math.random(3,12) * 2
sx = math.floor(math.random(4, mapWidth - w - 2)/2) * 2
sy = math.floor(math.random(4, mapHeight - h - 2)/2) * 2
for x = sx, sx + w do
for y = sy, sy + h do
map[x][y] = 1
end
end
-- pause
coroutine.yield()
end
end
function makeMaze()
-- set a random staring space
local found = 1
local i = 0
while found > 0 do
cx, cy = math.random(1,math.floor(mapWidth/2)) * 2, math.random(1, math.floor(mapHeight/2)) * 2
found = map[cx][cy]
end
stack = {{cx, cy}}
map[cx][cy] = 1
while #stack > 0 do
generateMaze()
-- a small counter to make the main generation go faster
i = i + 1
if i > 25 then
i = 0
coroutine.yield()
end
end
end
function fillGaps()
-- check for gaps here and fill in from top left
for x = 2, mapWidth - 1, 2 do
for y = 2, mapHeight - 1, 2 do
if map[x][y] == 0 then
cx, cy = x, y
stack = {{cx, cy}}
map[cx][cy] = 1
while #stack > 0 do
generateMaze()
-- we'll only yeild for a frame here as these should be smaller
-- (there is a small chance the first random maze was in a small hole but we won't worry about that)
coroutine.yield()
end
end
end
end
end
function breakThrough()
-- set initial regions
local region = 2
for x = 2, mapWidth - 1, 2 do
for y = 2, mapHeight - 1, 2 do
-- only set a region if it's currently 1
if map[x][y] == 1 then
floodFill(x, y, region)
region = region + 1
end
end
end
local eligible = {}
-- get eligible spots to break through
for x = 3, mapWidth - 2 do
for y = 3, mapHeight - 2 do
-- check vertical breakthrough
if map[x][y-1] > 0 and map[x][y+1] > 0 then
if map[x][y-1] ~= map[x][y+1] then
table.insert(eligible,{x,y})
end
end
-- check horizontal breakthrough
if map[x-1][y] > 0 and map[x+1][y] > 0 then
if map[x-1][y] ~= map[x+1][y] then
table.insert(eligible,{x,y})
end
end
end
end
-- break through until we're all connected. Don't update eligible tiles though, this will give more interconnectivity
local numRegions = 2 -- doesn't matter what the start value is, we know it's more than one
while numRegions > 1 do
local num = math.random(#eligible)
x = eligible[num][1]
y = eligible[num][2]
map[x][y] = region
floodFill(x, y, region)
region = region + 1
numRegions = countRegions()
coroutine.yield()
end
end
function generateMaze()
-- make maze using the recursive backtracker algorithm
local neighbours
cx, cy = stack[#stack][1], stack[#stack][2]
neighbours = getEligibleNeighbours(cx, cy)
if #neighbours > 0 then
-- we've got moves, take the first and dig!
-- first the intermediate space
cx = cx + neighbours[1][1]
cy = cy + neighbours[1][2]
map[cx][cy] = 1
-- then the destination space
cx = cx + neighbours[1][1]
cy = cy + neighbours[1][2]
map[cx][cy] = 1
-- add the tile to the end of the stack
cx, cy = cx, cy
table.insert(stack, {cx, cy})
else
-- no moves, remove the last entry on the stack
table.remove(stack)
if #stack == 0 then
cx, cy = -1, -1
else
cx, cy = stack[#stack][1], stack[#stack][2]
end
end
end
function countRegions()
local num = 0
local regions = {}
local newRegion, reg
for x = 1, mapWidth do
for y = 1, mapHeight do
reg = map[x][y]
if reg > 0 then
newRegion = true
for _, val in ipairs(regions) do
if reg == val then
newRegion = false
break
end
end
if newRegion then
table.insert(regions, map[x][y])
num = num + 1
end
end
end
end
return num
end
function floodFill(x, y, num)
-- fill an area with a number, ignoring zeroes
local frontier = {{x, y}}
local newFrontier = {}
while #frontier > 0 do
newFrontier = {}
-- check the tiles we have in the frontier
for _, val in ipairs(frontier) do
x, y = val[1], val[2]
-- check north
if map[x][y-1] > 0 and map[x][y-1] ~= num then
map[x][y-1] = num
table.insert(newFrontier, {x, y-1})
end
-- check east
if map[x+1][y] > 0 and map[x+1][y] ~= num then
map[x+1][y] = num
table.insert(newFrontier, {x+1, y})
end
-- check south
if map[x][y+1] > 0 and map[x][y+1] ~= num then
map[x][y+1] = num
table.insert(newFrontier, {x, y+1})
end
-- check west
if map[x-1][y] > 0 and map[x-1][y] ~= num then
map[x-1][y] = num
table.insert(newFrontier, {x-1, y})
end
end
frontier = newFrontier
end
end
function getEligibleNeighbours(x, y)
-- gets if a space two spaces away is legal and if it's a wall
-- if both adds a dx, dy to neighbours (only +/-1 as we'll use it twice when we dig)
local neighbours = {}
-- north
if y > 2 then
if map[x][y-2] == 0 then
table.insert(neighbours, {0, -1})
end
end
-- east
if x < mapWidth - 1 then
if map[x+2][y] == 0 then
table.insert(neighbours, {1, 0})
end
end
-- south
if y < mapHeight - 1 then
if map[x][y+2] == 0 then
table.insert(neighbours, {0, 1})
end
end
-- west
if x > 2 then
if map[x-2][y] == 0 then
table.insert(neighbours, {-1, 0})
end
end
-- shuffle the array if we have more than one elgible
-- five times should be fine we're only going to have 2 or 3 entries at most
if #neighbours > 1 then
shuffleArray(neighbours, 5)
end
return neighbours
end
-- quick and dirty array shuffle
function shuffleArray(array, num)
local s1, s2
for _ = 1, num do
s1 = math.random(#array)
s2 = math.random(#array)
array[s1], array[s2] = array[s2], array[s1]
end
end
function love.draw()
for x = 1, mapWidth do
for y = 1, mapHeight do
if x == cx and y == cy then
love.graphics.setColor(0.7, 0.2, 0.2)
elseif map[x][y] == 0 then
love.graphics.setColor(0.2, 0.2, 0.2)
else
love.graphics.setColor(0.7, 0.7, 0.7)
end
love.graphics.rectangle("fill", x * tileSize, y * tileSize, tileSize, tileSize)
end
end
end