404 Maze
How I came to make an 8-bit inspired maze-like 404 page, including a walk through of the javascript code.
As part of my work at the State Library of NSW’s DX Lab we were overhauling the DX Lab website itself (as described here) and the opportunity came up to make an ‘interesting’ 404 page for the site. Assuming you aren’t reading this after the site has been changed again you will be able to see it here. But just in case, here is a video of it:
So how does it work? Why did I do it?
Let’s deal with why first and get to the fun, juciy code second. Growing up in the 1980s seems to have infected me with a love of pixellated, 8-bit aesthetics. My brother and I were lucky enough to have a Commodore 64 home computer and played many a game on its 320 x 200 pixel, 16 colour output. I got right into low-level coding on that machine, disassembling game code, reading hexadecimal and scribbling copious notes in exercise books to find out how things worked, subsequently writing my own demos.
It was a time of Rubik’s Cubes, Devo’s ‘Whip It’ on the radio and discovering fun mathematical curiosities like the colourful, crinkly-edged fractals of the Mandelbrot Set and the cellular automata of Conway’s Game of Life.
With these as influences percolating in the subconscious, I had just finished working on another arguably pointless (read: creative) part of the site refresh: the shuffling text of the titles. For them I had taken inspiration from ‘procedural’ graphic designer Andreas Gysin’s ingenius ASCII art shuffling animation. Poking around some of his older work I was enjoying the interactive, animated page headers, especially this one where where a series of blobs wander randomly under the title, leaving trails of various densities.
Somehow these wandering paths reminded me of mazes. Perhaps also because I had, at the suggestion of Seb Chan, finally got round to reading the awesome book 10 PRINT in which the authors:
“… consider randomness and regularity in computing and art, the maze in culture, the popular BASIC programming language, and the highly influential Commodore 64 computer.”
I felt there is a parallel between being lost in a maze and being lost on the web, which is of course how one ends up on a 404 page. So that is why I decided to do something maze-like for the page.
On to how, then.
I have always found mazes fascinating, especially the algorithms relating to creating and solving them, and so I started looking in to maze generation algorithms in more detail. I stumbled across this great page by Jamis Buck (who also has written this excellent book) which not only describes how a wide range of algorithms work, but also has live, in-page demos so one can see them in action. Have a read and ask yourself about what you have seen above. Can you guess how it works?
It wasn’t until I read the Wikipedia entry on Maze Generation Algorithms that I discovered, much to my amazement (no pun intended) that the algorithm for Conway’s Game of Life could be coaxed into making maze-like patterns by modifying its rule set slightly. This really blew my mind! Despite all my years of nerdy dabbling in coding, mazes, algorithms, Conway’s Game of Life, I had NEVER heard of this. What a glorious overlap; it was destiny!
The DX Lab site is written in Node/React so all the code I wrote for this 404 page is just javascript. It was hastily written and much of the code is inelegant, but them’s the breaks. There is a canvas element into which our maze will be drawn using either 5px or 10px sized squares (depending on the size of the screen). These are our oversized pixels. The grid of content that will be drawn into the canvas using these pixels is stored in an array of arrays (or a two dimensional array, if you prefer). Here is an example data structure for a five wide, four tall maze:
Our grid or maze will be somewhat bigger, depending on how big the screen is. The values stored at each point in the array represent whether the cell is drawn or not. Above we see only 0 and 1 as values, but in practice our maze uses a wider range of integers. Zero still represents an empty cell, and any value above that is a living cell, however the number represents a colour. A simple lookup table is used to map the integer values to CSS hex colours.
As a big fan of lichen and fungal/bacterial blooms I decided to try and emulate them by adding colour to the maze. This works by ‘ageing’ the cells. When a new cell is brought to life, it starts off with a high value (which is mapped to the brightest pink) and with every ‘generation’ our Game of Life maze evolves through, the value stored in the array is decreased by one, until it gets to 1, which maps to the grey colour and that is where is stays. To my mind this manages to imbue the resulting structure with edges reminiscent of lichen or even a kind of low-res Mandelbrot set.
If you take a careful look at the what is happening on the page you will notice three ‘phases’:
- Setup
- Building/growing the maze
- Blobs run around the maze
Setup
All bells and whistles aside, we actually do need to tell the user it is a 404 page and so in the setup phase the number ‘404’ is etched into the centre of the canvas surrounded by a border of randomly on or off cells. The border forms the seed from which the maze will grow.
So let’s have a look at the first bit of code, which comes after some boring variable definitions:
The first function is pretty straightforward:
The next function draw404() creates the data for the numerals reading ‘404’ as this gets etched as pixels into the centre of the array during the setup phase. As you can see above, this area is designated a ‘no-go area’ so that our maze evolving algorithm doesn’t mess with the 404. Next seedMaze() picks some of the cells just outside that area and sets them to ‘alive’. Our maze will grow from these initial cells.
Once all that is done, the setInterval() repeatedly runs the update() function.
Here we can see that since we start off in the ‘building’ phase, each frame the evolve() function is called followed by the updateMaze() function. The latter simply takes the existing state of the maze 2D array and (re-)draws the contents of the canvas element to resemble it. Note the edgeCols[] lookup for the colour of the cell, depending on the value at that point in the maze 2D array:
The evolve() function is where all the juicy Game of Life (with modified rule set) magic happens:
So a word here about these modified rule sets. In the standard Conway’s Game of Life, a living cell will stay that way if it has 2 or 3 of its 8 neighbours also alive. More than that and it becomes a dead/empty cell (due to overcrowding) and less than that it ‘dies’ from loneliness. An empty cell may come alive if it has exactly 3 neighbours. This can be written B3/S23 which I assume means ‘born’ if 3, ‘survive’ if 2 or 3.
Now the ‘maze-like’ rule sets I found on Wikipedia are B3/S1234 and B3/S12345 and they make slightly different ‘shaped’ structures, so you will see towards the end of the evolve() function above I switch back and forth between the two every three generations in an attempt to avoid the resulting maze from looking too much like one or the other.
BUG!!!! 🐛🐛🐛
So the process of writing this Medium article has lead me to discover a bug in my code which has existed in production for over two years! Did you notice it?
It is in the implementation of the Conway’s Game of Life algorithm above…
What the algorithm is mean to do is this: for each cell we are considering, if it is ‘alive’, does it have enough neighbours to stay so? OK great, let it live on to the next generation, but if not KILL IT. (And then handle the case where a cell is not alive by checking if the it has the magic number of neighbours to come to life).
If you check the evolve function above, where the ‘***’ is (line 36) there should be an else clause that deals with an alive cell either being under- or over-crowded and thus transitioning to an un-alive cell… I missed that out somehow. Whoops!
Interestingly it doesn’t seem to make much difference. I mocked up a quick page where I added in that else clause: check out the results. Pretty much indistinguishable from the version with the bug. I guess this suggests that the B3/S12324 and/or B3/S12345 rule sets don’t result in many cases of live cells dying from under- or over-crowding, probably due to their propensity to create corridor-like structures. Lucky for me…
Blobs
So. Phase 3. When the maze evolves to a certain size we switch from the ‘building’ mode and unleash the blobs! What is a maze without things to run round in it?
Actually there are a couple of things that happen first. I felt the completion of the maze build should be punctuated somehow. Inspired by the Commodore-64 game Boulderdash in which the background flashes once to indicate when the player has collected enough diamonds and can make their way to the exit and move on to the next level, I decided to try the same thing out.
The blinkIt() function sets the background colour to our feature pink and sets a timer to switch it back.
Next the curiously named makeExtraHoles() is called. So it turns out that the maze-like structures that Conway’s Game of Life with the modified rule set creates are not inherently navigable. There are lots of blocked off sections and isolated tunnels and so on. So I decided to blow some random holes in my maze. There are no rules!
Last we pick some random locations for our roaming blobs to start from:
Note that the blobs each have a direction they are travelling. Also note that while loop. It makes sure the blobs aren’t located on a wall of the maze, and that they seem to be located inside the maze (ie have some neighbouring cells that ARE walls).
Blob party!
So now, since we are no longer building, everytime the update() function runs it will call moveBlobs() and then updateBlobs(). The move function is quite simplistic (you can check it out below) and the blobs end up moving essentially randomly. I was tempted to make them use more ‘smarts’ and involve maze solving algorithms, but by then I’d spent about as much time on the page as was available and decided to just calm the hell down. The update function is poorly named (like the updateMaze() function) and simply draws the blobs in the canvas.
And that is pretty much where things stay for our unnecessarily complicated 404 page. Unless of course you re-size the window or click anywhere, in which case we start all over again!
Thanks for reading. Here is the whole lot of code in one go:
