# Algorithm for spreading labels in a visually appealing and intuitive way

## Short version

Is there a design pattern for distributing vehicle labels in a non-overlapping fashion, placing them as close as possible to the vehicle they refer to? If not, is any of the method I suggest viable? How would you implement this yourself?

## Extended version

In the game I'm writing I have a bird-eye vision of my airborne vehicles. I also have next to each of the vehicles a small label with key-data about the vehicle. This is an actual screenshot:

Now, since the vehicles could be flying at different altitudes, their icons could overlap. However I would like to never have their labels overlapping (or a label from vehicle 'A' overlap the icon of vehicle 'B').

Currently, I can detect collisions between sprites and I simply push away the offending label in a direction opposite to the otherwise-overlapped sprite. This works in most situations, but when the airspace get crowded, the label can get pushed very far away from its vehicle, even if there was an alternate "smarter" alternative. For example I get:

  B - label
A -----------label
C - label


where it would be better (= label closer to the vehicle) to get:

          B - label
label - A
C - label


EDIT: It also has to be considered that beside the overlapping vehicles case, there might be other configurations in which vehicles'labels could overlap (the ASCII-art examples show for example three very close vehicles in which the label of A would overlap the icon of B and C).

I have two ideas on how to improve the present situation, but before spending time implementing them, I thought to turn to the community for advice (after all it seems like a "common enough problem" that a design pattern for it could exist).

For what it's worth, here's the two ideas I was thinking to:

Slot-isation of label space

In this scenario I would divide all the screen into "slots" for the labels. Then, each vehicle would always have its label placed in the closest empty one (empty = no other sprites at that location.

Spiralling search

From the location of the vehicle on the screen, I would try to place the label at increasing angles and then at increasing radiuses, until a non-overlapping location is found. Something down the line of:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...

• How many planes might be overlapping at one time? Jul 31 '11 at 15:14
• @wangburger - Never thought this would be relevant (would be interested to know more about your line of thought), but the answer is: it depends from the player's game strategy. Technically the world could have 24 vehicles overlapping, but a realistic figure in most game condition is 3-4.
– mac
Jul 31 '11 at 15:21
• Isn't it more confusing to have moving labels relative to the plane than overlapping but static ones for a reasonable amount of time? Jul 31 '11 at 22:12
• You might be interested in en.wikipedia.org/wiki/… - this is not a simple problem to solve. Don't expect to find a perfect solution. Aug 1 '11 at 4:11
• GraphViz is a suite of tools for laying out graphs in visually pleasing way, with a tendency to avoid overlaps in labels. While it may not be usable directly, you might be able to glean some information from their documentation or source code on what kind of algorithms they use to layout their graphs. They seem to have both energy-based models and spring-based models, for example. Aug 1 '11 at 7:49

Essentially this issue is similar to a collision avoidance problem. Yes, the planes can fly at different altitudes, but their labels are all at the same "altitude".

There are algorithms like Unaligned Collision Avoidance, that would be a step in the right direction for you. Of course for your situation, the labels are "tethered" to their planes, so they have a limited range of movement.

If you look at Flocking Behavior, you want to implement the first "rule" of flocking: short range repulsion. However, instead of "steering" in the direction that is away from the nearest neighbors, you'll use the "away" vector as the placement location for your label.

For example:

The large black circle represents your area of influence, the green circle represents the valid placements for the label, the center green dot is the plane your currently considering, small green dot is the point on the circle chosen for label placement.

Now the black dots could represent either other labels, or other planes. I'm not sure which one would work best, you may get better avoidance if they were other labels, but I'm not sure. Obviously the "force" arrows are the direction vectors between your current plane and the "objects of influence". Finally, the box is the label.

So using your example above, I think this would produce something like:

            - label
/
B
label - A
C
\
- label


Using this method there are some situations you'll have to make special cases for, like three planes vertically aligned:

          - label       label -
|                   |
B                   B
label - A                   A - label
C                   C
|                   |
- label       label -


All three labels could flip flop from right to left, depending on how your have your label corners defined. Basically, you'll just have to watch out for the angles around the circle where your labels can switch which corner they're drawn from: 0, 90, 180, 270.

I think in the end, this would look kind of neat, watching the labels avoid each other. If it gets too distracting, perhaps you can round to the nearest 10 degrees for less frequent movement.

Sorry for the weird details, most of this stuff I thought about when I was making a radial menu for my game, but I think in this "dynamic" form it would work pretty well.

• Actually my example didn't even take into account planes that are directly on top of each other, as in their x and z coordinates match exactly (but if you're using floats this likely won't happen). The examples I gave are of planes near each other. Additionally, you could, as I said, think of the black dots in the above image as other labels.
– House
Jul 31 '11 at 17:15
• Oh, it appears you removed your comment?
– House
Jul 31 '11 at 17:22
• What I meant with my previous [poorly formulated and thus now removed] comment, was that you could have a scenario in which a label is "trapped/surrounded" by other non-moveable (i.e. vehicles) sprites. In this case the label should perhaps "jump" outside the enclosing circle, but it's not exactly clear to me how this should happen. BTW: I originally though that the green dot of your picture were several aeroplanes stacked one on top of the other, but after your comment I realised I was wrong... sorry!).
– mac
Jul 31 '11 at 17:30
• Ah, I see. So you'd treat the black dots as both planes AND labels then. If the position found by the first iteration isn't good, double the radius and check again. Or you already have a vector that points away from the majority of the crowd, you could follow that out until you find somewhere that works. However I think the first method would have better results.
– House
Jul 31 '11 at 17:36

After some thought, I finally decided to implement the spiralling search method I briefly described in the original question.

The rationale is that the Byte56's method needs special treatment for certain conditions, while the spiralling search doesn't, and it codes in a really compact way. Also, the spriralling search emphasise finding the closer spot to the vehicle to place the label, which IMO is the main factor in making the map readable.

However please continue to upvote his answer, as it's not only useful, it's also very well written!

Here's a screenshot of the result achieved with the spiralling code:

And here's the code which - although not self-contained - it gives an idea on how simple is the implementation:

def place_tags(self):
for tag in self.tags:
start_angle = tag.angle
while not tag.place() or is_colliding(tag):  #See note n.1
tag.angle = (tag.angle + angle_step) % 360
if tag.angle == start_angle:
tag.connector.update()                       #See note n.2


Note 1 - tag.place() returns True if the tag is entirely on the visible area of the screen/radar. So that line reads like "keep on looping if the tag is outside the radar or it overlaps something else..."

Note 2 - tag.connector.update is the method that draw the line connecting the aeroplane icon to the label/tag with the text information.

• Well done, that's very compact indeed. Thanks for the praise. Also thanks for posting about what you ended up doing, that's always useful for people searching for answers later. From the screenshot it looks like it's working very well! Make sure to accept your answer, as it's what you ended up going with.
– House
Aug 3 '11 at 0:21
• @Byte56 - Thanks for the "retro-praise" ;) I am waiting for selecting the answer as accepted because I still would like to code your solution too and compare the result. For one, I suspect that your solution could result in longer but also faster code to execute. Also, I would like to see how the two compares in very crammed airspaces... so there is still a chance I could release the code with your algorithm. Watch this space! ;)
– mac
Aug 3 '11 at 14:56
• @Byte56 - I had a go at implementing your algorithm. It worked fine and fast in low densities, but as soon as the space got crammed, I had problems in finding a straightforward implementation that would manage specific situations in which a label should "jump" a block of other labels or got trapped by non-moveable (i.e. plane icon) sprites. I'm marking this answer as selected then, but again: thanks a lot for the time and contribution! :)
– mac
Aug 12 '11 at 20:31