maanantai 12. toukokuuta 2014

Making of Highway at Night

After finishing 6th in JS1k 2013, it was clear that I wanted to give this fun competition another go. First off, here is a list of things I took as "lessons learned" from my last year's entry:

  • Performance needs to be good with all devices
  • Controls take a lot of space and aren't always important
  • Many small visual details can be overlooked, so rather polish the important features
  • Let compressors help in making the code compact
What follows is an explanation of ideas and techniques behind my "Highway at Night" demo that was the runner-up in JS1k 2014.

1. Visual approach

 

 My initial idea was to do a very realistic looking demo of a car driving along a highway on a dark night. I watched some dashcam videos on YouTube and realized that what we see in real life is very limited - it's mainly just lights and silhouettes. I made notes on what I saw and how I could try and implement it. But first I needed a good yet small engine for road construction and rendering.

I wanted the demo to have true perpective 3D drawing combined with cheap tricks. I found out that I only needed to do the center line with real polygons and somehow that makes everything else around it look more realistic. Also using shadowBlur on the center line alone is enough to give the impression that all lights are glowing. I would have liked to do a lot of blurred lights but the performance cost was huge and I didn't want to fall into the same trap as last year. So the initial idea of photorealistic graphics was dropped in favor of vintage video game looks. Another thing that helps to fool the eye is high speed. This allowed the graphics to be very simple and raw as you can see from the "sprite sheet" below. Car lights are slightly offset to give a hint that the cars are at a small angle. Turn signal and emergency lights are animated. All these graphics are drawn with fillRect.



Imagine how much fun it would have been to add trucks, motorcycles, KITT and so on with this approach. The frustrating part about the 1kB limitation is that you have to leave a lot of stuff out. 

2. Track engine


The road is defined by an array of horizontal offsets from the center. The array itself is generated procedurally by a loop that runs 600 times. Every 30th time it creates a new target offset and the actual track points are calculated between these targets with a simple ease-in-out algorithm. Initially I had a much more complex track, but in the end used a cosine wave to save space. The hills are also defined with a cosine wave that depends on track position. It's not recorded to the array, but rather re-calculated each time. So now we have the track data as horizontal and vertical offsets from the center of the screen. To project we use the simplest possible 3d projection and just scale the offsets and road width based on distance. This works fine otherwise, but will eventually cause the road to move off the screen. So we need to have the camera follow the road and also make it look in the right direction. The most natural feeling is achieved when camera looks towards the point in the horizon where the road disappears. This is done by interpolating between that point and the camera position and adding that value to the corresponding horizontal offset. 

The camera position moves along the track and sees 100 steps ahead of the total 600. When it reaches the end it loops back to beginning. The visible distance is looped backwards while rendering so we are using the painter's algorithm for z-ordering. Objects are placed along the track in intervals defined by conditional statements that take remainders as input. For example if the remainder of track position divided by 8 is zero we draw a street light. For cars I use two offset variables that allow their placement to change constantly.

3. Rendering tricks


The theme of the competion was dragons, so instead of keeping the camera on the road I wanted it to seem like the viewer was flying. It turns out that translating and rotating the canvas in cosine waves is enough to pull this off. I found the right formulas by just experimenting. These things are never as complex as they might look.




For a 1kB demo it would be best to use one type of drawing method with everything. Using fillRect was the obvious choice and it almost worked great. But I couldn't live with the center line if it wasn't a real polygon and so I had to spend lots of bytes on path drawing. I think it was a good choice though. All other things on the screen are rects - road, cars, lights, tunnels, buildings... But the ground feels like it is drawn with some weird wireframe polygons. This is actually just another trick. What's really going on is that we draw vertical lines that are slightly rotated based on track position. Because the angle and line thickness follows the track position it gives the appearance of hills. I was very excited to come up with this technique and it really made the demo come alive.



4. Creating the atmosphere


