Q1K3 - An homage to Quake in 13kb of JavaScript(js13kgames.com)
js13kgames.com
Q1K3 - An homage to Quake in 13kb of JavaScript
https://js13kgames.com/entries/q1k3
77 comments
Amazing. I'll never understand why "invert mouse" was not the default and universally used. It's so much more intuitive!
Now I just need right-mouse-button to make me walk forward :)
Now I just need right-mouse-button to make me walk forward :)
Yes, thank you so much! I wanted to enjoy it and tried to power through without invert-y, but I just couldn't get used to it and stopped playing.
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.
[1] https://github.com/lifthrasiir/roadroller/
[1] https://github.com/lifthrasiir/roadroller/
Looks great. Could you highlight why it’s much faster in Node 16 as opposed to 14?
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.
Roadroller was the reason I was able to find the second level in. Thank you so much! :)
Do you mind commenting on what makes a “heavyweight javascript demo packer” different from any JS minifier?
Are there clever demo specific tricks it uses?
Are there clever demo specific tricks it uses?
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.
- 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).
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).
Really appreciate these details. Thank you.
It appears to actually compress your JS, rather than make it "shorter but still valid".
The code ends up being something like:
The code ends up being something like:
eval(decompress("hfkfkvj..."));
function decompress(data) {...}Interesting. So then it’s just better lossless compression than gzip?
Not necessarily better than gzip, as you have to add the size of the unpacker to the payload.
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.
[1] https://docs.google.com/spreadsheets/d/1dKJWpLPY9fQ2J_COffOJ...
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.
[1] https://docs.google.com/spreadsheets/d/1dKJWpLPY9fQ2J_COffOJ...
Thanks for the detailed reply.
Your name looks familiar. I think I've seen you around some code golf hangouts somewhere on the internet.
Your name looks familiar. I think I've seen you around some code golf hangouts somewhere on the internet.
Was that the Anarchy Golf? :-) Otherwise I've been here and there so I might not remember all the places I've ever been.
Yes I think so. I used to be moderately active there a few years ago, although not a "regular".
I also used Roadroller for my js13k game this year!
It's a massive help to the community.
Amazing that’s crammed in 13Kb but the other day I had to download a Meg of crap to view one web form.
We routinely send over 100MiB videos as instant messaging attachments now.
Ah yes. The ones that time out for me almost universally.
Regardless of that it’s about efficiency. The 100Mb video is probably fairly efficiently encoded already.
Regardless of that it’s about efficiency. The 100Mb video is probably fairly efficiently encoded already.
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.
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
related: https://news.ycombinator.com/item?id=17536727
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
related: https://news.ycombinator.com/item?id=17536727
Film Grain effects were available in ffdshow since forever, but it’s unmaintained.
that's not the same as having them in an open codec standard, right?
Well, no, but generally it’s something applied after decompression to decrease perceivable compression artifacts.
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.
[0] https://phoboslab.org/ttt
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.
[0] https://phoboslab.org/ttt
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.
[0] https://en.m.wikipedia.org/wiki/.kkrieger
[0] https://en.m.wikipedia.org/wiki/.kkrieger
It reminds me of Omniscent [0], a 4k intro from 1997, that used similar techniques.
[0] https://youtu.be/G1Q9LtnnE4w
[0] https://youtu.be/G1Q9LtnnE4w
Nit: It's a simplified version of E1M1 and E1M3.
It is interesting to see how the levels are basically
made up of axis aligned cubes
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].
[1] https://github.com/phoboslab/q1k3/blob/master/pack_map.c#L78... [2] https://github.com/phoboslab/q1k3/blob/master/source/map.js#...
The collision detection however builds a grid out of these, so the game can quickly look up any position within the game world[2].
[1] https://github.com/phoboslab/q1k3/blob/master/pack_map.c#L78... [2] https://github.com/phoboslab/q1k3/blob/master/source/map.js#...
Thanks for the explanation! I assume you built a visual map editor to make these levels, rather than writing that data directly?
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!
[1] https://trenchbroom.github.io/
[1] https://trenchbroom.github.io/
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.
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.
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.
Nice stuff but I almost went mad when I realized there's no invert mouse option.
wait, how do you play with inverted mouse? what controller do you use? a touchpad?
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.
By that reasoning pushing the mouse right should rotate the view left.
If you were holding a gun with two hands (and you're right-handed), you'd lift your right hand up to aim down.
This is great. I really enjoyed it, although I got stuck for ages trying to find the door on the second map.
I felt quite sick after playing though. Hadn't played an FPS in a long time. Anyone else?
I felt quite sick after playing though. Hadn't played an FPS in a long time. Anyone else?
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.
(edit) added a link to an article https://www.engadget.com/2008-07-17-how-mirrors-edge-fights-...
(edit) added a link to an article https://www.engadget.com/2008-07-17-how-mirrors-edge-fights-...
Ah wow, that's super interesting. Yeah I definitely noticed the lack of reticule and the effect it had on aiming.
What are the “l” and “m” binary files?
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.
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.
[1] https://github.com/phoboslab/q1k3/blob/master/source/map.js
[2] https://github.com/phoboslab/q1k3/blob/master/source/model.j...
[3] https://github.com/phoboslab/q1k3/blob/master/build.sh
[4] https://phoboslab.org/q1k3/q1k3.zip
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.
[1] https://github.com/phoboslab/q1k3/blob/master/source/map.js
[2] https://github.com/phoboslab/q1k3/blob/master/source/model.j...
[3] https://github.com/phoboslab/q1k3/blob/master/build.sh
[4] https://phoboslab.org/q1k3/q1k3.zip
sigh kb != kB.
Congratulations! This is really well done!
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.
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.
Wow. It is the exact replica of Q1's first map. Incredible for 13 kb.
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.
I'll never forget playing Quake for the first time, it was the first FPS experience that actually felt 3 dimensional.
Super cool. Stuff like this makes me sad because Quake Live required a browser plugin but it's quite doable now.
http://www.quakejs.com/ works well.
Very cool. How long did it take you from start to finish? What was your process like?
I loved how simple it is. It works well and does the job. Spent 5 mins playing it.
What no framework ?? :p
Lol just kidding, super well done :)
played through, lovingly built, amazing.
while all the techs are impressive, level design definitely counts for at least half the soul of a game.
Wow! And the gameplay is actually quite good!
wow, it almost but not quite fits into a qrcode. makes me think of distributing mini games through qr and js
QR code can only contain up to 2953 arbitrary octets, which is way smaller than the imposed 13 KB limit.
Standard QR codes maybe, but you can make bigger ones and there's QR-like systems that use colors and the like as well to store more data.
https://youtu.be/ExwqNreocpg
Itsn not js but at least one a qr code
Off topic but related, if you haven't heard of Pico-8, the "cartridge" PNG format it uses is a fun read [0].
[0] https://pico-8.fandom.com/wiki/P8PNGFileFormat
[0] https://pico-8.fandom.com/wiki/P8PNGFileFormat
loads of fun. shouldn't take many more bytes to add a crosshair and proper movement code
great, now add multiplayer netcode
no strafe jumping :()
TIL 13kb is not enough to get mouse look the right way round.
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.