Making the Megademica soundtrack (Part I)

 ,_,                                                        __
 (o,o) -- -------------------------------------------- - -__/  \
{{ _ }} Encoding ideas: making the Megademica soundtrack /  \__/
- "-" ------------------------------------------------ - \__/  \
        by Gasman - Part I                                  \__/

One of the key skills needed when writing size-limited code is an intuition for what should be possible in a given number of bytes. This is important not just for setting realistic goals, but also for knowing where to devote your efforts in optimisation - you don't want to spend hours trying to shave off a few bytes from a routine that's already close to the theoretical limit, when there are much bigger potential gains to be made elsewhere.

This challenge takes on an extra dimension once you introduce compressors. Coders often treat these as a black box, trying endless tweaks and variations in the hopes of finding one that happens to please the algorithm. It's all too easy to spend time writing a clever routine to generate some data table, only to find that the packed size of that routine is no better than just storing the data directly.

For these situations, I find it helpful to think of the byte count as a count of distinct ideas, or design decisions, that you're able to include. "The robot is a blueish silver colour" is a one byte design decision (assuming that there are 256 meaningfully different colours); "the walk animation for the robot's left leg is a mirror image of the right leg offset by 12 frames" might be... 10 bytes maybe? It's not an exact science, and clearly it depends on the level of knowledge that comes for free with the platform you're working with. "A filled triangle at coordinates v1, v2, v3" is a sub-10-byte idea if your platform has built-in support for drawing filled triangles, and rather more than that if you have to implement that from first principles.

Someone watching the progress of video compression any time in the last 20-30 years might well have asked themselves a question like "could there ever be an algorithm advanced enough that it could fit Citizen Kane onto a floppy in acceptable quality?" This kind of question takes on a new significance in an age of generative AI that can turn a text prompt into video. We can imagine the ultimate decompression algorithm as one that takes as input the stream of all the creative decisions that Orson Welles made - perhaps in text form, or perhaps some other machine-readable encoding - and outputs a video following those specifications. That input would include details such as a snowglobe dropping out of Kane's hand, and the specific framing of the shot of it smashing on the ground, but probably not the exact trajectories of every shard of glass. How many ideas make up the whole movie? Possibly hundreds of thousands - probably less than a million.

At a much more down-to-earth level, this kind of thinking was the key to optimising the TIC-80 Lovebyte 2021 invite I worked on with g0blinish and Hellmood, which centred around a waving Lovebyte logo. The bitmap for that logo took up the bulk of the intro's compressed size, and attempts to reduce that through approaches like RLE compression went nowhere. Understandable, really - a list of "6 white pixels, 20 black pixels, 10 white pixels..." is pretty far from the set of human design decisions that went into that logo. In the absence of the TIC-80 having access to the specific font used in the logo, it was clear that the closest approximation to that set of ideas would be the sequence of pen strokes that made up the letters - in other words, redrawing them in 'tri' and 'rect' statements. This was a couple of hours of laborious work, but I was confident that it would pay off, given how much closer it was to the ideal representation.

So how does this apply to music? Normally on the demoscene, we'd take our cue from tracker music - a grid that we progress through at a fixed rate, with events placed on that grid to tell us which notes to play at which times. But this isn't really capturing musical ideas any more than a grid of pixels is capturing pen strokes. A musician is thinking in terms of rhythms, scales, chord progressions - can we capture those ideas directly, rather than the results of applying them?

I had the chance to put this into action when SerzhSoft approached me to write the music for his 4K intro Megademica. It was a daunting challenge from the start - the visuals made full use of the Revision party's 8 minute time limit, leaving 700-800 bytes of the intro's packed size for a soundtrack that could fill that time while matching the diversity of the visuals.

As an extra complication, there was a hard limit of 2 kilobytes on the unpacked size of the routine and data too, since the visuals used up almost all of the Spectrum's memory. After all, repetition is another kind of idea that appears at many levels in music, whether that's at the micro level of drum beats or the macro level of establishing melodic motifs and coming back to them in variations. If the packed file size is your only concern, you can make the data stream as repetitive as you like and lean on the compressor to absorb that redundancy, so that an idea like "repeat this phrase 16 times" will naturally become a one-byte idea with no further effort. However, if the data structure you're working with at play time is size-constrained too, you don't have that luxury - you'll have to build the idea of repetition into your design.

So, jumping in to the opening of the Megademica soundtrack it's a four bar riff with a rhythm that goes DAN-dan-dan DAN-dan-dan. In a tracker, those four bars would be one pattern, 64 rows long. So that's 64 bytes, maybe a bit more if you're including information like samples and effects, maybe a bit less if you're clever about encoding the empty space. But what if we isolate that "DAN-dan-dan DAN-dan-dan" rhythm as a standalone idea? That's a 16-bit value %1001001010010010, with the 1 bits indicating the times where we want to play a note. That rhythm, by itself, is a two-byte idea.

We have four bars of that six-note DAN-dan-dan DAN-dan-dan rhythm, playing different pitches on each bar, giving a total of 24 note pitches that we have to store somehow. Given that there are 88 notes on a piano keyboard, it wouldn't be too far-fetched to store those as one byte per note - and alongside our two bytes of rhythm information, those 26 bytes are already a big improvement over the 64 that we would have spent storing it in a tracker grid arrangement. We can do better, though - after all, those 88 notes on a piano keyboard are not all equally likely. A melody is not going to jump several octaves from one note to the next, and it will probably stick to the notes of a given musical scale. In fact, once you've established what that scale is I'd say there are around 16 plausible options for any note, and you can probably see where I'm going with that figure.

For a musician, working within a musical scale is the equivalent of a pixel artist working with a fixed palette. It's a constraint on the choices you can make, and thus less information to store - but it's a constraint you were probably happy to follow anyway. If we decide up-front that we're going to stick to the notes A A# C# D D# E F G, then we can spend 8 bytes on defining that musical scale, and from then on each note of your melody can be encoded in three bits. In my case, I chose to use a fourth bit to denote shifting up an octave, giving me 16 notes across two octaves to play with.

A well-chosen scale is such a powerful concentration of musical essence into very few bytes, that sometimes it might be all you need for your soundtrack. Some intros, such as Mipmap by Ate Bit and my own Spectrumori-on, exploit the fact that with a suitably limited scale, even random data can sound musical. If your intro calls for a musical texture rather than a specific melody, then the individual notes might be as inconsequential as the shards of glass in Citizen Kane's snowglobe, and so there's no need to spend your idea-byte-budget on them. Your human contribution to that melody might be zero, or simply pointing to an address in ROM that happens to sound nice.

For Megademica, of course, I didn't want to leave the melody to random chance. Sticking to one fixed scale for the entire track would also be too limiting, given that there was a whole second part in a major key. Instead, I ended up defining several scales - a palette of palettes, if you like - and for each bar of music, storing a value indicating which scale to use.

Continued in Part II...