WOLF1K

2047 words ~ 9-20 mins

The idea of this entry for the JS1K contest was to do the impossible: a 1K remake of the famous WOLF5K that rocked the final edition of the5K. It does not feature guns, evil grins and violence for in WOLF1K there is no room for guns or any form of violence.

You can also try a development version of WOLF1K in which the SHIFT and TAB keys shows a few extras.

Hope you enjoy your stroll in the walls of WOLF1K and don't panic as the 15 rainbow characters swift away to their fate.

Features and non-features

WOLF1K features a 32x32 map ( a 1024 cells grid ) with textured walls colored by orientation ( North, South, East, West ), fog, 3 transparent bitmap graphics in 8x8, 15 rainbow characters steering smoothly across the map, collision detection, probably the most crazy optimization tricks I ever wrote.

Does not feature guns, violence: in WOLF1K, there is no room for guns or any form of violence.

It's the little things

Love is the little things. Here are a few little things I put much love into and you may not notice at first:

How does it work ?

The 3D rendering

WOLF1K works exactly like the original Wolfenstein 3D and Wolf 5k. It is using the raycasting technique. The world is built from a uniform grid of walls and corridors. In order to draw the world, a single ray is traced for every column of screen pixels and a vertical slice of wall texture is selected, scaled and colored according to where in the world the ray hits a wall and how far it travels before doing so.

The world

The world of WOLF1K is a regular grid of 32x32 cells. Obviously storing these 1024 cells in one byte or one bit each is not feasible. It would use the 1024 bytes or 128 bytes if stored as bits. It actually is the result of a binary operation applied to the ASCII codes of the source code of WOLF1K plus a mural on each edge of the world.

The graphics

There is 3 transparent bitmaps graphics of 8x8 pixels each: 2 textures for the walls and 1 sprite for the rainbow characters.

The naive approach would be to store a base64 encoded GIF image but it uses way too many bytes and implies to use the drawImage method which produces blurry graphics when upscaling.

Since the textures are monochrome and 8 pixels tall, we really only need 1 byte per column. We have 3 textures, of 8 columns each. That gives us 3x8=24bytes to store the graphics as a string. Since the characters of that string have a charCode that collide with the tokens of the JavaScript packer, we encode it in base64 and it becomes 32bytes long.

Rendering the graphics

The base64 encoded graphics are easily decoded using the builtin method atob()

That way it is possible to draw a column of graphic by checking each of the 8bits of a character and drawing a colorful rectangle for each bit set. This has the added benefit of producing sharp graphics. Clearing the screen, colors, fog and all things shiny.

The colors are all based on HSL where the saturation is fixed, the hue depends on the orientation of the wall or index of the rainbow character and the luminosity depends on the proximity to the player.

Clearing the screen is done by drawing a full height column at 0% luminosity before drawing any slice of wall. How does that fit in 1024 bytes of JavaScript ?

Obviously the code was minified and featured all the micro optimizations in the book and then some more. As a result Google's Closure Compiler and other automated JavaScript optimizers only managed to break the code or make it bigger instead of smaller.

The original code is carefully hand crafted to please the JavaScript packer. In it's minified version, prior packing, it does not contain a single whitespace, exclamation mark, double quote, hash symbol, dollar sign, tilde... and weighs 1370bytes.

Tweaking the code to be packer friendly and using and abusing existing features, methods and variables was key to reach the 1024 bytes mark.

Styling of the page and Canvas element

Initially WOLF1K used the same setting as the Animated Quaternion Julia ? I entered at the JS1K contest, i.e. using the default 300x150 canvas and using its innerHTML to inject a style rule setting every element on the page to full width and height with zero margin and hidden overflow and a black background.

A.innerHTML='<style>*{margin:0;width:100%;height:100%;overflow:hidden;background:#000}</style>';

While very clean are capable of risizing, this cost 96bytes or 9% of the whole 1024bytes available and was used only once in the code. For a while I was reluctant to compromise on this but it was simply too much. When showing a preview of WOLF1K to Andreas Bovens ? and fiddling with the code, he convinced me WOLF1K was fine with a more limited styling.

