Contours

Now that I’ve got a heightmap, I can start generating contours at regular intervals. Fortunately, d3 already has a built-in contour generator! I’m going to use the density estimator version, since I think the regular mode will give too discrete results, and would involve me generating lots of data points.

The density contour generator takes an array of points, and generates an area where the density of the points is similar. For each polygon in my heightmap, I can take the centroid (the red dots) and then pass that point into the generator multiple times, based on the height of that polygon.
That will effectively set the density equal to the height, so I should get some decent contours out! A few lines of code later…

…well, it’s a start.

I’m guessing the issue is since the density is so spiky around the centroids of the polygons, this leads to large variations of density around the heightmap points. I could pick a random point within the polygon instead, which would hopefully reduce the variation.
Picking a random point within a polygon isn’t trivial, so instead I’m just going to pick a point within the bounding box of the polygon, and simply try again if that point turns out not to be in the polygon.

That definitely seems better, but I can see a problem here. My polygons are not all the same size, so smaller polygons naturally have a higher density than larger ones. I can fix this by scaling the number of points I pick for each cell by the area of the polygon.

Perfect! That’s looking pretty good to me. OS map contours have a slightly thicker stroke every 5 intervals, so I can put that in pretty easily as well. The final version:

The birth of progenos

git init
Well, guess that’s the project officially started! I’ve dubbed it progenos (procedurally generated OS) for now.
I’ll be using d3.js, as that’s what both Martin O’Leary and Scott Turner are using for their map generators.
First off, I want to just get something rendering in my browser. Usually when I start these projects, I get overwhelmed with thinking about webpack+babel+react+redux etc., so I’m going to keep it simple this time. Before worrying about generating a realistic terrain map or anything complicated, I just want to draw some simple concentric contour lines as circles in SVG.

Well, that was easy! Next up, I’ll generate a separate heightmap and try to plot the height as a greyscale map.
I’ll need a grid system, so I’m using the method detailed here.
Using Poisson Disc Sampling generates a set of nicely-spaced random points:

I can then get the DeLauney triangulation of these points (black), and the centroid of each of those triangles (blue).

Once I’ve got the centroid points, I can construct polygons from all the centroids that share a base point (green).

Now that I’ve built a mesh of points with their associated neighbors and polygons, I can generate a simple greyscale heightmap by choosing a polygon at random to be set to a large height, then raising each of the neighbours of that point by slightly less, and so on. In code:

function addHill() {
  var handled = new Map();
  let startPoint = randomElement(mesh);
  let amount = 0.9;
  function iteration(points, amount) {
    if (amount < 0.001) {
      return;
    }
  
    let next = [];
    for(const s of points) {
      handled.set(s.id, true);
    }
  
    for(const s of points) {
      s.height += amount;
      next = next.concat(s.neighbors.filter(y => !handled.has(y.id) && next.indexOf(y) === -1));
    }

    iteration(next, amount * 0.75);
  }

  iteration([startPoint], amount);
}

Adding a few hills gives me something like this:
Perfect! Next time I’ll start looking into drawing contours around this heightmap at regular intervals.

git commit

Hello!

Finally set up a blog (about 15 years after it became cool), as a hope that it will encourage me to actually finish a project! I’ve been enjoying bullet journalling recently, so this seems like a logical extension to that.

The DM of our D&D group is using a procedural map generator in our campaign, and that led me down a rabbit hole of googling about procedural map generation. I’ve spent the last 2 days pouring over the fascinating Here Dragons Abound blog, and the equally interesting page on generating fantasy maps by Martin O’Leary. When I was younger, I spent a lot of time in the Scouts and basically grew up with Ordnance Survey maps, and I thought it would be an interesting challenge to try and procedurally generate an OS-style map fragment.

I don’t know how far I’ll get with this, but I’ll try to chronicle my progress here!