Monday, 7 April 2014

Journey to the Perfect Island

I took a two-day break from work to have a long weekend and some rest, and rest included working on a small project: island generation. My goals were simple, I wanted to make a procedural terrain generator that would create nice looking islands, and a triangle based isometric renderer in OpenGL.
First I calculated on paper the view transformation matrix to render a 2d heightmap as triangles, and wrote a wireframe renderer to check my calculations.

The view transformation was alright, so I added a noise texture and green colour to the triangles. First I also tried adding Gouraud shading, but it was ugly and the exact geometry couldn't be seen, so I switched to flat shading.

So rendering was sufficient, it was time to start generating the terrain. My plan was to generate a fractal heightmap, and then multiply the height values with a scaled 2d Gaussian function to have some land in the middle and quickly reach zero, that is, sea, as getting further away from the centre. After checking out a few methods (e.g. perlin noise, simplex noise, midpoint displacement) I chose the diamond-square method to generate the terrain, because it seemed to result in nice looking terrain quite fast.

It was not hard to implement it, and I was satisfied with the result. I also changed the viewing transformation from the skewed triangles to a more traditional isometric view. As the next step I have added the multiplication step with the 2d Gaussian bell curve, and also created the sea (and I saw that it was good) which is just a semi-transparent blueish plane slightly above the zero height level.

Looks good, right? Nope. It's the most boring island ever, a single pointy mount in the middle, an almost perfect circle shoreline, and most of the features from the fractal terrain are smoothed out.  I refined my expectations: interesting mountains, nice beaches and complex shoreline. As a fix I tried to add the Gaussian function to the noise heightmap instead of multiplying with it.

Now it's not terribly awful, just relatively bad. The features of the original fractal terrain are somewhat kept, but it is still just a single mount and a circular shore, no nice flat beach... far from perfect. I went back to reading articles and in the end found this one, which described a method similar to mine, but used another function instead of the Gaussian. It looked good, so I gave it a try.

Somewhat better, but still boring. I wanted something like this, with the constraint that it should be an island. The problem with that method was that it was based on Diffusion-limited aggregation which seems to be a looong process to me, and also the result is not always an island. After a good night of sleep I came up with a new and simple method: I would generate a random walk with Brownian motion to define the skeleton of the mountains, and apply Gaussian blur (you can't escape Gauss) a few times with different radii to smooth it into hills and shores. It took a while to code the Brownian noise generator and the Gaussian blur, but it was worth it. When I finally saw the first generated island I immediately knew that this was what I wanted.

This method seems to satisfy all my criteria: complex mountain structures, wide flat beaches, interesting shoreline. The shape of the island is mostly defined by the result of the Brownian noise, and the size is somewhat related to the steps used to generate the noise, though it can be stuck in a small place and result in a small island even with many steps. The implementation needs some tweaking (resample the terrain for higher resolution, rewrite the Gaussian blur to use a separated kernel instead of the O(N^2) slow naive 2d convolution, and fine tune the number of steps for the random walk and the radii of the blurs), but otherwise I'm very satisfied with the method. Now I can play with decorating the island, and soon I will have my own island with palm trees and beaches.