Maze Generation

Question

I know there is an (old) thread similar to this (here), but I'd like to reboot it with some modifications.

The goal: generate a random-looking maze using an algorithm of your choice, then output the maze graphically (printing counts).

• The width and height are determined by you.
• There should be at least one path from at least one entrance to at least one exit.
• The format of the maze (how you display it, mark entrance(s) or exit(s)) is up to you as well.
• The prettier, the better.
• Trivial mazes (e.g. blank mazes, lattice mazes, mazes of size 1x1) are discouraged.
• Cycles in the maze are allowed and, are encouraged, if the result is reasonable.
• Language abuse encouraged.
• The maze should look reasonably random (but a completely deterministic (e.g. chaotic) algorithm that generates this is fine too).

Edit: the main focus here is on making the smallest possible implementation. However, I want to allow some leeway within that constraint to encourage shininess. I have deliberately left exactly what "features" the maze has open-ended, but as a rough guideline you should try to pack the most amount of bang into the least lexical buck.

Answer 1

C: 265 253 Bytes

#define f(v)for(v=0;v<k;++v)
#define d(q,n)case q:r(c+n,c+2*n);
z[4225],i,j,k=65;r(p,c){if(!z[c]){z[p]=z[c]=1;f(p)switch(rand()%4){d(0,-k)d(1,k)d(2,-1)d(3,1)}}}main(){f(i)z[i]=z[i+4160]=z[i*k]=z[i*k+64]=z[4157]=1;r(67,132);f(i)f(j)putchar(33-z[i*k+j]);}

(Requires 65-character terminal) Generates a relatively random 31x31 maze with one guaranteed path from the entrance to exit.