We tweaked and removed CSS properties one by one and got some pretty good results like the following:

A.innerHTML='<style>*{width:98%;height:98%;background:#000}</style>';

Eventually I got rid of the innerHTML style injection altogether and went for the classic A.width=innerWidth-20 used by other participants of the JS1K contest in combination with A.height=A.width/2. When put in the main loop these assignments allowed for resizing too. Since A.width is used all other the place, the whole thing packs very well and made the styling virtually free.

Functions declarations and shadowing

Function declarations are verbose. They cost a minimum of 13 bytes each and WOLF1K has a total of 4 functions:

In a 1k contest we simply can't afford to waste 52 bytes, i.e. 5% of the available space, on such a trivial thing.

To make these 4 function declaration pack well, they all use the same signature function(x,y){...} to please the packer.

Actually there is a 5th function shadowed in the keydown handler:

onkeydown=function(x,y)
{
    // Flag the key x.which as down
    // If called to check a collision detection, x.which is simply undefined and it causes no harm 
    A[x.which]=1;
    
    // Go on with the collision detection which is harmless for the key handler
    // gets the combined X & Y coordinate for the collision detection.
    // Note that the argument y is optionnal.
    x|=y<<5;
    return (x&31)*(x&480)*(_.charCodeAt(x++%73)&19)?1:0
};

Combined rendering

The rendering loop, the last 4 lines of the original source code, combines the depth sort of the columns of wall and the rainbow characters and their rendering.

If the texture coordinate of the current entry of the sorted list is set to zero, a rainbow character is drawn. Otherwise single column of wall is drawn and the X loop, the middle for loop, is collapsed to process and render a single byte of texture instead the all 8 bytes making the 8 columns of each textures.

The packer

I looked at various JavaScript packers over the years and wrote a few myself. The most compact and efficient ones are all based on the search & replace approach. Basically find the substring of code that appear several times and provide the highest gain when replaced by a token. Repeat until there is no more tokens available or such substring.

This time around, @cowboy's packer ? showed the most compact way to combine the token and substring. A single string contains the list of tokens, each followed by the substring of code it replaces. The tokens were non printable character, which simplified the search to the following regular expression: /.([ -~])+/g.

The initial regular expression allowed to use any printable characters. The initial source code of WOLF1K didn't use many of the first printable characters. With a bit of discipline it was possible to push a little in the ASCII table and not use any whitespace, exclamation mark, double quote, hash symbol, dollar sign, or tilde. This allowed for more tokens and the reglar expression became: /.([%-}]+)/g. To gain one more token, I used the fact that the very first character of the token+substrings map could be anything and used a printable characters that isn't used in the original code.

These changes provided 6 more tokens to WOLF1K than the initial implementation.

Also I gained 8 bytes on the unpacking code by using code=code.split(x[0]).join(y) instead of another code=code.replace(RegExp(x[0],'g'),y) which was bigger and would require to escape tokens like the dollar sign.

Being packer-firendly

Knowing that the packer is looking for substrings of code that are repeated, we can craft the code to please it using subtles and otherwise meaningless changes.

In some places, using a coma instead of a semicolon helped increase the redudancy of the code. In other places where doing similar computations, using the exact same variable names then copying some result into other variables lead to big gains.

Here are a few examples of the interresting snippets that were specially crafted to please the packer:

// function signature
function(x,y)

// to compute the combined XY coordinate in the map
;x|=y<<5;

// to get a cell in the map and a slice of texture
.charCodeAt(x++%73)

// to compute the X and Y properties of the ray
%=1;u=a<0?-a:a,F=(a<0?d:1-d)/u;

// get the effect of the keys to move and turn the player
:A[j]-A[j+2];

