Maze Generation [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

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.

Also "The prettier, the better" seems hardly tangible (or simply irrelevant) to a code-golf challenge. Maybe a popularity contest would be the better choices if you're interested in pretty results. — Martin Ender, Commented Apr 17, 2014 at 9:59
So is it really code-golf or is it rather popularity-contest? — l0b0, Commented Apr 17, 2014 at 11:37
As another suggestion, if you do want to incentivise both short codes and neat mazes, you could make it a code-challenge and declare that the winner will be selected by some score that is a mixture of code length and upvotes - although it'll be up to you to determine each answers total score, because including the current number of upvotes in the post is a bit useless. — Martin Ender, Commented Apr 17, 2014 at 13:11
I think each answer should explain what constitute entrances and exits in each maze (as well as, what's a wall and what's a passage), so that we can evaluate the 2nd bullet. — LarsH, Commented Apr 17, 2014 at 16:41
@Geobits I wouldn't mind too much, but hence my suggestion to actually make it a code-challenge with combined scoring from code length and votes. That would exactly encourage what the OP wants: short code for interesting mazes. — Martin Ender, Commented Apr 18, 2014 at 20:34

Martin Ender · Accepted Answer · 2014-04-17 16:46:21Z

34

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:

enter image description here

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

edited Apr 17, 2014 at 16:46

answered Apr 17, 2014 at 10:09

Martin Ender

197k67 gold badges447 silver badges975 bronze badges

4

\$\begingroup\$ This is pretty, and the code is short, but I would say it's toward the "trivial maze" end of the spectrum. \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 16:32
2

\$\begingroup\$ You're right that making it bigger wouldn't change the triviality. The point is that solving this maze is a linear process: at every juncture you can quickly find out whether you've taken the wrong turn, without having to "recurse" into deeper branches. Ian's and aleph's answers, on the other hand, are "real" mazes: they can't be solved in this linear way. Since trivial mazes are discouraged, I'd be tempted to downvote this one, but I don't have enough rep. \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 16:55
1

\$\begingroup\$ @LarsH yep, we agree on that. That's why I said it's the most "efficient" way to draw a maze, not the most "effective" one. ;) Still, it may be simple, but I don't think it falls in a category with the ruled out ones like "blank" or "1x1". Of course, it's at the OP's discretion to disqualify this submission for its simplicity, but as long as he doesn't do that or changes the type of the challenge, I don't see an incentive to make it more complicated/interesting. \$\endgroup\$
– Martin Ender
Commented Apr 17, 2014 at 17:03
1

\$\begingroup\$ @LarsH that being said, I'm not sure if it's due to their algorithms or just a feature of the particular examples they posted, but neither of their answers required backtracking beyond depth "1" more than once. So while they do contain a lot of complexity, it's all in paths that are irrelevant anyway. \$\endgroup\$
– Martin Ender
Commented Apr 17, 2014 at 17:12
1

\$\begingroup\$ This maze isn't trivial, in my opinion, even if it's easy (and my circular maze below is even more trivial). I really just wanted to prevent blank-canvas/size-1/etc. "maze"s. \$\endgroup\$
– geometrian
Commented Apr 18, 2014 at 0:06

| Show 7 more comments

geometrian · Accepted Answer · 2014-04-17 03:52:02Z

33

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): enter image description here

answered Apr 17, 2014 at 3:52

geometrian

1,0251 gold badge9 silver badges16 bronze badges

8

\$\begingroup\$ @bwoebi MSPaint to the rescue! IMAGE \$\endgroup\$
– Ceiling Gecko
Commented Apr 17, 2014 at 11:34
6

\$\begingroup\$ Note that my intention was to have the path be inside the pipes (as here). \$\endgroup\$
– geometrian
Commented Apr 17, 2014 at 15:56
1

\$\begingroup\$ @IanMallett I think Ceiling Gecko was aware of that, but flood-filling the left wall with a colour gives you a (non-optimal) path following along the left wall until you find the exit. ;) \$\endgroup\$
– Martin Ender
Commented Apr 17, 2014 at 16:48
1

\$\begingroup\$ I'd be interested in seeing the un-golfed version of this code, if you have time. \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 17:00
4

\$\begingroup\$ While you wrote this you were a-maze-ing coder. \$\endgroup\$
– totymedli
Commented Apr 17, 2014 at 19:15

| Show 4 more comments

Community · Accepted Answer · 2020-06-17 09:04:33Z

24

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]

maze

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]):

knight's tour graph

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]

maze2

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 17, 2014 at 6:43

alephalpha

50k7 gold badges68 silver badges182 bronze badges

7

\$\begingroup\$ Nice maze… but I don't see any entrance which is connected to an exit…? \$\endgroup\$
– bwoebi
Commented Apr 17, 2014 at 11:07
9

