Sep 22, 2021

10 min read

Roadroller Postmortem

Roadroller tool was the big hit of this year’s js13kGames competition - it helped many developers squeeze in extra kilobytes into their entries. The author, Kang Seonghoon, agreed to write all about it.

(Korean version of this article can be found here: 한국어)

Kang Seonghoon: js13kGames this year is special to me, not because I have won something - winners are not yet announced at the time of writing. In fact I haven’t even participated in js13kGames so far and yet I’ve been offered a guest post in the js13kGames blog! Instead of making a game, I made a tool called Roadroller subsequently used by many entries and got overwhelming amount of thanks. A road to Roadroller (pun unintended) was a journey by its own and I’d like to share my story with this overlong post.

Background

For starters I’d like to introduce you to two branches of recreational programming: code golf - also known as size coding or short coding - and the demoscene. In code golf you have to minimize the number of (key)strokes for a particular program, akin to a hole in the real golf. In the demoscene you produce a self-contained audiovisual program called a demo, often limited in size. In both cases you can give pretty much everything else up to reduce the size, but demos have way more freedom to choose what to make. Also unlike code golf, the demoscene had a significant impact on game programming and it should be no surprise that size-limited game jams like js13kGames are distantly related to the demoscene.

While I had decade-long interest in both I was more of a code golfer. I have been particularly active in websites like codegolf.com or Anarchy Golf, and some of my golfed code was obscure enough to win IOCCC. More recently I have delved enough to JavaScript and I’ve won the first JS1024 annual golfing competition, teaming with Erik Sombroek to produce AquaPop1K, a version of Pang in 1,024 bytes of JavaScript.

That sounds like that I should have participated in js13kGames already, but most of them are all in common that I didn’t exactly choose what to make. For example I never wrote the initial version of AquaPop1K and I only joined the team when I found it was an enjoyable game but also not very optimized for size. I surely knew Pang and similar games, but I wouldn’t have made one if I hadn’t seen that initial version. This was also why I have never ever thought of becoming a demoscener. I wanted to change that for a long time: I wanted to make something that is entirely original and not an afterthought. But I still didn’t know what to make.

Fast forward to 2021, I was frustrated at increasing burnout from the daily job. I could hardly concentrate on anything at work and at home, so I reserved two weeks of vacation in August to ease my mind (spoiler: it didn’t work, so for what it’s worth, here is my CV :-). I then realized while I’ve completely missed JS1024 this year, the vacation coincided the beginning of js13kGames 2021 and I can try it out. While I have been a gamedev for last seven years and credited in several games, I mostly made tools and engines for other developers and this would be close to the first game I’ve ever made by my own. By late July I decided to prepare for the upcoming event, and then noticed something.

Needs for better compression

While demos are not necessarily limited in size, size-limited demos are most highly regarded ones. A common size includes 64 KB, 4 KB and 1 KB. As computing power explodes and audiovisual standard for demos skyrockets, it became common to compress demos with specialized tools. fr-08: .the .product, one of the most influential demos and also one of the first demos I have ever seen, was famously packed with a modified version of UPX. By the time of .kkrieger they had a separate tool which eventually became kkrunchy. Since then there have been increasingly complex tools, notably Crinkler and Squishy.

JavaScript packers had been primitive by comparison. The state of the art as far as I knew was PNG-based compressors (“bootstrap”) such as JsExe, which produces a PNG file that can be read as an HTML which reads itself via <canvas> and evals the embedded source code. There is also RegPack which I have used in AquaPop1K, but it is slow and not as effective as PNG bootstrap so I would have happily used PNG bootstrap if JS1024 environment allowed that. For js13kGames the 13 KB limit is measured by the size of the submitted ZIP file, so you can gain pretty much nothing out of PNG bootstrap and a plain ZIP file was the state of the art.

The truth is that, PNG and ZIP are based on a 30-year-old algorithm - namely DEFLATE - and modern algorithms like LZMA, Zstandard or Brotli easily outperform it. There are more computationally expensive algorithms that minimizes existing DEFLATE streams but they are all bound to the limitation of DEFLATE. The biggest reason that PNG bootstrap was still the state of the art was the decompressor size. Any compression method should be self-decompressing in order to be usable in demos and alikes, so the decompressor has to be included in the compressed file. And that decompressor is a textual JavaScript code, not a binary machine code, adding to the complication. For PNG bootstrap however the overhead is only about 200 bytes because it simply makes use of the existing algorithms implemented by browsers. The only other algorithm that can possibly replace DEFLATE is Brotli used by the WOFF2 font format, but it is very unclear how to recover arbitrary data from WOFF2; I’ve tried a lot and still don’t have a good answer. Therefore any subsequent improvement should be so significant that it can counter its own decompressor size.

And here’s where the code golf is actually useful for something! There is a website called golf.horse, a competition to make the smallest program that prints a particular text. I had great fun with golf.horse and I submitted top-ranking programs to every single task under a pseudonym. For bigger tasks I have successfully used an algorithm that is reminiscent of the aforementioned Crinkler, and from that experience I knew that the decompressor overhead of the algorithm was only about 600 bytes. As an experiment I ran my compressor to some of js13kGames 2020 entries and to my surprise, it was able to shave a whole kilobyte for some inputs.

