• Random perfect maze generation, solution and rendering in 1011 bytes

Okay, this is the last one for a while. Really.

Unlike my previous 1k JavaScript demos, I really had to struggle to get this one into the 1024 byte limit. I'd already done all the magnification and optimization techniques I knew of so I had to bring in some things which were new to me from qfox.nl and Ben Alman and a few other places. This, combined with some major code refactoring, brought it down from 1.5k to just under 1. In the process, all possible readability was lost so here's a quick run through what it does and why.

First up, a bunch of declarations.

These are the colours used to draw the maze. Note, I used the shortest possible way to write each colour (red instead of #F00, 99 instead of 100). The value stored in the maze array (mentioned later) refers not only to the type of block it is but also to the index of the colour in this array, saving some space.

u = ["#eff", "red", "#122", "rgba(99,255,99,.1)", "#ff0"],

This is used for the number of blocks wide and high the maze is, the number of pixels per block, the size of the canvas and the redraw interval. Thanks to Ben Alman for pointing out in his article how to best use a constant.

 c = 21,

Here is the reference to the canvas. Mid-minification, I did have a bunch of function shortcuts here - r=Math.random, for instance - but I ended up refactoring them out of the code.

m = document.body.children[0];

For most of the time when working on this, the maze was wider than it was high because I thought that made a more interesting maze. When it came down to it, though, it was really a matter of bytesaving to drop the distinct values for width and height. After that, we grab the canvas context so we can actually draw stuff.

m.width = m.height = c * c;
h = m.getContext("2d");

The drawing function

The generation and solution algorithm is quite nice and all but without this to draw it on the screen, it's really just a mathematical curio. This takes a colour, x and y and draws a square.

l = function (i, e, f) {
  h.fillStyle = i;
  h.fillRect(e * c, f * c, c, c)
};

Designing a perfect maze

"You've got 1 minute to design a maze it takes 2 minutes to solve."
- Cobb, Inception.

Apologies for the unnecessary Inception quote. It's really not relevant.

Algorithmically, this is a fairly standard perfect maze generator. It starts at one point and randomly picks a direction to walk in then it stops picks another random direction and repeats. If it can't move, it goes back to the last choice it made and picks a different direction, if there are no more directions, all blocks have been covered and we're done. In a perfect maze, there is a path (and only one path) between any two randomly chosen points so we can make the maze then denote the top left as the start and the bottom right as the end. This particular algorithm takes 2 steps in every direction instead of 1 so that we effectively carve out rooms and leave walls. You can take single steps but it's actually more of a hassle.

For more on how this kind of maze-generation works, check out this article on Tile-based maze generation.

Blank canvas

This is a standard loop to create a blank maze full of walls with no corridors. The 2 represents the 'wall' block type and the colour #122. The only really odd thing about this is the code f-->0 which is not to be read 'as f tends to zero' but is instead 'decrement f by 1, is it greater than zero?'

g = function () {
  v = [];  //our stack of moves taken so we can retrace our steps.
  for (i = [], e = c; e-- > 0;) {
    i[e] = [];
    for (f = c; f-- > 0;) i[e][f] = 2
  }

By this point, we have a two-dimensional JavaScript array filled with 2s

Putting things in

  f = e = 1;    // our starting point, top left.
  i[e][f] = 0; // us, the zippy yellow thing

Carving out the walls

This is our first proper abuse of the standard for-loop convention. You don't need to use the three-part structure for 'initialize variable; until variable reaches a different value; change value of variable'. It's 'do something before we start; keep going until this is false; do this after every repetition' so here we push our first move onto the stack then repeat the loop while there's still a move left on the stack.

  for (v.push([e, f]); v.length;) {

P here is the list of potential moves from our current position. For every block, we have a look to see what neighbours are available then concatenate that cardinal direction onto the strong of potential moves. This was originally done with bitwise flags (the proper way) but it ended up longer. It's also a bit of a nasty hack to set p to be 0 instead of "" but, again, it's all about the bytes.

  p = 0;

Can we walk this way?

These are all basically the same and mean 'if we aren't at the edge of the board and we're looking at a wall, we can tunnel into it.'.

 if (e < 18 && i[e + 2][f] == 2) p += "S"
 if (e >= 2 && i[e - 2][f] == 2) p += "N";
 if (f >= 2 && i[e][f - 2] == 2) p += "W";
 if (i[e][f + 2] == 2) p += "E";

 if (p) { //    If we've found at least one move
  switch (p[~~ (Math.random() * p.length)]) { // randomly pick one

If there was anything to note from that last chunk, it would be that the operator ~~ can be used to floor the current value. It will return the integer below thye current value.

Take two steps

This is a nice little hack. Because we're moving two spaces, we need to set the block we're on and the next one to be 0 (empty). This takes advantage of the right-associative unary operator 'decrement before' and the right associativity of assignment operators. It subtracts 1 from e (to place us on the square immediately above) then sets that to equal 0 then subtracts 1 from the new e (to put us on the next square up again) and sets that to equal the same as the previous operation, i.e. 0.

  case "N":
      i[--e][f] = i[--e][f] = 0;
      break;

Do the same for s, w and e

    case "S":
      i[++e][f] = i[++e][f] = 0;
      break;
    case "W":
      i[e][--f] = i[e][--f] = 0;
      break;
    case "E":
      i[e][++f] = i[e][++f] = 0
    }

Whichever move we chose, stick that onto the stack.

    v.push([e, f])

If there were no possible moves, backtrack

  } else {
    b = v.pop(); //take the top move off the stack
    e = b[0]; // move there
    f = b[1]
  }
 }

End at the end

At the very end, set the bottom right block to be the goal then return the completed maze.

  i[19][19] = 1;
  return i
};

Solver

This is the solving function. Initially, it used the same algorithm as the generation function, namely 'collect the possible moves, randomly choose one' but this took too much space. So instead it looks for spaces north, then south, then west, then east. It follows the first one it finds.

s = function () {

Set the block type of the previous block as 'visited' (rgba(99,255,99,.1) the alpha value makes the yellow fade to green).

  n[o][y] = 3;

A bit of ternary background

This next bit looks worse than it is. It's the ternary operator nested several times. The ternary operator is a shorthand way of writing:

if ( statement A is true ) {
  Do Action 1
} else {
  Do Action 2
}

In shorthand, this is written as:

Statement A ? Action 1 : Action 2;

In this, however, I've replace Action 2 with another ternary operator:

Statement A ? Action 1 : ( Statement B ? Action 2 : Action 3 );

And again, and again. Each time, it checks a direction, if it's empty, mark it as visited and push the move onto our stack.

(n[o + 1][y] < 2) ?
  (n[++o][y] = 0, v.push([o, y])) :
    (n[o - 1][y] < 2) ?
      (n[--o][y] = 0, v.push([o, y])) :
        (n[o][y - 1] < 2) ?
          (n[o][--y] = 0, v.push([o, y])) :
            (n[o][y + 1] < 2) ?
              (n[o][++y] = 0, v.push([o, y])) :

If none of the neighbours are available, backtrack

                (b = v.pop(), o = b[0], y = b[1]);

Show where we are

Finally, set our new current block to be yellow

  n[o][y] = 4;

Are we there yet?

If we are at the bottom right square, we've completed the maze

  if (o == 19 && y == 19) {
  n = g();    //Generate a new maze
  o = y = 1; //Move us back to the top right
  s()     //Solve again

If we haven't completed the maze, call the solve function again to take the next step but delay it for 21 milliseconds so that it looks pretty and doesn't zip around the maze too fast.

  } else setTimeout(s, c);

Paint it black. And green. And yellow.

This is the code to render the maze. It starts at the top and works through the whole maze array calling the painting function with each block type (a.k.a. colour) and position.

    for (d in n) for (a in n[d]) l(u[n[d][a]], a, d)
  };

Start

This is the initial call to solve the maze. The function s doesn't take any arguments but by passing these in, they get called before s and save a byte that would have been used if they had been on a line themselves.

s(n = g(), o = y = 1)

Done

This little demo isn't as visually appealing as the Art Maker 1k or as interactive as the Spinny Circles 1k but it is quite nice mathematically. There are now some astounding pieces of work in the JS1K demo competition, though. I do recommend spending a good hour playing about with them all. Don't, however, open a bunch of them in the background at the same time. Small code isn't necessarily memory-efficient and you could quite easily grind your computer to a standstill.

Even though the rules for js1k only let me make one submission, I couldn't stop myself making another. This one is inspired by those pseudo-romantic pictures that you get all over tumblr that get reblogged endlessly (actually, it was inspired by the blog That Isn't Art by someone with the same opinion as myself).

