Tribute to MINECRAFT, voxel flyby in 252 bytes of HTML5
Motivation
About one year ago Notch wrote a Minecraft flyby in JavaScript in 4kb with procedural textures, camera, fog, ... It was really cool and fast. The code was mostly optimized for speed, so surely with some efforts it could fit in 2 or maybe even 1kb.
Two weeks ago, I released WOLFENSTEINY and the feedback was absolutely amazing. The only way to go from there was to go one notch further and go full 3D.
Source code
<body onload=setInterval(F=";t+=.1;Q=Math.cos;for(x=n=c.height=300;x-=4;)for(y=n;y-=4;d.fillRect(x,y,E,Z^z?4:E))for(D=0;(E=4-D/2)&&F<F[(t+D*Q(T=x/n-.5+Q(t/9))&7)*8|(Z=3.7+D*Q(T-8)&7)*4|(6.5-D*y/n-E)];z=Z)D+=1/8",t=55),d=c.getContext('2d')><canvas id=c>
Tada! 252 bytes of 3D voxel world witchcraft with camera and fog.
Two four eight for the kicks
<body onload=setInterval(F=";t+=.1;Q=Math.cos;for(x=n=c.height=300;x-=4;)for(y=n;y-=4;c.getContext('2d').fillRect(x,y,E,Z^z?4:E))for(D=0;(E=4-D/2)&&F<F[(t+D*Q(T=x/n-.5+Q(t/9))&7)*8|(Z=3.7+D*Q(T-8)&7)*4|(6.5-D*y/n-E)];z=Z)D+=1/8",t=55)><canvas id=c>
Here is a version of MINICRAFT in 248 bytes, just for the kicks! It's exactly the same, only a little bit slower.
How ?
You might wonder how the rendering engine, camera path and the 3D world fit in 252 bytes of HTML and JavaScript. Well, it's a mix of many techniques and nice and dirty tricks.
Tiny shoulders
Really, MINICRAFT is only standing on the itsy bitsy shoulders of WOLFENSTEINY, TEA STORM and MINI DISTRICT. I invite you to read the technical details of these little demos.
Rendering
Considering the target size of this demo, there was no room for a fancy rendering technique. It had to be brutal: Fixed step raymarching.
If you wonder what this three cryptic words mean, this is pretty simple. It means that a function representing the world you want to display is evaluated for pretty much every point in space to the points you actually display. So you have this big function, and you resolve it thousands, hundreds of thousands, of times per frame of your animation without the slightlest speed optimization.
Resolution
The default resolution of a Canvas is 300x150. Setting either the width or height of a Canvas clears and resets it so to maximize the resolution at the lowest cost, the best approach is to set the height to 300 at each frame.
Thus our canvas is 300x300. But the rendering technique is too heavy to raymarch that many rays. Dividing the resolution by 4 we end up casting, and walking, 75x75 = 5,625 rays. Since we walk in 1/8 increments until we reach a solid block or reached a distance of 8, this account for up to 75x75x80 = 450,000 tests per frame.
I've got the world on a string
At such small size, there is no space to generate, store or have wild distance function for the map, so we are left with using the only data we have: The source code.
Indeed, placing the source code of the main loop into a variable, called F
, allows us to compare the characters of that string and use it as a map of the empty/solid blocks in a 3D grid.
Since the source code is quite short, it was only possible to have an 8 by 8 by 8 grid which maps to the first 64 characters of the main loop and gives us a world made of 512 voxels. Looking at the ASCII codes used in that string, I decided to have a solid voxel for each character that is or comes before the character ;
in the ASCII table. In other words any of the following characters !"#$%&'()*+,-./0123456789:;
is a solid block. Choosing this specific character cleared a straight line in the map which allowed to have a simple camera path.
The 3D function used in MINICRAFT is very simple:
// F = the source code of the main loop
';' < F[x + z * 4 + y * 8]
Now, you might remember something odd that you saw in the source code of MINICRAFT.
<body onload=setInterval(F=";t+=.1;Q=Math.cos;for(x=n=c.height=300;x-=4;)for(y=n;y-=4;d.fillRect(x,y,E,Z^z?4:E))for(D=0;(E=4-D/2)&&F<F[(t+D*Q(T=x/n-.5+Q(t/9))&7)*8|(Z=3.7+D*Q(T-8)&7)*4|(6.5-D*y/n-E)];z=Z)D+=1/8",t=55,d=c.getContext('2d'))><canvas id=c>
See how the code of the main loop, F
, starts with ;
. This seemingly pointless semicolon allows to gain one byte on the already compact 3D function by turning it into:
F < F[x + z * 4 + y * 8]
Raymarching and the camera
As I said above, the 3D function features a clear straight line for the camera to navigate through. Rays are cast from the origin of the camera in the view frustrum, and for each pixel of the rendering surface, we walk slowly along the ray and evaluate the 3D function until a solid block is hit or a maximum distance is reached. The further the rays is walked, the smaller and brighter the shade of grey for that pixel.
for(x=n=c.height=300;x-=4;)for(y=n;y-=4;/* draw a shade of grey D in x,y */)for(D=0;/* evaluate the 3D function in X, Y, Z */;z=Z)D+=1/8
The outer loops go through each x,y pixel and draw the resulting shade of grey. The inner loop walks along the ray corresponding to the x,y pixel until it hits a solid block in the map.
The X, Y, Z components of the current position along the ray are computed and composed like this to evaluate the 3D function:
// with (E=4-D/2)
(t+D*Q(T=x/n-.5+Q(t/9))&7)*8|(Z=3.7+D*Q(T-8)&7)*4|(6.5-D*y/n-E)
Which really means Y 8 | Z 4 | X
, but let's break this down:
// the angle the camera looks at is
cA = Math.cos(t/9)
// the angle the current ray points to
rA = x / h - .5 + cA
// D represents how far we have walked
// along the ray, also the camera moves
// on a straight line in Y which gives us
Y = D * Math.cos(rA) + t
Z = D * Math.sin(rA) + 3.7
X = D * ( y / h - .5) + 2.5
It's all a blur
Dithering, fog and shades of gray
The default fillStyle
of Canvas is black. There is no space to change it so we need to find a way to get more colors. The shades of grey are done by drawing axis aligned rectangle with a fractional width and height. The sub-pixel dimensions introduce anti-aliasing which results in a semi transparent black edges. Simple. Since we draw such rectangle for each ray, we end up with some kind of dithering.
The shading itself uses the same trick as MINI DISTRICT and WOLFENSTEINY, we check the integer Z coordinate of the ray before and after hitting a solid block to know whether we hit a wall facing Front-Back. You remember the main loop ?
;t+=.1;Q=Math.cos;for(x=n=c.height=300;x-=4;)for(y=n;y-=4;d.fillRect(x,y,E,Z^z?4:E))for(D=0;(E=4-D/2)&&F<F[(t+D*Q(T=x/n-.5+Q(t/9))&7)*8|(Z=3.7+D*Q(T-8)&7)*4|(6.5-D*y/n-E)];z=Z)D+=1/8
The important parts here are the Z^z?4:
, Z=
and z=Z
which store and compare the consecutive integer Z coordinate of the ray.
Number magic
MINICRAFT uses a couple of clean and dirty number tricks I have rarely seen explained elsewhere. Hopefully sharing them will give you a few ideas for your next production.
IEEE-754 floating point numbers
We all know how floating point numbers are suboptimal for applications that need exact numbers. The IEEE-754 standards is based on binary and combination of powers of two which yield rounding errors.
This means that in JavaScript and many other programming languages 0.1 + 0.2 = 0.30000000000000004
. This is unfortunate in many cases, but when all you deal with are powers of two, IEEE 754 fits the bill perfectly and that allows for a few tricks.
See by how much we march along the ray at each step ?
for(x=n=c.height=300;x-=4;)for(y=n;y-=4;/* draw a shade of grey D in x,y */)for(D=0;/* evaluate the 3D function in X, Y, Z */;z=Z)D+=1/8
That way we can easily check when D reaches 8.0 because the following expression reaches excatly zero which is falsy and exits the inner most for loop:
(E=4-D/2)
The value E corresponds to the size of the rectangle we will fill for this ray, but the value shares some properties with X component of the ray. All in all this optimization saves 3 bytes.
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.
Feedback
Of course MINICRAFT is available on Pouet.net where all comments and thumbs up are appreciated.
To be continued...
Other recent projects
There are many experiments and projects like MINICRAFT to discover other here.
- BLCK4777
- IMPOSSIBLE ROAD
- JS1K 2015 INVITATION
- SHEET
- WOLFENSTEINY
- TEA STORM
- TV NOISE
- RUBBER IN SOLID #