875 words ~ 4-8 mins — Mathieu 'p01' Henri on August 17th, 2013


How to build a 3D City in 256 bytes with Canvas 2D

About a week ago I saw this cool post by Jerome Etienne explaining How to Do a Procedural City in 100 Lines of JavaScript with Three.js. It reminded me a lot of MINAMI DISTRICT, the winning JS1k entry I did for DemoJS one month earlier, and got me thinking.

How many bytes does it take to render a 3D city like in the legendary Extension by Pygmy Projects that won the Amiga demo competition at Assembly 1993.

234 bytes

<body onload=setInterval(F="for(x=w=c.width|=0,Q=Math.cos;x--;)for(i=0;i<32;i+=X%8==X&&Y%8==Y&&F[X|Y<<3]<':'?w:.5)X=14*Q(t)-i*Q(T=t+x/w-.5)+4,Y=14*Q(t+8)-i*Q(T+8)+4,c.getContext('2d').fillRect(x,i*6,1-i/32,3);t+=88",t=9)><canvas id=c>

That's it. No libraries. No dependencies.

How does it work ?

At 234 bytes there isn't much room to do things the right way, store data, change default properties, generate things procedurally, ... well, anything. So how the hell does it work ?

The shades of grey

The default fillStyle of Canvas is black. The shades of grey are done by drawing axis aligned rectangle less than a pixel wide. The sub-pixel width introduces anti-aliasing which results in a semi transparent black rectangle. Simple.

City planning

It turns out that we do have some data: the source code!

Placing the source code of the main loop into a variable allows us to compare the characters of that string and use it a map.

Since the source code is quite short, it was only possible to have an 8 by 8 grid which maps to the first 64 characters of the main loop. Looking at the ASCII codes used in that string, I decided to place a building for each character that comes before the character : in the ASCII table. In other words any of the following characters !"#$%&'()*+,-./0123456789 is a building.

for(x=w=  -->  ...#....
c.width|  -->  .#.....#
=0,Q=Mat  -->  .##.....
h.cos;x-  -->  .#.....#
-;)for(i  -->  #.#...#.
=0;i<32;  -->  .#..#...
i+=X%8==  -->  .#..##..
X&&Y%8==  -->  .##.##..

Dirty trigonometry

In order to save 4 bytes with the trigonometry code where two Math.cos and Math.sin are needed, an alias is created for Math.cos alone. Adding 8 to the angle gives a decent approximation of Math.sin. The margin of error is 0.15 radians.

At each frame the camera rotates by 88 radians, modulo 2π that is 0.035 radians, which means it takes ~177 frames to go around the city.

The rendering

Here we use some good old brute force: A fixed step raycaster.

The raycaster "walks" the city plan and stops rendering little shades of grey when it hits a building. The field of view is 1 radian wide. The camera looks at the center of the city and spins around it.

As the rays are walked further from the camera a shade of grey is drawn onto the canvas. For each step further from the camera, we move a few pixels down onto the canvas and use a lighter shade of grey.

We move on to the next ray and column on the canvas when we hit a building or the bottom of the canvas.

Final bytes

The initial version of MINI DISTRICT was neat as a first shot but let's be honest, it looked cheap and not much like a city. With 22 bytes available, it was high time to crank this up to 256 and bring back the city.

<body onload=setInterval(F="for(X=x=h=c.height|=Q=Math.cos;x--;)for(i=j=1;i<h;c.getContext('2d').fillRect(x*2,i,U^X?1.7:2,j-i/h,i+=j))j^1||((U=X,X=15*Q(t)-i/8*Q(T=t+x/h-.5)+4)|(Y=15*Q(t+8)-i/8*Q(T+8)+4))<8&&F[X|Y<<3]<Q&&(j=19-i/8);t+=88",t=9)><canvas id=c>

As you can see the buildings now have floor dividers, and different windows/shading on their North-South and East-West side.

Improved shading

This uses the same technique as the initial version except that we do the tiny subpixel rectangle in both direction:

One for the vertical gradient of the sky line, the other for the shading of the buildings which is based on the integer difference of the X position of the rays cast from the camera.

If the integer difference is not null, it means the ray hit the building while crossing an East-West line.

Optimized city planing

Alrighty the city planing is 18 bytes in the final version but it does a lot more things. It also does them correctly unlike the initial release.

Restricting the buildings to an 8 by 8 grid is now correct and more compact thanks to the simple formula (X|Y)<8. It works like charm because it check the values unsigned. Therefore negative values become far greater than 8.

Also since we have a better shading technique we can show more buildings without looking messy. That way we can save two bytes by replacing the ":" by any of the strings or objects available since they would be implicitly cast to a string. The candidate were F, c and Q. The last one proved to produce the most interesting city.

What about the initial version ?

Using these new optimizations should bring the initial version around 220-225 bytes. But who wants to see this now ?


As usual for my demoscene productions, MINI DISTRICT is available on where any comments and gestures are appreciated. Hope you like this little production. It was fun optimizing this effect. Twice.