It randomly creates a sentence, adds some softly-moving almost bokeh coloured-circles and look, I made an art! Wait for the sentence to change or click (or touch) to change it yourself.

Art Maker 1k

And of course, don't forget the original spinny-circles 1k

As described in detail previously, I've recently taken part in the JS1K competition where you have to squeeze something cool and clever into 1024 bytes of JavaScript. The quest to condense has become quite addictive and I found myself obsessing over every byte. This is the kind of stuff that the Closure Compiler does quite well automatically but there are some cases where you just need to get in there and manually tweak.

Here are some of the tricks I've picked up in my struggle for extreme minification:

Basic improvements

Use short variable names.

This one's fairly obvious. A more useful addition to this is:

Shorten long variable names.

If you're going to be accessing an element more than once, especially if it's a built-in element like 'document', you'll save a few bytes every time you reference it if you create a shortened reference to it.

  document.body.style.overflow="hidden"
  document.body.style.background="red"
  (74 characters)

can shorten to

  d=document;b=d.body;s=b.style;
  s.overflow="hidden";
  s.background="red"
  (69 characters)

and any references to s after are going to save 19 characters every time.

Remove whitespace

This one's so obvious, I don't need to mention it.

Set Interval

The extremely handy setInterval function can take either a function or a string. If you give it an anonymous function declaration:

  setInterval(function(){x++;y--},10);