\$\begingroup\$ I believe the idea is to pick a random node (say, upper left) as entrance and another (bottom right) as exit. Mathematica makes sure all nodes are connected with all other nodes, but - especially in the second maze - finding how they are connected is the harder part. \$\endgroup\$
– EagleV_Attnam
Commented Apr 17, 2014 at 11:49
\$\begingroup\$ Are the lines (graph edges) supposed to be maze walls, or passages? I thought I knew, but now I'm not sure. \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 16:58
\$\begingroup\$ @LarsH They are passages. \$\endgroup\$
– alephalpha
Commented Apr 18, 2014 at 2:48
1

\$\begingroup\$ @LarsH The graph is connected, so you can just take two arbitrary nodes, one as entrance, the other as exit. \$\endgroup\$
– alephalpha
Commented Apr 18, 2014 at 4:40

| Show 2 more comments

nneonneo · Accepted Answer · 2023-02-04 14:01:24Z

13

Bash, 53 50 bytes

w=(╱ ╲);while :;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):

Sample maze output

edited Feb 4, 2023 at 14:01

answered Apr 18, 2014 at 7:50

nneonneo

12.4k8 gold badges30 silver badges49 bronze badges

2

\$\begingroup\$ I once figured this out: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. See this post \$\endgroup\$
– gniourf_gniourf
Commented Apr 19, 2014 at 13:41
5

\$\begingroup\$ This is based on an algorithm that cannot guarantee itself to be solvable, one that is many years old. \$\endgroup\$
– Claudia
Commented Apr 20, 2014 at 2:45

Add a comment |

Dendrobium · Accepted Answer · 2014-04-21 03:35:16Z

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):

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

\$\begingroup\$ You don't even need int p,int c. p,c is enough... \$\endgroup\$
– chubakueno
Commented Apr 21, 2014 at 3:30 — chubakueno, Commented Apr 21, 2014 at 3:30

Community · Accepted Answer · 2020-06-17 09:04:33Z

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>

I'm not sure ... is the light or the dark area the maze? If the dark, then it has a big loop and one can just stay at the outside when choosing any point as entering/exit point. If the light, then you should add the exit/entry. — Paŭlo Ebermann, Commented Oct 11, 2015 at 13:09
@PaŭloEbermann it is the light of course, dark area is the walls. Repeating myself: The maze is totally connected with no loops, so any location can be the starting or ending point — edc65, Commented Oct 11, 2015 at 13:43
Wow, this is a-mazing! Shaved some bytes and got it down to 133 bytes: twitter.com/aemkei/status/889587308894326785 But all credits should go to you! — aemkei, Commented Jul 24, 2017 at 20:46
@aemkei 8 instead of '#', I can't believe I missed that at time — edc65, Commented Jul 26, 2017 at 17:00

Brian · Accepted Answer · 2014-04-17 21:08:30Z

8

ZX Basic - 54 characters

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

Output

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

path

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

better graphics

edited Apr 17, 2014 at 21:08

answered Apr 17, 2014 at 7:00

Brian

1,2578 silver badges9 bronze badges

2

\$\begingroup\$ Hm, cheeky. ^^ What's the start and what's the end there? And are the slashes the paths or the walls? And what is the minimum gap size I can pass through? \$\endgroup\$
– Martin Ender
Commented Apr 17, 2014 at 14:49
2

\$\begingroup\$ "There should be at least one path from at least one entrance to at least one exit." I don't see any indication that this criterion is met. Random walls don't necessarily create a maze. \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 16:38
1

\$\begingroup\$ @m.buettner: I'm guessing that the slashes are walls, and that we're supposed to visualize it as though there were zero space between rows, and between columns. So the bottom-left 2x2 characters form a totally closed diamond (square) shape. \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 17:45
\$\begingroup\$ @LarsH yeah I thought so. That just makes another point for your case on the OP's question that people should indicate what start and finish are. Also, this scheme doesn't even allow for junctions. You can only have those closed squares or meandering paths (which might also be closed loops). \$\endgroup\$
– Martin Ender
Commented Apr 17, 2014 at 19:09
\$\begingroup\$ +1 for the improved graphics and showing the route. I guess given so many potential entrances and exits, the likelihood of having "at least one path from at least one entrance to at least one exit" is pretty high! \$\endgroup\$
– LarsH
Commented Apr 17, 2014 at 21:18

| Show 3 more comments

Level River St · Accepted Answer · 2014-04-20 18:38:06Z

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

enter image description here

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.

enter image description here

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)

enter image description here

geometrian · Accepted Answer · 2014-04-18 00:13:27Z

7

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): enter image description here

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.

edited Apr 18, 2014 at 0:13

answered Apr 18, 2014 at 0:03

geometrian

1,0251 gold badge9 silver badges16 bronze badges

\$\begingroup\$ It's a bit hard to see where you can pass through and where you can't. I have to say, I preferred the pipes ;) (to both this and my circular submission). \$\endgroup\$
– Martin Ender
Commented Apr 18, 2014 at 0:30
\$\begingroup\$ @m.buettner: I actually agree. If you change the i+=2 to i+=3, it might be more clear what's happening. \$\endgroup\$
– geometrian
Commented Apr 18, 2014 at 5:32

