IMPOSSIBLE ROAD by @p01

Back in October 2014, a good friend of mine, showed me IMPOSSIBLE ROAD and half joked that I should do a remake for JS1k the yearly 1kb JavaScript contest happens in Spring. This set my mind on hyperdrive.

Impossible remake in 1024 bytes, made for JS1k 2015.

The original game

IMPOSSIBLE ROAD by Kevin NG is a pure, minimal arcade game about risk, reward, and rollercoasters. You should definitely give it a try on your Android or iOS device.

Impossible project

Seemingly simple, there is more than meet the eye. The original game is technical and incredibly addictive.

Squeezing this in 1024 bytes is not given. However after checking more on the game, screenshots, gameplay videos, ... and thinking of different ways to tackle this, I became confident it was possible to do a faithful remake for JS1k.

But first and foremost, I needed to ask Kevin. IMPOSSIBLE ROAD is active on the various mobile stores and the Threes tragedy was still fresh. So I contacted Kevin to know if he liked the idea of a JS1k remake/adaptation or was rather reluctent to it. He was enthusiastic about the project.

Take one

The first prototypes made in November 2014 with my classic worflow looked promising: The basic idea to build the road was there, the rendering speed was descent too. But the project hit a dead end within two weeks.

This initial approach had several drawbacks:

Memory consumption and setup time were too big.
It didn't give enough control over the shape and curvature of the road.
The attempts of collision detections were messy.

Yet it proved that the project was doable with a bit more thinking. Some times the best thing to do is to sleep over a project. There was no rush and I needed to think some aspects through.

If you are so curious as to see this first version, here is the private gist and a bl.ocks link to see the first prototype of IMPOSSIBLE ROAD for JS1k 2015. Watch out. It is quirky!

Reboot

Fast forward to February 2015. It was time to reboot the project and the experience gained with the invitation for JS1k 2015 and its smoother workflow came very handy.

Starting fresh, with this new workflow, everything fell in place quickly and the compressed size was under control. I updated the private gist often, keeping Kevin NG in the loop with a live preview using bl.ocks.org.

Key ideas for a JS1k remake

The original IMPOSSIBLE ROAD is a pure 3D game, with physics engine and collision detection. Also there are severals roads, each of which is made of predefined sections. Obviously this wouldn't fit in 1kb of JavaScript.

1. Procedural generation

The only way to get an interesting and long winded road was to go procedural.

To control the shape of the road a noise function is required. The only "noise" functions availabe in a JS1k entry are Math.random() and the JavaScript source code itself. If you want repeatability and absolute control over the noise you use the later approach. This allowed to use a seed to generate different roads that are always the same for a given seed.

So I used the charCode of the source code itself with an ramp and a modulo to adjust the start position and range of the noise function for the different variables of the road.

In IMPOSSIBLE ROAD, the road are smooth, very smooth. Trying different approaches like . Applying a 5th order smoothstep ensured that all variables of the road were smooth, including the first and second derivative. No crease. No breaks. Just butter smooth roads.

Source code of the procedural generation

// F = the seed to generate different roads
F = Date.now()>>9;
// ...
// z = the position of road
// _ = the source code^H^H^H^H^H^H^Hnoise function
for(j=4;--j;) {
  s = z / (32+j*37-z/160/160);
  t=(_.charCodeAt(s+F&1023)%(12-j*3))*(s++>=j*4);
  u=(_.charCodeAt(s+F&1023)%(12-j*3))*(s++>=j*4);
  // smoothstep 5th = x*x*x*(x*(x*6-15)+10);
  s%=1;
  c[j]=t+(u-t)*s*s*s*(s*(s*6-15)+10);
}

The various components of the road vary smoothly over time, at different scale to produce a wide variety of roads.

2. Polar road

Doing collision detection in full 3D, per section of the road or per polygon, or even some approximation of the road would blow away the budget of 1024 bytes of this project.

It was clearly impossible to go full 3D. The JS1k remake of IMPOSSIBLE ROAD is actualy a 2.5D game.

The key change was to turn make one coordinate of the road ever increase. That way, I knew at all time the exact position on the road to do collision detection, count score, ... Combined with the twisting of the road, this effectively turned the road into an infinte helix of varying distance, angle and width.

On top of that, this allowed to compute the collision detection in polar coordinates by simply comparing the vertical distance to the road and the difference of angle.

This one change, made everything a million times more simple and compact without sacrificing too much of the sinuous aspect of the road.

3. Rendering

The reboot of the project started with real polygons. Unfortunately with 2D Canvas, the edge common to two polygons often have sub pixel holes.

Also the pattern of the road, alternating between blue and white 5 times accross each section would burn many precious bytes to draw using paths and polygons.

Here, the fast pace of IMPOSSIBLE ROAD helped us because we could get away with a more approximate rendering technique. The easiest to use and most compact drawing primitive in 2D Canvas is ctx.fillRect(x, y, width, height);

Using fillRect, the 5 strides that make each slice of the road can drawn with 3 calls:

A full width one in blue
Two smaller ones in white

The white strides need to be slightly taller to make up for the slight overlap of the blue stride of the next slide.

All in all, the rendering look likes this:

