MINI DISTRICT
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 ?
Karma
As usual for my demoscene productions, MINI DISTRICT is available on Pouet.net where any comments and gestures are appreciated. Hope you like this little production. It was fun optimizing this effect. Twice.