Maze Generation

41

22

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.

imallett

Posted 2014-04-17T03:52:02.890

Reputation: 995

Question was closed 2016-08-16T01:10:36.900

What does "random-looking" mean? Can I get away without a single call to the rand()-equivalent of my function as long as the output looks like a mess? – Martin Ender – 2014-04-17T09:06:42.400

4Also "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 – 2014-04-17T09:59:20.430

5So is it really code-golf or is it rather popularity-contest? – l0b0 – 2014-04-17T11:37:10.623

2As 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 – 2014-04-17T13:11:50.423

3I 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 – 2014-04-17T16:41:09.633

I want this to be a popularity-contest. We'll see more inventive mazes that way. – Kevin – 2014-04-18T19:42:00.587

1You should also remove the [code-golf] tag then. I'm not sure it's going to go over so well though, since there are multiple golfed entries already. – Geobits – 2014-04-18T19:57:52.563

2@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 – 2014-04-18T20:34:52.653

I wouldn't mind a change of scoring system either, this is supposed to be a bit of fun. However it can't stay as it is now with both code-golf and popularity-contest, those are incompatible and close votes will start because of the ambiguous winning criterion. If you want to consider both, a better way is a formula combining votes and bytes, like this question: http://codegolf.stackexchange.com/questions/23581/eiffel-tower-in-3d

– Level River St – 2014-04-18T21:57:00.817

I'm not going to make a troll answer here, but I don't think that anyone is going to beat this (assuming it is a code golf).

– Isiah Meadows – 2014-04-20T02:40:03.037

Matter of fact, if it uses that algorithm, it should be immediately downvoted (it does not guarantee a start and end point). – Isiah Meadows – 2014-04-20T02:47:10.110

Having taken this far too seriously, I've now got 60 lines (2000 characters) of original Spectrum BASIC using a combination of Recursive backtracker and Hunter-Killer algorithms (http://www.astrolog.org/labyrnth/algrithm.htm), so no hope of winning a golf contest, but the mazes sure are purty.

– Brian – 2014-04-20T16:25:40.400

@impinball it DOES guarantee start/endpoint. If you consider the blank area to be the path, any point on the edge of the maze leads trivially without branching to another point on the edge (theoretically all paths on the edge of the maze could be only 2 squares long but the odds of this happening are minuscule, you normally get some nice long random walks.) On the other hand if you consider the printed area as path, fairly large mazes are formed (corollary of the fact that they must be bounded by unprinted areas) and you get interesting mazes, as seen in my answer. The problem is picking one. – Level River St – 2014-04-20T21:31:38.410

Answers

10

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

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

Dendrobium

Posted 2014-04-17T03:52:02.890

Reputation: 2 412

2You don't even need int p,int c. p,c is enough... – chubakueno – 2014-04-21T03:30:45.083

Ah, thanks for pointing that out – Dendrobium – 2014-04-21T03:35:36.857

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.

Martin Ender

Posted 2014-04-17T03:52:02.890

Reputation: 184 808

4This is pretty, and the code is short, but I would say it's toward the "trivial maze" end of the spectrum. – LarsH – 2014-04-17T16:32:26.437

@LarsH it was non-trivial enough for Dom Cobb :P. you can make it more complicated with one character: turn that last 9 into a 99 :P. But yes that's qualitatively the same thing. I think it does fulfil the specification though. If the OP changes the contest away from pure code-golf I'm willing to come up with something more interesting (e.g. paths that need you to go back inside a ring). – Martin Ender – 2014-04-17T16:44:33.080

2You'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. – LarsH – 2014-04-17T16:55:57.167

1@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. – Martin Ender – 2014-04-17T17:03:08.733

1@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. – Martin Ender – 2014-04-17T17:12:47.693

OK. I haven't analyzed their mazes in any detail. It's not obvious that they don't require significant backtracking, and that makes a difference; but maybe they're not much further down the continuum away from being trivial. – LarsH – 2014-04-17T17:42:30.310

1This 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. – imallett – 2014-04-18T00:06:25.420

1@IanMallett How is it not trivial? In each ring, you're just looking for the passage in the outer wall to the next outer ring. – Kaz – 2014-04-18T05:24:49.000

1-0, your maze isn't impossible like the one from Inception – Nick T – 2014-04-20T22:45:34.197

@NickT there is a possibility that there is another exit behind Cobb's hand ;) (I'd have to rewatch it to be sure). – Martin Ender – 2014-04-21T00:15:25.173

@m.buettner no, the 3rd ring is impossible to cross. https://www.youtube.com/watch?v=nKI432lCZaU#t=33s

– Nick T – 2014-04-21T01:59:27.767

@NickT, oh right, overlooked that. I suppose that would invalidate my answer though :P – Martin Ender – 2014-04-21T09:08:30.843

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

imallett

Posted 2014-04-17T03:52:02.890

Reputation: 995

I stared for 10 minutes at it, but I cannot find a start which matches an end? If there is, I'd really like to see the solution to the maze. I tried every entrance, but there were just dead ends… – bwoebi – 2014-04-17T11:20:43.953

8

@bwoebi MSPaint to the rescue! IMAGE

– Ceiling Gecko – 2014-04-17T11:34:58.363

@CeilingGecko Thank you. Effectively missed to look at the very topleft, not realized that could even be an entry – bwoebi – 2014-04-17T11:51:15.320

6

Note that my intention was to have the path be inside the pipes (as here).

– imallett – 2014-04-17T15:56:48.537

