Maze generation

[kevin]

... On a separate note, do you (or anyone else) have any demonstration or tips on creating one, for solving a maze (ie finding the route out of the maze) by the quickest route?

I have a BBCBasic program that generates a maze then shows how it searches the maze for the exit. I am not sure if it can be converted to N7, but if you want to try, I can post a copy.

J

Hi Johnno, yes please, I would love to give it a go.....

[Marcus]

I think there's a maze solver (pathfinder library) included in n6. But I can't remember or check if the source code is included right now.

[johnno56]

... On a separate note, do you (or anyone else) have any demonstration or tips on creating one, for solving a maze (ie finding the route out of the maze) by the quickest route?

I have a BBCBasic program that generates a maze then shows how it searches the maze for the exit. I am not sure if it can be converted to N7, but if you want to try, I can post a copy.

J

Hi Johnno, yes please, I would love to give it a go.....

As you wish...
  maze.zip (Size: 976 bytes / Downloads: 3)

---

I think there's a maze solver (pathfinder library) included in n6. But I can't remember or check if the source code is included right now.

You are incorrect. There "is" a pathfinder library in N6... "Think"? pfftt...  lol

  pathfinder.zip (Size: 4.74 KB / Downloads: 4)

[kevin]

Thanks both, I will study both of these tomorrow......

[johnno56]

Tomorrow? It "is" tomorrow... Well... for those of us on "this" side of the planet... lol Have a great rest!

[Marcus]

I woke up two hours early and couldn't fall asleep again  So I did some n7 coding before work ...

Here I use the n6 path finder converted to n7 to solve mazes. I believe the original code, by John, was meant for controlling characters in top-down tilemap games by clicking with the mouse. So the "optimizations" (search order in FindPathRec) probably just slows things down in mazes like these.

Code:

set window "maze", 320, 240, false, 2
set redraw off

randomize time()

' Generate maze and convert to a suitable format.
maze = GenerateMaze(24, 24)
map = fill([wall: true], sizeof(maze)*2 + 1, sizeof(maze[0])*2 + 1)
for x = 0 to sizeof(maze) - 1  for y = 0 to sizeof(maze[0]) - 1
    map[x*2 + 1][y*2 + 1].wall = false
    if maze[x][y].l = true  map[x*2][y*2 + 1].wall = false
    if maze[x][y].u = true  map[x*2 + 1][y*2].wall = false
next
' Display the map.
set color 0, 0, 0
cls
set color 255, 255, 255
side = 4
for x = 0 to sizeof(map) - 1  for y = 0 to sizeof(map[0]) - 1
    dx = x*side; dy = y*side
    if map[x][y].wall  draw rect x*side, y*side, side, side, true
next
' Find a path from top left to bottom right corner. FindPath returns an array of objects with x
' and y fields.
path = FindPath(map, 1, 1, sizeof(map) - 2, sizeof(map[0]) - 2)
' Display solution. Let d be an index for the path array, increase it by one every frame.
d = 0
set color 0, 128, 200
while not mousebutton(0, true)
    ' Draw current step in the path.
    if d < sizeof(path)
        draw rect path[d].x*side, path[d].y*side, side, side, true
        d = d + 1
    endif
    redraw
    fwait 30
wend

' FindPath
' --------
' Find path in map from (srcX, srcY) to (dstX, dstY) as an array of objects with x and y fields. If
' no path could be found, an empty array is returned. The map must be a 2d array, map[x][y], where
' each element is an object with a wall field that tells whether the position is blocked or not.
function FindPath(map, srcX, srcY, dstX, dstY)
    for x = 0 to sizeof(map) - 1 for y = 0 to sizeof(map[0]) - 1  map[x][y].dist = unset
    result = []
    FindPathRec(map, srcX, srcY, dstX, dstY, 0, result)
    return result

    ' FindPathRec
    ' -----------
    function FindPathRec(map, x, y, dstX, dstY, distance, result)
        if x < 0 or x >= sizeof(map)  return false
        if y < 0 or y >= sizeof(map[0])  return false
        if map[x][y].wall  return false
        if typeof(map[x][y].dist) and map[x][y].dist <= distance  return false
        map[x][y].dist = distance
        if x = dstX and y = dstY
            clear result
            result[distance] = [x: x, y: y]
            return true
        endif
   
        dx = dstX - x
        dy = dstY - y
        if |dx| > |dy|
            if dx < 0
                resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                if dy < 0
                    resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                    resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                    resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                else
                    resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                    resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                    resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                endif
            else
                resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                if dy < 0
                    resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                    resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                    resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                else
                    resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                    resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                    resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                endif
            endif
        else
            if dy < 0
                resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                if dx < 0
                    resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                    resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                    resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                else
                    resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                    resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                    resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                endif
            else
                resDown = FindPathRec(map, x, y + 1, dstX, dstY, distance + 1, result)
                if dx < 0
                    resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                    resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                    resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                else
                    resRight = FindPathRec(map, x + 1, y, dstX, dstY, distance + 1, result)
                    resUp = FindPathRec(map, x, y - 1, dstX, dstY, distance + 1, result)
                    resLeft = FindPathRec(map, x - 1, y, dstX, dstY, distance + 1, result)
                endif
            endif
        endif
        if resLeft or resRight or resUp or resDown
            result[distance] = [x: x, y: y]
            return true       
        else
            return false
        endif
    endfunc