Example output (with simulated 65-character terminal):

 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 
 !     !       !   !       !     !           !             !   ! 
 !!!!! !!! !!! ! !!! ! !!! ! !!! !!!!!!! !!! !!!!!!!!! !!! ! ! ! 
 !   !   !   ! !     ! ! ! ! ! ! !       !   !         !   ! ! ! 
 ! !!!!! !!! ! !!!!!!! ! ! ! ! ! ! !!!!!!! !!! ! !!!!!!! !!! ! ! 
 !     !     !         ! !   !   !     !   !   ! !     !   ! ! ! 
 ! !!! !!!!!!!!!!!!!!!!! !!!!! !!! !!! !!! ! ! !!! !!! !!! !!! ! 
 !   !         !     !   !     !     !   ! ! ! !     !   !   ! ! 
 !!!!!!!!!!! ! ! !!! !!! ! !!!!!!!!!!!!! ! !!! ! !!!!!!! !!! ! ! 
 !           !   !       ! !             !   !     !     !     ! 
 ! !!!!!!! !!!!!!! !!!!!!! ! !!!!!!!!!!!!!!! !!!!!!! !!!!!!!!!!! 
 ! !     ! !   !     !   ! !           !   !       ! !         ! 
 ! !!! ! ! ! ! !!!!!!! ! ! ! !!!!!!!!! ! ! !!!!!!! ! ! !!!!!!! ! 
 !   ! !   ! !       ! !   ! !         ! !       ! ! !   !   ! ! 
 !!! ! !!!!! !!!!!!! ! !!!!!!! !!!!!!!!! !!! !!!!! ! !!! ! !!! ! 
 !   !   ! ! !       !   !     !   !     ! !           ! !   ! ! 
 ! !!!!! ! ! ! !!!!!!!!! ! !!!!! !!! !!!!! !!!!!!!!!!! ! ! ! ! ! 
 ! !       ! !   !   !   ! !       ! !       !   !     ! ! ! ! ! 
 ! !!!!!!!!! !!! ! ! ! !!! !!!!!!! ! !!!!!!! ! ! !!!!!!! !!! ! ! 
 !             !   ! !   !       ! !     !   ! !             ! ! 
 !!!!!!!!!!!!!!!!!!! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!!!!!!!! ! 
 !               !   !   !       !         !   !     !   !     ! 
 ! !!!!!!!!!!!!! ! ! ! !!! !!!!!!! !!!!!!!!! !!! !!! !!! ! !!! ! 
 ! !   !       !   ! ! ! !     ! ! ! !     !     !   !   !   ! ! 
 ! ! ! !!!!! !!!!!!! ! ! ! !!! ! ! ! ! !!! !!!!!!! !!! !!!!! !!! 
 !   ! !   !       ! ! !     ! !     ! ! !     !   !       !   ! 
 !!!!! ! ! !!! !!! ! ! !!!!!!! !!!!!!! ! ! !!! ! !!!!!!!!! !!! ! 
 !     ! !   !   !   !       !       ! ! ! !   !   !         ! ! 
 ! !!!!! !!! !!! !!!!!!!!!!! !!!!!!! ! ! ! !!!!!!! ! !!!!!!! ! ! 
 !         ! !           !   !       ! ! !     !   ! !       ! ! 
 !!!!!!!!!!! !!!!!!!!!!! ! !!! !!!!!!! ! !!!!! ! !!! !!!!!!!!! ! 
 !         !     !     ! ! !       !   !     ! !     !         ! 
 ! !!!!!!! !!!!! ! !!! !!! !!!!!!! ! !!!!! ! ! !!!!! ! !!!!!!!!! 
 ! !     !     !   ! !   !       ! !       ! !       !         ! 
 ! ! !!! !!!!! ! !!! !!! !!!!!!! ! !!!!!!!!! !!!!!!!!!!!!!!!!! ! 
 !     !     ! !   !   ! !     ! !       !   ! !     !         ! 
 !!!!!!!!!!! ! !!! !!! ! ! ! !!! ! ! !!!!! !!! ! !!! ! !!!!!!! ! 
 !           ! !       !   ! !   ! !       !   ! ! ! !     !   ! 
 ! !!!!!!!!!!! !!!!!!!!!!!!! ! !!! !!!!!!!!!!! ! ! ! ! !!! ! !!! 
 !       !   !             ! ! ! !   !         ! !   !   ! ! ! ! 
 !!!!!!! !!! !!!!!!!!!!!!! ! ! ! !!! ! !!!!!!! ! !!! !!!!! ! ! ! 
 !       !         !     ! ! ! !   !   !     ! !   !       !   ! 
 ! !!!!!!! !!!!!!! ! !!!!! ! ! !!! !!!!!!! ! ! !!! !!!!!!!!!!!!! 
 !   !         ! !   !       ! !           ! !   !             ! 
 ! ! ! !!!!!!! ! ! !!! !!!!!!! ! !!!!!!!!!!! ! !!!!!!!!!!!!!!! ! 
 ! ! ! !     ! !   !   ! !     !   !   !     ! !               ! 
 ! ! !!! !!! ! !!!!! !!! ! !!!!! ! ! ! !!!!!!! ! !!!!!!!!!!!!! ! 
 ! !   !   ! !   !       !   !   !   !         ! !         !   ! 
 !!!!! !!! ! !!! ! !!!!!!!!! !!!!!!! !!!!!!!!!!! !!!!! !!!!! !!! 
 !     !   !   !   !       !       !       !   !     !       ! ! 
 ! !!!!! !!!!! !!!!! !!!!! !!!!!!! !!!!!!!!! ! !!!!! !!!!!!! ! ! 
 !           !     ! !   !   !   !           !   !   !     !   ! 
 ! !!!!!!!!! !!!!! ! !!! ! !!! ! !!!!!!!!!!!!!!! ! !!! !!! !!! ! 
 ! !     !       ! !     !     !     !         ! !       !   ! ! 
 !!! !!! !!!!!!!!! !!!!! !!!!!!!!! ! !!!!!!! !!! ! !!!!!!!!! ! ! 
 !   !     !   !   !   ! !       ! !         !   ! !         ! ! 
 ! !!!!!!! ! ! ! ! !!! ! !!!!!!! ! !!!!!!!!! ! !!!!! !!!!!!!!! ! 
 !       !   !   ! !   !         !   ! !   ! ! !     !       ! ! 
 ! !!!!! !!!!!!!!! ! !!!!!!!!!!! !!! ! ! ! ! ! ! !!!!! !!!!! ! ! 
 ! !     !           !         ! ! ! !   !   ! !   !   !     ! ! 
 ! ! !!!!!!!!!!!!!!!!! !!! !!!!! ! ! !!!!!!!!! !!! ! !!!!!!!!! ! 
 ! !                     !         !               !           ! 
 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ! 

