Perlin noise is a really simple way to create contiguous regions with a contour that is both smooth and rugged at the same time. However, it is far from perfect. One problem is that Perlin noise has the same rate of change at all areas. Another, that Perlin noise on large scales is dissimilar to Perlin noise on small scales.
While Perlin noise is great for filling out shapes but is more difficult to use for describing contours, the coastline approach here is the opposite. The land is a list of points that define its contour. Its inside area has to be found post-hoc by a li'l function that counts the amount of line segments to the right of a given point - if the number is odd, the point is inside the polygon, if the number is even, outside. It's not terribly difficult, but it does take some computational ressources.
The biggest benefit of fractal coastlines is their incredibly high amount of detail, that tends to look quite natural, mostly independent of scale. However, Perlin noise doubles as an easy way to describe terrain height, which is an approximation of distance to the coastline. For the fractal coastlines, a more accureate distance can be found using some trigonometry, which might honestly be faster than with Perlin - though again, it will take its own script.
A fractal method for generating regions solves both these problems.
Here we see a very intricate coastline that, if you ask me, actually looks pretty natural. Overall, the algorithm is pretty simple and could easily be changed for further control of what parts of the coastline are more rugged and which are smoother.
But with this above example, it still is not very clear how the coastline is generated. Basically, you start off with a simple shape, like a triangle, and then you repeatedly double the amount of edges. This is done by bifurcating every line, then displacing the new midpoint. Or, with an animation:
The way that the coast is folded - that is, the midpoints displaced - is the same with the first iteration as the last iteration. The only thing that changes is the magnitude of displacement. One thing is to be noted - the magnitude is not dependent on the length of the line segment, but rather on the overall step. This means that short line segments are folded proportionally more than long line segments in the same iteration.
The reason this is important is that the coastline is not folded at the true midpoint of each line segment. Rather, a point between 1/4 and 3/4 of the way between the two points is picked. This is what leads to some areas having higher density of folding than others, creating the fractally nature.
What does fractal mean in this case? Well, long story short, that no matter how far we zoom in, there are still more details.
And if that isn't detailed enough, all I need to do is to let the algorithm run for a few more iterations. Infinite detail.
A question that comes up is how much control one should hand over to the fractal folding. The algorithm seems to work quite well as long as you can accept not really having much control over the process at all. Feed it a triangle, it'll make an island that isn't triangular at all. If you're okay with this spontanous creation of geographic features, this might be a better approach than Perlin.
Above is an example of trying to control the shape of the landmass. To the left is a low-poly model of the island of Great Britain, and to the right, the output of the fractal folding. There is a pretty good similarity, to be honest, and the low-poly nature of the input is not apparent at all. Of course, it isn't GB, and especially the Scottish highlands part is quite poor.
The reason the coastline keeps its shape is that the control points are not moved at all during the folding algorithm. This holds true for all iterations, too. Each iteration, the amount of points are doubled, but only the new points are ever moved. Not only does this grant a certain control over the shape of the terrain, it could also be used by cleverer people than I to do LOD loading with some massive landmasses.
Comparison to Perlin terrain
A question that comes up is how much control one should hand over to the fractal folding. The algorithm seems to work quite well as long as you can accept not really having much control over the process at all. Feed it a triangle, it'll make an island that isn't triangular at all. If you're okay with this spontanous creation of geographic features, this might be a better approach than Perlin.
Above is an example of trying to control the shape of the landmass. To the left is a low-poly model of the island of Great Britain, and to the right, the output of the fractal folding. There is a pretty good similarity, to be honest, and the low-poly nature of the input is not apparent at all. Of course, it isn't GB, and especially the Scottish highlands part is quite poor.
The reason the coastline keeps its shape is that the control points are not moved at all during the folding algorithm. This holds true for all iterations, too. Each iteration, the amount of points are doubled, but only the new points are ever moved. Not only does this grant a certain control over the shape of the terrain, it could also be used by cleverer people than I to do LOD loading with some massive landmasses.
Comparison to Perlin terrain
While Perlin noise is great for filling out shapes but is more difficult to use for describing contours, the coastline approach here is the opposite. The land is a list of points that define its contour. Its inside area has to be found post-hoc by a li'l function that counts the amount of line segments to the right of a given point - if the number is odd, the point is inside the polygon, if the number is even, outside. It's not terribly difficult, but it does take some computational ressources.
The biggest benefit of fractal coastlines is their incredibly high amount of detail, that tends to look quite natural, mostly independent of scale. However, Perlin noise doubles as an easy way to describe terrain height, which is an approximation of distance to the coastline. For the fractal coastlines, a more accureate distance can be found using some trigonometry, which might honestly be faster than with Perlin - though again, it will take its own script.
Also, Perlin noise easily creates several islands. Here, they each would have to be a completely seperate data-structure, and attention to be made to ensure they would not overlap. Really, the whole thing with overlapping is a problem I have not quite been able to solve. See the points where the coastline overlaps itself. Oops.
I really want to work more on this approach since it creates such realistic-looking coastlines, but it is just so foreign to me to work with polygons instead of region-grids. Let's see if something won't come of this in the new year.
Anyway, code and demonstration can be found on OpenProcessing. Also, credit has to be given to the Dragons Abound guy for the idea of a different sort of fractal coastline, inspiring this.
Very interesting! And your illustrations are much better than mine, as well!
ReplyDeleteThe biggest drawback (from my POV) with fractal coastlines is the lack of control over the overall shape. For me that makes it really hard to use this approach for the overall generation of land / coastlines. And I'm not 100% happy about how I adapted it to work on an existing coastline.
See my reply below (oops, replied in the wrong field)
DeleteIt is a bit of a tug-of-war between top-down control and bottom-up fractal influence. I was going to suggest just simplifying the desired landmass into a very simple polygon. However, the strange thing is that the original shape (triangle or square) is not particularly apparent in the final product, this despite those three/four original corners not changing at all. I'll be sure to let you know if one of my experiments finds a way to resolve this.
ReplyDeleteThanks for your tweet by the way, much appreciated!
Looks very promising to me, if you want to create many islands.
ReplyDeleteIt would be interesting to see a benchmark of how long it takes to generate an island, so that it is possible to approximate how long it takes to generate many islands/continents for a complete game world.
I could imagine, using it as an algorithm to generate the coastline of an continent, where you only apply the algorithm to sides, which are actual coasts, and then using perlin noise or voronoi to generate the continents heightmaps and so on.
Right, I never even thought of benchmarking it. Without a lot of optimisation and running in-browser on OpenProcessing on a cheap laptop, it takes between 222 and 242 (avg. 230.8) milliseconds to go from 4 vertices to 131072 vertices (that is, 2^17). This is around 8 times more detail than what is needed for a 1080p rendering - though this of course depends on taste and how folded the coastline is. In conclusion, after working with marching squares Perlin noise, it is preeetty fast.
DeleteI have some vague plans of doing something like what you describe at some point - several landmasses crudely rendered by Perlin noise, then made pretty with this algorithm. So if you won't do it, I will - you should try too, of course!