Add a comment |

Giuseppe Strafforello · Accepted Answer · 2014-04-17 19:07:14Z

6

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

answered Apr 17, 2014 at 19:07

Giuseppe Strafforello

691 bronze badge

17

\$\begingroup\$ If you can fit your code into the post, do that. Also, include a header like #Language(s) - Bytecount. If you only used ASCII characters in your code, you can get a nice bytecount here. A summary of what your code does, any insights you may have had, or any clever things you did might be a nice addition to your post. By the way, Darth Vader makes it very hard to see some of the lines. Finally, Welcome to Code Golf! \$\endgroup\$
– Rainbolt
Commented Apr 17, 2014 at 19:58
\$\begingroup\$ You learnt a bit of programming with your children and I learnt a bit of golfing. This is my first golfing and the result is still rather long. Byte count: Original: 55+6822=6877. A bit reorganised: 39+3131=3170 Golfed: 39+1593=1632 \$\endgroup\$
– BartekChom
Commented Jul 1, 2015 at 13:42

Add a comment |

Community · Accepted Answer · 2017-05-23 12:41:23Z

6

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:

YouTube 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).

edited May 23, 2017 at 12:41

CommunityBot

1

answered Apr 18, 2014 at 7:35

nneonneo

12.4k8 gold badges30 silver badges49 bronze badges

\$\begingroup\$ Isn't this exactly the same Brian's submission? (just a bit shorter) And so is your Bash answer? Then the question here is as well, is a maze without junctions still a maze? \$\endgroup\$
– Martin Ender
Commented Apr 18, 2014 at 9:12
\$\begingroup\$ nneonneo, +1 for proper and honest attribution of this great idea. @m.buettner The unprinted area produces unbranched labyrinths as you point out. However (and I am surprised no-one else has shown this yet) the printed area forms some interesting, non-trivial, branched mazes (see my answer.) I'm upvoting your maze too as it has the best defined start and end. Defining start and end on these diagonal mazes is not easy. \$\endgroup\$
– Level River St
Commented Apr 18, 2014 at 21:50
\$\begingroup\$ @m.buettner 1. The x86 binary is only 10 bytes at its smallest. 2. This is a well-honed algorithm, and is not at all original, nor was it intended to create a solvable maze. \$\endgroup\$
– Claudia
Commented Apr 20, 2014 at 2:43

Add a comment |

Geobits · Accepted Answer · 2014-04-18 19:32:43Z

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:

20x20

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

100x100

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;
    }
}

Brian · Accepted Answer · 2014-04-19 13:42:08Z

2

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"

Maze

edited Apr 19, 2014 at 13:42

answered Apr 19, 2014 at 10:22

Brian

1,2578 silver badges9 bronze badges

2

\$\begingroup\$ No I actually meant that you should swap the start and the end (start bottom right, end top left). As it stands its trivial, because due to the rules you just have to go down and right all the time to reach the end. \$\endgroup\$
– Martin Ender
Commented Apr 19, 2014 at 14:55
1

\$\begingroup\$ Even if the start and end are reversed, the maze has the (perhaps interesting) property that the correct path will only move up and left. The maze isn't trivial anymore, though, because there are many points at which you can go one of two ways. \$\endgroup\$
– Kevin
Commented Apr 19, 2014 at 16:30

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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:

Maze

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 22, 2014 at 9:17

Mohammad

2,01817 silver badges27 bronze badges

Add a comment |

Stack Exchange Network

Maze Generation [closed]

14 Answers 14

Mathematica, 144 132 bytes

C: 364 Bytes

Mathematica, 134 130 chars

Bash, 53 50 bytes

C: 265 253 Bytes

JavaScript (ES6), 174

ZX Basic - 54 characters

BBC BASIC, 18 Bytes

BBC BASIC, 35 Bytes / 107 95 Bytes

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

C: 235 Bytes

Commodore 64 BASIC - 38 bytes

Java : 700

ZX Basic - 281 characters

C- 244

Not the answer you're looking for? Browse other questions tagged
code-golf
popularity-contest
maze
or ask your own question.

Linked

Hot Network Questions

Maze Generation [closed]

14 Answers 14

Mathematica, 144 132 bytes

C: 364 Bytes

Mathematica, 134 130 chars

Bash, 53 50 bytes

C: 265 253 Bytes

JavaScript (ES6), 174

ZX Basic - 54 characters

BBC BASIC, 18 Bytes

BBC BASIC, 35 Bytes / 107 95 Bytes

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

C: 235 Bytes

Commodore 64 BASIC - 38 bytes

Java : 700

ZX Basic - 281 characters

C- 244

Not the answer you're looking for? Browse other questions tagged code-golfpopularity-contestmaze or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
popularity-contest
maze
or ask your own question.