I paid special attention to the sky as it creates the atmosphere for the whole demo. It consists of a changing background color, flickering stars and a moon. Even though the end result is very simple, and the code behind it seems obvious, it took a lot of effort to get there. At first I tried and failed with gradients, used expensive random numbers to place stars, and added the moon with a special character. When you ran out of space you start to rethink everything, make compromises and always notice how much simpler things can be. What you see in the final version is created like this...

    // Sky with some polar light effects
    c.fillStyle="hsl("+99+m%99+",50%,9%)";
    c.fillRect(-600,-600,1200,600);

    // Flickering stars
    for(c.fillStyle=c.shadowColor="#FFF",i=600;i--;)c.fillRect(400-i*i%800,-i%600,1,Z*i%.9);
   
    // Moon
    c.fillText("(",99,-99);


Variables m and Z change with track position, and they are used here to make the sky color and star size change. You can imagine how stupid I felt when I realized I could replace the charcode for a moon with a parenthese. :)





5. Conclusions and source code


Most important technical aspects of this demo:

  • Using modulus operator (remainder) on the track position index is the key to placing objects along the track, but also helps in adding all sorts of effects
  • Cosine waves are everywhere to achieve that analog feel
  • HTML5 canvas translate and rotate functions were used to do visually striking effects with very small cost

This time around I used Siorki's RegPack for compression. Last year I wasn't familiar with the use of compressors and I didn't get much help by using one. I still haven't learned to take full advantage of them but after some tests it was clear to me that repeating code patterns works better than creating special functions.

Finally here's the full source code...


// Create track
for(T=[B=F=Z=D=i=0];i<600;i++){
 if(i%30<1)m=D,D=1800-(i%4-2)*600;
 T[i]=m+(D-m)*(.5-Math.cos(i%30/9)/2)
}
// Timer loop
setInterval(function(){
 m=Z/5|0;
 
 // Reset canvas and fill with black
 c.fillRect(0,0,a.width=a.height=600,600);
 
 // Dragon flight waving and tilting
 c.translate(300,300+Math.cos(Z/99)*99);
 c.rotate(i>540?Z/50%6:Math.cos(i/9)/9);
 
 // Sky with some polar light effects
 c.fillStyle="hsl("+99+m%99+",50%,9%)";
 c.fillRect(-600,-600,1200,600);

 // Flickering stars
 for(c.fillStyle=c.shadowColor="#FFF",i=600;i--;)c.fillRect(400-i*i%800,-i%600,1,Z*i%.9);
 
 // Moon
 c.fillText("(",99,-99);

 // Loop through visible distance of the track
 for (i=99+m;i>m;i--){
  D=i-Z/5;
  
  // Hills
  y=Math.cos(Math.cos(i/9+i/50)+8)*300;
  
  // Calculate road and camera direction from track data
  O=T[m]+(T[m+1]-T[m])*(Z%5)/5-T[i];
  
  if(i%3<1){
  
   // Draw ground and hills
   c.rotate(Math.cos(i)/9); // Do we need to rotate at all?
   c.fillRect(-600,300/D+y/D+9,1200,Math.cos(i));
   c.rotate(Math.cos(i)/-9);
      
   // Draw white lines
   c.shadowBlur=D<9?30:0;
   if(i%2){
    c.beginPath();
    c.moveTo(-30/D+O/D,300/D+y/D);
    c.lineTo(30/D+O/D,300/D+y/D)
   }
   if(i%2<1){
    c.lineTo(30/D+O/D,300/D+y/D);
    c.lineTo(-30/D+O/D,300/D+y/D);
    c.fill()
   }
   c.shadowBlur=0
  } 
  
  // Road
  c.fillStyle="#000";
  c.fillRect(-600/D+O/D,300/D+y/D,1200/D,60/D);
  
  if(i%8<1){ // Draw street or tunnel lights
   c.fillRect(-800/D+O/D,300/D+y/D-800/D,30/D,800/D);
   c.fillStyle="#FFA";
   i%400<80?c.fillRect(-100/D+O/D,300/D+y/D-600/D,200/D,50/D):c.fillRect(-600/D+O/D,300/D+y/D-800/D,80/D,20/D)
  }
  if(i%400<80){ // Tunnel walls
   c.fillStyle=i%2?0:"#222";
   c.fillRect(600/D+O/D,300/D+y/D-900/D,1400/D,900/D);
   c.fillRect(-2e3/D+O/D,300/D+y/D-900/D,1400/D,900/D);
   c.fillRect(-2e3/D+O/D,300/D+y/D-900/D,4e3/D,300/D)
  }
  
  // Draw cars
  c.fillStyle="#000";
  if((i+~~B)%30==0){
   c.fillRect(150/D+O/D,300/D+y/D-200/D,260/D,160/D);
   c.fillStyle="red";
   c.fillRect(180/D+O/D,300/D+y/D-90/D,60/D,30/D);
   c.fillRect(340/D+O/D,300/D+y/D-90/D,60/D,30/D);
   // Turn signal
   c.fillStyle="#FFA";
   i%300<99&&i%9<5?c.fillRect(140/D+O/D,300/D+y/D-90/D,60/D,30/D):0
  }
  if((i+F)%40<1){
   c.fillStyle="#000";
   c.fillRect(-400/D+O/D,300/D+y/D-200/D,260/D,1/D*160);
   c.fillStyle="#FFA";
   c.fillRect(-240/D+O/D,300/D+y/D-90/D,60/D,30/D);
   c.fillRect(-400/D+O/D,300/D+y/D-90/D,60/D,30/D);
   // Police car
   if(i%200>99)
    c.fillStyle=i%2?"red":"#00F",
    c.fillRect(i%3-(i%2*80+260)/D+O/D,300/D+y/D-220/D,60/D,30/D)
  }
   
  // City
  if(i>500&&i%4<1)for(j=i%9*8;j--;)
    c.fillStyle=j%5?"#FFA":"#999",
    c.fillRect((i%12?-2e3:2e3)/D-j%5*200/D+O/D,300/D+y/D-(j-j%5)*60/D,200/D,200/D);
  
  c.fillStyle="#999"
 }
 // Integrate car movement
 B-=.3;F+=.5;
 // Move forward and loop back to start if track ends
 Z++;Z%=3e3
},20)

