TerrainVer
Worms-style cartoon terrain in JavaScript

Last year we started a for-the-fun project with some colleagues: a Worms clone in JavaScript. While we didn't get very far, I had good results(and great fun!) working on terrain generation. It's now open source and this page will serve as both a detailed explanation of the algorithm and a demo:

There was a problem loading the interactive demo, screenshots are displayed as a fallback mode.
To access the demo make sure you run a recent version of your browser, try to empty the cache and reload the page.
Loading...
Smaller noise Larger noise

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!

Part I: Terrain generation

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:

Step 1

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.

Step 2

Next as suggested in bummzack answer you add some Perlin noise.

This generates continuous "wrinkles" of different size over the image. I used this JavaScript library by josephg to generate two layers of noise:

Step 3

In this step we paint the terrain on top of the noise.

We do this by applying the flood fill algorithm(the bucket tool in a paint program) from all the points at the border of the red zone. For a fast way to do this, I translated to JavaScript this c++ code by Lode Vandevenne.

Step 4

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 the next steps, we'll need to apply some filters to our terrain like the ones in an image editor software. This is done via an operation called a convolution, where the value of one pixel depends on the values of all its neighbours. We can do this in JavaScript with nested for-loops but it would be very slow. Instead we'll use a WebGL shader, which is a fancy way to make the GPU run all these for-loops efficiently.

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.

Step 5

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.

Step 6

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.

Step 7

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.

Step 8

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.

To improve things I first tried to apply successive mean filters, or average filters, followed by a threshold pass. When repeated multiple times for both the red and the black regions, this greatly improves the contour but there is still some aliasing(Avg below). Looking for a solution online, I learned that there exist a number of algorithms for my anti-aliasing/depixelating task, even some recent research. I could implement Scale3x as a filter, and found JavaScript libraries for the xBR and hqx algorithms. Here is a comparison of the results:

Original

Avg

Scale3x

Xbr

Hqx

Original

Avg

Scale3X

Xbr

Hqx

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!

Part II: Terrain rendering

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.

Step 9

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.

Step 10

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.

Step 11

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:

Less characters More characters

Step 12

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.

Conclusion

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.


Home
Fork me on GitHub