Use the Force (Layout) Luke!

I was a little surprised to look at the blog and see that I seemingly haven't written about how Dragons Abound places labels on the map.  I was pretty sure I had.  Turns out I was remembering a Reddit post from before I started this blog.  That's pretty skimpy, so let me go into a little more detail.

Placing labels is a significant topic in cartography.  The seminal paper is by Eduard Imhof from 1975, Positioning Names on Maps.  It's a pretty interesting read, even if you're not into maps.  With the advent of modern computers and cartography software, there's been a fair amount of effort put into figuring out decent methods of automatic label placement.

Martin O'Leary's original map generator used an ad-hoc approach to placing labels, and it worked okay but it was a bit of a kludge.  As Dragons Abound started adding more features and getting more complex, this just wasn't working very well.  So I switched over to using an algorithm known as "force layout".  Dragons Abound uses d3js for some of its graphics, and d3js has a built-in force layout function, so that seemed like an easy choice (although that didn't turn out to be entirely true!).

The basic idea of force layout is that you treat the labels and other map elements as objects with forces acting on them, and let them move around until they find a "comfortable" spot. For example, if you don't want labels to overlap, you use a force that pushes labels apart when they do overlap.  Depending upon how you want to lay out your labels, you can combine different forces to achieve different effects.  Then the force layout engine runs a little simulation, and at every step of the simulation the force push the labels around.  At some point they hopefully all get to "comfortable" positions where there are no forces acting upon them (or a bunch of balancing forces), and that should be a "good" layout.  Let me walk through how that works in Dragons Abound.

This image shows a map with cities, city names, and region names (e.g., "Maualaus" is a region name).  The purple boxes show the size of the labels and the green boxes show the size of the city symbols.  The labels start on top of the cities and consequently hard to read. Initially, there are two forces in Dragons Abound.  The first causes elements that are colliding (on top of each other) to push off against the collision. The second is an attractive force that pulls labels towards their anchors, e.g., that tries to keep the city labels near the city symbols.

(As it turned out, although d3js has a force layout component, the forces it implements were not very suitable for this problem, so I had to code up a couple of new force implementations.)

Let's run the simulation with those two forces.

In this image, red shows the original placement of the label, and purple the current placement. Note how "Kusun" (for example) has moved downwards until it is no longer overlapping the city symbol. This is better, but if you look on the top half of the map you'll see "Aukusun" and "Auuk Kienu" are on top of the coastlines.  That's not ideal.  I already have a force that pushes away two colliding objects, so I can use that to push things off the coastlines by making each little segment of the coastline an object to avoid (a green box).

In this image, the green boxes identify all the segments of the coastline.  Labels that overlap these boxes get a force pushing them away.  You can see that "Aukusun" has moved downwards and "Auuk Kienu" to the right to avoid the coastlines. Also notice how "Auuk Kienu" was stopped by running into the opposing coastline.

Another problem in this map is that some of the labels are overlapping rivers (e.g., "Maualaus").  So the next step is to add the rivers as features to avoid.

Each segment of the river has been made an object to avoid, and the labels have now moved off the rivers. Note that "Isaulni Muun" moved quite a distance but is still visually pretty close to it's symbol -- the attractive force is keeping it nearby.  Unfortunately, "Isaulni Muun" is overlapping a border, so I need to do the same thing to force labels away from borders.

Now "Isaulni Muun" has moved downward to minimize its overlap with the border while still staying fairly close to its city symbol.  On the other hand, "Lausunpam" has hardly moved at all.  It is caught between a river and a border.  The opposing forces cancel out and the label doesn't go anywhere (or ping pongs slow back and forth).  The situation is even worse for "Auuk Kienu" near the top of the map -- being pushed away from the border has caused it to go from overlapping just the border to overlapping both the border and the coast!

Here's an animation that shows the steps:

Unfortunately, the kind of problems that show up in the last step are typical for force layout.  It's pretty easy for labels to get "trapped" in a poor location with forces pressing in from all sides, when there's a much better location just on the other side of one of the forces.  In computing terms, this is known as getting stuck in a local minima.  A better labeling algorithm would have a way to escape these local minima.  I'll talk about one next time.