sunnuntai 28. huhtikuuta 2013

Making of 3D City Tour

"3D City Tour" was my entry for JS1K Spring '13 JavaScript programming competition. In this article I will explain how the demo was done and hopefully it will inspire others to push the limits of JS further and further.

To better understand what the following is all about first check out the demo if you haven't done so already  - "3D City Tour". Be sure to do the same with all JS1K demos past and present. There's a lot of brilliant stuff there!

The rules of the competion in short:
  • 1kB or less JavaScript
  • No external resources
  • Code must work in Firefox, Chrome and Opera
  • Code has to work in provided shim
I like to program tricks that simplify complex things. To get something done with 1024 bytes of code you need a lot of them. There are many ways to make the code itself compact but that's not enough to fit worlds into 1kB. You need to come up with a concept that in reality is very limiting but gives the illusion of something bigger. There are countless ways one could do a procedural city. There are also many ways to approach 3D projection. What I did evolved from an idea to combine "Mode 7" style ray casting with a height map.
    1. Building the city
      First I create a grayscale birdseye view of the city which will be the texture for raycasting. "Why grayscale?" you might ask. Because defining colors takes lots of space. I'll later explain how we work around this limitation.


      Above are images of the texture and height map arrays drawn in 2D. In the first pic you can see that I've created overlapping grids. First layer is just small rects with some darker spots. Then some areas are made lighter. Last layer draws the streets. When the array is read I add an offset which creates the central boulevard. The height map defines the size and shape of the buildings. In the zoomed part of the second image you can see the small traffic signs and an example of a building with a more interesting structure. Both of these arrays are created within a single loop and combining loops is in my opinion a very important part of size optimization.

      2. Camera and controls

      Since this is a 1st person view "game", we don't need to actually draw the player but simply define a moveable camera. The possibility to freely fly or drive around the 3D city is perhaps the most impressive feature of the demo. The camera is defined with 5 variables - yaw, pitch and position coordinates in three dimensions.



      Mouse pointer position relative to the center of the canvas element is used to calculate yaw and pitch. Speed is constant and pitch only affects the change in height - not camera orientation. Little compromises like these save a lot of bytes.



      Collision detection is done based on camera height. The collision response is simplified to two cases shown above. Since spring was the theme of the competition it was only fitting to add the possibility to jump from roof to roof.

      3. Ray casting

      I like ray casting. :) Here we simplify the process into what I call floor casting. We are mainly interested in the lower half of the screen. We shoot rays in reverse - from right to left and bottom to top (front to back). This makes the loops more compact and, since I keep track of the highest drawn pixel, I never draw anything in vain. Most of the time I don't even need to ray cast most of the pixels. For each screen pixel we find the corresponding coordinate on the city texture to be used as the color.


      Below are screen captures showing how the city texture looks after the normal ray casting process and how it looks after we apply the height map information. We simply draw the texture pixel vertically until the perspective corrected height map value is reached.


      4. Rules for coloring

      None of the above images look like the demo yet. We need to add the colors and now you'll finally see why I used grayscale for the texture. Here's the trick: add rules to adjust RGBA channels based on height map data. This is very simple but also very effective...

      • If height is zero adjust green channel. For most grayscale parts this means they turn more green (grass) but if the grayscale value is slightly higher than the new green channel we get a purple tint (streets)
      • If height is not zero, make the highest pixel brown -> roofs
      • make the second highest pixel transparent -> white frames on buildings and traffic signs
      • If the pixel is outside the texture make it blue -> water...
      • Change alpha channel based on height -> fake shading
      • etc.
      Keep adding conditions and the picture comes alive!


      5. Sky gradient

      Sky gradient is done with another compact algorithm. I first tried to use canvas gradients but they took too much space. I started to experiment with ways to have a gradient that would look like there were sun rays coming in from the side, further emphasizing the spring theme. Once I found the right formula I made the main color change based on camera position. This gave another cool feature with very minimal cost. You can see how the palette changes from blue to yellow in the image below. This gives the illusion of camera facing in different directions in relation to the sun.




      Sky drawing loop also checks if the current image data array index is already set. If so, it won't draw anything on it. This takes care of the reverse Z-order problem and also improves performance a bit.

      6. Making waves

      Everything outside the texture map is water (sea) making our city reside on an island. It looked boring and lifeless so I first tried adding some random sparkles to it. It looked ok from distance but what I really wanted was some waves. By simply experimenting,  I found a way to do a moiré pattern. From some angles it looks really wacky!



      7. Other little things

      Cars are done by height map alteration. They always go in one direction and appear back from the other side when they reach the shore.

      Distance fogging is done by changing opacity based on distance from camera. Common and cheap trick that always works.

      Auto pilot is based on the way movement integration and collision detection work. I just give good initial position and angle for the camera so the first views look nice. Then the camera circles endlessly between the island and the sea. This feature was important to add so the demo could be enjoyed without a mouse around.

      Nesting ternary operators was the key to fitting this demo inside the 1kB limit.

      The wonderful JSCrush by Aivo Paas was used for the final compression.

      Reusing variables helps compress code. For example I use 410 as the width and height of canvas, but also for the dimensions of the texture and heigth map. I use 40 everywhere from timer interval to space between streets. Just round and quantize numbers as far as possible without it showing clearly in the demo.

       8. HTML5 stuff

      I first tried to do the texture with canvas drawing functions but I could do it a lot smaller by using an array. So at the end I'm just using getImageData and putImageData functions from the canvas API. In other words all drawing is done by manipulating an RGBA data array.

      Conclusions and source code

      Finally I'd like to mention that this was my first time taking part in any programming competition and I wasn't prepared at all for it. I started working on the code way too late and learned many things after the deadline. I'm still very happy with the entry overall but now I know how to make it smaller which would allow me to improve the visuals and performance. There was also a bad mistake in my code which really bugs me. :) I'm taking the liberty to publish the source of the corrected version here...

      // Canvas size
      c.width=c.height=w=410;
      W=w/2;
      // Camera data
      cx=cy=h=99;
      cp=Z=0;
      // Height map and texture arrays
      hD=[ca=.9];
      d=[X=-20];
      // Listen to mouse move events
      c.onmousemove=function(e){
          X=e.clientX-W;
          Y=e.clientY-W
      }
      
      // Timer loop
      setInterval(function(e){
          // Integrate movement
          cx+=Math.cos(ca+=X/w/9); 
          cy+=Math.sin(ca);
          h+=cp=h<4?.1:cp-Y/w/9;
          
          // Collision detection
          if(hD[(cx|0)+(cy|0)*w+W]/7>h)cp=1;
          
          // Raycasting
          for(x=w;x--;){ 
              L=w;
              R=ca+Math.asin((x-W)/w);
              for(y=700;y>W;y--){
                  T=w*h/(y-W);
                  tX=cx+T*Math.cos(R)|0;
                  tY=cy+T*Math.sin(R)|0;
                  i=tX<0||tY<0||tX>w||tY>w?0:tX+tY*w+W;
                  k=hD[i];
                  o=k*50/T|0;
                  N=y-o<0?0:y-o;
                  if(N<L){
                      // Distance fogging
                      s=T/w;
                      l=s>1?0:U/s;
                      // Rendering
                      for(o=L-N,L=N;o--;){
                          j=(x+N*w+o*w)*4;
                          D[j+3]=l;
                          D[j]=U;
                          if(!k||o){
                              // Red channel
                              D[j]=k==U?99:k&&!(o%9)?U:d[i];
                              // Green channel
                              D[j+1]=!k?99:d[i];
                              // Blue channel
                              D[j+2]=i?d[i]:W;
                              // Alpha channel
                              D[j+3]=o&&o<w/T&&L>1?U:i?l+=Math.cos(s):Math.sin(R*T)>.8?l*.8:l
                          } 
                      }
                  }
              }
          }
          // Sky
          for(i=3;i<w*w*4;i+=4)
              if(!D[i]){
                  D[i]=(w*w*4-i)/w/9*(i/4%w)/i*3*w;
                  D[i-1]=W;
                  D[i-2]=D[i-3]=cx
              }
              
          // Put image data buffer to canvas
          a.putImageData(I,0,0);
          
          // Clear buffer
          for(Z++;i--;)D[i]=0;
          
          // Cars
          Z%=w;
          for(i=9;i--;){
              o=5+U*i+Z*w;
              if(Z<w-1)hD[o]=9;
              hD[o-w]=0
          }
      },U=Y=40) 
      
      // City creation
      for(i=w*w;i--;){
          x=i%w;y=i/w;
          
          // Buildings
          z=y%U>16&&x%U>11?Math.abs(Math.cos(x/U|0)/Math.cos(y/U|0)*h):0;
          hD[i]=z<U?0:x%74>U&&y%75>U?z/ca:z; 
          
          // Tiling and roads
          d[i]=(x-3)%U<4||(y-3)%U<9?h:x%8<2||y%9<2?0:Math.cos((x/8|0)+(y/9|0))<ca?hD[i]&&x%W>h&&y%W<h?U+h:U:0; 
          
          // Traffic signs
          if((x-8)%U>38&&(y-2)%U>38)hD[i+1]=U    
          } 
      
      // Create image data buffer
      I=a.getImageData(0,0,w,w);
      D=I.data;

      Feel free to post any questions or comments! More JavaScript madness coming soon...