# Open the maze

This is my random generated maze. But sometimes it generates closed rooms. Do anyone have an idea on how I can avoid generating closed rooms?

--# Main

-- Use this function to perform your initial setup
function setup()
print("Hello World!")
maxwalls = 400
wall = {}
for a = 1,maxwalls do
wall[a] = physics.body(POLYGON,vec2(0,30),vec2(0,0),vec2(30,0),vec2(30,30))
wall[a].x = math.random(0,WIDTH/30) * 30
wall[a].y = math.random(0,HEIGHT/30) * 30
while wall[a].x < WIDTH/2 + 45 and
wall[a].x > WIDTH/2 - 45 and
wall[a].y < HEIGHT/2 + 45 and
wall[a].y > HEIGHT/2 - 45 do
wall[a].x = math.random(0,WIDTH/30) * 30
wall[a].y = math.random(0,HEIGHT/30) * 30
end

wall[a].type = STATIC

end
end

-- This function gets called once every frame
function draw()
-- This sets a dark background color
background(255, 255, 255, 255)

-- This sets the line thickness
noStroke()

fill(0, 0, 0, 255)
for a = 1,maxwalls do
rect(wall[a].x,wall[a].y,30,30)
end

end

@chunnoo

Do a search for maze generation algorithm. Look at the Wikipedia link. There you’ll see several topics on how to create mazes. There is also an example written in Python.

Dave.

I did something like this once. Each segment was part of a connected set of segments. Each set had an Id number. When you added a segment that connected to nothing, it would form a new set with a new id number. When you added a segment that connected to another segment, you would give the new segment the set Id number of the old segment. If the new segment established a connection between two different sets, you would choose one of the two set Id numbers and renumber all the segments not in that set so that all segments in the new, larger set had the same Id number. And here’s the nice part: if the new segment connected segments with the SAME Id number, it meant that you were about to encircle an area with a continuous wall.

I used this to make a maze for my kids that always had just one path from start to finish. The program kept adding segments until it couldn’t add anything else without joining together the last two sets.

I have in fact just written a maze generator for iPad in Codea. I use the depth-first algorithm (see Wikipedia) with an explicit stack instead of true recursion. I can generate NxN mazes from 5x5 to 20x20. The entrance is always at bottom left, exit at top right. It is fast.

Here is my maze generator source code. Enjoy!

--# Main

-- Use this function to perform your initial setup
function setup()
EAST = 0
NORTH = 1
WEST = 2
SOUTH = 3
EWALL = 1
NWALL = 2
WWALL = 4
SWALL = 8
XOFF = 30
YOFF = 70
ALLWALLS = EWALL + NWALL + WWALL + SWALL
VISITED = 16
NMAX = 40
iparameter("N", 5, NMAX, 20)
pN = N
M = WIDTH
XYOFF = XOFF
if HEIGHT < WIDTH then
M = HEIGHT
XYOFF = YOFF
end
stack = {}
startx = 1; starty = 1
endx  = N; endy = N
createmaze(N, startx, starty, endx, endy)
--solvemaze()
end

-- This function gets called once every frame
function draw()
-- This sets a dark background color
background(0,0,0)

-- This sets the line thickness
strokeWidth(5)

-- See if maze size has changed
if pN ~= N then
createmaze(N, startx, starty, endx, endy)
pN = N
end

for i=1, N do
x = XOFF + (i-1)*S
for j=1, N do
y = YOFF + (j-1)*S
c = maze[i][j]
w = c%VISITED
we = w%2
wn = math.floor(w/NWALL)%2
ww = math.floor(w/WWALL)%2
ws = math.floor(w/SWALL)
if we == 1 then
line(x+S, y, x+S, y-S)
end
if wn == 1 then
line(x, y, x+S, y)
end
if ww == 1 then
line(x, y, x, y-S)
end
if ws == 1 then
line(x, y-S, x+S, y-S)
end
end
end
end

function createmaze(n, sx, sy, ex, ey)
if ex > N then
ex = N; ey = N
end
S = (M - 2*XYOFF)/N
maze = {}
for i=0, NMAX+1 do
maze[i] = {}
for j = 0, NMAX+1 do
maze[i][j] = ALLWALLS
if i == 0 or i == N+1 then
maze[i][j] = maze[i][j] + VISITED
elseif j == 0 or j == N+1 then
maze[i][j] = maze[i][j] + VISITED
end
end
end
x = ex; y = ey
sp = 1
setvisited(ex, ey)
erasewalls(sx-1, sy, sx, sy)
erasewalls(ex, ey, ex+1, ey)
while true do
nx, ny = getunvisitedneighbor(x, y)
if nx < 0 then
x, y = pop()
if sp == 1 then
break
end
else
setvisited(nx, ny)
push(x, y)
erasewalls(x, y, nx, ny)
x = nx; y = ny
end
end
end

function push(a, b)
stack[sp]  = a
stack[sp+1] = b
sp = sp + 2
end

function pop()
sp = sp - 1
b = stack[sp]
a = stack[sp-1]
sp = sp - 1
return a, b
end

function getneighbor(x, y, d)
--print("x ", x, "y ", y, "d ", d)
if d == EAST then
x = x + 1
elseif d == NORTH then
y = y + 1
elseif d == WEST then
x = x -1
else
y = y - 1
end
return x, y
end

function notvisited(x, y)
if x < 1 or x > N then
return false
end
if y < 1 or y > N then
return false
end
v = math.floor(maze[x][y] / VISITED)
if v >= 1 then
return false
else
return true
end
end

function setvisited(x, y)
maze[x][y] = maze[x][y] + VISITED
end

function getunvisitedneighbor(x, y)
nu = 0
uds = {}
for i=EAST, SOUTH do
nx, ny = getneighbor(x, y, i)
if notvisited(nx, ny)then
nu = nu + 1
uds[nu] = i
end
end
if nu == 0 then
return -1, -1
end
td = math.random(1, nu)
nx, ny = getneighbor(x, y, uds[td])
return nx, ny
end

function getdirection(x, y, nx, ny)
if nx > x then
d = EAST
elseif ny > y then
d = NORTH
elseif nx < x then
d = WEST
else
d = SOUTH
end
return d
end

function erasewalls(x, y, nx, ny)
d = getdirection(x, y, nx, ny)
if d == EAST then
maze[x][y] = maze[x][y] - EWALL
maze[nx][ny] = maze[nx][ny] - WWALL
elseif d == NORTH then
maze[x][y] = maze[x][y] - NWALL
maze[nx][ny] = maze[nx][ny] - SWALL
elseif d == WEST then
maze[x][y] = maze[x][y] - WWALL
maze[nx][ny] = maze[nx][ny] - EWALL
else
maze[x][y] = maze[x][y] - SWALL
maze[nx][ny] = maze[nx][ny] - NWALL
end
end