Open the maze

Questions
1

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()

    -- Do your drawing here
    fill(0, 0, 0, 255)
    for a = 1,maxwalls do
        rect(wall[a].x,wall[a].y,30,30)
    end
    
end
2

@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.

3

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.

4

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.

5

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

    -- Do your drawing here
    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