Our experience of participating in 10K Apart or how to squeeze 40 KB of code in 10

    Not so long ago on Habré they already wrote about the 10K Apart contest - a competition for the best web application with a total volume of up to 10K, created using only client technologies: (HTML, CSS, Javascript, SVG, etc.).

    image

    I want to introduce your attention to our work for this contest, which private_face and I did in the evenings for two weeks: an adventure game in the style of a dungeon-crawler called "Fontanero" ( Spanish plumber).

    • Random connected dungeon generator.
    • Disclosure of the card as you progress, the disclosure of rooms.
    • 13 monsters with primitive AI and an algorithm for finding the path.
    • Food, Drink, 4 different spell books: vision, heal, cure and genocide.
    • The effects of poisoning and blinding.
    • Mini game with rotation and repair of pipes
    • And even the monstrous boss at the end.

    All this diversity in three files with a total weight of 10,230 bytes. If you ever find a 1.44MB disk on the mezzanine, you can record 144 such games on it.
    After we have decided on the nature of the application (adventure), the genre (dungeon crawler in the style of nethack) and the setting (the plumber goes down to the basement to fix the pipe and goes to hell), it is time to figure out whether we can even realize our plan and at the same time keep within 10K.

    Zip


    The first drafts of the code (a map generator and a game field template) showed that 10K is not enough even for a third of the game. It was necessary either to drop everything or somehow increase the available space.

    I, as a low-level programmer, were immediately very interested in the ability to pin js into zip so that I could unpack it at runtime. The first thought was to write your own LZSS, but a little later a much simpler thought was born: put js in PNG, because the data in it is compressed with the same zip. (As it turned out later, we were not the first to come up with this idea ).

    Having studied the technology, we checked the ability to load arbitrary code through Canvas from the palette png, encoding the characters in one of the color components. The test was successfully completed in all required browsers, including IE 9 preview (which now also supports Canvas). It was a success. The eight-bit palette can store 256 colors, but after the obfuscator there are only characters with codes 32-94, and \ n (10). Encoding them into 64 values, rather than 256, also gave significant savings (Strange, but png does not know how to compress the palette).

    Thus, the structure of our future application became clear: an HTML loader page with a script that restores javascript from PNG, which contains all the game logic, as well as dynamically creates all the necessary HTML and CSS. In the final version of the project, the loader occupied 850 bytes, including even alert (“no canvas”); (You cannot leave users of old browsers in front of a white screen).

    Obfuscation


    Zip increased the actual amount of code we could afford, but that was still not enough. Therefore, the next step in optimizing the size was the choice of obfuscator for JS.

    From the free solutions on the market, we chose between yui compressor and google closure compiler. The competition, of course, was won by the google closure compiler (hereinafter gcc), which, honestly, is by far the best in compression, plus it displays warnings, most of which are useful.

    We used gcc in advanced mode, in which it throws out unused code, renames all identifiers to one or two letters, rebuilds branches, inlines functions, and in every possible way kills the code in pursuit of saving bytes.

    However, even when using gcc in advanced mode, there is still room for optimization. Firstly, gcc is afraid to rename fields with standard, in his opinion, names: left, right, top, bottom, name, type, width, heightetc. Therefore, we preprocessed our code before running gcc by renaming such names ourselves. Secondly, after obfuscation, the code contains many frequently repeated words “function” and “this”. To save money, we replaced their @ ​​and `characters. Loader thus rose slightly on the back substitution replace(/@/g, ‘function’).replace(/\`/g. ‘this’)and code after such treating an looked quite monstrous:
    ;`.g=n;`.K=`.v=o;`.F=@(d){var c=`.e;,
    but it was worth it: as a whole, with each byte replacing turned 50.

    the CSS compressed using the yui compressor and underlay directly to the end of javascript, pre-slicing semicolons before closing brackets (60 bytes of savings!).

    When we determined the appearance of the game, our opinions with private_face diverged. I offered a classic 2D view:


    Vova-2 insisted on an isometry like this:


    Therefore, afterwards, having sketched a simple old-school renderer (everything was drawn with text inside the textarea tag), I continued to write game logic and a map generator, and Vova started messing with my isometry. He did not yet know what surprise IE9 was preparing for him. Ahahahahahahahahaha: ((

    Passion isometric


    private_face :
    The implementation of the isometry was supposed to be as follows: rectangular blocks with textures superimposed on them were transferred to an isometric projection by CSS transformations skew and scale, after which they were absolutely positioned in the right place.

    This solution required the creation of a separate DOM element for each tile, but it looked simpler and more compact (and most importantly more productive) than drawing on the canvas.
    In addition, the use of DOM elements made it possible not only to impose textures, but also to easily write any text on the walls , which could become a killer feature for our game.

    After some time, the prototype was ready. The render turned out to be quite compact (all drawing was rendered in CSS, javascript only positioned blocks)
    and produced a pretty good picture (although it slowed down significantly in Firefox 3.6):


    Life seemed beautiful and cloudless. However, igniting the idea of ​​isometry, I forgot to do one important thing: to make sure that CSS transforms are supported by the new Internet Explorer 9. This error cost me pointless time spent and tons of innocently killed nerve cells in the final. Because it turned out that the only option to implement the transformation in IE9 is the Matrix filter. But the performance of such a solution was simply none.
    In general, isometry had to be abandoned.

    Back to basics


    After the failure of the 3D version, we decided to return to a simple tile version.

    All tiles were drawn in the usual GIMP and combined into a PNG sprite with a 4-bit (16 colors) palette, after which the latter was pinched by pngcrush with the -brute switch.

    We managed to add some volume to the picture by setting the box-shadow property to the wall and floor tiles. However, this unexpectedly negatively affected the performance of Internet Explorer 9, while other browsers worked at normal speed. In order not to frustrate IE9 users with brakes, I had to add the “Enable Shadows” option to the game’s interface, which is disabled by default in this browser. Let's hope that the release box-shadow performance in IE9 will be corrected.

    There was a good side to the transition to 2D: the total amount of the rendering code was significantly reduced compared to the isometric version, and we ultimately used the freed up space to add a pipe repair minigame to the game process.

    Epilogue


    This is a brief history of how we made this game. Starting to work on this project, none of us assumed that it would be so interesting to work in tight restrictions and saving precious bytes. We got a huge amount of fan, and 10k did a great job with its task - reinspire the web.

    Outside the narrative there are many other tasks that we had to solve during the work on this project. Such as, for example, a compact algorithm for generating a level with a connection check, an ultra-compact algorithm for moving monsters that could walk along corridors and would not look too dumb.

    And at the end of this topic, I will give once again a short list of optimizations that allowed us to cram almost 40K of code into 10K.
    CSS optimization:
    1. Packing CSS by YUI Compressor into a string, adding the result to the source .js file.
    2. Delete optional semicolons at the end of each rule block.
    3. Insert the resulting style string to JS (that is, css + js packaging in one archive block).
    JS optimization:
    1. Before obfuscation: replacing fields with the names left, right, name, type, etc. to others (since GCC does not rename them even in advanced mode).
    2. Obfuscating GCC code in advanced mode.
    3. After obfuscation: replacing function and this keywords with single-letter abbreviations ('@' and '' ').
    4. Proton Container Encapsulation PNG Packaging.
    Image Optimization:
    1. All images were stored in one sprite.
    2. The number of colors in the palette was limited to 16.
    3. After any change, the file was pinched by pngcrush with the -brute option to ensure the best compression.

    Small update: Today, by popular demand, we fixed the display of the mini-game in opera, although this is not in the requirements of the competition. Patch on the way to 10K Apart.

    Thank you very much for your attention, we will be very happy if you rate our game on the competition page .
    PS Click on, continued.
    PPS The contest is over, thank you all!

    Also popular now: