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...

      2 kommenttia:

      1. Very cool tutorial, thanks for sharing.

        Just one question:
        for(Z++;i--;)D[i]=0;

        there has to be faster and easier ways to fill the ClampedUint8Array with 0s, maybe creating a previous one and doing a set?

        VastaaPoista
        Vastaukset
        1. Thanks! That bothered me too and I hope there is a shorter way that I have overlooked. The problem is that the array belongs to the ImageData object. I'm not even sure if all browsers use Uint8ClampedArray for the data property as that used to be something different in early HTML5 specs.

          Poista