You can use the controls above to generate another terrain at random, or change the terrain type.
Pretty neat, huh? Graphics come from my colleague pOxaes plus the Android blob smileys.
I'll explain the two main parts to arrive at this image: how to generate a random terrain mask, and how to apply a (simple) rendering algorithm. Like most projects the general ideas are easy to understand but getting the details right is tricky!
First let me acknowledge that my approach for terrain generation is based on this great answer by bummzack. Basically it suggests to start by thresholding some 2D Perlin noise and go from there. I suspect there is a better vectorial way to do this, but this solution seemed relatively simple and so a good fit for a hobby project, and indeed I could get something working in a couple of days. I have since refined and optimized the process, here is a complete explanation in 8 steps:
First you start with the terrain type.
This is a low-resolution image that you can create with any image editor. Notice that there are three zones:
Initially I had only 2 zones(inside/outside) but it turned out to be difficult to generate hollows and bumps that would not encroach far into the outside zone. The additional blue zone is used to contain the encroachment.
In this step we paint the terrain on top of the noise.
Now we just have to get rid of the yellow part to see the first approximation of our terrain appears. Yellow(Perlin noise) is replaced by black(not terrain).
So far, the algorithms we applied worked by looping through the pixels of an image. There are a lot of pixels, but because these algorithms are relatively simple it all happens very fast.
For shaders I started from this library by Dominic Szablewski, that I adapted a bit to work with larger kernels(more neighbouring pixels) and different filters.
Next we apply a dilation filter, it makes our terrain grow.
Our goal is to remove all the tunnels and the hollows that are too small:
the size of the dilation should be the size of the regions we want to fill. Here we don't want any hollow to be less than 20 pixels (so that
our game characters can enter them), we do 5 dilations with a 5x5 kernel that looks like this(the white corners will smooth our contours a bit):
You don't want to dilate too much either, otherwise all our hollows and bumps would disappear.
In this step we want to get rid of the remaining holes in our terrain.
We do this by first applying flood fill on our background area. To seed the flood fill we use all pixels that are not terrain at the left, top, right, and bottom edges of the image.
Any black remaining after this gets turned to terrain, and we can move the yellow background back to black.
Now we can apply an erosion filter, to shrink our terrain back to the pre-dilation size.
In image processing, the dilation plus erosion filtering we used is sometimes called a closing. Basically it removes small background regions and smooth the contours a bit, without changing the overall size of the terrain.
Because the images on the right are reduced to give way to the explanations you will probably not see much of a difference, but this last step is actually crucial and probably the most difficult to get right, it is about anti-aliasing.
Up to here all the operations were in essence binary, a pixel is either terrain or not terrain. Additionally, to speed things up we worked on images 4 times smaller than the final result we want. This means that when scaled at the final size, our terrain has unpleasant jaggies at the contour.
As you can see the differences are quite subtle but there is a clear winner: the hqx algorithm
gives the clearest image, with sharp contours and no visual artifact. This is what I ended up using for this step, the output of hqx is the final
mask representing our terrain.
I didn't realize it at first but the two libraries I choose completely independently for doing WebGL filters and depixelating(hqx) are from the same author. Hats off!
Now that we have our terrain mask, how do we make it look nice? If you were doing a real game, at this point you probably need to integrate with a game engine library with tools for background layers, texturing, animations, and more. But because this is just a demo, we'll skip the library and do a simple rendering pass.
In this texturing step we loop through the pixels of our mask one by one. If the current pixel is off in the terrain mask, we just set alpha to zero. If it's terrain, we first set alpha to be the terrain mask value to preserve hqx anti-aliasing. Then we count the pixels on top before we reach the edge of the terrain: if there are less than let's say 8 pixels we'll assign some border color value, otherwise the pixel will be ground.
Ground pixels are textured from an image, and we apply a random translation to the texture to add some variation.
Before we can drop some characters on our terrain, we need to find where they can fit. Easily enough the surface pixels are the pixels at the top edge of our border.
To avoid collisions and spots that are too narrow, we apply a small erosion filter that will chop off some pixels at the ends of each surface segment. We also drop surface pixels that are too low, because this is where we want to add water.
Now we'd like to add some characters randomly, but with some minimal distance between them and ideally spread over the total length of the surface.
For this I used a pretty cool algorithm that I stumbled upon several years ago on a different project, the Halton sequence. Basically it generates pseudo-random numbers that cover a surface evenly, with the surface being more densely covered as you generate more points.
This means we can generate uniformly distributed points without knowing the total number of points in advance,
something that we could use in a game for dropping objects, adding more characters...
You can see the effect of the Halton sequence by changing the numbers of characters with the slider below:
Finally for a touch of animation we'll add some water. For that we can simply draw a semi-transparent sinus wave at regular intervals. To give a sense of depth we'll put one behind the terrain and one in front.
We end up with four layers to display: the background image, the background water, the rendered terrain, and the foreground water. There is no support for compositing layers in the canvas API, but from what I've read a common solution is to have one canvas per layer and stack them on top of each other. This is what I've done for the final result at the top of this page.
Thanks to all the APIs available in modern browsers we've been able to do some image processing and generate a pretty decent terrain all client-side. It's also reasonably fast, less than one second on my machine for generating a 1400x900 terrain image, and there are several places that could be optimized further if needed. I haven't covered all the details but the code is open source, hopefully with enough comments, so I invite you to check it out if you want to know more. And maybe reuse it for your own game?
Note: this article is discussed on Hacker News here.