You will use up more characters than if you give it just the inside of the function as a string:

  setInterval('x++;y--',10);

But the outcome will be the same.

Little-used aspects

Not many people use JavScript's scientific notation unless they're doing scientific stuff but it can be a great byte saver. The number 100 is equivalent to 1 * 10^2 which is represented in JavaScript as 1E2. That's not a great saving for 100 but 1000 is 1E3, 10000 is 1E4. Every time you go up a factor of 10, you save 1 byte.

Fight your good style tendencies

In the war against space, you have to bite the bullet and accept that you may need to sacrifice some of your hard-earned practices. But only this once. Don't get in to the habit, okay?

No zeroes

  0.5  = .5

Yeah, it looks ugly but it works and saves a byte.

Naked clauses

  if {
    :
    :
  } else y

The y looks so naked out there. No braces to keep it warm. But if you only have one statement in your else clause, you don't need them...

No semi-final. . . final-semi. . . Semi-colon. No final colon.

You don't need a semi-colon on your last line, even if it does make it look as though you've stunted its growth.

The final few bytes

Operator precedence

You don't need brackets. Brackets are handy for you as the programmer to remember what's going on when and to reduce ambiguity but if you plan correctly, most of the time you won't need brackets to get your arithmetic to work out.

  b.getMilliseconds()/(a*250) 
      is the same as
  b.getMilliseconds()/a/250 

Shorthand notation

  l=l+1;l=l%14;
  l++;l%=14;
  l=++l%14;

The three lines above are equivalent and in order of bytes saved.

Shorthand CSS

If you need to set some CSS values in your script, remember to pick the most appropriate short form. Instead of s.background='black', use s.background='#000' but instead of s.background='#F00', use s.background='red'. In the same vein, the statements margin="0px" and margin=0 mean the same but the latter saves bytes.

Don't be generic

One final thing to mention is that these little challenges are not the norm. If you find yourself trying to squeeze code down like this you're probably working on a very specific project. Use that to your advantage and see if there are any savings to be made by discarding your usual policies on code reuse. In the JS1K challenge, we're provided with a specific HTML page and an empty script tag. One good saving made here (and mentioned in my previous post) was the way I grabbed the reference to the canvas element. The standard method is to use the id assigned to the canvas.

  d.getElementById('c')

Which is a good generic solution. No matter what else was on the page, no matter what order stuff was in, this would return the canvas. However, we have a very specific case here and the canvas is always going to be in the same place - the first child of the body element. That means we can do this instead:

  b.children[0]

This makes use of the reference we grabbed to the body earlier. If the page were rearranged, this would stop working but as it won't, we've saved 8 bytes.

In conclusion

Yes, this is all quite silly but it's also fun and tricky. Attempting these kinds of challenges keep us developers mindful of what it is we actually do and that makes it an extremely productive silly hobby.

The Angry Robot Zombie Factory launched its second iPhone/iPad app this week. I haven't mentioned it much yet because I spotted a minor typo in the final version after it had been approved so I submitted an update immediately. To get an early copy (like those misprinted stamps where the plane is upside down), go check out The Elementals. It's free, too. It's a simple, cartoonish periodic table.

