Around The World, Part 18: Charting the seas
Maps will be an important part of the game. Let’s take a look at how we can draw those!
By “maps”, I don’t mean your usual in-game map, which is always there in the corner of the screen, tracks your position and orientation, knows all parts of the world, and is never wrong. No, I’m talking about the kind of maps that sailors in the age of discovery actually used: sketchy, partly based on hearsay, woefully incomplete, often just plain wrong, and with no built-in GPS to tell you where on the map you are.
In the real world, it takes a lot of effort to remove incompleteness and wrongness. In our perfect computer-generated world, it takes effort to add them. So let’s first try to come up with a complete and correct map instead.
(Aside: if you like reading about procedural map generation, I can highly recommend Here Dragons Abound by Scott Turner. Scott’s map generator does way more than I can ever hope to achieve, and he blogs about it in detail.)
Maps? Maps?!
Actually, using the word “map” is not quite right at best, and almost blasphemy at worst. The correct term is “chart”. NOAA’s National Ocean Service is almost condescending towards maps:
A chart is used by mariners to plot courses through open bodies of water as well as in highly trafficked areas. Because of its critical importance in promoting safe navigation, the nautical chart has a certain level of legal standing and authority. A map, on the other hand, is a reference guide showing predetermined routes like roads and highways.
Nautical charts provide detailed information on hidden dangers to navigation. Maps provide no information of the condition of a road.
Here’s an example of a typical chart. This one was drawn by Johannes Jansson around 1650:
It’s a good example of the style I’ll be aiming for.
Charting the coast
We have a height map of our world, so the easiest way to produce a topographical map (and yes, this is more like a map than a chart) is to apply a colour scale to these heights:
It’s start, but it’s still a far cry from Jansson’s beautiful work. Our height map focuses on the land, whereas nautical charts usually had very little detail on land; only features that are helpful in navigation were drawn. So let’s start by detecting coastlines from the height map using a marching squares algorithm. Drawing the coastlines on a nice parchment-like texture:
Okay, that looks more like it. But without prior knowledge, it’s hard to distinguish land from water. The old charts address this in several ways:
- Shade either land or sea, often only along the coast. Or shade both with a different colour.
- Draw rhumb lines (those criscrossing compass lines) only on the sea.
- Place city labels only on land.
I’d like my charts to have some variety, so I’ll implement at least the first two. Because I’m detecting contours as closed loops anyway, it’s easy to give each landmass its own distinct colour:
It’s more readable, but perhaps a bit over the top. How about shading only near the coast? This requires me to implement a distance transform, which thankfully is well documented (Meijster, Roerdink, Hesselink, 2002):
That looks a lot more professional. Let’s also add a windrose network to fill up all that empty space:
Lakes
We still have a small problem:
The coastline detector detects every transition between land and water, including ones inside a continent. These are lakes, and would historically not have been included in a coastal survey. More importantly, they make the chart look cluttered and aren’t reachable by the player anyway.
Fortunately, it’s easy to detect whether a polygon is a lake or a coastline, because one will be oriented clockwise and the other counterclockwise, so we can just get rid of them:
Unfortunately, this leaves us with another problem, because the land colouring is based on the original land/sea matrix, so it isn’t aware that we removed some polygon outlines. A second, smaller problem is that islands inside lakes are still drawn; see the yellow spot just above the ‘k’ in ‘Gdansk’.
A more robust approach is to fill lakes in the land/sea matrix, effectively replacing them by land before we trace the coastlines. Let’s classify as a lake every water area that’s fully surrounded by land. This does mean that lakes touching the edge of the chart won’t be removed, but we’ll deal with that later. It nicely gets rid of lake polygons, islands inside lakes, and land colouring in one fell swoop:
That’s looking a lot cleaner.
Ports
So far, I’ve been using a tiny placeholder icon to represent cities:
Surely we can do better. Somebody by the name of Zarkonnen recently published a great asset pack of map icons extracted from a 1688 German map:
The city icons are probably too big and detailed for our purposes, but the town icons fit nicely:
However, their placement leaves something to be desired. The icons currently overlap the coastline too much, showing half the city in the water.
Right now, the icon sprite is centered on the location of the city. However, the icon is quite a bit bigger than the actual city would be on the chart, causing it to stick out into the sea. Let’s try moving each icon a little in each of 8 directions, and pick the one that gives the greatest overlap with land. To make it clear what’s happening, I added some debug drawing:
This shows the actual city location in red, and the candidate icon positions in blue. The green rectangle indicates the portion of the icon that we try to keep on land. The algorithm seems to be doing a reasonable job. It sometimes puts the icon in a slightly misleading position (most notably Zeebrugge), but this does not seem to happen a lot, and in-game we can just blame it on the chart author!
Name labels
You may already have spotted the other problem: the city name labels also overlap coastlines, and each other. Let’s tackle that next.
In general, this is a hard problem to solve, because every adjustment you make to the placement of a single element might cause it to overlap other elements, which would then also need to be moved, which might have a cascading effect. The aforementioned Here Dragons Abound started with a force layout algorithm to solve this, but eventually switched to simulated annealing. That’s a rather big hammer though, so I’ll try something simpler first.
First, I’ll give each label a few possible placement positions, and check which of those gives the least amount of overlap with the coastlines:
Additionally, there is a weight factor assigned to each of the placements, to give some preference to the label being put to the right of the icon, instead of to the left, above or below.
This algorithm makes a valiant attempt to avoid coastlines, but it doesn’t yet avoid overlap between labels. For that, we can simply add previously drawn labels to the area that should be avoided:
You can see that the Qingdao label has moved to make room for Jubail. I’m not happy with the outcome yet, but with a smaller font size, hopefully such problems won’t occur frequently. So let’s increase the chart’s resolution, meaning all icons and labels get smaller:
That’s starting to look presentable. In the game, the player will be able to zoom in on these charts, so I’m not worried about drawing text at very small sizes.
I’m sure I’ll revisit chart drawing in the future, wherever the gameplay demands it: mountains, trade goods, hazards, names of regions and coastal features, and of course the mysterious X that marks the spot.