Maze Generation in Thirteen Bytes (2012) | Hacker News Reader

Maze Generation in Thirteen Bytes (2012)

trixter.oldskool.org

102 pointspanic21 comments

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

The link you provided suggests it is a 'simple maze'? What is a true maze by your definition?

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

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/

    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.

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.

Here is thirteen bytes of your program:

    var d = docum

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.

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.

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

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.

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

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.

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.

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.

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

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

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?

What constitutes a maze? Enforced solvability?

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.

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?

Mike Bostock's visualizations of maze-creation algorithms (via spanning tree) are absolutely beautiful:

http://bost.ocks.org/mike/algorithms/#maze-generation

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.

Reply on news.ycombinator.com