In map generator projects that generate polygons[1], I often want to use the polygons for the structure of the map:
But I don't want the player to see polygons on the final map. I use "noisy edges" to hide the polygon structure:
On this page I'll show you how this works.
I've been using a mesh structure[2]. Red points are the interiors of the polygons. Blue points are the corners of the polygons.
In addition to the polygons and their duals (triangles, not shown), there's another structure that's useful. We can build quadrilaterals out of two red points and two blue points:
Let's look at one of these quadrilaterals more closely:
We're interested in drawing a line between the two blue points:
These lines are used for the polygon boundaries, which might be the borders between biomes, the coastlines, or rivers.
We want to vary this line while keeping it inside the quadrilateral. We can use a variant of midpoint displacement. Pick a division point between the red points. Use it to divide the line segment between the blue points into two shorter line segments:
Once we have picked a division point, it forms four smaller quadrilaterals. We'll use two of the quadrilaterals to further subdivide the line:
We can repeat this process, recursively dividing the quadrilaterals, each time picking a random subdivision point that breaks a line segment into two shorter ones:
This gives us a noisy line between the blue points, with two parameters to control how noisy it is:
amplitude =
I used a variant of this in my polygon map generator project in 2010 but never explained the technique in detail until now. In that project I picked the green division point along both axes instead of only the red point axis. I haven't explored that variant here. Making these diagrams made me realize my old code was not only buggy, but unnecessarily complicated. For this project I needed to pick a point only along one axis.
An amplitude parameter of 0.5 seems pretty good in this demo but the best value will depend on your map and your needs; I ended up using 0.25 for my map generator, but I think an even lower value might be better. You can choose the number of levels by calculating when the line segments become too short to matter (a few pixels/tiles).
There's something weird when going from 0 levels to 1 level. Try setting amplitude to 0 and levels to 0, then levels to 1. There's a bend in the line. But from 1 to 2 or more, theres's no change. That means that at all but the top level, the intersection of the red segment and blue segment occurs at the midpoint of the red segment, but at the top level it does not.
I feel that the noisy edges from this algorithm can be a little too “sharp” but that's something to investigate later. For coastlines and rivers, noisy edges aren't the only option. I also want to look more closely at Scott Turner's blog[3] and Azgaar's blog[4]. For biome boundaries, I want to try noise-based dithering.