Maze generation
Generate and show a maze, using the simple Depth-first search algorithm.
- Start at a random cell.
- Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
- If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.
You are encouraged to solve this task according to the task description, using any language you may know.
This page uses content from Wikipedia. The original article was at Maze generation algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
See also Maze solving.
Ada
mazes.ads: <lang Ada>generic
Height : Positive; Width : Positive;
package Mazes is
type Maze_Grid is private;
procedure Initialize (Maze : in out Maze_Grid);
procedure Put (Item : Maze_Grid);
private
type Directions is (North, South, West, East);
type Cell_Walls is array (Directions) of Boolean; type Cells is record Walls : Cell_Walls := (others => True); Visited : Boolean := False; end record;
subtype Height_Type is Positive range 1 .. Height; subtype Width_Type is Positive range 1 .. Width;
type Maze_Grid is array (Height_Type, Width_Type) of Cells;
end Mazes;</lang>
mazes.adb: <lang Ada>with Ada.Numerics.Discrete_Random; with Ada.Text_IO;
package body Mazes is
package RNG is new Ada.Numerics.Discrete_Random (Positive); package Random_Direction is new Ada.Numerics.Discrete_Random (Directions);
Generator : RNG.Generator; Dir_Generator : Random_Direction.Generator;
function "-" (Dir : Directions) return Directions;
procedure Depth_First_Algorithm (Maze : in out Maze_Grid; Row : Height_Type; Column : Width_Type);
function Has_Unvisited_Neighbours (Maze : Maze_Grid; Row : Height_Type; Column : Width_Type) return Boolean;
procedure Move (Row : in out Height_Type; Column : in out Width_Type; Direction : Directions; Valid_Move : out Boolean);
function "-" (Dir : Directions) return Directions is begin case Dir is when North => return South; when South => return North; when East => return West; when West => return East; end case; end "-";
procedure Depth_First_Algorithm (Maze : in out Maze_Grid; Row : Height_Type; Column : Width_Type) is Next_Row : Height_Type; Next_Column : Width_Type; Next_Direction : Directions; Valid_Direction : Boolean; begin -- mark as visited Maze (Row, Column).Visited := True; -- continue as long as there are unvisited neighbours left while Has_Unvisited_Neighbours (Maze, Row, Column) loop -- use random direction Next_Direction := Random_Direction.Random (Dir_Generator); Next_Row := Row; Next_Column := Column; Move (Next_Row, Next_Column, Next_Direction, Valid_Direction); if Valid_Direction then -- connect the two cells if not Maze (Next_Row, Next_Column).Visited then Maze (Row, Column).Walls (Next_Direction) := False; Maze (Next_Row, Next_Column).Walls (-Next_Direction) := False; Depth_First_Algorithm (Maze, Next_Row, Next_Column); end if; end if; end loop; end Depth_First_Algorithm;
function Has_Unvisited_Neighbours (Maze : Maze_Grid; Row : Height_Type; Column : Width_Type) return Boolean is Neighbour_Row : Height_Type; Neighbour_Column : Width_Type; Is_Valid : Boolean; begin for Dir in Directions loop Neighbour_Row := Row; Neighbour_Column := Column; Move (Row => Neighbour_Row, Column => Neighbour_Column, Direction => Dir, Valid_Move => Is_Valid); if Is_Valid and then not Maze (Neighbour_Row, Neighbour_Column).Visited then return True; end if; end loop; return False; end Has_Unvisited_Neighbours;
procedure Initialize (Maze : in out Maze_Grid) is Row, Column : Positive; begin -- initialize random generators RNG.Reset (Generator); Random_Direction.Reset (Dir_Generator); -- choose starting cell Row := RNG.Random (Generator) mod Height + 1; Column := RNG.Random (Generator) mod Width + 1; Ada.Text_IO.Put_Line ("Starting generation at " & Positive'Image (Row) & " x" & Positive'Image (Column)); Depth_First_Algorithm (Maze, Row, Column); end Initialize;
procedure Move (Row : in out Height_Type; Column : in out Width_Type; Direction : Directions; Valid_Move : out Boolean) is begin Valid_Move := False; case Direction is when North => if Row > Height_Type'First then Valid_Move := True; Row := Row - 1; end if; when East => if Column < Width_Type'Last then Valid_Move := True; Column := Column + 1; end if; when West => if Column > Width_Type'First then Valid_Move := True; Column := Column - 1; end if; when South => if Row < Height_Type'Last then Valid_Move := True; Row := Row + 1; end if; end case; end Move;
procedure Put (Item : Maze_Grid) is begin for Row in Item'Range (1) loop if Row = Item'First (1) then for Col in Item'Range (2) loop if Col = Item'First (2) then Ada.Text_IO.Put ('+'); end if; if Item (Row, Col).Walls (North) then Ada.Text_IO.Put ("---"); else Ada.Text_IO.Put (" "); end if; Ada.Text_IO.Put ('+'); end loop; Ada.Text_IO.New_Line; end if; for Col in Item'Range (2) loop if Col = Item'First (2) then if Item (Row, Col).Walls (West) then Ada.Text_IO.Put ('|'); else Ada.Text_IO.Put (' '); end if; elsif Item (Row, Col).Walls (West) and then Item (Row, Col - 1).Walls (East) then Ada.Text_IO.Put ('|'); elsif Item (Row, Col).Walls (West) or else Item (Row, Col - 1).Walls (East) then Ada.Text_IO.Put ('>'); else Ada.Text_IO.Put (' '); end if; if Item (Row, Col).Visited then Ada.Text_IO.Put (" "); else Ada.Text_IO.Put ("???"); end if; if Col = Item'Last (2) then if Item (Row, Col).Walls (East) then Ada.Text_IO.Put ('|'); else Ada.Text_IO.Put (' '); end if; end if; end loop; Ada.Text_IO.New_Line; for Col in Item'Range (2) loop --for Col in Item'Range (2) loop if Col = Item'First (2) then Ada.Text_IO.Put ('+'); end if; if Item (Row, Col).Walls (South) then Ada.Text_IO.Put ("---"); else Ada.Text_IO.Put (" "); end if; Ada.Text_IO.Put ('+'); --end loop; end loop; Ada.Text_IO.New_Line; end loop; end Put;
end Mazes;</lang>
Example main.adb: <lang Ada>with Mazes; procedure Main is
package Small_Mazes is new Mazes (Height => 8, Width => 11); My_Maze : Small_Mazes.Maze_Grid;
begin
Small_Mazes.Initialize (My_Maze); Small_Mazes.Put (My_Maze);
end Main;</lang>
Output:
Starting generation at 3 x 7 +---+---+---+---+---+---+---+---+---+---+---+ | | | | | + + + +---+ + + +---+---+---+ + | | | | | | | + +---+---+ +---+---+ + + + +---+ | | | | | | | | + +---+---+---+---+ +---+ + + + + | | | | | | | + + +---+ + + + +---+---+---+ + | | | | | | | + + +---+---+---+---+---+ +---+ + + | | | | | | +---+ + +---+---+---+ +---+---+---+ + | | | | | + +---+ +---+---+ +---+---+---+---+---+ | | +---+---+---+---+---+---+---+---+---+---+---+
C
Generation/solver in one. Requires UTF8 locale and unicode capable console. If your console font line-drawing chars are single width, define DOUBLE_SPACE to 0. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <locale.h>
- define DOUBLE_SPACE 1
typedef unsigned char cell; enum { U = 1, D = 2, L = 4, R = 8, V = 16 };
wchar_t glyph[] = L" │││─┘┐┤─└┌├─┴┬┼ ┆┆┆┄╯╮ ┄╰╭ ┄";
int irand(int n) { int r, rand_max = RAND_MAX - (RAND_MAX % n); while ((r = rand()) >= rand_max); return r / (rand_max/n); }
- define FOR(i, h) for(i = 0; i <= h; i++)
cell **grid(int w, int h) { int i, j; cell **x = malloc(sizeof(cell*) * h + h * w); x[0] = (cell*)(x + h); FOR(i, h-1) x[i+1] = x[i] + w; FOR(i, h-1) FOR(j, w-1) x[i][j] = 0; return x; }
int rand_neighbor(cell **c, int w, int h, int x, int y, int *x2, int *y2) { int d, ofx[] = {1, -1, 0, 0}, ofy[] = {0, 0, -1, 1}; int i, j, cnt = 0; FOR(d, 3) { j = x + ofx[d], i = y + ofy[d]; if (j < 0 || j >= w || i < 0 || i >= h || (c[i][j] & V)) continue; if (!irand(++cnt)) *x2 = j, *y2 = i; } return cnt; }
int build(cell **c, int w, int h, int x, int y, int avail) { int x2, y2; c[y][x] |= V;
while (avail) { if (!rand_neighbor(c, w, h, x, y, &x2, &y2)) break; if (x2 > x) c[y][x] |= R, c[y][x2] |= L; else if (x2 < x) c[y][x] |= L, c[y][x2] |= R; else if (y2 > y) c[y][x] |= D, c[y2][x] |= U; else if (y2 < y) c[y][x] |= U, c[y2][x] |= D;
avail = build(c, w, h, x2, y2, avail - 1); }
return avail; }
cell** make_maze(int w, int h) { cell **cells = grid(w, h); build(cells, w, h, 0, 0, w * h - 1); return cells; }
int walk(cell **c, cell **s, int w, int h, int x, int y, int x2, int y2) { int i, j, d, dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
s[y][x] = V; if (y == y2 && x == x2) return 1;
FOR(d, 3) { if (!(c[y][x] & (1 << d))) continue; i = y + dirs[d][1]; j = x + dirs[d][0];
if (i < 0 || i >= h || j < 0 || j >= w) continue; if (s[i][j] & V) continue;
if (walk(c, s, w, h, j, i, x2, y2)) break; }
if (d <= 3) { s[y][x] |= (1 << d); if (d <= 1) s[i][j] |= 1 << (1 - d); else s[i][j] |= 1 << (5 - d); return 1; } return 0; }
void show_maze(cell **c, cell **s, int w, int h) { int i, j, x, y; cell **tile = grid(2*w + 1, 2*h + 1);
FOR(i, 2*h) FOR(j, 2*w) tile[i][j] = ((j&1) ? 0 : (U|D)) | ((i&1) ? 0 : (L|R));
FOR(i, 2*h) tile[i][0] &= ~L, tile[i][2*w] &= ~R; FOR(j, 2*w) tile[0][j] &= ~U, tile[2*h][j] &= ~D;
FOR(i, h-1) FOR(j, w-1) { y = 2 * i + 1, x = 2 * j + 1;
if (c[i][j] & R) { tile[y-1][x+1] &= ~D; tile[ y ][x+1] = 0; tile[y+1][x+1] &= ~U; } if (c[i][j] & D) { tile[y+1][x-1] &= ~R; tile[y+1][ x ] = 0; tile[y+1][x+1] &= ~L; } if(!s) continue;
tile[y][x] = s[i][j]; if (s[i][j] & U) tile[y-1][ x ] |= V|D; if (s[i][j] & D) tile[y+1][ x ] |= V|U; if (s[i][j] & L) tile[ y ][x-1] |= V|R; if (s[i][j] & R) tile[ y ][x+1] |= V|L; }
FOR(i, 2*h) { FOR(j, 2*w) printf((tile[i][j] & V) ? "\033[31m%lc\033[m" : "%lc", glyph[ tile[i][j] ]); putchar('\n'); } free(tile); }
int main(int c, char *v[]) { cell **solu, **maze; int w = 0, h = 0;
setlocale(LC_CTYPE, ""); if (!DOUBLE_SPACE) glyph[0] = glyph[16] = L' ';
if (c > 2) w = atoi(v[1]), h = atoi(v[2]); if (w <= 0) w = 16; if (h <= 0) h = 8;
maze = make_maze(w, h); solu = grid(w, h); walk(maze, solu, w, h, 0, 0, w-1, h-1); show_maze(maze, solu, w, h); /* free(maze); free(solu); */ return 0; }</lang>output<lang>┌─┬───────┬───────┬─────────────┐ │┆│╭┄┄┄┄┄╮│ │ │ │┆│┆────┐┆└───┐ │ │ ┌───┐ ──────┤ │┆│╰┄┄┄╮│╰┄┄┄╮│ │ │ │ │ │ │┆└─┐ │┆└───┐┆└─┤ │ │ │ └─────┐ │ │╰┄╮│ │╰┄┄┄╮│╰┄╮│ │ │ │ │ │ ├─┐┆│ └─┬──┆├─┐┆│ │ │ │ │ ┌───┤ │ │ │┆│ │╭┄╯│ │┆│ │ │ │ │╭┄╮│ │ │ │┆├── │┆──┤ │┆│ ──┴─┘ ├─┘┆│┆│ │ │ │┆│ │╰┄╮│╭┄╯│ │╭┄╯│╰┄╮│ │ │┆└─┬─┴──┆│┆┌─┴───┬───┘┆┌─┴──┆│ │ │╰┄╮│╭┄┄┄╯│┆│ ╭┄╮│╭┄┄┄╯│╭┄┄┄╯│ │ └─┐┆│┆┌───┤┆└─┐┆│┆│┆────┤┆┌───┤ │ │╰┄╯│ │╰┄╮│┆│┆│╰┄┄┄╮│┆│ │ │ │ └───┘ │ └──┆│┆│┆└────┆│┆└── │ │ │ │ ╰┄╯│╰┄┄┄┄┄╯│╰┄┄┄┄│ └─┴───────┴───────┴───────┴─────┘</lang>
D
<lang d>import std.stdio,std.random,std.algorithm,std.array,std.typecons;
void main() {
enum int W = 11, H = 8; auto hWalls = new bool[][](W, H), vWalls = new bool[][](W, H), seen = new bool[][](W, H); alias Tuple!(uint,"x", uint,"y") P;
void visit(int x, int y) { seen[x][y] = true; P[] D = [P(x-1,y), P(x+1,y), P(x,y-1), P(x,y+1)]; P[] ns = array(filter!((P p){ return p.x<W && p.y<H; })(D)); while (ns.length) { P n = ns[uniform(0, ns.length)]; if (!seen[n.x][n.y]) { if (x != n.x) hWalls[min(x, n.x)][y] = true; else vWalls[x][min(y, n.y)] = true; visit(n.tupleof); } ns = array(filter!((x){ return x != n; })(ns)); } } visit(uniform(0, W), uniform(0, H));
writeln("+", "--+".replicate(W)); foreach (y; 0 .. H) { string s = "|"; foreach (x; 0 .. W) s ~= hWalls[x][y] ? " " : " |"; s ~= "\n+"; foreach (x; 0 .. W) s ~= vWalls[x][y] ? " +" : "--+"; writeln(s); }
}</lang> Output example:
+--+--+--+--+--+--+--+--+--+--+--+ | | | | | + + + + + +--+--+ + + + + | | | | | | | | | | + +--+ +--+--+ + +--+ + + + | | | | | | | + +--+--+--+--+ +--+ + + +--+ | | | | | | + + + + +--+--+--+--+--+--+ + | | | | | | +--+--+ + +--+--+ + + + + + | | | | | | | | | + + + +--+ +--+--+ + + +--+ | | | | | | | | + +--+--+ +--+ +--+--+--+ + + | | | +--+--+--+--+--+--+--+--+--+--+--+
Alternative version
See Maze_solving#D
F#
Using mutable state in the form of 2D arrays: <lang fsharp>let rnd : int -> int =
let gen = new System.Random() fun max -> gen.Next(max)
// randomly choose an element of a list let choose (xs:_ list) = xs.[rnd xs.Length]
type Maze(width, height) =
// (x,y) -> have we been here before? let visited = Array2D.create width height false // (x,y) -> is there a wall between (x,y) and (x+1,y)? let horizWalls = Array2D.create width height true // (x,y) -> is there a wall between (x,y) and (x,y+1)? let vertWalls = Array2D.create width height true let isLegalPoint (x,y) = x >= 0 && x < width && y >= 0 && y < height let neighbours (x,y) = [(x-1,y);(x+1,y);(x,y-1);(x,y+1)] |> List.filter isLegalPoint let removeWallBetween (x1,y1) (x2,y2) = if x1 <> x2 then horizWalls.[min x1 x2, y1] <- false else vertWalls.[x1, min y1 y2] <- false let rec visit (x,y as p) = let rec loop ns = let (nx,ny) as n = choose ns if not visited.[nx,ny] then removeWallBetween p n visit n match List.filter ((<>) n) ns with | [] -> () | others -> loop others
visited.[x,y] <- true loop (neighbours p)
do visit (rnd width, rnd height)
member x.Print() = ("+" + (String.replicate width "-+")) :: [for y in 0..(height-1) do yield "\n|" for x in 0..(width-1) do yield if horizWalls.[x,y] then " |" else " " yield "\n+" for x in 0..(width-1) do yield if vertWalls.[x,y] then "-+" else " +" ] |> String.concat "" |> printfn "%s"
let m = new Maze(10,10) m.Print()</lang> Output example:
+-+-+-+-+-+-+-+-+-+-+ | | | | + +-+-+-+-+ +-+ + + + | | | | | | + +-+-+ + +-+-+ +-+ + | | | | | +-+ +-+ +-+-+ +-+-+ + | | | | | + +-+ +-+ +-+-+-+ +-+ | | | | | | + + +-+ +-+ +-+ +-+ + | | | | | | | | + + +-+ + +-+-+-+ + + | | | | | +-+ + +-+-+-+-+-+-+ + | | | | | + +-+-+ +-+ +-+-+ + + | | | | | | + +-+ +-+ +-+-+ +-+-+ | | | +-+-+-+-+-+-+-+-+-+-+
Haskell
<lang haskell>import Control.Monad import Control.Monad.ST import Data.Array import Data.Array.ST import Data.STRef import System.Random
rand :: Random a => (a, a) -> STRef s StdGen -> ST s a rand range gen = do
(a, g) <- liftM (randomR range) $ readSTRef gen gen `writeSTRef` g return a
data Maze = Maze {rightWalls, belowWalls :: Array (Int, Int) Bool}
maze :: Int -> Int -> StdGen -> ST s Maze maze width height gen = do
visited <- mazeArray False rWalls <- mazeArray True bWalls <- mazeArray True gen <- newSTRef gen liftM2 (,) (rand (0, maxX) gen) (rand (0, maxY) gen) >>= visit gen visited rWalls bWalls liftM2 Maze (freeze rWalls) (freeze bWalls) where visit gen visited rWalls bWalls here = do writeArray visited here True let ns = neighbors here i <- rand (0, length ns - 1) gen forM_ (ns !! i : take i ns ++ drop (i + 1) ns) $ \there -> do seen <- readArray visited there unless seen $ do removeWall here there visit gen visited rWalls bWalls there where removeWall (x1, y1) (x2, y2) = writeArray (if x1 == x2 then bWalls else rWalls) (min x1 x2, min y1 y2) False
neighbors (x, y) = (if x == 0 then [] else [(x - 1, y )]) ++ (if x == maxX then [] else [(x + 1, y )]) ++ (if y == 0 then [] else [(x, y - 1)]) ++ (if y == maxY then [] else [(x, y + 1)])
maxX = width - 1 maxY = height - 1
mazeArray = newArray ((0, 0), (maxX, maxY)) :: Bool -> ST s (STArray s (Int, Int) Bool)
printMaze :: Maze -> IO () printMaze (Maze rWalls bWalls) = do
putStrLn $ '+' : (concat $ replicate (maxX + 1) "---+") forM_ [0 .. maxY] $ \y -> do putStr "|" forM_ [0 .. maxX] $ \x -> do putStr " " putStr $ if rWalls ! (x, y) then "|" else " " putStrLn "" forM_ [0 .. maxX] $ \x -> do putStr "+" putStr $ if bWalls ! (x, y) then "---" else " " putStrLn "+" where maxX = fst (snd $ bounds rWalls) maxY = snd (snd $ bounds rWalls)
main = getStdGen >>= stToIO . maze 11 8 >>= printMaze</lang>
Sample output:
+---+---+---+---+---+---+---+---+---+---+---+ | | | + +---+---+---+ +---+---+---+---+---+ + | | | | | | + +---+---+ +---+---+ + + + + + | | | | | | | | + + + +---+---+---+---+ +---+ + + | | | | | | +---+---+ + +---+---+---+---+ +---+---+ | | | | | | + + + + +---+---+---+ +---+ + + | | | | | | | + +---+---+ + +---+---+---+ +---+ + | | | | | + +---+---+---+---+ + +---+---+ + + | | | | +---+---+---+---+---+---+---+---+---+---+---+
J
This algorithm allows almost no parallelism. So, while it might be "simple", generating very large mazes this way will not be necessarily efficient to implement on future (highly parallel) systems. That said, perhaps mazes with millions of cells are not very likely to be needed to be generated quickly.
Anyways, based on the picolisp implementation, except without any relevant grid support:
<lang j>maze=:4 :0
assert.0<:n=.<:x*y horiz=. 0$~x,y-1 verti=. 0$~(x-1),y path=.,:here=. ?x,y unvisited=.0 (<here+1)} 0,0,~|:0,0,~1$~y,x while.n do. neighbors=. here+"1 (,-)=0 1 neighbors=. neighbors #~ (<"1 neighbors+1) {unvisited if.#neighbors do. n=.n-1 next=. ({~ ?@#) neighbors unvisited=.0 (<next+1)} unvisited if.{.next=here do. horiz=.1 (<-:here+next-0 1)} horiz else. verti=. 1 (<-:here+next-1 0)} verti end. path=.path,here=.next else. here=.{:path path=.}:path end. end. horiz;verti
)
display=:3 :0
size=. >.&$&>/y text=. (}:1 3$~2*1+{:size)#"1":size$<' ' 'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y ' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text
)</lang>
The result of maze
is a pair of arrays: one for open "doors" in the horizontal direction and the other for open "doors" in the vertical direction. The entry and exit doors are not represented by maze
-- they are implicitly defined and are implemented in display
.
Example use (with ascii box drawing enabled):
<lang j> display 8 maze 11 + +---+---+---+---+---+---+---+---+---+---+ | | | | | + + + + +---+ + +---+---+ + + | | | | | | | | + +---+---+ + +---+---+---+ + + + | | | | | | | +---+ +---+ + + +---+ + +---+---+ | | | | | | | + + +---+---+ +---+ + +---+---+ + | | | | | | | | | + +---+ + + + + +---+---+ + + | | | | | + +---+---+---+---+---+---+---+ +---+ + | | | | | | | | | + + + + + + + + +---+ + + | | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>
JavaScript
<lang javascript>function maze(x,y) { var n=x*y-1; if (n<0) {alert("illegal maze dimensions");return;} var horiz=[]; for (var j= 0; j<x+1; j++) horiz[j]= []; var verti=[]; for (var j= 0; j<x+1; j++) verti[j]= []; var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)]; var path= [here]; var unvisited= []; for (var j= 0; j<x+2; j++) { unvisited[j]= []; for (var k= 0; k<y+1; k++) unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1)); } while (0<n) { var potential= [[here[0]+1, here[1]], [here[0],here[1]+1], [here[0]-1, here[1]], [here[0],here[1]-1]]; var neighbors= []; for (var j= 0; j < 4; j++) if (unvisited[potential[j][0]+1][potential[j][1]+1]) neighbors.push(potential[j]); if (neighbors.length) { n= n-1; next= neighbors[Math.floor(Math.random()*neighbors.length)]; unvisited[next[0]+1][next[1]+1]= false; if (next[0] == here[0]) horiz[next[0]][(next[1]+here[1]-1)/2]= true; else verti[(next[0]+here[0]-1)/2][next[1]]= true; path.push(here= next); } else here= path.pop(); } return ({x: x, y: y, horiz: horiz, verti: verti}); }
function display(m) {
var text= [];
for (var j= 0; j<m.x*2+1; j++) {
var line= [];
if (0 == j%2)
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
line[k]= '+';
else
if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
line[k]= ' ';
else
line[k]= '-';
else
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
if (k>0 && m.horiz[(j-1)/2][k/4-1])
line[k]= ' ';
else
line[k]= '|';
else
line[k]= ' ';
if (0 == j) line[1]= line[2]= line[3]= ' ';
if (m.x*2-1 == j) line[4*m.y]= ' ';
text.push(line.join()+'\r\n');
}
return text.join();
}</lang>
Variable meanings in function maze
:
x
,y
-- dimensions of mazen
-- number of openings to be generatedhoriz
-- two dimensional array of locations of horizontal openings (true means wall is open)verti
-- two dimensional array of locations of vertical openings (true means wall is open)here
-- current location under considerationpath
-- history (stack) of locations that might need to be revisitedunvisited
-- two dimensional array of locations that have not been visited, padded to avoid need for boundary tests (true means location needs to be visited)potential
-- locations adjacent tohere
neighbors
-- unvisited locations adjacent tohere
Variable meanings in function display
:
m
-- maze to be drawntext
-- lines of text representing mazeline
-- characters of current line
Note that this implementation relies on javascript arrays being treatable as infinite in size with false (null) values springing into existence as needed, to support referenced array locations. (This significantly reduces the bulk of the necessary initialization code.)
Example use:
<lang html><html><head><title></title></head><body>
</body></html>
<script type="text/javascript"> /* ABOVE CODE GOES HERE */ document.getElementById('out').innerHTML= display(maze(8,11)); </script></lang>
produced:
<lang>+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ + +---+ + +---+---+ + + | | | | | | | | + + + +---+ +---+ +---+---+ + + | | | | | | | + +---+ +---+---+---+---+---+ + + + | | | | | | +---+ +---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+---+---+---+---+ + + + | | | | | | + +---+---+ +---+---+ + +---+---+ + | | | | | | | + + + +---+ +---+---+ + + +---+ | | | | +---+---+---+---+---+---+---+---+---+---+---+</lang>
For an animated presentation of the progress of this maze creation process, you can use display
in each iteration of the main loop. You would also need to take steps to make sure you could see each intermediate result.
For example, change replace the line while (0<n) {
with:
<lang javascript> function step() { if (0<n) {</lang>
And replace the closing brace for this while loop with:
<lang javascript> document.getElementById('out').innerHTML= display({x: x, y: y, horiz: horiz, verti: verti, here: here}); setTimeout(step, 100); } } step();</lang>
To better see the progress, you might want a marker in place, showing the position being considered. To do that, replace the line which reads if (0 == k%4) {
with
<lang javascript> if (m.here && m.here[0]*2+1 == j && m.here[1]*4+2 == k) line[k]= '#' else if (0 == k%4) {</lang>
Note however that this leaves the final '#' in place on maze completion, and that the function maze
no longer returns a result which represents a generated maze.
Note also that this display suggests an optimization. You can replace the line reading path.push(here= next);
with:
<lang javascript> here= next; if (1 < neighbors.length) path.push(here);</lang>
And this does indeed save a negligible bit of processing, but the maze algorithm will still be forced to backtrack through a number of locations which have no unvisited neighbors.
Perl 5
Tested on Perl 5.8, but should work on any Perl5 installation on most platforms.
This implementation observes that due to the grid formation of the maze, reflection can be used to simplify the algorithm. Walls are only removed on the East (right) and South (bottom) walls (if those walls are not part of the maze boundary).
<lang perl5>use strict;
my $dimension = $ARGV[0] || 7; my $maze = init_maze($dimension, $dimension);
my ($startRow, $startCol) = (int(rand($dimension)), int(rand($dimension))); make_maze($maze, $startRow, $startCol, undef);
print_maze($maze);
- ---Subs---
sub init_maze {
my ($max_row, $max_col) = @_;
my $maze = []; for (my $r=0; $r < $max_row; $r++) { for (my $c=0; $c < $max_col; $c++) { push @{$maze->[$r]}, {'visited' => 0,
'bottom' => 1,
'right' => 1, }; } } return $maze;
}
sub make_maze {
my ($maze, $row, $col) = @_;
$maze->[$row]->[$col]->{'visited'} = 1;
while (my $unvisited = get_unvisited($maze, $row, $col)) { last unless @$unvisited;
# Randomly select a neighbor my $choice = $unvisited->[ rand(@$unvisited) ];
# Knock down the wall between them remove_wall($maze, [$row, $col], $choice);
# move to this new cell make_maze($maze, $choice->[0], $choice->[1]); }
}
sub remove_wall {
my ($maze, $r1, $r2) = @_; my $selected;
if ( $r1->[0] == $r2->[0] ) { # Rows are equal, must be East/West neighbors $selected = ($r1->[1] < $r2->[1]) ? $r1 : $r2; $maze->[ $selected->[0] ]->[ $selected->[1] ]->{'right'} = 0;
} elsif ( $r1->[1] == $r2->[1] ) { # Columns are the same, must be North/South neighbors $selected = ($r1->[0] < $r2->[0]) ? $r1 : $r2; $maze->[ $selected->[0] ]->[ $selected->[1] ]->{'bottom'} = 0; } else { die("ERROR: bad neighbors ($r1->[0], $r1->[1]) and ($r2->[0], $r2->[1])\n"); } return;
}
sub get_unvisited {
my ($maze, $row, $col) = @_; my @found;
# look for neighbors in cardinal directions; # be mindful of maze boundaries if ($row == 0) { push @found, [$row + 1, $col] unless $maze->[$row + 1]->[$col]{'visited'}; } elsif ($row == @$maze - 1) { push @found, [$row - 1, $col] unless $maze->[$row - 1]->[$col]->{'visited'}; } else { if ($row + 1 < @$maze) { push @found, [$row + 1, $col] unless $maze->[$row + 1]->[$col]->{'visited'}; } push @found, [$row - 1, $col] unless $maze->[$row - 1]->[$col]->{'visited'}; }
if ($col == 0) { push @found, [$row, $col + 1] unless $maze->[$row]->[$col + 1]->{'visited'}; } elsif ($col == (@{$maze->[0]} - 1)) { push @found, [$row, $col - 1] unless $maze->[$row]->[$col - 1]->{'visited'}; } else { if ($col + 1 < @{$maze->[0]}) { push @found, [$row, $col + 1] unless $maze->[$row]->[$col + 1]->{'visited'}; } push @found, [$row, $col - 1] unless $maze->[$row]->[$col - 1]->{'visited'}; }
return \@found;
}
sub print_maze {
my ($maze) = @_; my $screen = [];
my $screen_row = 0; for (my $r=0; $r < @$maze; $r++) { if ($r == 0) { # Top border push @{$screen->[$r]}, '+'; for (@{$maze->[0]}) {
push @{$screen->[$r]}, '--', '+';
} }
for (my $c=0; $c < @{$maze->[0]}; $c++) { my @middle; if ($c == 0) {
push @middle, "|";
}
push @middle, " "; # room center if ($maze->[$r]->[$c]->{'right'}) {
push @middle, "|";
} else {
push @middle, " ";
} push @{$screen->[$screen_row + 1]}, @middle;
my @bottom; if ($c == 0) {
push @bottom, "+";
}
if ($maze->[$r]->[$c]->{'bottom'}) {
push @bottom, "--";
} else {
push @bottom, " ";
} push @bottom, "+"; push @{$screen->[$screen_row + 2]}, @bottom; } $screen_row += 2; }
for (my $r=0; $r < @$screen; $r++) { for (my $c=0; $c < @{$screen->[0]}; $c++) { print $screen->[$r]->[$c]; } print "\n"; } print "\n";
}
</lang>
Sample output (7x7):
+--+--+--+--+--+--+--+ | | | + +--+ + +--+--+ + | | | | | +--+ +--+--+--+ + + | | | | | + +--+ + +--+ + + | | | | | + + +--+--+ +--+--+ | | | | + +--+--+ +--+--+ + | | | | +--+ + +--+ + + + | | | | | +--+--+--+--+--+--+--+
Perl 6
Works with Rakudo 2011.01
Supply a width and height and optionally the x,y grid coords for the starting cell. If no starting cell is supplied, a random one will be selected automatically. 0,0 is the top left corner.
<lang perl6>display( gen_maze( 11, 8 ) );
sub gen_maze ( $x_size,
$y_size, $start_x = (^$x_size).pick, $start_y = (^$y_size).pick )
{
my %walls; my @maze; for ^$y_size -> $x { @maze[$x] = [ 1 xx $x_size]; %walls{'y'}[$x] = ['|' xx $x_size]; %walls{'x'}[$x] = ['---' xx $x_size]; } my @stack; my @current = $start_y, $start_x; loop { if my @next = get_unvisited_neighbors( @maze, @current ) { @stack.push: [@current]; move( @maze, @next, @current, %walls ); @current := @next; } else { last unless @stack; @current := @stack.pop; } } return %walls;
}
sub get_unvisited_neighbors(@maze, @current) {
my ($x, $y) = @current; my @neighbors; @neighbors.push([ $x-1, $y ]) if $x > 0 and @maze[$x-1][$y]; @neighbors.push([ $x+1, $y ]) if $x < @maze and @maze[$x+1][$y]; @neighbors.push([ $x, $y-1 ]) if $y > 0 and @maze[$x][$y-1]; @neighbors.push([ $x, $y+1 ]) if $y < @maze[0] and @maze[$x][$y+1]; return |@neighbors.roll(1) if @neighbors;
}
sub move ($maze, $next, $current, $walls) {
$maze[$next[0]][$next[1]] = 0; given () { when $next[0] < $current[0] { $walls{'x'}[$next[0]][$current[1]] = ' '} when $next[0] > $current[0] { $walls{'x'}[$current[0]][$current[1]] = ' '} when $next[1] < $current[1] { $walls{'y'}[$current[0]][$current[1]] = ' ' } when $next[1] > $current[1] { $walls{'y'}[$current[0]][$next[1]] = ' ' } }
}
sub display ($walls) {
say '+' ~ ('---' xx $walls{'y'}[0]).join('+') ~ '+'; for ^$walls{'x'} -> $i { say ~$walls{'y'}[$i].join(' ') ~ ' |'; say '+' ~ $walls{'x'}[$i].join('+') ~ '+'; }
}</lang> Sample Output:
+---+---+---+---+---+---+---+---+---+---+---+ | | | | | +---+---+ + + + +---+---+---+---+ + | | | | | + +---+---+ +---+---+ +---+---+---+---+ | | | | + +---+ +---+ +---+ +---+---+---+ + | | | | | | + +---+---+ +---+ +---+ + +---+---+ | | | | | | | | +---+ + + +---+---+ + +---+ + + | | | | | | | + +---+---+---+ + + + +---+---+ + | | | | | | + + +---+---+---+---+---+---+ +---+ + | | | +---+---+---+---+---+---+---+---+---+---+---+
PicoLisp
This solution uses 'grid' from "lib/simul.l" to generate the two-dimensional structure. <lang PicoLisp>(load "@lib/simul.l")
(de maze (DX DY)
(let Maze (grid DX DY) (let Fld (get Maze (rand 1 DX) (rand 1 DY)) (recur (Fld) (for Dir (shuffle '((west . east) (east . west) (south . north) (north . south))) (with ((car Dir) Fld) (unless (or (: west) (: east) (: south) (: north)) (put Fld (car Dir) This) (put This (cdr Dir) Fld) (recurse This) ) ) ) ) ) (for (X . Col) Maze (for (Y . This) Col (set This (cons (cons (: west) (or (: east) (and (= Y 1) (= X DX)) ) ) (cons (: south) (or (: north) (and (= X 1) (= Y DY)) ) ) ) ) ) ) Maze ) )
(de display (Maze)
(disp Maze 0 '((This) " ")) )</lang>
Output:
: (display (maze 11 8)) + +---+---+---+---+---+---+---+---+---+---+ 8 | | | | + + + + + + +---+ +---+---+ + 7 | | | | | | | | | +---+ +---+---+ + + +---+ + + + 6 | | | | | | | | + +---+ +---+ +---+---+---+ + +---+ 5 | | | | | | +---+ +---+ +---+---+---+ +---+---+ + 4 | | | | | | | + +---+ +---+ +---+ + + +---+ + 3 | | | | | | | | + +---+---+ + + + + +---+ + + 2 | | | | | | | | | + + + +---+ + +---+ + +---+ + 1 | | | | +---+---+---+---+---+---+---+---+---+---+---+ a b c d e f g h i j k
Prolog
Works with SWI-Prolog and XPCE. <lang Prolog>:- dynamic cell/2.
maze(Lig,Col) :- retractall(cell(_,_)),
new(D, window('Maze')),
% creation of the grid forall(between(0,Lig, I), (XL is 50, YL is I * 30 + 50, XR is Col * 30 + 50, new(L, line(XL, YL, XR, YL)), send(D, display, L))),
forall(between(0,Col, I), (XT is 50 + I * 30, YT is 50, YB is Lig * 30 + 50, new(L, line(XT, YT, XT, YB)), send(D, display, L))),
SX is Col * 30 + 100, SY is Lig * 30 + 100, send(D, size, new(_, size(SX, SY))),
% choosing a first cell L0 is random(Lig), C0 is random(Col), assert(cell(L0, C0)), \+search(D, Lig, Col, L0, C0), send(D, open).
search(D, Lig, Col, L, C) :- Dir is random(4), nextcell(Dir, Lig, Col, L, C, L1, C1), assert(cell(L1,C1)), assert(cur(L1,C1)), erase_line(D, L, C, L1, C1), search(D, Lig, Col, L1, C1).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% erase_line(D, L, C, L, C1) :- ( C < C1 -> C2 = C1; C2 = C), XT is C2 * 30 + 50, YT is L * 30 + 51, YR is (L+1) * 30 + 50, new(Line, line(XT, YT, XT, YR)), send(Line, colour, white), send(D, display, Line).
erase_line(D, L, C, L1, C) :- XT is 51 + C * 30, XR is 50 + (C + 1) * 30, ( L < L1 -> L2 is L1; L2 is L), YT is L2 * 30 + 50, new(Line, line(XT, YT, XR, YT)), send(Line, colour, white), send(D, display, Line).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% nextcell(Dir, Lig, Col, L, C, L1, C1) :- next(Dir, Lig, Col, L, C, L1, C1); ( Dir1 is (Dir+3) mod 4, next(Dir1, Lig, Col, L, C, L1, C1)); ( Dir2 is (Dir+1) mod 4, next(Dir2, Lig, Col, L, C, L1, C1)); ( Dir3 is (Dir+2) mod 4, next(Dir3, Lig, Col, L, C, L1, C1)).
% 0 => northward next(0, _Lig, _Col, L, C, L1, C) :- L > 0, L1 is L - 1, \+cell(L1, C).
% 1 => rightward next(1, _Lig, Col, L, C, L, C1) :- C < Col - 1, C1 is C + 1, \+cell(L, C1).
% 2 => southward next(2, Lig, _Col, L, C, L1, C) :- L < Lig - 1, L1 is L + 1, \+cell(L1, C).
% 3 => leftward next(2, _Lig, _Col, L, C, L, C1) :- C > 0, C1 is C - 1, \+cell(L, C1).
PureBasic
<lang PureBasic>Enumeration
;indexes for types of offsets from maze coordinates (x,y) #visited ;used to index visited(x,y) in a given direction from current maze cell #maze ;used to index maze() in a given direction from current maze cell #wall ;used to index walls in maze() in a given direction from current maze cell #numOffsets = #wall ;direction indexes #dir_ID = 0 ;identity value, produces no changes #firstDir #dir_N = #firstDir #dir_E #dir_S #dir_W #numDirs = #dir_W
EndEnumeration
DataSection
;maze(x,y) offsets for visited, maze, & walls for each direction Data.i 1, 1, 0, 0, 0, 0 ;ID Data.i 1, 0, 0, -1, 0, 0 ;N Data.i 2, 1, 1, 0, 1, 0 ;E Data.i 1, 2, 0, 1, 0, 1 ;S Data.i 0, 1, -1, 0, 0, 0 ;W Data.i %00, %01, %10, %01, %10 ;wall values for ID, N, E, S, W
EndDataSection
- cellDWidth = 4
Structure mazeOutput
vWall.s hWall.s
EndStructure
- setup reference values indexed by type and direction from current map cell
Global Dim offset.POINT(#numOffsets, #numDirs) Define i, j For i = 0 To #numDirs
For j = 0 To #numOffsets Read.i offset(j, i)\x: Read.i offset(j, i)\y Next
Next
Global Dim wallvalue(#numDirs) For i = 0 To #numDirs: Read.i wallvalue(i): Next
Procedure makeDisplayMazeRow(Array mazeRow.mazeOutput(1), Array maze(2), y)
;modify mazeRow() to produce output of 2 strings showing the vertical walls above and horizontal walls across a given maze row Protected x, vWall.s, hWall.s Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2) vWall = "": hWall = "" For x = 0 To mazeWidth If maze(x, y) & wallvalue(#dir_N): vWall + "+ ": Else: vWall + "+---": EndIf If maze(x, y) & wallvalue(#dir_W): hWall + " ": Else: hWall + "| ": EndIf Next mazeRow(0)\vWall = Left(vWall, mazeWidth * #cellDWidth + 1) If y <> mazeHeight: mazeRow(0)\hWall = Left(hWall, mazeWidth * #cellDWidth + 1): Else: mazeRow(0)\hWall = "": EndIf
EndProcedure
Procedure displayMaze(Array maze(2))
Protected x, y, vWall.s, hWall.s, mazeHeight = ArraySize(maze(), 2) Protected Dim mazeRow.mazeOutput(0) For y = 0 To mazeHeight makeDisplayMazeRow(mazeRow(), maze(), y) PrintN(mazeRow(0)\vWall): PrintN(mazeRow(0)\hWall) Next
EndProcedure
Procedure generateMaze(Array maze(2), mazeWidth, mazeHeight)
Dim maze(mazeWidth, mazeHeight) ;Each cell specifies walls present above and to the left of it, ;array includes an extra row and column for the right and bottom walls Dim visited(mazeWidth + 1, mazeHeight + 1) ;Each cell represents a cell of the maze, an extra line of cells are included ;as padding around the representative cells for easy border detection Protected i ;mark outside border as already visited (off limits) For i = 0 To mazeWidth visited(i + offset(#visited, #dir_N)\x, 0 + offset(#visited, #dir_N)\y) = #True visited(i + offset(#visited, #dir_S)\x, mazeHeight - 1 + offset(#visited, #dir_S)\y) = #True Next For i = 0 To mazeHeight visited(0 + offset(#visited, #dir_W)\x, i + offset(#visited, #dir_W)\y) = #True visited(mazeWidth - 1 + offset(#visited, #dir_E)\x, i + offset(#visited, #dir_E)\y) = #True Next ;generate maze Protected x = Random(mazeWidth - 1), y = Random (mazeHeight - 1), cellCount, nextCell visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True PrintN("Maze of size " + Str(mazeWidth) + " x " + Str(mazeHeight) + ", generation started at " + Str(x) + " x " + Str(y)) NewList stack.POINT() Dim unvisited(#numDirs - #firstDir) Repeat cellCount = 0 For i = #firstDir To #numDirs If Not visited(x + offset(#visited, i)\x, y + offset(#visited, i)\y) unvisited(cellCount) = i: cellCount + 1 EndIf Next If cellCount nextCell = unvisited(Random(cellCount - 1)) visited(x + offset(#visited, nextCell)\x, y + offset(#visited, nextCell)\y) = #True maze(x + offset(#wall, nextCell)\x, y + offset(#wall, nextCell)\y) | wallvalue(nextCell) If cellCount > 1 AddElement(stack()) stack()\x = x: stack()\y = y EndIf x + offset(#maze, nextCell)\x: y + offset(#maze, nextCell)\y ElseIf ListSize(stack()) > 0 x = stack()\x: y = stack()\y DeleteElement(stack()) Else Break ;end maze generation EndIf ForEver ; ;mark random entry and exit point ; x = Random(mazeWidth - 1): y = Random(mazeHeight - 1) ; maze(x, 0) | wallvalue(#dir_N): maze(mazeWidth, y) | wallvalue(#dir_E) ProcedureReturn
EndProcedure
If OpenConsole()
Dim maze(0, 0) Define mazeWidth = Random(5) + 7: mazeHeight = Random(5) + 3 generateMaze(maze(), mazeWidth, mazeHeight) displayMaze(maze()) Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() CloseConsole()
EndIf</lang> The maze is represented by an array of cells where each cell indicates the walls present above (#dir_N) and to its left (#dir_W). Maze generation is done with a additional array marking the visited cells. Neither an entry nor an exit are created, these were not part of the task. A simple means of doing so is included but has been commented out.
Sample output:
Maze of size 11 x 8, generation started at 9 x 3 +---+---+---+---+---+---+---+---+---+---+---+ | | | | | + + +---+ + +---+ + +---+ + + | | | | | | | | + +---+ +---+---+ +---+ + +---+---+ | | | | | | + + +---+---+ +---+---+---+---+---+ + | | | | | | + +---+ +---+ + +---+ + +---+---+ | | | | | | +---+---+---+ + + +---+---+ +---+ + | | | | | | + +---+---+ +---+ +---+---+ + +---+ | | | | | | | + + + +---+---+---+ + +---+---+ + | | | | +---+---+---+---+---+---+---+---+---+---+---+
Python
<lang python>from random import choice
def make_maze(height, width):
conn = [ [[] for j in range(width)] for i in range(height) ] visited = [[False] * width for i in range(height)]
def neighbors(x, y): return [ (i, j) for (i, j) in ((y+1, x), (y-1, x), (y, x+1), (y, x-1)) if j >= 0 and j < width and i >= 0 and i < height if not visited[i][j] ]
def walk(y, x, avail=width*height - 1): visited[y][x] = True
while avail: n = neighbors(x, y) if not len(n): return avail
(i,j) = choice(n) conn[y][x].append((i,j)) conn[i][j].append((y,x))
avail = walk(i, j, avail - 1)
walk(0, 0) return conn
def show_maze(cells):
w, h = len(cells[0]), len(cells) for i in range(h): s1 = ["+ " if (i-1, j) in cells[i][j] else "+--" for j in range(w)] s2 = [" " if (i, j-1) in cells[i][j] else "| " for j in range(w)] print("".join(s1 + ["*\n"] + s2 + ["|"]))
print("*--" * w + "*")
show_maze(make_maze(8, 11))</lang>output<lang>+--+--+--+--+--+--+--+--+--+--+--+ | | | | | +--+ + +--+ + + +--+ +--+ + | | | | | | | | + + + +--+--+ +--+ +--+ + + | | | | | | | | + +--+ + + +--+ +--+--+ + + | | | | | | | +--+ +--+ +--+ +--+ + +--+--+ | | | | | | | + + + +--+ +--+--+ +--+--+ + | | | | | | | + + +--+ +--+--+--+--+ + + + | | | | | | | + +--+--+--+ +--+--+ + + + + | | | | +--+--+--+--+--+--+--+--+--+--+--+</lang>
Alternative version
<lang python>from random import randrange, choice from collections import namedtuple
W, H = 11, 8 hWalls = [[True] * H for _ in xrange(W)] vWalls = [[True] * H for _ in xrange(W)] seen = [[False] * H for _ in xrange(W)] P = namedtuple("P", "x y")
def visit(x, y):
seen[x][y] = True D = [P(x-1,y), P(x+1,y), P(x,y-1), P(x,y+1)] ns = [p for p in D if p.x>=0 and p.x<W and p.y>=0 and p.y<H] while ns: n = choice(ns) if not seen[n.x][n.y]: if x != n.x: hWalls[min(x, n.x)][y] = False else: vWalls[x][min(y, n.y)] = False visit(*n) ns = [x for x in ns if x != n]
visit(randrange(W), randrange(H))
print "+" + ("--+" * W) for y in xrange(H):
s = "|" for x in xrange(W): s += " |" if hWalls[x][y] else " " s += "\n+" for x in xrange(W): s += "--+" if vWalls[x][y] else " +" print s</lang>
Tcl
<lang tcl>package require TclOO; # Or Tcl 8.6
- Helper to pick a random number
proc rand n {expr {int(rand() * $n)}}
- Helper to pick a random element of a list
proc pick list {lindex $list [rand [llength $list]]}
- Helper _function_ to index into a list of lists
proc tcl::mathfunc::idx {v x y} {lindex $v $x $y}
oo::class create maze {
variable x y horiz verti content constructor {width height} {
set y $width set x $height
set n [expr {$x * $y - 1}] if {$n < 0} {error "illegal maze dimensions"} set horiz [set verti [lrepeat $x [lrepeat $y 0]]] # This matrix holds the output for the Maze Solving task; not used for generation set content [lrepeat $x [lrepeat $y " "]] set unvisited [lrepeat [expr {$x+2}] [lrepeat [expr {$y+2}] 0]] # Helper to write into a list of lists (with offsets) proc unvisited= {x y value} { upvar 1 unvisited u lset u [expr {$x+1}] [expr {$y+1}] $value }
lappend stack [set here [list [rand $x] [rand $y]]] for {set j 0} {$j < $x} {incr j} { for {set k 0} {$k < $y} {incr k} { unvisited= $j $k [expr {$here ne [list $j $k]}] } }
while {0 < $n} { lassign $here hx hy set neighbours {} foreach {dx dy} {1 0 0 1 -1 0 0 -1} { if {idx($unvisited, $hx+$dx+1, $hy+$dy+1)} { lappend neighbours [list [expr {$hx+$dx}] [expr {$hy+$dy}]] } } if {[llength $neighbours]} { lassign [set here [pick $neighbours]] nx ny unvisited= $nx $ny 0 if {$nx == $hx} { lset horiz $nx [expr {min($ny, $hy)}] 1 } else { lset verti [expr {min($nx, $hx)}] $ny 1 } lappend stack $here incr n -1 } else { set here [lindex $stack end] set stack [lrange $stack 0 end-1] } }
rename unvisited= {}
}
# Maze displayer; takes a maze dictionary, returns a string method view {} {
set text {} for {set j 0} {$j < $x*2+1} {incr j} { set line {} for {set k 0} {$k < $y*4+1} {incr k} { if {$j%2 && $k%4==2} { # At the centre of the cell, put the "content" of the cell append line [expr {idx($content, $j/2, $k/4)}] } elseif {$j%2 && ($k%4 || $k && idx($horiz, $j/2, $k/4-1))} { append line " " } elseif {$j%2} { append line "|" } elseif {0 == $k%4} { append line "+" } elseif {$j && idx($verti, $j/2-1, $k/4)} { append line " " } else { append line "-" } } if {!$j} { lappend text [string replace $line 1 3 " "] } elseif {$x*2-1 == $j} { lappend text [string replace $line end end " "] } else { lappend text $line } } return [join $text \n]
}
}
- Demonstration
maze create m 11 8 puts [m view]</lang> Output:
+ +---+---+---+---+---+---+---+---+---+---+ | | | | +---+---+ +---+---+ + +---+ +---+ + | | | | | | + + +---+ +---+---+ +---+ + + + | | | | | | | | + +---+ +---+---+---+ + + + + + | | | | | | | | + + + + +---+---+ + +---+---+ + | | | | | | | | +---+---+---+---+ + +---+ + + +---+ | | | | | | | | + +---+---+ + + + + + +---+ + | | | | | | | | +---+ + +---+---+---+---+ + +---+ + | | +---+---+---+---+---+---+---+---+---+---+---+