endfunc

function GenerateMaze(w, h)
    maze = fill([vis: false, dead: false, l: false, r: false, u: false, d: false], w, h)
    GenerateMazeRec(maze, rnd(sizeof(maze)), rnd(sizeof(maze[0])), 0)
    return maze

    function GenerateMazeRec(maze, x, y, dir)
        if x < 0 or x >= sizeof(maze) or y < 0 or y >= sizeof(maze[0])  return false
        if maze[x][y].vis  return false
        maze[x][y].vis = true
        if dir = 1
            maze[x][y].r = true
            maze[x + 1][y].l = true
        elseif dir = 2
            maze[x][y].l = true
            maze[x - 1][y].r = true
        elseif dir = 3
            maze[x][y].d = true
            maze[x][y + 1].u = true
        elseif dir = 4
            maze[x][y].u = true
            maze[x][y - 1].d = true
        endif
        visit = [1, 2, 3, 4]
        count = 0
        while sizeof(visit)
            index = rnd(sizeof(visit))
            if visit[index] = 1  count = count + GenerateMazeRec(maze, x - 1, y, 1)
            elseif visit[index] = 2  count = count + GenerateMazeRec(maze, x + 1, y, 2)
            elseif visit[index] = 3  count = count + GenerateMazeRec(maze, x, y - 1, 3)
            else  count = count + GenerateMazeRec(maze, x, y + 1, 4)
            free key visit, index
        wend
        maze[x][y].dead = count = 0
        return true
    endfunc
endfunc

[kevin]

