Advent of Code Goes 8-bit

Every December, developers the world over wait a-tremble to open their advent calendars. But there’s no chocolate involved: Advent of Code is an annual series of daily programming challenges, intricate and deserving of contemplation; fiendishly designed to test the mettle of our algorithm and data structure knowledge. And, if you get up at 5am, the chance of appearing on the leaderboard!

This year, during one of our weekly tech lunches, a colleague showed off a couple of AoC challenges he’d completed. One of them, annoyingly, he’d solved with a spreadsheet.

The TL;DR is: A number of stars have starting coordinates, and velocities. They move once per second, and will eventually spell out a code. But only for a single frame, and you could be waiting a while.

I left that tech lunch wanting to solve the problem with code, and reminded myself that picking the right tool for the job was important.

Not knowing what any of those were, I went with PICO-8. Think of it as an emulator for an 80s console that never existed, in which you can edit the code, sprites, level maps, music and sfx, and play or edit other people’s games. I knew my goal: I wanted to see the elves’ secret message spelled out in glorious 8-bit pixels. I needed to create the elves’ universe.

Creating the Universe

It turns out, building a universe MVP is surprisingly easy. I started with a small list of stars, each with predictable paths. PICO-8 uses a subset of Lua, and this snippet shows a list of maps, assigned to a global variable:

With the data in place, we can write code to move the stars around the screen:

As part of the PICO-8 game loop, we have three main callback functions in which we can create our program. Starting in the `_init()` function, I set up some state.

In the `_update()` function, we cycle through the list of stars, and add their x/y velocity to each coordinate. Then we add one to our timer.

Then in the `_draw()` function, it’s just a matter of displaying the stars. I wanted `{0,0}` to be the centre of the screen, so I call a helper function to add half the screen’s width/height to each pair of coordinates, and then use `pset` to draw a pixel at that point. And with that done, I’ll just hit `Cmd-R`, and…

It works! Buoyed along by my hubris, I plugged in my challenge input (which as any AoC afficionado knows, is often ridiculously large).

Not so good. The stars are barely moving. I pondered for a while. Eventually I realised, that to decode the message from the elves, I needed to be able to control time.

Controlling Time

Starting small, I thought two things would be most immediately useful: pausing time, and being able to set the start frame. Fortunately, both were easy.

To pause, I just set a global variable, and then wrapped a conditional around my ` _update()` logic:

Binding this value to a keypress is also simple. PICO-8 only has six keys available on its ‘joypad’: the arrow keys, z, and x, and in this case pressing z will pause

I also added the ability to set the starting frame:

Well that sort of helped, but by the time the stars collided my zoom level was too far away to see any detail. And zooming in closer was a matter of changing around numbers in variables and hoping for the best. I sort-of made progress, but it felt like working out the elves’ code this way might lead too closely to the edges of sanity.

I realised, sensibly, that not only did I need to control time, I needed to control space itself.

Controlling Space Itself

After a lot of mulling and trying out terrible ideas, I realised I needed a camera, and the stars should be on a fixed plane. As it’s a single object with several attributes, I made a map to hold its state, and set a couple of constants:

I managed, despite my lack of mathematical aptitude, to transcribe into Lua a formula I found for translating 3d points onto a 2d plane:

With this in place, I can define button controls to pan and zoom the camera:

Had it not been for a subtle bug I would have found the secret code at this point. I could find the frame with the message, but it was strangely garbled. Missing some parts. I got annoyed, and decided to take my mind off it by programming something pointless but aesthetically pleasing. You may notice in the screenshots after this, that the stars sparkle.

The bug turned out to be due to the limits of PICO-8 itself. The SDK is full of purposeful constraints, and one of those is that the maximum integer limit is 32676. That was nowhere near enough for my challenge input, so I swallowed my pride, and built a Ruby script to run through the first steps for me, until the numbers were safely in range. Don’t @ me.

With fresh data in place, I gingerly pressed `Cmd-R`, and sat back to marvel at the gentle ballet of the elvish heavens:

It’s… beautiful
I can zoom! I can pan around the infinite ouroborous of starfields!
And I can speed up time or play it in reverse!
Wait… what happened? Did it implode? Lucky I built that time machine…

And there it was, the elves’ secret code, glistening coolly in the night sky. Sure, it had taken me a lot longer than Tom and his damn spreadsheet, but I’d had fun, learned some maths, and made a cool thing that was fun to play with.

And in the moments when I was confounded by some problem, I could work on graphical tweaks, or add to the soundtrack, and inevitably the original thing would come to me and I’d go back to it.

It’s easy as engineers, building software, to forget that we’re part of a creative endeavour, magicking up things where once there was nothing. And people in other creative fields often employ false constraints, from the jazz musician sticking to only one scale or mode when improvising, to the re-emergence in popularity of Brian Eno and Peter Schmidt’s Oblique Strategies as fodder for ideas.

It’s counter-intuitive, but freeing up brain cycles by being constrained allows you to concentrate more on the heart of whatever problem you’re trying to solve. And this is where PICO-8 excels — you’re limited in pretty much every aspect, and it’s so much fun. If you don’t believe me, have a look at some of the amazing things that people smarter than me are making with it:

Finally, the full code is here, and you can ‘play’ the ‘game’ here, with the following keys (whilst listening to my 8-bit rendition of the Dance of the Sugar Plum Fairy):

`z`                  : pause/play
`up/down/left/right` : pan
`x + up/down` : zoom
`x + left/right` : when paused, skip 1 second.
when playing, skip 50 seconds.
Just a hint: this uses the sample input from the AoC website, and winds back in time 5000 steps. The message is at step 3, so you'll need to zoom in, and get ready with the pause key to catch the message :)

Thank you for reading, and please let me know in the comments if you’ve come up with any creative solutions to Advent of Code challenges!