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