I remember as a kid getting completely stuck on one of the Doom2 maps until my Dad showed me you have to combine the forward key on the keyboard with pushing the mouse forward to run fast enough to jump a gap, i'm still not sure I would have figured it out today!
I'm honored that Q1K3, among many other entries to js13kGames 2021, is compressed with Roadroller [1], which is the reason that its (compressed) source code is basically a random-looking string plus some bit of JS code.
As others commented on it is actually a compression algorithm in disguise, but it does have some tricks.
- js13kGames measures the file size by its ZIP archive size, where the ZIP file itself is provided by the participant. In the past people used ZIP recompressors like ADVZIP or ECT to minimize the ZIP file. Roadroller needs to store a large amount of binary data, but JS string literals are not efficient in terms of information entropy (~6.96 bits per byte [1]). Therefore Roadroller actually stores 6-bit code which can be encoded in a very efficient Huffman tree. The 6-bit code is ASCII only, so it is much easier to handle.
- Roadroller tunes a lot of compression parameters during its optimization phase. It is normally a curse that you have to bring your own decoder, but Roadroller generates a decoder optimized specifically for given compressed data.
- Roadroller is allowed to transform the JS code input, so it tries to strategically insert a whitespace around tokens for better compression (see Packer.prepareJs comments for more information). So it doesn't necessarily produce the most minified code---Roadroller currently doesn't care about JS syntax and only does tokenization---but it will produce the most compressible code.
[1] Assuming UTF-8. If the file is encoded in ISO-8859-1 or similar this can be greatly improved: there are 4 or 5 forbidden bytes [2] out of 256 possible octets so ~7.977 bits per byte is possible.
[2] $, `, \, \r. When included in the <script> element \0 is also included.
That's wild. Would there ever be a usecase for this in a normal web app? I.e. would it be possible that decoding could take less time than downloading the extra data?
Absolutely not. Roadroller currently targets the maximum latency of 1 second for "typical" inputs (~50 KB), so it would translate to ~50 KB/s decompression rate. If we were able to get any gain out of it the communication channel should have been much slower (~5 KB/s). At that point we would just avoid JS anyway.
It is possible to make it an order of magnitude faster (the decoder is size-optimized, not speed-optimized), but its usefulness is still limited. The algorithm (context mixing) runs a large number of context models both for the compression and decompression, so its run time is proportional to the number of bytes being compressed. In the other words, if the input size is 1 MB the run time is proportional to that 1 MB, no matter it compressed into 200 KB or 10 KB. The only way to make the decompression faster is to reduce the input size via preprocessing; that preprocessor would have to run the context models to be efficient however.
I did hear of a semi-serious use case where an embedded device has to ship a JS front end to its API and its ROM is limited and can't be expanded. In that case it would make more sense to put a custom compression algorithm. However a more reasonable answer would be to force `Content-Encoding: br` to the client and store a Brotli stream (which would be at most 10% larger than Roadroller anyway).
Note that while you are correct in principle (for example it will perform poorly for LZ77 best cases), Roadroller reaches a very high compression ratio when used with the typical minified JS input and DEFLATE recompressors.
I have kept an internal benchmark using some of js13kGames 2020 entries [1] and for those samples Roadroller universally beat gzip and in most cases even Brotli by a large margin (~8%) even with the embedded decoder. Of course Roadroller is much more computationally expensive though.
No idea. Low-level JS performance is very sensitive to small changes and I haven't tried to look at why. For example I've seen a situation where a simple well-predictable conditional deoptimized the entire method but I couldn't see exactly why (I've rewritten that bit of code anyway). It was one of the reasons that Roadroller now uses a WebAssembly implementation by default.
Videos are really the thing where you just can't get around large formats. There's only so much you can compress, and even then if there is a lot of movement or color change even compressing won't do much.
"You can't compress noise." Well, humans can't tell the difference between two snippets of white noise.
It'll be fun. Remember jbig? (can't find the source, but iirc "most of what we're sending is text, so our fax can detect identical characters and reuse them! genius! [ten years and several bonuses later] um boss, our fax swapped a few ... 'identical' ... digits in someone's legal documents, so you have to appear in court now. also their entire scanned document archive is potentially corrupted and they may want damages")
I guess the 'no photos on the internet' people will have the last laugh; they won't be the ones seen criming in the background of someone else's blurry holiday photo.
> "You can't compress noise." Well, humans can't tell the difference between two snippets of white noise.
new codecs (decoders?) have something called Film Grain Synthesis. i think you have to encode the content before this is applied at the source?
i'm not sure this actually madebit into the AV1 standard or encoders yet.
tried encoding Hurt Locker a few years ago and the film grain added to it really put the hurt on x264/handbrake. the final file size was nearly as big as the original content. back then the same amount of cpu burning could have probably found a full btc :D
Nice, i actually played through its two levels twice (they are simplified recreations of the E1M1 and E1M2 though the second level has a few differences).
It is interesting to see how the levels are basically made up of axis aligned cubes which simplifies collision detection and response considerably.
The textures are also made using procedural generation using a tool (and library) the author made[0]. I think a "blur rect" and "blur and map result to existing colors" would help a lot with the aesthetic. Also the editor would benefit from a "duplicate step" option too.
This sounds a lot like the classic .kkrieger[0], though that had more complex geometry based on deforming simple shapes and wasn't trying to mimic an existing game.
The levels are stored as 6 bytes per "brush" (i.e. block): 1 byte per each x, y, z coordinates and width, depth and length[1]. The y (vertical) resolution of these values is a bit higher than the x/z resolution to allow for stairs while allowing for bigger levels on the horizontal plane. So the level files are not directly stored as a grid, but as a collection of axis aligned blocks.
The collision detection however builds a grid out of these, so the game can quickly look up any position within the game world[2].
I used TrenchBroom[1] to build the levels. It was initially created to build Quake maps but now supports many derivative games like Half-Life, too. I can't speak highly enough of it; it's really really good!
The latter — each edge is parallel to one of three coordinate axes (X, Y, Z), which forces angles between different edges and surfaces to be multiples of 90 degrees. They don't need to be on a grid, just parallel to one.
One way in which this simplifies things, for example, is checking whether two boxes overlap: They do so exactly when there is an overlap on each axis. (E.g. you look at them from the front, side, and top, and there is no gap between them. This test wouldn't be sufficient if they could be rotated arbitrarily.)
The original Quake levels make use of this: a lot of things have an invisible axis-aligned bounding box (i.e. a cuboid just large enough to contain them) around them. Before checking for an exact intersection, the much cheaper test for the AABBs is performed first. This is useful even when only one of the objects tested is approximated in this way; the other one could be a bounding cylinder around a player/enemy, or a surface in the level geometry.
I like the idea of TTT. When I discovered the JS13k I made a Texture generator ( https://github.com/Lerc/stackie ) with for a game that I never quite got around to. I didn't make that game but I have used Stackie in a heap of projects.
Mine came in at a whopping 2k but could generate some very nice stuff from compact strings.
Looking at the different approach of TTT. I wonder if I could rip out the core of Stackie that makes a (x,y)=>number and add it as a layer to TTT.
The way I could try to make sense of it is, something is being moved from outside so pushing the mouse forward means look down. Flight sims, joystick, 2d plane, ...stuff.
It's missing a gun reticle which was what the developers of Mirror's edge determined was at the root of some of the sim sickness. They added a reticle to Mirror's edge and improved their sim sickness issues. IIRC Quake did have a reticle.
I observe that the core index.html file is only 13k big, but the game depends on two binary blob datafiles: “l” and “m” in the same directory, making the binary total size 22782 bytes (13,472 bytes in a .tar.xz file for the entire website with game).
It’s still impressive, but it’s a little bigger than 13Kib.
`l` is the binary data for the levels, `m` is for the models. These are loaded in the map.js[1] and models.js[2].
JS13k, the contest this game was made for, has the 13kb size limit for a ZIP containing all necessary files. The build process[3] produces a q1k3.zip[4] that sits at 13309 bytes.
Granted, the JS and assets without ZIP compression are a bit bigger, but when sent out over http with fast gzip compression there's still only around 15kb going through the wire.
Besides the eng feat of fitting everything in 13kb, this demo captures the essence Quake 1 gameplay and aesthetics really well. Everything is different - characters, textures, weapons, etc. - but somehow it still feels very much like Quake 1.
Played through till I needed a key then stopped. The first gun's feedback felt quite poor, other than that it's well put together. It felt like Quake that I expected the jump grunt sound to play, albeit I don't know how compressible that would be.
The theme of this years js13k was "Space". When I see demos like I assume someone decided to submit a demo they were working on previously. I don't see how this game fits the theme in any way.
Well it's not an exact replica. It's missing all of the interactive elements, most of the secrets, elevators etc. Everything that makes Quake interesting as a game. But it is still very impressive for 13kb.
I think the shooting and motion feels good, it wouldn't sustain a full game (or even a full episode) but for the two maps it has it feels nice as a game.
Forgot all about this guy. Biolab disaster was so cool(it's e demo for a game engine he wrote) and got me into playing around with Javascript side-scrollers.
Play: https://phoboslab.org/q1k3/
Code: https://github.com/phoboslab/q1k3/commit/a522cb597d805ef7e9d... - curiously this only increased the final ZIP size by one byte. 13309 bytes in total now. ZIP compression (and by extension: Roadroller compression) can be very non-intuitive.