// 3 out of the 7 for loops starts with
for(n=A.width,i=0;

// sets the color of the texture and the black background
B.fillStyle='hsl('+D[n][2]+'1,99%,

// to clear a column and draw a rectangle of texture
B.fillRect(a,b,u

Original source code before minification

This version is sprinkled with a few comments.

// the usual suspects
// A is also used a keydown map
// B is also used as player/entities collection
A=document.body.children.c;
B=A.getContext('2d');

// the keydown method is also the collision detection with the map
// the map is actually a 32x32 big ( 1k ;) ) square using the charCode & 19 of uncompressed JS code % 73
// NOTE: Make sure to set _ if you want to try the uncompressed version
onkeydown=function(x,y)
{
    A[x.which]=1;
    x|=y<<5;
    return(x&31)*(x&480)*(_.charCodeAt(x++%73)&19)?1:0
};

// clear the keyboard mapping ( aka A )
// set the keyup method
// initial the player and rainbow characters in 1.1, 1.1, facing towards 1.1 radians
for(n=A.width,i=0;n--;B[n]=[1.1,1.1,1.1,A[n]=0])
    onkeyup=function(x,y)
    {
        A[x.which]=0
    };

// D is the array of wall slices raycasted + entities on screen
D=[setInterval(function(x,y)
{
    // update the width & height of the canvas to fit the window
    A.width=innerWidth-20;A.height=A.width/2;

    // raycast the walls
    for(n=A.width,i=0;n--;D[n]=[t,n,S,8+(S+x*9&8)|(X+y+t*s+t*c)*8&7])
    {
        w=X=x=B[i][0];v=y=B[i][1];
        z=B[i][2];
        x|=y<<5;
        b=z+n/A.width-.5,
        // Y properties of the ray
        a=s=Math.sin(b),d=y%=1;
        u=a<0?-a:a,F=(a<0?d:1-d)/u;
        G=F,r=u;
        // X properties of the ray
        a=c=Math.cos(b),d=X%=1;
        u=a<0?-a:a,F=(a<0?d:1-d)/u;
        // loop until the ray hits a wall
        for(;onkeydown(x);)
            F<G?(t=F,F+=1/u,x+=S=c/u):(t=G,G+=1/r,x+=S=32*s/r)
    }

    // process the entities
    for(n=A.width,i=0;i<15;i++)
    {
        // move
        b=B[i][2];
        j=38;
        t=i?1:A[j]-A[j+2];

        X=B[i][0]+=onkeydown(B[i][0]+Math.cos(b)*t/8,B[i][1])*Math.cos(b)*t/8;
        Y=B[i][1]+=onkeydown(B[i][0],B[i][1]+Math.sin(b)*t/8)*Math.sin(b)*t/8;

        // turn
        j--;
        t=i?Math.random()*8-4:A[j]-A[j+2];
        B[i][2]=(b-1*t/16+9.42%6.28)-3.14;

        // angle relative to the player
        b=z-Math.atan2(Y-=v,X-=w);
        i&&Math.cos(b)>.5?D[n]=[Math.sqrt(X*X+Y*Y),A.width/2-A.width*b,i,0,++n]:0
    }

    // sort the array of slices & entities and render them
    for(D.sort(function(x,y){return+x[0]-y[0]});n--;)
        for(a=D[n][1],b=a/A.width-.5,F=A.width/2/Math.cos(b)/D[n][b=0],c=8,u=v=F/4+1,x=D[n][3],x?B.fillRect(a,b,u=c=1,A.width,B.fillStyle='hsl('+D[n][2]+'1,99%,0%)'):a-=F;c--;a+=F/4)
            for(B.fillStyle='hsl('+D[n][2]+'1,99%,'+v+'%)',d=atob('CBF+/p6f9AC9bsP/w/dqvdvb2NvD29sb').charCodeAt(x++%73),y=8,b=A.width/4,b-=F;y--;b+=F/4)
                d>>y&1?B.fillRect(a,b,u,v):0
},9)]

Other recent experiments

There are many experiments and projects like WOLF1K to discover other here.

Let's talk

Don't be shy; get in touch by mail, twitter, github, linkedin or pouet if you have any questions, feedback, speaking, workshop or performance opportunity.