-----------------------------------

zylum

Mon May 23, 2005 9:27 pm


[source] Maze Program in 100 Lines

-----------------------------------

ultrahex's maze program inspired me to make one aswell...

mine is a lot faster and more efficient, but his is more visually apealling.

%sets screen parameters
setscreen ("graphics:700;700,offscreenonly,nobuttonbar")

%define constants
const rows := 42
const cols := 42
const cellSize := 16

%declare variables:

/*
 travelled is a 2d array which keeps track of which squares have been visited when the maze is
 being generated. to ensure all spaces are accessible, each square MUST be visited once and
 only once. keys keeps track of which keys are being pressed. maze stores the image of the maze.
 px and py are the position of the dot. t is time.

 travelled starts at 0 and ends at cols+1/rows+1 because later on we will initialize these outter
 squares to true (travelled on) so when we check whether its possible to travel to a node outside
 the maze, we see the square has been travelled on and will return false. this makes it easier to
 handle boundaries rather than use a bunch of if statements

 adjMatrix stands for adjaceny matrix. this is a datastructure which allows you to check whether
 there is a path from one node of a grpah to another node. in this case the nodes are each square.
 how the adjacency matrix works is if there is a path between node i and node j, then adjMatrix(i,j)
 becomes true. otherwise its false. adjMatrix conserves direction so adjMatrix(i,j) might be true
 but adjMatrix(j,i) might be false. in the case of this maze, when we find that (i,j) is true, we
 automatically make (j,i) true aswell (so we can travel both ways). adjMatrix contains
 rows*cols x rows*cols elements because there are cols*rows nodes which can travel to rows*cols
 other nodes. for our purposes the most nodes that one node can be connected to is 4 (top, bottom,
 right and left). there is an algorithm called the floyd-warshal algorithm which checks whether node
 i can reach node j (anywhere on the graph). if we were to implement this algorithm and check whether
 any 2 nodes can be connected, it will always return true in our case because the algorithm which
 generates the maze will always produce a path to all other nodes. Since we referenc each node with
 the coordinate system (x,y) we need to find a way to assign a unique value (between 1 and cols*rows)
 for each node. this is simple done by multiplying the nodes current row minus 1 by how many nodes
 there are in a colomn (this value is equal to rows). then we add the current row the node is at.
 So to rephrase, the nodes address in adjMatrix will be (col-1)*rows+row. i use x instead of col
 and y instead of row.
 */

var adjMatrix : array 1 .. rows * cols, 1 .. rows * cols of boolean
var travelled : array 0 .. cols + 1, 0 .. rows + 1 of boolean
var keys : array char of boolean
var maze, px, py, t : int

%recursive procedure which generates a random maze
proc genMaze (x, y : int)
    %updates the travelled array
    travelled (x, y) := true
    %dir will store which directions we can travel in from our current position. there are at most
    %4 posibilities and and you can move in 2 different directions (up/down or left/right)
    var dir : array 1 .. 4, 1 .. 2 of int
    var n : int %the current number of routes the maze an go from the current location
    loop
        %loops until there are no more places to go
        n := 0
        %checks all direcionts (up, down, left, right)
        for i : -1 .. 1
            for j : -1 .. 1
                %not moving (0,0) is not valid, and moving in a diagonal is not valid.
                %if you move in a diagonal you x and y movements will sum to either 0 or they will
                %equal each other. they will also equal when both are 0. also, a move is invalid
                %when it goes to a square that has previously been travelled on.
                if i ~= j and i + j ~= 0 and ~travelled (x + i, y + j) then
                    %a move is found, increment n
                    n += 1
                    %add move to the array
                    dir (n, 1) := i
                    dir (n, 2) := j
                end if
            end for
        end for
        exit when n = 0
        %choose a random direction
        n := Rand.Int (1, n)
        %update the adjacency matrix to show that there is a path between nodes
        adjMatrix ((x - 1) * rows + y, (x - 1 + dir (n, 1)) * rows + (y + dir (n, 2))) := true
        adjMatrix ((x - 1 + dir (n, 1)) * rows + (y + dir (n, 2)), (x - 1) * rows + y) := true
        %move to the next node
        genMaze (x + dir (n, 1), y + dir (n, 2))
    end loop