// z = the position 
// L = the perspective ratio
// c[3] = the width of the road
// i = the index of the slice of road for this frame
s = L * 8 - L * c[3] * 2;
t = L / (2 + i / 160);
// Draw the road slice in 'i'
c.fillStyle = a[160 + i - C * 8];
c.fillRect(-s, L * H - L * R - t, s * 2, t * 2);
u = s / 9;
// Reduce the width alternately by .3 and .6 for the white strides
s *= z & 4 ? .3 : .6;
// Increase the height for the white parts
t++;
c.fillStyle = '#fff';
c.fillRect(-u, L * H - L * R - t, -s, t * 2);
c.fillRect(u, L * H - L * R - t, s, t * 2);

Speed optimization

The original IMPOSSIBLE ROAD is a mobile game that goes fast. Really fast. The JS1k remake had to be as close as possible.

Reaching 60fps was not a problem on desktop, but on mobile this is another story. Everything is about 10 times slower.

Instrumentation

In order to track the progress I tried various instrumentations of the shim of JS1k showing the time to render individual frames, then the average number of frames per second in the last X frames. Of course I also profiled the code in the Developer Tool to find different bottlenecks.

Speed bottle necks

The first, and main, bottle neck was the generation and setting of the color of the road. Setting the fillStyle using the hsl(31,33%,73%) or rgb(31,33,73) notations took 6-8ms more per frame than using the #313373 notation on a beefy laptop. With that in mind I went beyond and preclaculated all the values needed. This probably cost around 50 bytes but every ms saved count.

// Precalculate the colors
// Setting a #hex fillStyle is much faster than rgb() or hsl()
for(i=444;--i;){
  a[i]='#';
  for(j=4;--j;) {
    a[i]+=Math.min(255,16+(i*5>>j)).toString(16);
  }
}

The number of slices of road rendered also changed over time from 1024 to 960, 384, 512, 444, ... as I was trying to find the balance between visual fidelity and mobile performance.

// Main loop
// ...
// Compute the components of the road
z+=444.5;
for(i=444;--i;){
  z--;

You can see that z, the position in the road increases by 1.5 per frame while we compute and render 444 slices of road. This 1.5 increment gave the best feeling of speed at 60fps.

With 400-1000 slices of road to render per frame, the number of canvas commands also had to be kept in check. Initially for each slice of the road drawn there was the following operations:

save
rotate
tranlate
fillStyle x2
fillRect x3
restore

This looks pretty innocent but this totalled to a really big amount of commands killing the performance. All these affine transformations and state handling were redundant. The 2D Canvas context has a nice method that allows to set the transformation matrix, thus changing the operations to:

setTransform
fillStyle x2
fillRect x3

Eventually, after optimizing the fillStyle, reducing the number of canvas commands and tweaking the size and number of slices of road, IMPOSSIBLE ROAD ran at 25fps on mobile.

Size optimization

Like with the invitation for JS1k 2015, size was always under control as I packed the code often.

When you code for a packer, you must reduce entropy and try to make little patterns of code that are exactly the same. For instance the inner and outer loops appear both in the setup and main loop.

Tooling

Some people use a build tool + Uglify + RegPack. Unless I miss something important, that doesn't seem to be the most efficient approach in term of final size.

Uglify'ed code often compresses better than quickly hand optimized code because it repeats simple micro patterns. However it is not made for client side compression and breaks macro patterns that were put in place in the original code.

Compressing the code of IMPOSSIBLE ROAD thus went this way:

Uglify the original code
Hand tweak by uglified code
Regpack the hand tweaked code

Each time!

This was the most tedious part of the workflow. Please let me know if you have any idea to prevent Uglify from mangling parts of a script or if you have another approach to this. The manual tweaks could made a difference of 40 to 70 bytes.

Without any better tool, I went for the "lazy" option and stuck to Uglify as I prefered to work at the macro level rather than deep dive into micro optmizations.

In retrospect, JSmin seems more appropriate, than Uglify, as an intermediate tool for JS1k.

Holy tool ?

You may remember WOLF1k, my first entry to JS1k, where I tweaked the packer to match a range of tokens using a very short regular expression.

Regpack took this further and again by automating of this process, allowing multiple ranges of characters for the tokens and renaming variables in the original script to optimize the ranges in the regular expression.

Since then a couple of compression tools hit the right spot, namely gzThermal and pngThermal which give some kind of thermal view of the packing efficient for every byte/pixel.

The holy tool might be a Frankenstein offspring of JSmin + Regpack + gzThermal with live editing and preview. It could also be a plugin for Sublime Text, who knows ?

One thing is for sure, we need better tools and I will look into this.

JS1k 2015 is a wrap

Again, there was some amazing entries in this new edition of JS1k. I'm particularly happy to see webGL entries making a great use vertex shaders where I feared to see a fragment shader showdown. The quality of the music was impressive too.

IMPOSSIBLE ROAD was a nice project with a couple of new challenges:

First time doing a remake of an active game
First time optimizing a JS1k production for mobile

Hope you liked the project. And another million thanks to [Kevin NG] who approved it.

A couple of regrets: I pondered about having a proper intro and game over screen but thought these would be more disturbing in the context of JS1k than of a game the user installed. It wouldn't hurt either if the physics simulation was more accurate.

All in all, I'm quite happy with the end result and hope you are too.

Source code

The original source code and all the revisions are available.

Feedback ?

You can find the IMPOSSIBLE ROAD at Pouet.net and JS1k. Suggestions and comments are welcome.

I would like to thank again Kevin NG for approving this project and his support. Really looking forward to try the next instalment of IMPOSSIBLE ROAD you showed at the Game Developer Conference.

Other recent experiments

There are many experiments and projects like IMPOSSIBLE ROAD 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.