I make maps. A lot of maps. Almost always of somewhere on Earth. It was time for a change.

The challenge: a procedurally generated map of this alternative Earth, produced on the fly, vector tile by vector tile. An easier approach might be to, say, first generate some continents and coastlines, then erode some mountains with rivers and dot towns in appropriate locations. But I wanted to have a tiny server with no global context. When the user’s browser requests the tile at ZXY coordinates 11/1976/1368, it quickly generates and responds:

So many challenges.

Dynamic vector tile generation

First, we need a server which can generate vector tiles on demand. We use NodeJS Express, with vector-tile specific libraries: vt-geojson, tilebelt, vtpbf.

1. Find the bounding box (in lat/longs) covering the area for the tile requested.
2. Generate data that covers that area, in GeoJSON.
3. Convert the GeoJSON to vector tiles.
4. Extract the one vector tile requested
5. Convert it to PBF (Mapbox vector tile format) and send it back.

It’s a bit inefficient to keep generating multiple vector tiles and only selecting one, but it’s simple. :)

It basically looks like this:

I’m using Glitch to host this server: glitch.com/~procmap

Deterministic generation

The big challenge for this kind of procedural generation is to make everything absolutely deterministic, even when it looks “random”. If a formula says the location of a given town is [123.1,-45.7] then it must always be that, no matter which tile the town is generated as part of. The basic strategy goes like this:

• Use the number-generator library to generate pseudo-random numbers.
• Before generating any random numbers for a given entity (town, road etc), seed the library with the hash of a string that uniquely identifies that entity.
• Make a lot of mistakes and get very confused.

Towns on grids

If we were generating the whole world in one go, we could iterate 1,000,000 times, dropping a town in a random location each iteration. Instead, we need to create a global, immutable structure that sort of always “exists” and relate each town to that structure. A simple way to do this (actually, the only one I could think of!) is to use a grid that covers the whole world, where each grid point is one town. That grid point is also the seed for the random number generator, and hence all the town’s properties (name, size etc) derive from its position.

How good this looks in practice comes down to how well we disguise the grid. By simply pseudo-randomly displacing each town up to half a grid coordinate in any direction, it suddenly looks much better:

Actually managing the grid was a bit fiddly. The random displacement means that we don’t know exactly which towns will end up within the vector tile we’re generating for. So we have to generate all towns in or next to the vector tile, then crop the ones that end up falling outside it.

Interesting towns

All the properties are just a question of finding formulas with attractive distributions and representing them appropriately. For instance, the size of a town (on a scale of 1-5) is: Math.ceil(random() * random() * random() * 5).

That is, a cubic distribution so there are far more tiny towns than big ones.

We generate town names with the fake-town-name library, which I wrote for this purpose. It’s pretty simple:

1. Take a random starting fragment (eg, Ton-, Hyde-, Lang-, Stam-)
2. Add a random ending fragment (eg -bury, -well, -mont, -rick)
3. Sometimes add a prefix (eg Outer, North, East, or nothing)
4. Sometimes add a suffix (eg Creek)
5. Hence create Outer Tonbury, North Hydewell, East Langmont Creek, or Stamrick.

Roads

The nice thing about roads is that generally they connect two towns, so we have a great place to start from. For each town, look at all the neighbouring towns (the grid makes this very easy!), and consider whether to connect it with a road.

However, there is a trap: our decision for connecting A to B must be the same as that for connecting B to A – and following exactly the same route. So, we use the western-most (northern-most to tie-break) of the two towns as the “A” to seed the random number generator.

The formula I came up with takes a couple of things into account:

• How near are the towns geographically (closer towns are more likely to connect)
• How big are the towns (a bigger town has more roads)
• A general ratio for the number of roads

There’s also a “size” property which is determined by the sizes of the towns at either end: bigger towns cause bigger roads betweens them.

Wiggles

Now, straight roads are boring. We can make a more interesting road by simply adding some extra vertices along the way. We can use a kind of L-system to do this:

• Between every two vertices, create a midpoint vertex.
• Randomly displace that vertex by a distance relative to the length of the segment and a “wiggliness” coefficient.
• Repeat as many times as required (“complexity”).

The wiggliness coefficient is affected by the size of the road (smaller roads between small towns are more wiggly), and the complexity is affected by the zoom level (so we aren’t wasting CPU cycles making very complex roads that can’t even be seen.

Water

Lakes and coastline are quite challenging. If we simply randomly decide that a given area is water or land, we will probably end up with an unattractive pattern of many fragmented lakes.

We start with the same grid structure as towns, but on a bigger scale. Next, we use Simplex Noise as a method for determining whether there is water somewhere. It naturally produces big clumps that work well for this purpose.

Perfect. Let’s distort this grid, too.

The one thing missing is interesting coastlines/lake edges. Let’s start by extending each straight edge into a triangle, with the tip a random location somewhere in the neighbouring cell.

Then we can apply the same complexification algorithm that we used for roads.

Finally,  by using slightly different parameters to these algorithms we can generate “deep water” and “beach” layers.

Forests are water

Forests are literally created using the same process as water, but slightly different parameters.

Limitations

One obvious limitation in this approach is that the layers we generate don’t interact with each other. We’re just slapping a lake over the top of the map and hoping no one notices that there are towns under there. Labels get cut off, highways mysterously disappear into the water.

Another problem is that it’s tricky to make things that require more than local context. We’d like major highways to purposefully connect distant cities, passing through small towns on the way. Not just starting and stopping at random. We’d like railways that similarly have an overall direction, and don’t meander too much. Most of all, we’d like streams that flow in one direction, continually merging with other streams to become rivers, eventually emptying into lakes and seas. I’m not sure how to achieve that.

There is also a reversability problem. We can generate a random location for a town from grid position, but it would be good to be able to find the grid position from the generated location. It would be nice to be able to search for a town name without brute force.

Finally, there are challenges with the vector tiling process. For instance, by restricting our search for roads to towns within the current tile, we miss out on roads that merely cross the tile without originating or ending within it. For instance, here the town from Katefields to Ilwick doesn’t show up in the bottom left tile, and the road from Morganburn northeast is not shown in the bottom right tile. We can reduce the visibility of this issue by using bigger vector tiles, but probably we just need to search a bit wider for towns.

All up, I’m pretty happy with the result. It’s been a lot of fun so far. :)

Have a play at stevage.github.io/alt-world!