Answer 2

Mathematica, 144 132 bytes

Since Inception, we all know the most efficient way to draw a maze.

c=0;Graphics@Most[Join@@{Circle[{0,0},i,{a=c-(r=Random[](d=2Pi-1/i)&)[],a+d}],Line[{{i},{i+1}}.{{Cos[c=a+r[]],Sin@c}}]}~Table~{i,9}]

Ungolfed and example output:

Of course, the lines are the walls. You're the minotaur who starts in the centre and needs to get out.

Answer 3

C: 364 Bytes

#define I int
m[1600],i=0,r;f(I x,I y,I l){m[80*y+x]|=l;I d[]={x-1,y,2,1,x+1,y,1,2,x,y-1,8,4,x,y+1,4,8},
s[]={5,5,5,5},j=0;for(;j<4;){L:r=rand()%4;for(I k=0;k<4;)if(s[k++]==r)goto L;s[j]=r;I*p=d+
4*s[j++],X=p[0],Y=p[1];if(!(X<0|X>79|Y<0|Y>19|m[80*Y+X])){f(X,Y,p[2]);m[80*y+x]|=p[3];}}}
main(){f(0,0,4);m[9]|=4;for(;i<1600;)putchar("#5FMP<HJR;IK:9LN"[m[i++]]+128);}

Note: in the above, I added newlines to make it fit on the page. Expected output (on 80-character terminal) (note start and end at top left):

Answer 4

Mathematica, 134 130 chars