I immediately recognized its potential, but wondered whether it is actually useful for js13kGames or not. Compared to most code golfing competitions 13 KB is sort of luxury, basically allowing everything you want as long as you plan ahead carefully. It also means that you may have relatively easy ways to shave a kilobyte or two, reducing needs for generic compressors. Reluctantly I posted the initial result to the JS1024 discord on July 30 and the reaction was overwhelmingly positive, so I set out to make the actual tool. I’m particularly indebted to Frank Force who encouraged me, tested earlier versions and gave me valuable feedbacks.

Shaving onions

I’ve publicly announced the project to Twitter on August 2. It then took two full weeks from the prototype to an actual tool. My original intention was to finish the compressor right before the beginning of js13kGames and work on an actual game during the vacation, so I was on a relatively tight schedule. I named the tool Roadroller mainly because the name was available in npm, though everyone was thinking of the JoJo reference.

The first version of Roadroller was released on August 13. At this point it was able to compress Edge Not Found from 12,385 bytes (with best ZIP recompressors) to 11,234 bytes, which is already a great success given that with Brotli the same code compresses to 11,358 bytes and that doesn’t include the decompressor. By the way I’ve used Edge Not Found as a primary sample partly because it is a fun game by its own and also because it had every element of typical js13kGames entries.

The 2019 theme was BACK and the 2021 theme is SPACE. Clearly we are talking about keyboard.

Having released the first version I went to make my own game for js13kGames, but I had too many ideas to choose from. One idea involved an isometric platformer with a spacebar-shaped character (pictured above), which sounded promising but I had several problems with game mechanics. I kept improving Roadroller from time to time and I came to realize that I was way more productive while working on Roadroller than my game. I eventually gave up with my game ideas and instead released four more versions of Roadroller during the vacation, with each minor version shaving another hundred bytes or so. This was mainly possible because I found a new optimizable parameter that greatly impact the compression each time, and I was consistently amazed that there were yet another parameters to squeeze.

A benchmark against various versions of Roadroller and stock compressors. Optimization is randomized, so a slight variation in size is expected.

I tried to advertise Roadroller wherever appropriate because I thought it is unfair to make Roadroller available only to selected people. The initial response was slow, but I posted a preliminary result for 2.0.0 to the js13kGames slack on August 24 and suddenly everyone was asking me about Roadroller. It is understandable because Roadroller was able to compress Edge Not Found down to about 10,600 bytes by that time, so pretty much entry using Roadroller was given one or two more kilobytes for free. I even jokingly apologized for making js13kGames into js15kGames!

Thank you all

The submission has been closed now and games are looking amazing. Roadroller is now at the version 2.1.0 and I’m honored that it was used by at least 35 games (I did my best but sorry in advance if I’ve missed your games):

I’ve previously said that I was suffering from burnout. I was unable to make progress in any side project for months and genuinely thought that I had burnt out so much that I had no energy left for anything. The success of Roadroller proved that it was not true; while it didn’t exactly help the recovery, it did save me from low self-esteem. I’m deeply grateful to everyone involved in js13kGames for this reason and this list is my token of gratitude.

Future of Roadroller

Roadroller turned out to be a powerful tool, but it is far from complete. One thing I really wanted to implement but haven’t is a support for multiple inputs. Roadroller expects a single JavaScript code as an input, but actual games have HTML, CSS and images to name a few. Ideally everything has to be translated to a JavaScript code for the optimal compression, which is not a simple task and I ended up writing a guide to make best use of Roadroller. Multiple inputs will largely eliminate such tasks. I have also realized that a lot of people uses stock bundlers like Webpack or Rollup to build their games, so multiple inputs will allow smoother integration to those tools.

It can sound ridiculous but we might be also able to further improve the compression. This is evident when we compare Roadroller with high-end compressors that are really slow and consume a lot of memory but provide the best compression. cmix is one of them, and the most recent version (19) is able to compress Edge Not Found into jaw-dropping 8,554 bytes. Of course it will take more than 1 minute and about 12 GB of memory just for decompression so it is not really usable, but that does suggest a margin for possible improvement. I have mentioned existing demo packers like Crinkler and Squishy before, and while I believe Roadroller is slightly more powerful than Crinkler it is no way comparable to Squishy’s complex models. I have learned a lot about compression algorithms while developing Roadroller and surely there would be more to learn and possibly make use of.

Finally, I want to stress that packers like Roadroller are no substitute for manual size optimization. Dominic Szablewski of Q1K3 said that Roadroller was the reason [he] was able to fit the second level in, which suggests that he was already able to fit the first level into 13 KB without Roadroller. Roadroller will help you pushing more contents into the game, but it doesn’t magically make your games optimized for size. It would be best to regard Roadroller as final helping hands.

Roadroller Postmortem

Background

Needs for better compression

Shaving onions

Thank you all

Future of Roadroller

More from js13kGames

Get the Medium app

Andrzej Mazur