My friend L recently mentioned that he hadn’t seen any blog posts from me. It’s true, I haven’t posted for a while. Earlier this year I had explored signed distance field fonts, in particular using Viktor Chlumský’s multi-channel distance fields[1]. I really enjoyed the many experiments I did, and I learned a lot. I had intended to use it in a real game project but the timing wasn’t right. So I put it away. Then before I got started on a new project, life happened. I had to take a break and attend to other things. I haven’t been blogging because I haven’t had projects to blog about.
Then in July I started thinking about other places I could apply the font code. I thought back to my 2019 blog post about map annotations[2], where I observed that even small amounts of text added to a procedurally generated map could make the map much more interesting. I started dreaming up a new map generator. Broadly, the tasks would be along these four categories:
- Procedurally generate a map that has interesting “point” features including chasms, volcanos, waterfalls, and towns.
- Identify large scale “area” features on a map such as peninsulas, bays, and mountain ranges.
- Generate names for both point and area features, tied into geography, history, cultures, etc.
- Place labels on the map corresponding to these features.
Normally I’d approach this as separate steps, but I wanted to consider the possibility that these steps influence each other. For example what if I identify two adjacent mountain ranges that are each too small for a label? I could modify the map to turn these into one larger mountain range. Maybe I modify a label to match the size of the mountain range, or modify the mountain range to match the length of the label. Maybe I favor east-west oriented geographic features because it’s easier to read the labels for them.
Before I got too far, I wanted to get a sense of what the final maps would look like. Seeing the end result can help me decide if this is going to be inspiring or mundane. For now, I can manually identify features and generate names to get started. I wanted to quickly get something running, the equivalent of rendering a triangle in a 3d world. I used a static map image and then I drew text on top of it using my distance field font renderer from earlier this year:
That’s the “hello world” level for this project. The next step was to try text that I might actually want to render:
I decided yes, this would be a nice summer project.
The next step was to spend a lot of time reading about map labeling. I made notes for myself. I don’t normally share these notes because interpreting them is dependent on what’s in my head, but I’m going to share them here so you can get a sense of the kinds of notes I take while reading:
- https://en.wikipedia.org/wiki/Automatic_label_placement[3] and also a paper evaluating algorithms suggests simulated annealing is best
- for areas[4] - polylabel
- Positioning Names on Maps[5] - paper by Edward Imhof, 1975, paywall
- https://observablehq.com/@veltman/centerline-labeling[6] - @veltman’s page used by Azgaar’s project
- heredragonsabound has many posts on this subject
- mewo2’s post http://mewo2.com/notes/terrain/[7] → code[8]
- city labels are placed on one side of the city icon, with penalties for overlapping with other things
- region labels get a score for each possible location, with overlaps decreasing score, bonus for being over land
- https://heredragonsabound.blogspot.com/2017/04/use-force-layout-luke.html[9] also - on imgur[10]
- scott says mewo2’s tries label positions but doesn’t let them move around; he’s using force layout instead
- simulated annealing part 1[11] and part 2[12]
- uses simulated annealing because force layout got stuck in local minima
- tip: put margins on the left/right of labels so that they don’t merge with an adjacent label
- tip: save intermediate steps because sometimes with simulated annealing the final result is worse
- tip: spend more time moving labels that are currently bad, and not the ones that look good already
- tip: use a spatial hash to speed up the intersection tests
- labeling areas[13] is different than labeling points
- some shapes are much harder to label, but he avoids making those shapes
- labeling coasts part 1[14], part 2,[15]part 3[16], part 4[17], part 5, part 6
- measures the curvature of the coastline to decide what goes there (coast label vs bay)
- labels along a curved path didn’t look good in his experiments, but arcs worked ok
- to make a mysterious area like “The Lost Coast”, eliminate some of the features generated there
- he also has a special “islands at the end of a peninsula” feature he wants to label
- he’s using code to detect existing peninsulas and bays; try the simplest thing, test it a lot, tweak it
- bays can have multi-line labels
- also label “points” as navigation aids
- labeling oceans part 1[18] and part 2[19]
- unlike other area labels, there’s an implied extension of the ocean past the map border
- places candidate circles in water, bonus for touching the map border, might be better if circle goes partly off the map
- labels along an arc
- arc curve should be pointed away from the center of the map
- label text should be upright
- river path labels part 1[20], part 2[21], part 3[22], part 4[23], part 5[24], part 6[25], part 7[26]
- looks for less-curvy location along the river
- smooths out the path using Visvalingam’s Algorithm[27]
- offsets the label from the river
- uses simulated annealing to rule out bad placements
- uses the Greiner-Horman[28] polygon clipping algorithm to detect polygon intersection
- the Martinez-Rueda can handle more cases
- Sutherland-Hodgman[29] is faster but more limited, and he uses it first before Greiner-Horman
- getting the area of the polygon intersection worked better for overlap avoidance than a boolean yes/no intersection
- he plotted number of iterations vs quality of results, and found most of the improvement happens at the beginning
- check the font metrics to make sure you’re getting the bounding box you want
- don’t need to label all rivers; he labels the ones that are “substantially longer” than the river name, and only ones that are straight enough
- Imhof’s paper suggests adding more labels for the same river, above major fork points
- he’s using svg so he can reuse svg’s text along path, zoom for debugging, and other svg features
- using a rectangle approximation to the curved path led to labels not being placed right, so switched to a polygon approximation
- fixing upside down labels was trickier than it seemed at first
- sometimes it’s ok to have labels drawn on top of graphics (forest, mountains), but masking/outlining can help make it stand out
- to make labels look hand-drawn, he offsets/rotates characters occasionally
- island labels part 1[30], part 2[31], part 3[32]
- he generates groups of islands with a separate algorithm, not just single islands as part of noise generation
- draws convex hull around them
- wants a label for the whole group
- had an issue where an island merged into the mainland, so the labels were wrong
- when there are lots of islands, the labels are often too crowded
- mewo2’s post http://mewo2.com/notes/terrain/[7] → code[8]
- https://frozenfractal.com/blog/2024/7/24/around-the-world-18-charting-the-seas/[33]
- instead of force layout or simulated annealing, tries a bunch of possibilities in one pass
I’ll sometimes take parts of my notes and turn them into a proper page, but most of the time I don’t. I use text files instead of bookmark services because I want to be able to group things together in outline form. I hear good things about Obsidian[34] but I use emacs org-mode.
That’s just for step 2 of the four steps I listed. There are also lots of things to learn for step 3 and step 4. After reading all of this, I felt overwhelmed. Scott’s heredragonsabound blog is amazing, and you can see he’s put many years of work into these problems. I wanted a summer project, not a multi-year project. I decided the scope of this project was too large for me with my current skill level. To level up, I should work on smaller projects first.
So I started a one week project to manually place and style labels on maps, focusing on step 4. That was six weeks ago. I’m still working on it. I’ve had many more bugs and unexpected rabbit holes than expected. I’ll blog about them soon!