Graph[Range@273,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=GridGraph@{13,21},c@#=#]}]&@1][[2,1]],Options@g]

---

In fact, we can use this algorithm to generate a maze from any (undirected) graph.

For example, generate a maze from the 8*8 knight's tour graph (KnightTourGraph[8,8]):

Graph[Range@64,Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g=KnightTourGraph[8,8],c@#=#]}]&@1][[2,1]],Options@g]

Answer 5

Bash, 53 bytes

w=(╱ ╲);while true;do echo -n ${w[RANDOM%2]};done

Similar idea to the C64 code. Uses Unicode characters as the slashes because they look much nicer in a terminal that supports Unicode. Sample output on OS X Terminal (Menlo font):

Answer 6

JavaScript (ES6), 174

This is the maze builder I used in this other challenge, just golfed. It's a function with 2 parameters: rows and columns. The maze is totally connected with no loops, so any location can be the starting or ending point.

(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}

Example

f(7,10)

Output

,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
,8, , , ,8, , , , , ,8, , , , , , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8,8,8,8,8,8,8, ,8, ,8,
,8, , , ,8, , , ,8, , , ,8, , , , , ,8, ,8,
,8, ,8,8,8, ,8,8,8,8,8, ,8, ,8,8,8,8,8, ,8,
,8, ,8, , , , , ,8, ,8, ,8, ,8, , , , , ,8,
,8, ,8, ,8,8,8, ,8, ,8, ,8, ,8, ,8,8,8,8,8,
,8, ,8, ,8, , , ,8, , , , , ,8, ,8, , , ,8,
,8, ,8, ,8, ,8,8,8,8,8,8,8,8,8, ,8, ,8,8,8,
,8, ,8, ,8, , , , , , , ,8, , , ,8, , , ,8,
,8, ,8, ,8,8,8,8,8,8,8, ,8,8,8, ,8,8,8, ,8,
,8, ,8, , , , , , , ,8, , , ,8, , , , , ,8,
,8, ,8,8,8,8,8,8,8,8,8,8,8, ,8,8,8,8,8, ,8,
,8, , , , , , , , , , , , , ,8, , , , , ,8,
,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8

Test

f=
(r,c,o=2*c+2,i=2*r*o+o,z=[],F=(p,i=Math.random()*4)=>[o,1,-o,-1].map((s,j,d)=>z[s=p+2*d[j+i&3]]>0&&(z[s]=z[(p+s)/2]=' ',F(s))))=>{for(;i--;)z[i]=i%o?8:`\n`;F(o+2);return''+z}
    
function update() {    
  O.textContent='';
  [r,c]=I.value.match(/\d+/g)
  O.textContent=f(r,c)
}  

update()

pre { line-height: 0.8em }

Rows,Columns <input id=I oninput='update()' value='8,12'>
<pre id=O></pre>

Answer 7

ZX Basic - 54 characters

a$="/\":for i=1 to 24*32:print a$(1+int(rnd*2));:next

Here is the maze showing a route through it (spaces between lines)

and a small snippet from when I first did this (several years ago), and spent a bit of time doing better graphics.

Answer 8

BBC BASIC, 18 Bytes

An improvement in length on the 23-byte C64 infinite loop version by @nneonneo. VDU sends a single character to the VDU controller: either 2+1*45=ASCII 47 / or 2+2*45=ASCII 92 \

  VDU2+RND(2)*45:RUN

BBC BASIC, 35 Bytes / 107 95 Bytes

35 bytes is just for the last line, which gives a 25 row maze in 40 column layout. MODE1 ensures that no extra space is left between lines. The remainder of the program is optional and improves the formatting. The VDU23 statements redefine the font for characters 47 and 92 (8 bytes forming an 8x8 bitmap.) I include a light pixel in all four corners to stop straight runs from getting pinched off. The side effect of this is that a dot appears in the empty diamonds. 107 bytes total including 2 newlines.

  VDU23,47,131,7,14,28,56,112,224,193
  VDU23,92,193,224,112,56,28,14,7,131
  MODE9FORa=0TO999VDU2+RND(2)*45:NEXT

Edit this program can be shortened to 95 bytes by encoding some of the 8 bit VDU codes into 16 bit small endian values (denoted by a semicolon after them instead of a comma) and representing the MODE statement as a pair of VDU codes, as follows.

VDU23,47,1923;7182;28728;49632;23,92,57537;14448;3612;33543;22,9:FORa=0TO999VDU2+RND(2)*45:NEXT

Output

Using BBC Basic for Windows from bbcbasic.co.uk

Last line only, 35 bytes

Whole program, 107 95 bytes

As I commented on @Brian's answer, the slash splits the square into 2 dark triangles, each of which has exactly 2 entrances/exits. This guarantees a (trivial, unbranched) path from any point on the edge of the maze to some other point on the edge of the maze. Many of these are very short, but there always seem to be a few long ones. Of course, in the middle of the maze there are also some loops.

As other answers have not mentioned it, I'd like to take a good look at the light areas. These are bounded by dark areas, therefore as a corollary to the statement made above, a light area bounded externally by N dark areas touches the edge of the field at N (exactly as many) points. Therefore some fairly large light areas occur, and these form interesting, branched mazes.

In the example below, you can see the raw output (monochrome) from my program. Below that (using Windows Paint) I have coloured the two longest dark areas in blue. Then I coloured the largest light area in yellow, and the two areas bounded by blue in red and green. The yellow, green (and even the red) mazes are quite interesting and nontrivial.

EDIT - Automatic picking of mazes and selection of starts/ends

For one more line (59 characters) the program can automatically pick out up to 6 mazes by choosing squares at random and flood filling in colours red,green,yellow,blue,magenta and cyan. It does not always find a full 6, because if it picks a random square that has already been coloured it does nothing.

The rest of the code below picks out a start for each colour by scanning each column from top to bottom and left to right, and picking the first square it encounters. It picks an end by scanning in the opposite direction.

This produces a set of colourful, intertwined mazes. Sometimes they are so intertwined it looks like the mazes must cross somewhere. But of course, they don't!

Additional code and output 59+187=246 additional characters to be added to the end of the original program (for enhancement beyond question spec.)

  GCOL135FORa=1TO6GCOLa FILLRND(40)*32-16,RND(25)*32+208:NEXT   :REM set background to grey so fill can identify. For each colour 1 to 6, pick a point in the centre of a character and flood fill (characters are logically 32x32 although they are physically only 8x8 pixels.)
  f=126:g=126                                                   :REM flags 1111110 to indicate which starts and ends have not been allocated yet
  FORx=0TO39FORy=0TO24                                          :REM maze is 40x25. There is some blank space at the bottom of the screen (32 rows total)
  p=POINT(x*32+16,1008-y*32)                                    :REM check start point. Text origin is at top of screen, Graphics origin is at bottom, 1280x1024 logical. therefore y offset is 1024-32/2=1008.
  IFf AND2^p f=f-2^p:VDU31,x,y,17,p,79                          :REM if start for colour P has not been allocated yet, allocate it now. VDU31,X,Y go to that square. VDU 17,p select text colour. VDU 79 print an "O"                 
  p=POINT(1264-x*32,240+y*32)                                   :REM check end point
  IFg AND2^p g=g-2^p:VDU31,39-x,24-y,17,p,79                    :REM if end for colour P has not been allocated yet, allocate it now.
  NEXT:NEXT
  VDU31;26                                                      :REM get the cursor off the board. Move to (0,26). Semicolon used instead of comma here indicating that 31 is a 16 bit small endian value, equivalent to VDU31,0,26 or PRINTTAB(0,26)

Answer 9

C: 235 Bytes

#define P(X,Y)M[(Y+40)*80+X+40]=rand()%49/6;
#define B(X,Y)P(X,Y)P(Y,X)
M[6400],r,i;main(){for(i=0;i<40;i+=2){int x=i,y=0,e=1-x;while(x>=y)
{B(x,y)B(-x,y)B(-x,-y)B(x,-y)++y;e+=e<0?2*y+1:2*(y-x--);}}for(i=0;
i<6400;)putchar(64>>!M[i++]);}

Note: in the above, I added newlines to make it fit on the page. Expected output (on 80-character terminal):

I regret this isn't a very hard maze (in fact, no backtracking to inner rings is required (and you should be able to find a path from the perimeter to the center trivially). However, it has a nice implementation of Bresenham's circle drawing algorithm at its core.

Answer 10

I helped my kid to do this, to learn a bit of programming: http://jsfiddle.net/fs2000/4KLUC/34/ how do you like it?

Answer 11

Commodore 64 BASIC - 38 bytes

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

This is not my invention, I am simply repeating a very beautiful and short program from days gone past. In fact, there is an entire book named 10 PRINT CHR$(205.5+RND(1)); : GOTO 10 celebrating this piece of code!

You can see the output on this YouTube video; here's a screencap:

Here at this StackOverflow question are more implementations of this maze-generator program. The shortest implementation of the program is the following 23-byte C64 BASIC program posted by that question's author:

1?cH(109.5+rN(1));:gO1

where lowercase letters are entered as-is, and uppercase letters are entered using the Shift key (these have different appearances on an actual C64 screen).

Answer 12

Java : 700

Here's a recursive wall adder. The algorithm is outlined on this site:

public class Z{int i,j,u=20,v=u,g[][]=new int[v][u];public static void main(String[]a){new Z().d(0,0,20,20,0).p();}int q(int m){return(int)(Math.random()*m);}<T>void z(T m){System.out.print(m);}void p(){for(i=0;i++<u*2;z("_"));for(i=0;i<v;i++){z("\n|");for(j=0;j<u;j++){boolean b=i+2>v,s=g[i][j]%2>0||b;z(s?"_":" ");z(g[i][j]>1||j+2>u?"|":s&(j+1<u&&g[i][j+1]%2>0||b)?"_":" ");}}}Z d(int x,int y,int w,int h,int o){int a=x,b=y,c=a,d=b,e,f;boolean t=o<1;if(t){b+=q(h-2);c+=q(w);}else{a+=q(w-2);d+=q(h);}for(i=t?w:h;i-->0;j=t?a++:b++)if(a!=c&&b!=d)g[b][a]|=t?1:2;e=t?w:a-x+1;f=t?b-y+1:h;if(e>2&&f>2)d(x,y,e,f,e<f?0:1);e=t?w:x+w-a-1;f=t?y+h-b-1:h;if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);return this;}}

Basically, it splits each rectangle in two with a wall (and passage), then splits those in two, etc. It generates a "perfect" maze - one with no cycles - that has a path from every point to every other point. Plenty of dead ends, so it's not "trivial" in any sense for larger mazes.

So, the entrance and exit can be decided arbitrarily. If I have to choose one, It'll just say top/left and bottom/right.

It's drawn in double-width ascii, so it's a good idea to pipe output to a file if you're doing one of any size. Here's a 20x20 in console:

And a 100x100 in notepad++ (I had to zoom out to get ti all, so it's somewhat... small):

Code with line breaks:

public class Z{
    int i,j,u=20,v=u,g[][]=new int[v][u];
    public static void main(String[]a){
        new Z().d(0,0,20,20,0).p();
    }

    int q(int m){return(int)(Math.random()*m);}
    <T>void z(T m){System.out.print(m);}

    void p(){
        for(i=0;i++<u*2;z("_"));
        for(i=0;i<v;i++){
            z("\n|");
            for(j=0;j<u;j++){
                boolean b=i+2>v,s=g[i][j]%2>0||b;
                z(s?"_":" ");
                z(g[i][j]>1||j+2>u?"|":s&(j+1<u&&g[i][j+1]%2>0||b)?"_":" ");
            }
        }
    }

    Z d(int x,int y,int w,int h,int o){
        int a=x,b=y,c=a,d=b,e,f;
        boolean t=o<1;
        if(t){
            b+=q(h-2);
            c+=q(w);
            }
        else{
            a+=q(w-2);
            d+=q(h);
        }

        for(i=t?w:h;i-->0;j=t?a++:b++)
            if(a!=c&&b!=d)
                g[b][a]|=t?1:2;

        e=t?w:a-x+1;f=t?b-y+1:h;
        if(e>2&&f>2)d(x,y,e,f,e<f?0:1);
        e=t?w:x+w-a-1;f=t?y+h-b-1:h;
        if(e>2&&f>2)d(t?x:a+1,t?b+1:y,e,f,e<f?0:1);
        return this;
    }
}

Answer 13

ZX Basic - 281 characters

This is more of a "proper" maze, less golfier, but more mazier. So called Binary maze algorithm, each cell can have an exit going down or right, but not both. (Now includes marked Start "S" and End "E", to prevent just going straight along one side).

The "::" is ZXB's way of entering Spectrum graphic characters into a text file, equates to a sold block character.

randomize:border 1:paper 1:ink 6:cls
for x=0 to 30 step 2
 for y=0 to 20 step 2
  r=1+int(rnd*2)
  if x=30 and r=1 then 
   r=2
  end if
  if y=20 and r=2 then
   r=1
  end if
  print at y,x;"\::"
  print at y+(r=2),x+(r=1);"\::"
 next
next
print inverse 1;at 0,0;"S";at 20,31;"E"

Answer 14

C- 244

#include <unistd.h>
#include <windows.h>
int main(i,j,rv,rs){srand( time(0));for (i = 0; i < 80; i++)for (j = 0; j <50 ; j++){rv = rand() %10;rs = rand() %100;if(rs < 10 || rs  > 90)continue;if(rv<4){gotoxy(i,j);printf("%c", '#');}}return 0;}

Here is how it looks like:

Note: this solution is inspired by the untrusted game level 8:into the woods.