Maze generation - Printable Version

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