1@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. ;) – Martin Ender – 2014-04-17T16:48:27.043

1I'd be interested in seeing the un-golfed version of this code, if you have time. – LarsH – 2014-04-17T17:00:04.967

4While you wrote this you were a-maze-ing coder. – totymedli – 2014-04-17T19:15:16.487

@m.buettner sure; hence my clarification. – imallett – 2014-04-17T20:01:59.413

@LarsH Regrettably, I don't have the ungolfed version myself. It works by recursively digging a box into an empty space. The hardest part is probably the choice of direction, which works by permutation of an array (with, IIRC O(∞) runtime). – imallett – 2014-04-17T20:05:04.180

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

alephalpha

Posted 2014-04-17T03:52:02.890

Reputation: 23 988

7Nice maze… but I don't see any entrance which is connected to an exit…? – bwoebi – 2014-04-17T11:07:20.927

9I 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. – EagleV_Attnam – 2014-04-17T11:49:31.920

Are the lines (graph edges) supposed to be maze walls, or passages? I thought I knew, but now I'm not sure. – LarsH – 2014-04-17T16:58:04.943

@LarsH They are passages. – alephalpha – 2014-04-18T02:48:38.683

In that case, what are the exits and entrances in your first image? Are they all the nodes on the outside edge? – LarsH – 2014-04-18T04:24:28.463

1@LarsH The graph is connected, so you can just take two arbitrary nodes, one as entrance, the other as exit. – alephalpha – 2014-04-18T04:40:22.647

+1 This is, by far and away, the most interesting maze posted so far. – Kevin – 2014-04-20T04:15:20.253

13

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

Sample maze output

nneonneo

Posted 2014-04-17T03:52:02.890

Reputation: 11 445

2

I once figured this out: yes 'c=(╱ ╲);printf ${c[RANDOM%2]}'|bash. See this post

– gniourf_gniourf – 2014-04-19T13:41:00.777

5

This is based on an algorithm that cannot guarantee itself to be solvable, one that is many years old.

– Isiah Meadows – 2014-04-20T02:45:28.643

9

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>

edc65

Posted 2014-04-17T03:52:02.890

Reputation: 31 086

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 – 2015-10-11T13:09:38.893

1@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 – 2015-10-11T13:43:36.037

Wow, this is a-mazing! Shaved some bytes and got it down to 133 bytes: https://twitter.com/aemkei/status/889587308894326785

But all credits should go to you!

– aemkei – 2017-07-24T20:46:24.530

@aemkei 8 instead of '#', I can't believe I missed that at time – edc65 – 2017-07-26T17:00:05.833

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

Brian

Posted 2014-04-17T03:52:02.890

Reputation: 1 209

2Hm, 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? – Martin Ender – 2014-04-17T14:49:21.180

2"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. – LarsH – 2014-04-17T16:38:11.683

1@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. – LarsH – 2014-04-17T17:45:02.273

@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). – Martin Ender – 2014-04-17T19:09:50.153

+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! – LarsH – 2014-04-17T21:18:45.773

@LarsH true, but it also means that from each each entrance there is only a single path you can possibly take it will always lead to an exit. If you considered my mazes trivial, these are even more so. ;) – Martin Ender – 2014-04-17T21:50:44.970

@LarsH The criterion is met, ALL points on the edge lead to another point somewhere on the edge. But paths are trivial because there's no branches or dead ends. Proof: every square is divided into 2 triangles, each of which is a path fragment with exactly 2 entrances/exits. It's like a tangle of http://en.wikipedia.org/wiki/Rubik%27s_Snake I like this answer and I'd like to see the paths randomly colored. I'd also like to see a 3d version (in which 2 of the 6 possible orientations cause a block, depending on interpretatation.) The walls form a more challenging maze, with no guarantee of validity

– Level River St – 2014-04-17T22:13:54.097

@steveverrill: OK, if you define entrances/exits that way. Tho it's not very natural, e.g. to define the upper left corner as constituting 2 entrances/exits. If you require entrances and exits to be separate from each other (as per the usual understanding of the terms), a strictly alternating lattice of slashes wouldn't have any paths through it. – LarsH – 2014-04-18T04:21:39.123

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

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

Level River St

Posted 2014-04-17T03:52:02.890

Reputation: 22 049

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.

imallett

Posted 2014-04-17T03:52:02.890

Reputation: 995

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). – Martin Ender – 2014-04-18T00:30:21.707

@m.buettner: I actually agree. If you change the i+=2 to i+=3, it might be more clear what's happening. – imallett – 2014-04-18T05:32:26.540

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?

Giuseppe Strafforello

Posted 2014-04-17T03:52:02.890

Reputation: 69

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

– BartekChom – 2015-07-01T13:42:04.613

17

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!

– Rainbolt – 2014-04-17T19:58:50.293

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

nneonneo

Posted 2014-04-17T03:52:02.890

Reputation: 11 445

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? – Martin Ender – 2014-04-18T09:12:07.750

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. – Level River St – 2014-04-18T21:50:23.893

@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. – Isiah Meadows – 2014-04-20T02:43:48.737

5

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

Geobits

Posted 2014-04-17T03:52:02.890

Reputation: 19 061

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

Brian

Posted 2014-04-17T03:52:02.890

Reputation: 1 209

2No 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. – Martin Ender – 2014-04-19T14:55:36.227

1Even 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. – Kevin – 2014-04-19T16:30:36.613

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.

Mhmd

Posted 2014-04-17T03:52:02.890

Reputation: 2 019