Yesterday, the 1k JavaScript demo contest (#js1k) caught my eye. The idea is to create something cool using 1024bytes of JavaScript or less. I rootled around in the middle of The Elementals, grabbed the drawing function and 20 minutes later had made my entry.

The code I submitted is quite minified but isn't obfuscated. When it's unfolded, you can follow the flow fairly easily.

var d = document,
b = d.body,
s = b.style,
w = innerWidth,
h = innerHeight,
v = b.children[0],
p = 2 * Math.PI,
Z = 3,
x = tx = w / 2,
y = ty = h / 2;

The above is a bunch of declarations. Using things like d = document and b = d.body allows reuse later on without having to resort to the full document.body.style and saves a bunch of characters. When you've got such a small amount of space to play with, every character counts (mind you, the ZX81 only had 1k of RAM and look what you could do with that). Now that I'm looking at it, I think I could have tidied this a bit more. Darn. The sneaky bit about this code is the way we grab the reference to the canvas. The code d.getElementById('c') uses 21 characters but if we look at the provided HTML, we can use the fact that the canvas is the first child of the body element. The code b.children[0] uses 13 characters instead.

s.margin = "0px";
s.background = "black";
s.overflow = "hidden";
v.width = w;
v.height = h;
t = v.getContext("2d");

This sets the provided canvas to be the full width and height of the window then grabs the drawing context of it so we can make pretty pictures.

zi = function () {
 Z++;
 Z %= 14
};
m = function (X) {
 return (X * 200) % 255
};

Functions to be reused later. zi increases the number of spinning circles and is used by onmousedown and ontouchstart (oh yes, it works on the iPad, too). m is a mapping of the index of the circle to a colour. The 200 is arbitrary. I played about a bit until I found some colour combinations I liked.

 d.ontouchstart = function (e) {
 zi();
 tx = e.touches[0].pageX;
 ty = e.touches[0].pageY
};
d.onmousemove = function (e) {
 tx = e.clientX;
 ty = e.clientY
};
d.onmousedown = zi;

Setting the event handlers.

function r() {
 t.globalCompositeOperation = 'lighter';

I played about with the various composite operations. Lighter seemed the nicest.

 t.clearRect(0, 0, w, h);
 t.save();
 x = x + (tx - x) / 20;
 y = y + (ty - y) / 20;
 t.translate(x, y);

Originally, the circles followed the mouse pointer exactly but it lacked any life. By adding in this bit where the movement is delayed as if pulling against friction, it suddenly became a lot more fun and dynamic.

 var c = new Date();
 for (var i = 1; i <= Z; i++) {
  t.fillStyle = 'rgba(' + m(i) * (i % 3) + ', ' + m(i) * ((i + 1) % 3) + ',' + m(i) * ((i + 2) % 3) + ', 0.5)';
  t.beginPath();
  t.rotate((c.getSeconds() + i) / (i / 4) + (c.getMilliseconds()) / ((i / 4) * 1000));
  t.translate(i, 0);
  t.arc(-10 - (Z / 5), -10 - +(Z / 5), 100 - (Z * 3), 0, p, false);
  t.fill()
 }

Erm. Yeah. In essence, all this does is figure out where to draw the circles, how big and what colour. It looks worse than it is. Line-by-line, it translates to:

1. Find out the current time
2. For each circle we want to draw,
3. Pick a colour based on the index of the circle
4. Start drawing
5. Turn by some amount based on the time and the index
6. Move by a small amount based on the index
7. Actually draw, making the circles smaller if there are more of them.
8. Fill in the circle with the colour.
9. Right curly bracket.

 t.save();
 t.fillStyle = "white";
 for (var i = 1; i <= Z; i++) {
  t.beginPath();
  t.rotate(2);
  t.translate(0, 28.5);
  t.arc(-120, -120, 5, 0, p, false);
  t.fill()
 }
 t.restore();
 t.restore()
}

This does pretty much the same as the one above but always the same size and always the same colour. The t.save and t.restore operations throughout mean we can add the transformations onto each other and move stuff relative to other stuff without messing up everything. Goshdarn, that was technical.

setInterval(r, 10);

Kick it all off.

That make sense? Good. Now go make your own js1k entry and submit it. Then download The Elementals. Or Harmonious.