end genMaze

%initializes all variables etc...
proc initialize
    put "Loading..."
    View.Update
    cls
    px := 1
    py := 1

    %since we can travel in both directions in our maze (able to backtrack) we only need
    %to use half of the nodes in our adjecency matrix. this makes loading times faster.
    %to ensure we check initialized values later on, we always check if there is a path from
    %a smaller indexed node to a higher indexed node (hence i : 1..rows*cols j : i .. rows*cols)
    for i : 1 .. rows * cols
        for j : i .. rows * cols
            %initializes all pathways to false
            adjMatrix (i, j) := false
        end for
    end for


    for i : 0 .. cols + 1
        for j : 0 .. rows + 1
            if i = 0 or j = 0 or i = cols + 1 or j = rows + 1 then
                %initializes out of bound squares to true (appear as though they were travelled on)
                travelled (i, j) := true
            else
                %all other square are false (yet to be travelled on)
                travelled (i, j) := false
            end if
        end for
    end for
    %generates the maze
    genMaze (Rand.Int (1, cols), Rand.Int (1, rows))
    %draws the maze
    %first checks all the pathways between squares which are adjacent vertically. if there is no path
    %then draw a horizontal wall. remember that we initialized the adjMatrix so that we only check
    %pathways from smaller indexed nodes to higher indexed nodes. therefore the min/max functions
    %seperate the 2 nodes accordingly.
    for i : 1 .. cols
        for j : 1 .. rows - 1
            if ~adjMatrix (min ((i - 1) * rows + j, (i - 1) * rows + j + 1), max ((i - 1) * rows + j, (i - 1) * rows + j + 1)) then
                drawline (i * cellSize, (j + 1) * cellSize, i * cellSize + cellSize, (j + 1) * cellSize, 7)
            end if
        end for
    end for
    %now check all pathways between squares which are adjacent horitontally. if there is no path then
    %draw a vertical wall
    for j : 1 .. rows
        for i : 1 .. cols - 1
            if ~adjMatrix (min ((i - 1) * rows + j, i * rows + j), max ((i - 1) * rows + j, i * rows + j)) then
                drawline ((i + 1) * cellSize, j * cellSize, (i + 1) * cellSize, j * cellSize + cellSize, 7)
            end if
        end for
    end for
    %draw outer walls
    drawbox (cellSize, cellSize, cols * cellSize + cellSize, rows * cellSize + cellSize, 7)
    %draw destination
    drawfilloval (cols * cellSize + cellSize div 2, rows * cellSize + cellSize div 2, cellSize div 2 - 2, cellSize div 2 - 2, green)
    %save the maze
    maze := Pic.New (cellSize, cellSize, cols * cellSize + cellSize, rows * cellSize + cellSize)
    cls
    t := Time.Elapsed
end initialize
initialize

loop
    %draws the maze
    Pic.Draw (maze, cellSize, cellSize, picCopy)
    %draws the current position of the user
    drawfilloval (cellSize * px + cellSize div 2, cellSize * py + cellSize div 2, cellSize div 2 - 2, cellSize div 2 - 2, brightred)
    View.Update
    exit when px = cols and py = rows
    Input.KeyDown (keys)
    if keys (KEY_LEFT_ARROW) then
        if px - 1 > 0 and adjMatrix (min ((px - 1) * rows + py, (px - 2) * rows + py), max ((px - 1) * rows + py, (px - 2) * rows + py)) then
            px -= 1
        end if
    elsif keys (KEY_RIGHT_ARROW) then
        if px + 1