5 ms·

Maze Generation in Thirteen Bytes (2012)

102 points by panic 12y ago

awjr 12y ago
I grew up with this stuff. Such a long long time ago since I've played at this level of optimisation. Very very very clever.
mxfh 12y ago
As the article states, it's impressive but The output isn’t really a true maze. It looks more like the simplest possible implementation of a diagonal type Truchet tiling algorithm with a single tile and 2 unique rotations: "\", "/" rendered as ╲ ╱ http://en.wikipedia.org/wiki/Truchet_tiles#Diagonal http://en.wikipedia.org/wiki/Truchet_tiles#Diagonal
- acjacobson 12y ago
  The link you provided suggests it is a 'simple maze'? What is a true maze by your definition?
  - mxfh 12y ago
    One that has at least an entry and a connected exit or some defined goal somewhere in the maze with a connection to the exit. For proper maze generation see: http://en.wikipedia.org/wiki/Maze_generation_algorithm http://en.wikipedia.org/wiki/Maze_generation_algorithm Here's a simple JS snippet that overwrites any loaded page in the browser when pasted into the console. Or live here: http://jsfiddle.net/15fmx4L7/ http://jsfiddle.net/15fmx4L7/ var d = document, tiles = ["\u2571","\u2572"], i = 0, s = 12, b, s, l; d.open(); d.write("<html><body>"); b = d.body; b.style.cssText = "font-size:" + s + "px;" b.style.cssText += "word-wrap:break-word;padding:0;margin:0;line-height:100%"; l = Math.floor(b.clientHeight/s) * Math.floor(b.clientWidth/s); while (i < l) { d.write(tiles[Math.round(Math.random())]); i++; } d.write("</body></html>") d.close(); It's dead simple and relies a lot on known output formatting, which requires some CSS fluff. The core function though is a simple stream of random code points from a set of two, really nothing spectacular to see here: while (1) {document.write(["\","/"][Math.round(Math.random())]);} This does not generate a maze, it's a pure tiling side effect, which might generate by chance a tunnel through the pattern. If you look closely you'll find no T-type intersections or any other kind of path bifurcation.
    - RodgerTheGreat 12y ago
      In K you could do: {x}{`0:"/\\"1?2;x}/1 {x}{...;x}/1 is essentially while(true) {}. `0: writes values to standard output. "/\\"1?2 indexes into a two element array given the result of selecting one random result from the numbers up to but excluding 2.
    - DanBC 12y ago
      Here is thirteen bytes of your program: var d = docum
- tokenrove 12y ago
  Left as an exercise to the reader: write a program to interpret the output and massage connectivity until it satisfies whatever pedantic definition of "maze" you prefer.
userbinator 12y ago
My favourite part about this article is that his original solution of 13 bytes was quickly beaten down to 10 by some friendly competition in the comments. Sizecoding may not have any real practical use in most cases, but I think it's still a good form of mental exercise since the type of creative thinking it requires is a useful skill in thinking about other problems too.
- Trixter 12y ago
  While I was the beat-down recipient, it was my favorite part too. I have no problem getting beaten if I'm laughing the entire time (same goes for getting my ass handed to me in 1st-person shooters).
rilita 12y ago
This code displays forward slash and backslash randomly over the entire screen. This may look a bit like a maze, but it is not. Title should read "How to display random garbage to the screen as slashes in 13 bytes". Still impressed?
- lkbm 12y ago
  What constitutes a maze? Enforced solvability?
  - tromp 12y ago
    Forming a spanning tree; or equivalently, having a unique path between any two cells. Sometimes a few additional connections (adding cycles to the spanning tree) are considered ok.
    - theoh 12y ago
      Really, multiply connected mazes are more interesting and more aesthetically pleasing. A question, though. If, in 2D, having all walls in one piece is simply connected, and having some islands is multiply connected, what are the possible types of 3D maze (let's call it a cave). You can obviously have simply connected walls, or multiply connected walls (floating shells of rock) but what name would you give the type that has some looping paths but no floating rocks? Do we talk about genus?
    - bufordsharkley 12y ago
      Mike Bostock's visualizations of maze-creation algorithms (via spanning tree) are absolutely beautiful: http://bost.ocks.org/mike/algorithms/#maze-generation http://bost.ocks.org/mike/algorithms/#maze-generation
- CamperBob2 12y ago
  You were modded down, but I tend to agree. Randomly printing slash characters is not a valid way to generate anything that could be called a "maze," and it's consequently not a very interesting thing to optimize. I suppose that if you fed it with a source of true randomness and let it run long enough, the output would eventually contain all possible mazes with unit corridor width. It may be more precise to say it can't generate a labyrinth, or a dungeon with rooms.
peter303 12y ago
reminds me old punchcard computer homework days where students competed on the minimal number of punchcards for a homework problem
jhallenworld 12y ago
My USENET signature.. int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0) +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2 ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
- deleted 12y ago
  [deleted]
boomlinde 12y ago
I love that each step further down in size has you thinking "nope, it won't get smaller". Here is a C64 version in 13 bytes: .pc=$7c loop: lda $d012 ; content of $d012 into accumulator lsr ; shift accumulator right, moving lsbit into carry lda #$cd ; value of diagonal line into accumulator adc #0 ; add 0 + carry. if carry, accumulator will hold $ce, opposite diagonal line jsr $ffd2 ; call CHROUT in rom; outputs character in accumulator on device bcc loop ; branch to loop if carry is cleared; an effective branch-always which saves 1 byte from a jump I'm sure it can be golfed further with the illegal opcodes that I am not familiar with. EDIT: Shed one byte, added comments, moved the origin to $7c which means that adding 2 bytes of header will make it a runnable C64 PRG.
- PythonicAlpha 12y ago
  I'm sure it can be golfed further with the illegal opcodes that I am not familiar with. Possible. But not necessarily. Long time ago I reviewed the many illegal opcodes of the 6502. Many are simply doing nothing and most of them are not useful at all. The few that are useful give little benefits, because they can be used in very very few situations. I finally did not use them, since I don't wanted to break compatibility with 6502 successors (which where very few, finally).
  - boomlinde 12y ago
    I mean "sure" only as a manner of speaking, not to say that I am absolutely certain. The challenge for me in using the illegal opcodes is internalizing them and recognizing the situations where they can actually be used effectively to save a byte or a cycle. When writing code for platforms with very little memory or harsh time constraints, they can certainly save you headaches. Something like LAX for example can be used to do an y-indexed load to the x register, which often times can save you an accumulator transfer when doing doubly indirect loads.
    - PythonicAlpha 12y ago
      Sorry for the inconvenience. I am not familiar with the details of English language, so sometimes I just understand things wrong. Yes, there are some interesting opcodes too, but I found their usage so limited, that it was not worthwhile to drop compatibility. Of course, with a fixed setting, where you need every byte .... but I must say, that for me today it is just academic, since I also do no embedded programming today. With computers of today, I still think, that optimizing is worthwhile, but not to that degree, that breaking compatibility makes sense.

102 points by panic 12y ago

awjr 12y ago

I grew up with this stuff. Such a long long time ago since I've played at this level of optimisation. Very very very clever.

mxfh 12y ago

As the article states, it's impressive but The output isn’t really a true maze. It looks more like the simplest possible implementation of a diagonal type Truchet tiling algorithm with a single tile and 2 unique rotations: "\", "/" rendered as ╲ ╱ http://en.wikipedia.org/wiki/Truchet_tiles#Diagonal http://en.wikipedia.org/wiki/Truchet_tiles#Diagonal

acjacobson 12y ago
The link you provided suggests it is a 'simple maze'? What is a true maze by your definition?
- mxfh 12y ago
  One that has at least an entry and a connected exit or some defined goal somewhere in the maze with a connection to the exit. For proper maze generation see: http://en.wikipedia.org/wiki/Maze_generation_algorithm http://en.wikipedia.org/wiki/Maze_generation_algorithm Here's a simple JS snippet that overwrites any loaded page in the browser when pasted into the console. Or live here: http://jsfiddle.net/15fmx4L7/ http://jsfiddle.net/15fmx4L7/ var d = document, tiles = ["\u2571","\u2572"], i = 0, s = 12, b, s, l; d.open(); d.write("<html><body>"); b = d.body; b.style.cssText = "font-size:" + s + "px;" b.style.cssText += "word-wrap:break-word;padding:0;margin:0;line-height:100%"; l = Math.floor(b.clientHeight/s) * Math.floor(b.clientWidth/s); while (i < l) { d.write(tiles[Math.round(Math.random())]); i++; } d.write("</body></html>") d.close(); It's dead simple and relies a lot on known output formatting, which requires some CSS fluff. The core function though is a simple stream of random code points from a set of two, really nothing spectacular to see here: while (1) {document.write(["\","/"][Math.round(Math.random())]);} This does not generate a maze, it's a pure tiling side effect, which might generate by chance a tunnel through the pattern. If you look closely you'll find no T-type intersections or any other kind of path bifurcation.
  - RodgerTheGreat 12y ago
    In K you could do: {x}{`0:"/\\"1?2;x}/1 {x}{...;x}/1 is essentially while(true) {}. `0: writes values to standard output. "/\\"1?2 indexes into a two element array given the result of selecting one random result from the numbers up to but excluding 2.
  - DanBC 12y ago
    Here is thirteen bytes of your program: var d = docum
tokenrove 12y ago
Left as an exercise to the reader: write a program to interpret the output and massage connectivity until it satisfies whatever pedantic definition of "maze" you prefer.

userbinator 12y ago

My favourite part about this article is that his original solution of 13 bytes was quickly beaten down to 10 by some friendly competition in the comments. Sizecoding may not have any real practical use in most cases, but I think it's still a good form of mental exercise since the type of creative thinking it requires is a useful skill in thinking about other problems too.

Trixter 12y ago
While I was the beat-down recipient, it was my favorite part too. I have no problem getting beaten if I'm laughing the entire time (same goes for getting my ass handed to me in 1st-person shooters).

rilita 12y ago

This code displays forward slash and backslash randomly over the entire screen. This may look a bit like a maze, but it is not. Title should read "How to display random garbage to the screen as slashes in 13 bytes". Still impressed?

lkbm 12y ago
What constitutes a maze? Enforced solvability?
- tromp 12y ago
  Forming a spanning tree; or equivalently, having a unique path between any two cells. Sometimes a few additional connections (adding cycles to the spanning tree) are considered ok.
  - theoh 12y ago
    Really, multiply connected mazes are more interesting and more aesthetically pleasing. A question, though. If, in 2D, having all walls in one piece is simply connected, and having some islands is multiply connected, what are the possible types of 3D maze (let's call it a cave). You can obviously have simply connected walls, or multiply connected walls (floating shells of rock) but what name would you give the type that has some looping paths but no floating rocks? Do we talk about genus?
  - bufordsharkley 12y ago
    Mike Bostock's visualizations of maze-creation algorithms (via spanning tree) are absolutely beautiful: http://bost.ocks.org/mike/algorithms/#maze-generation http://bost.ocks.org/mike/algorithms/#maze-generation
CamperBob2 12y ago
You were modded down, but I tend to agree. Randomly printing slash characters is not a valid way to generate anything that could be called a "maze," and it's consequently not a very interesting thing to optimize. I suppose that if you fed it with a source of true randomness and let it run long enough, the output would eventually contain all possible mazes with unit corridor width. It may be more precise to say it can't generate a labyrinth, or a dungeon with rooms.

peter303 12y ago

reminds me old punchcard computer homework days where students competed on the minimal number of punchcards for a homework problem

jhallenworld 12y ago

My USENET signature.. int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0) +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2 ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}

deleted 12y ago
[deleted]

boomlinde 12y ago

I love that each step further down in size has you thinking "nope, it won't get smaller". Here is a C64 version in 13 bytes: .pc=$7c loop: lda $d012 ; content of $d012 into accumulator lsr ; shift accumulator right, moving lsbit into carry lda #$cd ; value of diagonal line into accumulator adc #0 ; add 0 + carry. if carry, accumulator will hold $ce, opposite diagonal line jsr $ffd2 ; call CHROUT in rom; outputs character in accumulator on device bcc loop ; branch to loop if carry is cleared; an effective branch-always which saves 1 byte from a jump I'm sure it can be golfed further with the illegal opcodes that I am not familiar with. EDIT: Shed one byte, added comments, moved the origin to $7c which means that adding 2 bytes of header will make it a runnable C64 PRG.

PythonicAlpha 12y ago
I'm sure it can be golfed further with the illegal opcodes that I am not familiar with. Possible. But not necessarily. Long time ago I reviewed the many illegal opcodes of the 6502. Many are simply doing nothing and most of them are not useful at all. The few that are useful give little benefits, because they can be used in very very few situations. I finally did not use them, since I don't wanted to break compatibility with 6502 successors (which where very few, finally).
- boomlinde 12y ago
  I mean "sure" only as a manner of speaking, not to say that I am absolutely certain. The challenge for me in using the illegal opcodes is internalizing them and recognizing the situations where they can actually be used effectively to save a byte or a cycle. When writing code for platforms with very little memory or harsh time constraints, they can certainly save you headaches. Something like LAX for example can be used to do an y-indexed load to the x register, which often times can save you an accumulator transfer when doing doubly indirect loads.
  - PythonicAlpha 12y ago
    Sorry for the inconvenience. I am not familiar with the details of English language, so sometimes I just understand things wrong. Yes, there are some interesting opcodes too, but I found their usage so limited, that it was not worthwhile to drop compatibility. Of course, with a fixed setting, where you need every byte .... but I must say, that for me today it is just academic, since I also do no embedded programming today. With computers of today, I still think, that optimizing is worthwhile, but not to that degree, that breaking compatibility makes sense.