Many thanks - I started to look at this, and Johnno's BBC Basic example, yesterday, but:
- the BBC Basic lost me very quickly (I've never looked at BBC Basic before)
- the pathfinder library in N6 just left me realizing how much I have forgotten about N6 - pretty much everything
All the best - Kevin

[johnno56]

Yeah... I had the same reaction to BBC... Most of the Basic is fairly straight forward, but the way it handles arrays(?) has me totally confused... but, then again, it doesn't take much for that to happen... lol I am still learning N7 (and a little of N6 as well)... Same here... I forget stuff pretty easily too... lol

[Marcus]

Old post, but here's an s3d version of the maze. I really want to add a player, some enemies, keys and locked doors   Maybe I can combine s3d with the tilemap library and editor ...

Code:

' rnd_dungeon.n7
' --------------

include "s3d.n7"

constant RES = 480

' Images.
visible vWallImage, vFloorImage, vCeilingImage

set window "maze", RES*min(screenw()/screenh(), 2), RES, false
set redraw off

S3D_SetView(primary, rad(45), 0.1, 12)


' Generate some images.
CreateAssets()

randomize time()

' Generate and display maze.
maze = GenerateMaze(16, 16)
side = 16
set color 0, 0, 0
cls
set color 255, 255, 255
for x = 0 to sizeof(maze) - 1  for y = 0 to sizeof(maze[0]) - 1
    dx = x*side
    dy = y*side
    if not maze[x][y].l  draw line dx, dy, dx, dy + side - 1
    if not maze[x][y].r  draw line dx + side - 1, dy, dx + side - 1, dy + side - 1
    if not maze[x][y].u  draw line dx, dy, dx + side - 1, dy
    if not maze[x][y].d  draw line dx, dy + side - 1, dx + side - 1, dy + side - 1
next
set caret width(primary)/2, height(primary) - fheight()*3
center "A random maze"
center "Click to continue ..."
redraw
while not mousebutton(0, true)  fwait 60

' Convert it to an 2d map array where each element is either empty or a wall. Let each room in the
' maze array be represented by 5x5 elements in the map array - a 5x5 units large room.
map = fill(true, sizeof(maze)*6 + 1, sizeof(maze[0])*6 + 1)
removedWallsLeft = 0
removedWallsUp = 0
for x = 0 to sizeof(maze) - 1  for y = 0 to sizeof(maze[0]) - 1
    ' Clear the 5x5 room.
    for xx = x*6 + 1 to x*6 + 5  for yy = y*6 + 1 to y*6 + 5  map[xx][yy] = false
    ' A way left?
    if maze[x][y].l
        ' Either remove the entire wall or create a doorway.
        if rnd(2 + removedWallsLeft) = 0
            removedWallsLeft = removedWallsLeft + 1
            for yy = y*6 + 1 to y*6 + 5  map[x*6][yy] = false
        else
            map[x*6][y*6 + 1 + rnd(5)] = false
            removedWallsLeft = 0       
        endif
    else
        removedWallsLeft = 0
    endif
    ' A way up?
    if maze[x][y].u
        ' Either remove the entire wall or create a doorway.
        if rnd(2 + removedWallsUp) = 0
            removedWallsUp = removedWallsUp + 1
            for xx = x*6 + 1 to x*6 + 5  map[xx][y*6] = false
        else
            removedWallsUp = 0
            map[x*6 + 1 + rnd(5)][y*6] = false
        endif
    else
        removedWallsUp = 0
    endif
next
' Display it.
set color 0, 0, 0
cls
set color 255, 255, 255
side = 4
for x = 0 to sizeof(map) - 1  for y = 0 to sizeof(map[0]) - 1
    dx = x*side; dy = y*side
    if map[x][y]  draw rect x*side, y*side, side, side, true
next
set caret width(primary)/2, height(primary) - fheight()*3
center "Same maze but way more interesting"
center "Click to continue ..."
redraw
while not mousebutton(0, true)  fwait 60

' Create mesh.
levelMesh = S3D_BeginMesh()
S3D_Begin(S3D_QUADS)
S3D_Color(255, 255, 255)
for y = 0 to sizeof(map[0]) - 1  for x = 0 to sizeof(map) - 1
    if map[x][y]
        ' "Ceiling".
        S3D_Texture(vCeilingImage)   
        S3D_Vertex(x, y, -1,        0, 0)
        S3D_Vertex(x + 1, y, -1,    1, 0)
        S3D_Vertex(x + 1, y + 1, -1, 1, 1)
        S3D_Vertex(x, y + 1, -1,    0, 1)
        ' Walls.
        S3D_Texture(vWallImage)
        if x = 0 or not map[x - 1][y]
            S3D_Vertex(x, y, -1,    0, 0)
            S3D_Vertex(x, y + 1, -1, 1, 0)
            S3D_Vertex(x, y + 1, 0,  1, 1)
            S3D_Vertex(x, y, 0,      0, 1)
        endif
        if x = sizeof(map) - 1 or not map[x + 1][y]
            S3D_Vertex(x + 1, y, -1,    0, 0)
            S3D_Vertex(x + 1, y, 0,      0, 1)
            S3D_Vertex(x + 1, y + 1, 0,  1, 1)
            S3D_Vertex(x + 1, y + 1, -1, 1, 0)
        endif
        if y = sizeof(map[0]) - 1 or not map[x][y + 1]
            S3D_Vertex(x, y + 1, -1,    0, 0)
            S3D_Vertex(x + 1, y + 1, -1, 1, 0)
            S3D_Vertex(x + 1, y + 1, 0,  1, 1)
            S3D_Vertex(x, y + 1, 0,      0, 1)
        endif
    else
        ' Floor.
        S3D_Texture(vFloorImage)
        S3D_Vertex(x, y, 0,        0, 0)
        S3D_Vertex(x + 1, y, 0,    1, 0)
        S3D_Vertex(x + 1, y + 1, 0, 1, 1)
        S3D_Vertex(x, y + 1, 0,    0, 1)
    endif
next
S3D_End()
S3D_EndMesh()

' Fog color.
fogR = 0
fogG = 8
fogB = 32

' Camera position.
camX = 10
camY = 10

' Game loop.
prevTime = clock()
fps = 0
while not keydown(KEY_ESCAPE)
    t = clock()
    dt = (min(t - prevTime, 66))/1000
    prevTime = t
    if dt  fps = fps*0.95 + 0.05/dt

    if keydown(KEY_LEFT) camX = camX - 2*dt
    if keydown(KEY_RIGHT) camX = camX + 2*dt
    if keydown(KEY_UP) camY = camY - 2*dt
    if keydown(KEY_DOWN) camY = camY + 2*dt
    set color fogR, fogG, fogB
    cls

    ' Render 3d stuff.
    S3D_Clear()
    S3D_RotateX(-rad(45.0))
    S3D_Translate(-camX, -camY, 5)
    S3D_Color(255, 255, 255)
    S3D_Mesh(levelMesh, 0)
    S3D_Render()
    S3D_RenderFog(fogR, fogG, fogB, false)
   
    set color 255, 255, 255
    set caret width(primary)/2, 2
    center "Scroll with the arrow keys"
    redraw
    wait 1
wend

' GenerateMaze
' ------------
' Return an array of the size w*h, where every element has four fields, l, r, u and d, telling if
' there's a way left, right, up and down.
function GenerateMaze(w, h)
    maze = fill([vis: false, l: false, r: false, u: false, d: false], w, h)
    GenerateMazeRec(maze, rnd(sizeof(maze)), rnd(sizeof(maze[0])), 0)
    return maze

    function GenerateMazeRec(maze, x, y, dir)
        if x < 0 or x >= sizeof(maze) or y < 0 or y >= sizeof(maze[0])  return false
        if maze[x][y].vis  return false
        maze[x][y].vis = true
        maze[x][y].wall = false
        if dir = 1
            maze[x][y].r = true
            maze[x + 1][y].l = true
        elseif dir = 2
            maze[x][y].l = true
            maze[x - 1][y].r = true
        elseif dir = 3
            maze[x][y].d = true
            maze[x][y + 1].u = true
        elseif dir = 4
            maze[x][y].u = true
            maze[x][y - 1].d = true
        endif
        visit = [1, 2, 3, 4]
        while sizeof(visit)
            index = rnd(sizeof(visit))
            if visit[index] = 1  GenerateMazeRec(maze, x - 1, y, 1)
            elseif visit[index] = 2  GenerateMazeRec(maze, x + 1, y, 2)
            elseif visit[index] = 3  GenerateMazeRec(maze, x, y - 1, 3)
            else  GenerateMazeRec(maze, x, y + 1, 4)
            free key visit, index
        wend
        return true
    endfunc
endfunc

' CreateAssets
' ------------
function CreateAssets()
    ' Wall image.
    vWallImage = createimage(64, 64)
    set image vWallImage
    for y = 0 to 63  for x = 0 to 63
        if rnd(4) = 0  set color 96 - y, 96 - y/2, 64 + rnd(64)
        else  set color 144 - rnd(64) - y, 64 - rnd(64) + y/2, 16 + rnd(32)
        set pixel x, y
    next
    set image vWallImage
    for y = 0 to 64/16 for x = 0 to 64/32+ y%2  Draw3DBorder(x*32 - y%2*16, y*16, 32, 16, 5, 192, 32, true)
    BoxBlur(vWallImage, 2, 2)
    set image vWallImage
    for y = 0 to 64/16 for x = 0 to 64/32+ y%2  Draw3DBorder(x*32 - y%2*16 + 1, y*16 + 1, 30, 14, 4, 64 - y*16, 64 + y*16, false)

    ' Floor image.
    vFloorImage = createimage(64, 64)
    set image vFloorImage
    for y = 0 to 63  for x = 0 to 63
        i = 32 + rnd(32)
        if rnd(4) = 0  set color 16 + rnd(24), 48 + rnd(32), 16 + rnd(24)
        else  set color i/2, i/2, i/2
        set pixel x, y
    next
    set image vFloorImage
    Draw3DBorder(0, 0, 64, 64, 16, 80, 32, true)
    BoxBlur(vFloorImage, 2, 2)
    set image vFloorImage
    Draw3DBorder(4, 4, 56, 56, 3, 32, 64, false)

    ' Ceiling image.
    vCeilingImage = createimage(64, 64)
    set image vCeilingImage
    for y = 0 to 63  for x = 0 to 63
        i = 24 + rnd(24)
        set color i*1.5 + rnd(24), i + rnd(8), i
        set pixel x, y
    next
    BoxBlur(vCeilingImage, 1, 4)
    set image vCeilingImage
    set color 0, 0, 0, 64
    draw rect 32, 0, 32, 32, true
    draw rect 0, 32, 32, 32, true
    Draw3DBorder(0, 0, 32, 32, 2, 24, 64, false)
    Draw3DBorder(32, 0, 32, 32, 2, 64, 24, true)
    Draw3DBorder(0, 32, 32, 32, 2, 64, 24, true)
    Draw3DBorder(32, 32, 32, 32, 2, 24, 64, false)

    set image primary
endfunc

' BoxBlur
' -------
function BoxBlur(img, rx, ry)
    rx = max(int(rx), 0); ry = max(int(ry), 0)
    set image img
    w = width(img); h = height(img)
    data = dim(w, h)

    ' Blur vertically
    for y = 0 to h - 1  for x = 0 to w - 1  data[x][y] = pixeli(img, x, y)
    count = ry*2 + 1
    for x = 0 to w - 1
        sr = 0; sg = 0; sb = 0; sa = 0
        for y = -ry to ry
            p = data[x][y%h];
            sr = sr + Red(p); sg = sg + Green(p); sb = sb + Blue(p); sa = sa + Alpha(p)
        next
        for y = 0 to h - 1
            set color sr/count, sg/count, sb/count, sa/count
            set pixel x, y
            p = data[x][(y - ry)%h]
            sr = sr - Red(p); sg = sg - Green(p); sb = sb - Blue(p); sa = sa - Alpha(p)
            p = data[x][(y + ry + 1)%h]
            sr = sr + Red(p); sg = sg + Green(p); sb = sb + Blue(p); sa = sa + Alpha(p)
        next
    next
    ' Blur horizontally.
    for y = 0 to h - 1  for x = 0 to w - 1  data[x][y] = pixeli(img, x, y)
    count = rx*2 + 1
    for y = 0 to h - 1
        sr = 0; sg = 0; sb = 0; sa = 0
        for x = -rx to rx
            p = data[x%w][y]
            sr = sr + Red(p); sg = sg + Green(p); sb = sb + Blue(p); sa = sa + Alpha(p)
        next
        for x = 0 to w - 1
            set color sr/count, sg/count, sb/count, sa/count
            set pixel x, y
            p = data[(x - rx)%w][y]
            sr = sr - Red(p); sg = sg - Green(p); sb = sb - Blue(p); sa = sa - Alpha(p)
            p = data[(x + rx + 1)%w][y]
            sr = sr + Red(p); sg = sg + Green(p); sb = sb + Blue(p); sa = sa + Alpha(p)
        next
    next
    set image primary

    ' Pixeli helpers.
    function Alpha(c); return int(c/16777216); endfunc
    function Red(c); return int((c/65536))%256; endfunc
    function Green(c); return int((c/256))%256; endfunc
    function Blue(c); return c%256; endfunc
endfunc

' Draw3DBorder
' ------------
function Draw3DBorder(x, y, w, h, thickness, lightAlpha, darkAlpha, invert)
    if thickness <= 0  return
    if invert
        light = 0
        dark = 255
    else
        light = 255
        dark = 0
    endif
    dal = lightAlpha/thickness
    dad = darkAlpha/thickness
    for i = 0 to thickness - 1
        set color light, light, light, lightAlpha
        draw line x + i, y + i, x + w - i - 1, y + i
        draw line x + i, y + i + 1, x + i, y + h - i - 1
        set color dark, dark, dark, darkAlpha
        draw line x + w - i - 1, y + i, x + w - i - 1, y + h - i - 1
        draw line x + w - i - 2, y + h - i - 1, x + i, y + h - i - 1
        lightAlpha = lightAlpha - dal
        darkAlpha = darkAlpha - dad
    next
endfunc

   

Edit: Here I create a big mesh for the entire maze and render it every frame. It might be faster to skip the mesh and just try to render the visible faces one by one instead, not sure - mesh rendering is pretty optimized.

[johnno56]

What! No aliens? Nah. Kidding. Very cool demo indeed! The makings of a 3D "top down" Dungeon Crawler...