Post Mortem
Island Not Found is a game by Ben Clark and Salvatore Previti for https://2020.js13kgames.com/
PLAY IT HERE https://js13kgames.com/entries/island-not-found
MIT License, Ben Clark, Salvatore Previti, 2020
https://www.linkedin.com/in/ben-clark-18bb3b20/
https://www.linkedin.com/in/salvatorepreviti/
The game is rendered primarily using a technique called "ray marching" or "sphere tracing". This is where you define the world as a mathematical function representing a distance to the nearest geometry. It is much more inefficient (in processing) than standard polygonal rasterization, but appears to be much more efficient in code size. Curved surfaces are easier to render with better fidelity and less overhead, since there is no triangulation involved.
The Art of Code on youtube has a great introduction: Ray Marching for Dummies!.
You can see a lot of amazing examples of the technique on Shadertoy.
Earlier in the year we were working on a demo using these techniques and had learnt a lot. The demo never got completed as coronavirus hit and we lost all motivation when the party (Revision) became online-only.
However, with what we had learned, Salvatore suggested we should use the techniques for our next js13k entry and try to blow everyone's mind with what's possible within the size limit.
There are not many games around based on raymarching, so we were not sure we could make this work especially in the limited amount of time we had. As always, we deeply enjoyed working together and we are really happy of what we could achieve.
How the game would appears rendering just the distance from the camera in grayscale (divided the maximum distance)
We met up on day 1 after work and after the theme (404) was announced and began deciding what we should build.
The general linking of these things from 404 was ideas about finding things, being lost, Lost (the TV series), not knowing where you are. Combined with what we knew was possible with ray marching techniques, we settled on a Myst style adventure game on an island. Some sketches of what the island could look like and the idea for the start of the game (waking up in a Prison, finding a key to get out).
Despite the fact that the theme 404 would connect very well also with a futuristic and hi-tech concept, we tried to do something different, considering also that in 2019 we submitted the cyberpunk/sci-fi inspired game xx142-b2.exe.
Ben created a Trello board to keep track of tasks and Salvatore wrote a script collecting all the ideas, features and texts. We based the development on the script and the board. Naturally, we changed several requirements during the development taking into consideration performance, time and size constraints or simply better ideas that came with time.
The first thing was to set up a comfortable development environment & build system for us. Developer experience is important! vitejs was used to have a very fast dev mode with hot reload. With a bit of work, the dev mode showed FPS, time, rendering and other debug information while playing and on screen error details in case of error. With a little of custom code it was also possible to implement a fragment and texture hot reload, to keep the game state valid while reloading the shaders on file change. The initial code included also a math and vector library and rudimentary camera controls so that we could start to build geometry and move around it.
Since we had to make an island, we decided to work on that first. Salvatore was to work on building a height map, while Ben worked on the rendering side.
Ben initially used a downloaded island heightmap image and got that rendering
First rendering based on a heightmap image
Salvatore was working on using FBm fractal noise to generate an island height map procedurally. We flip-flopped between generating it within the main shader and generating it in javascript. Generating it within the shader seemed to be too slow as you need to recalculate all the noise every iterations of the ray-march loop, of which there can be hundreds per pixel. Generating it in javascript seemed to require too much code and too much loading time. In the end Salvatore settled on generating a heightmap texture with a shader and passing that to the main render shader, so we only needed to generate the texture once.
An early render based on Salvatore's heightmap code
The final version of the terrain heightmap took 3 intense days, trying different algorithms and types of noise. In the end, a simplex noise paired with some manual adjustments and math tricks provided the best results. One key point is that once the terrain was marked as complete there was no way back, the famous Butterfly Effect would have forced us to change again the positions of all the buildings over it on even a small change in the heightmap generation.
The final heightmap. In game is a 4096x4096 pixels texture with a float from 0 to 1 encoded in the RGBA channels
To feed the island with a bit of entropy a pseudorandom generator was used to fill a texture with noise. We used that texture for several things, including the heightmap generation. An optimization trick used is to store in green, blue and alpha channels the neighbour values of the red channel so with a single texel fetch is possible to know what are the values of the neighbour cells. Xoshiro pseudorandom generator was adopted because is very small in code size and provided a good random distribution compared to other tested algorithms. Since the shape of the island depends precisely on all the pixels in this texture, we were very careful also during refactoring to not change it.
A detail of the noise texture with its channels. R, G, B and A in white.
Ben's primary role was creating geometry for the game. Armed with the simple primitives of Sphere, Cuboids and Cylinders, the first thing he built was a bridge that could be rendered with a customisable number of "segments". The bridge is made our of just cylinders and cuboids. We use a technique possible in raymarching to divide the world up and repeat geometry efficiently, essentially performing a "modulus" on the world position so that it repeats.
The first version of the bridge Bridge code
We had an idea to make things quite "brutalist" - concrete and simple structures. This fits well with ray marching and our aesthetic preferences. The next thing Ben designed was an early version of the radio antenna/satellite dish structure. The antenna is build with a sphere that has been cut part-way up to produce the dish, along with some additional cylinders, sphere and a cuboid for the main structure.
The first version of the antenna, set in the first version of the island heightmap Antenna code
The sea is a flat axis-aligned plane. We lift the sea up and down entirely in order to simulate waves with sin(time).
Because it is a flat plane, it is easier and cheaper to ray-trace rather than ray-march. So we in fact calculate the sea separately from the rest of the geometry.
We then take the closer of (geometry, sea) and render that. Where they are very close together we render the sea with some transparency using the computed distance to drive the transparency.
The water surface color and normals are determined by a simple Fractional Brownian motion with few octaves computed in the main shader once per pixel, reducing the octaves the more a pixel is near the horizon to optimize performance. The random texture is used to feed the FBm.
Example of water rendered with 1, 2, 3, 4 octaves
The colours of the island are simply based on the normal and altitude of the render point. we mix between green and brown based on the dot-product of the normal to the vertical (essentially: more flat = more green, the more vertical = more brown) We then mix this with a sand colour based on the altitude (y-axis) of the point.
We also add some noise with the noise texture in order to make it a bit more interesting
Code for the terrain texturing
Other colours/materials are defined by a global variable that is updated based on the object that is nearest as the ray is marched. The noise texture is also used to provide a concrete-style effect on the structures.
Code for the various geometry colours
By changing the terrain height dynamically is easy to see how coloring is performed depending on height and normal
The prison is made of a cuboid that has been "onion-skinned". Onion skinning is a surprisingly simple operation: abs(distance) - width. This hollows out the geometry (abs, so the inside of the primitive is also a positive distance) and gives the original surface (where distance=0) some thickness.
We then use a cylinder to cut out the windows. And another single cylinder for the bars on the windows. The window bars are duplicated by repeating the space in x axis, and mirroring the space on the z axis.
We call this the "Monument". It is produced with a single cuboid. We use an operation that divides the space by angle so that any geometry gets repeated around the origin.
The original antenna was expanded with an onion-skinned cylinder to make a room that can be entered. Additional cylinders used to cut holes for the windows and door.
The oil rig is the most complex geometry in the game, but is again simply produced by combinations of cylinders and cuboids. We used a lot of world-mirroring functions in order to reduce the number of operations. But it is likely the heaviest part of the code and you can get noticeable frame-rate drops when nearby.
The guard tower is made almost entirely of cylinders. The holes cut into it are made with combinations of space and angle repetition. We needed to show some movement on the elevator, so we added the cuts into the elevator shaft to make the movement clearer. This required an additional primitive - the torus.
We were very surprised and happy that the elevator worked without any special code. Just moving the geometry and the collision detection algorithm worked to move us up and down within the elevator.
The submarine was a late addition as we needed to come up with an end-game and a way to escape the island. It uses a smooth-minimum operation to smoothly combine an elongated sphere(for the body), cuboids (for the tail) and an elongated-cylinder (for the protrusion at the top)
Collision detection of the player with the surrounding world is performed on the GPU with some post-analysis on the CPU (classic map-reduce implementation). We didn't know if this could work, we had an idea on how roughly this could be done but we did not have any idea if it could work. Since day one, Plan B was to do a classic point and click adventure without freedom of movement if this was not possible to do. We achieved our collision detection algorithm during a live pairing sessions, and then iterated upon separately.
Salvatore initially set up the code infrastructure so that we could separately render a smaller texture based on the distance function in the shader. After a lot of trial and error, we decided to render a 128x128 image which is a Cylinder of points around the player, representing the distance from nearest object.
Based on the center 64 rows of this texture we analyse it and push the camera away from anywhere that is intersecting with geometry. Based on the bottom 32 (actually the top 32 because the texture appears inverted) rows of this texture, we calculate how close we are to the ground and push the player either downwards or upwards.
Collision Shader code
Collision Resolution code
Example of collision inside the prison. The small black rectangle on the bottom left is what the collider sees. Green blobs indicates a collision
All the game logic and animations logic fits in a simple and straightforward state machine implemented as an object in JavaScript. Rendering is decoupled from the game logic and we pass the state of the various levers, doors, bridges through uniforms values to the shader at every frame. Text on screen is a div with position absolute over the 3D canvas that gets updated in JavaScript depending on the player position or game state. This implementation makes extremely easy also to save and load the current game state by serializing and deserializing the state machines.
The screens in the antenna room are simply made by rendering an invisible Canvas2D to a texture. With WebGL is quite a straightforward operation, and indeed this gives quite well the illusion of a working computer in the game.
For the minigame we update the texture only when the user press a key so it has really a minimal overhead on the rendering performance. We decided to lock the player position in front of the computer during the minigame but we left the ability to look around with the mouse, to not break the illusion of being in a 3D world.
We wanted a simple minigame but had to be very aware of the size constraints. The sin-wave matching game ended up taking approximately 375 bytes.
The music was composed using SoundBox and we incorporated the player library into the game. This initially added about 1.8kb after compression, but this was reduced later through some modifications. Neither of us are musicians but I (Ben) have played with trackers before this, so understanding the soundbox interface was easy. I wanted something quite chilled out but also a little bit creepy, to enhance the feeling of being alone on the island.
The biggest problem of raymarching, as stated before, is that it is quite inefficient on current hardware. It requires a lot of GPU power to render also the simplest scene, and this means that old machines can easily suffer from very low framerate. This could have affected the playability of the game in old(ish) or cheap(ish) hardware. We used an Intel integrated GPU on a MacBook pro during development, testing from time to time on other machines with more powerful or slower GPUs and to maintain a playable framerate several tricks were employed.
The easiest one was to use "cone tracing" instead of just sphere tracing, incrementing the epsilon used to detect the surface hit condition with the distance from the camera. This made the code more complex in several points, including the material detection, but ensured a faster render time.
Another technique we employed is to wrap every main geometry with hierarchical bounding spheres and cylinders with "fuzzy" edges (a form of geometry culling). Those bounds are cheap to calculate and allow to skip the computation of complex geometries when not visible from the current fragment.
The biggest improvement, however, was obtained by prerendering the distance from the camera on a smaller texture (256x256) every frame using a larger initial epsilon (the size of the pixel plus another small epsilon). This allowed to begin the raymarching iteration for a block of pixels from a known shared minimum distance in the main render instead of starting every time from the camera position.
GLSL code was refactored multiple times to keep the framerate between 40 to 60 FPS.
The hardest part to optimize was the real time soft shadows. In the end we could not make any particular useful optimization on that also if Salvatore invested two days in research and experiments. Poor Salvatore is still not sleeping at night thinking at ways how to optimize soft shadows :) Help him if you can!
All those optimizations have of course a cost in terms of size, but by continuosly iterating between optimizing for code and speed the result was a good compromise between both.
iterations count heatmap, without optimizations, 36fps
iterations count heatmap, with optimizations, 60fps
While for our previous game xx142-b2.exe we didn't have to put much energy in code golfing, this time much more effort was required.
A large portion of the final bundle is occupied by the GLSL code. To reuse functions, uniforms and variables across multiple shaders, the best solution was to have a single big file and switch the main function to use with a string replace when loading. The GLSL transpiler on the browser (ANGLE) already perform unused function elimination and constant folding, so it was not a concern to load unused variables and functions.
-
void main_h()is the heightmap shader, called only once at startup to render to texture. -
void main_c()is the collision shader, called every frame to render to a buffer. -
void main_p()is the prerender shader, called every frame to render to texture. -
void main_m()is the main shader, called every frame to render to screen.
Our fragment.frag file has 1034 lines! Since this is a lot of GLSL code, spglsl, an experimental GLSL minifier written in C++ based on ANGLE and compiled in WASM for NodeJS, was necessary to stay in the 13k limit. Unfortunately we didn't find any working or very powerful webgl2 (shader version 300 es) minifier around, so I made my own with constant folding, name mangling and basic dead code elimination.
The good thing about ViteJS is that with the same configuration it bundles with rollup when compiling in release mode. With the addition of terser, babel and eslint (yes, even some eslint autofix rules to make the code smaller) and a lot of custom glue code we had a strong builder and minifier in our hands that even suprassed closure compiler for this specific codebase from our tests. Terser was also configured to mangle every object property starting with underscore, so we did not have to sacrifice code readability for code size too much.
For zipping, adm-zip monkey patched to use zopfli instead of zlib was used to reduce the zip file even more.
Changing a bit the source code of the Soundbox player also helped to save some more bytes in the final build.
It was needed to do several rounds of refactoring every few changes to reduce the code size and optimize the performance.
- [before day 1] experiments with ANGLE, experiments with ViteJS and the build system, vector library, study of raymarching.
- [13 august] brainstorming, drawings
- [14 august] pipeline and dev tools
- [15 august] pipeline and dev tools, camera, raymarching
- [16 august] heightmap png texture and rendering
- [17 august] heightmap, materials, bridge, monument, camera improvements
- [18 august] heightmap, noise texture, raymarching improvements
- [19 august] water raytracing, raymarching improvements
- [20 august] water FBm, the prison, the bridge, colours
- [21 august] fog, optimizations
- [22 august] player initial position, door, key, objects and animations
- [23 august] integration with soundbox, initial work on the collider, spglsl
- [24 august] spglsl, merged shader, collisions experiments
- [25 august] better lighting and fog, water specular, water improvements, realtime shadows
- [26 august] better lighting, final heightmap, final location for existing geometries, collisions
- [27 august] collisions, flashlight
- [28 august] torch item, oil rig, collisions, final script
- [29 august] sun in the sky, antenna and antenna console
- [30 august] computer screens, antenna and door animations, all the script main elements, size improvements, monument animation
- [31 august] better lighting and shadow, guard tower, elevator, floppy disk, main menu
- [1 september] prerender texture, menu
- [2 september] prerender texture, texturing, multiple materials and colours
- [3 september] speed and size optimizations, camera rumble, clamp camera position, save and load
- [4 september] better lighting
- [5 september] better shadows in water, submarine, save and load, frequency minigame, song, size optimizations
- [6 september] size optimizations, camera fixes, elevator dents, console colors, menu improvements
- [7 september] delayed ending, better music, mipmaps generation, better spglsl mangling algorithm
- [8 september] better rendering quality, head-bob, geometry final touches and colours, music volume slider
- [9 september] performance and size optimization, rendering quality improvements
- [10 september] disable load and save when needed, size optimizations
- [11 september] refactoring and optimizations, better lighthing, oil rig ramp lever, debugging and cleanup, OS13K trophy, endgame
- [12 september] better lighting, small improvements and adjustment, final tests, RELEASE!!!
- [13 september] Sleep.
- https://github.com/SalvatorePreviti/js13k-2020 - The repository containing all the source codes.
- https://www.iquilezles.org/www/index.htm - Thank you! Your articles are amazing, truly inspiring, and our shader code is heavily based on your work. And we love ShaderToy!
- https://github.com/mbitsnbites/soundbox - The tool that Ben used to compose the music.
- http://mercury.sexy/hg_sdf/ by MERCURY - We used or adapted some functions from this amazing library. Thanks MERCURY!
- https://www.shadertoy.com/view/Xl2XRW - We got inspiration from here for the water Fractional Brownian motion.
- http://prng.di.unimi.it/ - We used xoshiro pseudorandom number generator to feed randomness to our virtual island.
- https://developer.mozilla.org/ - for documentation
- https://www.gamasutra.com/view/feature/131326/designing_and_integrating_puzzles_.php?print=1 - Designing and Integrating Puzzles in Action-Adventure Games by Pascal Luban
- https://twitter.com/kostik13337 - for helping us in testing and fixing the font for Linux
- spglsl - https://github.com/SalvatorePreviti/spglsl experimental GLSL minifier based on ANGLE project
- vitejs - https://github.com/vitejs/vite an opinionated web dev build tool that serves your code via native ES Module imports during dev and bundles it with Rollup for production.
- rollup - https://rollupjs.org/guide/en/ JavaScript module bundler
- terser - https://github.com/terser/terser JavaScript minifier
- esbuild - https://github.com/evanw/esbuild an extremely fast JS bundler (and TypeScript transpiler)
- TypeScript - https://www.typescriptlang.org/
- node-zopfli - https://github.com/pierreinglebert/node-zopfli ZOPFLI compressor for NodeJS
- adm-zip - https://github.com/cthackers/adm-zip pure JavaScript implementation for zip data compression. Monkey patched to use node-zopfli instead of zlib.
- csso - https://github.com/css/csso css optimizer and minifier
- clean-css - https://github.com/jakubpawlowicz/clean-css css optimizer and minifier
- html-minifier - https://github.com/kangax/html-minifier HTML minifier
- babel - https://babeljs.io/ a JS compiler, to add some minification additional steps
- and NodeJS, GitHub, eslint, prettier, husky, lint-staged, chalk, and many others.
Yes, this png files is 1.2 megabytes, a jpeg screenshot of the game is around 200k. The whole game is 12.8k (zipped), 29.3k (unzipped).
