[source] Maze Program in 100 Lines

[zylum]

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

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

code:

%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 <= cols and adjMatrix (min ((px - 1) * rows + py, px * rows + py), max ((px - 1) * rows + py, px * rows + py)) then             px += 1         end if     elsif keys (KEY_UP_ARROW) then         if py + 1 <= rows and adjMatrix (min ((px - 1) * rows + py, (px - 1) * rows + py + 1), max ((px - 1) * rows + py, (px - 1) * rows + py + 1)) then             py += 1         end if     elsif keys (KEY_DOWN_ARROW) then         if py - 1 > 0 and adjMatrix (min ((px - 1) * rows + py, (px - 1) * rows + py - 1), max ((px - 1) * rows + py, (px - 1) * rows + py - 1)) then             py -= 1         end if     end if     delay (75) end loop cls put "GOOD JOB!!!\nYou took ", (Time.Elapsed - t) / 1000, " seconds!!!" View.Update

[Delos]

zylum strikes again. Great work as usual.
I Believe! I Believe! It can be solved. w00t. 241 seconds. Now my eyes hurt.

Anyway, have some bits, and next time make the movement smoother.
+ bits.
Edit:
Wait...are you now a mod? Or are those 1000 bits just coincidence? We'll see...

[zylum]

ofcourse it can be solved, what would be the point if it couldnt? wait a second... this gives me an idea...

[Bacchus]

wow really nice, but yes my eyes now hurt lol. 150.299 seconds lol, cmon Delos, you can do it faster! +bits

[RaPsCaLLioN]

110.566. Very nice. However.. It basically created a path for me to the end. At no point did it give me extended forked pathways. When it did I could see that one option always ended immediately so the decision was obvious.
So it could be a bit more difficult. I'm now going to beat it in under 100 secs.

[Cervantes]

Nice stuff, zylum.
87 seconds, first try. Like rapscallion, I didn't get very many alternatives. In fact, I think I only got one real alternative that actually lead somewhere (there were many that go for a few squares, but not much more than that). I happened to make the right guess on that one real alternative that I did get.
Does this work such that there is only one possible path to get there (without retracing, that is)?

[zylum]

yeah. there is always exactly 1 route from any square to any other square and all squares are reachable... i also noticed that the generated mazes are easy, but i dont know why...

what my algorithm does is it starts at (1,1) and then makes a random path (only going to squares that have not been travelled on yet) untill it cannot travel anymore (no unoccupied squares to move to). once the current path ends, then it traces back untill it finds a square which can have a path branch from it.

any ideas on how to make it harder?

[Delos]

Well, if any two squares can be reached by some path, how about you alter the goal a bit. Randomly choose two squares on the board and set the aim to be to get from one to the other. You can work on the logistics of making sure they're not too close.
Also, you could start your creation of the maze from somewhere other than a corner. Or, if your recurssion would allow it, at more than one point. The only problem here is ensuring that the two mazes connect...but you could figure that out....

[zylum]

starting from a random location was a good idea... i updated the source and now its a *bit* harder... the idea i have is that instead of backtracking to the first square which has a path, i have an array of squares which still have a path and then randomly choose one to fork from.. the maze will be finished generating when there are no more paths to fork from. i'll try implementing it later tonight. if anybody else wants to try this algorithm with my source, go right ahead

[Delos]

zylum wrote:

Turing:

px := 1  py := 1

Did you really update that? Or did you mean you only updated on your computer and left us here w/ the old source?

[zylum]

px and py refer to the starting position of the dot...

im my initialize method, i call genMaze like so: genMaze (Rand.Int (1, cols), Rand.Int (1, rows))

it used to be: genMaze(1,1)

so ya, it's updated

[jamonathin]

Amazing job. I still cannot figure out how you make it so that there's never an area blocked off, and that you will always reach the end eventually, but I'll just keep lookin it over. I have a dumb question though, why is there a ~ before adjMatrix, is that because you want to make sure its false? Also can you comment your code, that'd help too

Anyways, good job, well done.

<cough> 73.432 seconds <cough>

+ 57 Bits

[Delos]

It's all about recursion. If you check his fcn out, it's set up so that every box connects to at least one other box. So, since no routes are completely blocked off, every square is accessible.
Also, I think zylum is admin of sorts now...bits don't mean anything to him...

[jamonathin]

Delos wrote:

It's all about recursion. If you check his fcn out, it's set up so that every box connects to at least one other box. So, since no routes are completely blocked off, every square is accessible.

Ok that makes sense, I took another look and I can see it now

Delos wrote:

Also, I think zylum is admin of sorts now...bits don't mean anything to him...

I was thinking that before I did that, because he was exactly at 1000, but then I thought about it and he was just in the 900's, so I said meh and gave him it anyways, and now hes at 1057.

[Delos]

He's at 1057 now, but wait till he posts again...perhaps the zylum himself could clear up this uncertainty...