How can I position a large amount of boxes to prevent overlap efficiently

Question

I've been working on an asset to position labels like they do in Diablo or Path of Exile, but I'm having trouble finding an algorithm to position the labels efficiently.

Currently I just boxcast in each of the 4 directions until there is no overlap, compare their distances, and take the smallest value to place it, but this just seems too much hassle and too slow with a large number of labels.

Especially when you look at this video clip from Path of Exile without loot filter. There's no way they can iterate over that many labels and place them instantly.

I think they keep some kind of array that says "there are X open spots for this label group currently, select the nearest one or any", and update it when a label gets placed.

I know this question has been asked and I know about automatic label placement etc. but I don't think it really applies in this case. At a certain point it doesn't really matter where the labels get positioned, they just need to be positioned around another label as fast as possible without overlap.

Basically, I'm looking for a way to save occupied/unoccupied space around a label and retrieve that value somehow.

Answer 1

Here's a sketch of one solution:

Divide your placement domain into rows, each row the height of a label. (If you have boxes of different vertical sizes this becomes more complicated, but it looks like the majority of items in Pillars of Eternity have very similar heights)

For each row, store a list of labels in that row. Each label knows its center, width, and the target point it's trying to align to.

This lets us greatly simplify the problem into finding a placement in a line, without hitting the full \$n^2\$ complexity of checking against every other label on screen.

When you add a new label, round its target point's vertical position divided by the row height to find which row it "wants" to be in.

Try first to place the label in this row.

With a linear or binary search, you can find the first label in the row that belongs to the right of this one / the last label that belongs to the left (based on their respective target positions). If there's no label that belongs to the left or right, you can treat those constraints as infinite.

Check if there's room to place the label between these limits - shifted to bring you as close as you can to your target position. If so, place the label, and you're done.

If not, compute the minimum penetration depth - how much would the other labels need to slide apart to make room? Hang onto that as a score for the disruptiveness of the placement.

Then check the row above/below in the same way, factoring in the vertical shift from where your label "wants" to be as part of their disruptiveness score. You can repeat this out to a controllable maximum vertical displacement. If you find a placement opportunity below a target disruptiveness score, place it. Otherwise, just pick the lowest score you found out of the rows you checked.

If your chosen placement requires sliding, you iterate over the other labels in the row to the left or right of your newly-placed label, shifting them over by the remaining overlap, until no overlap remains.

This approach is \$O(r \cdot k)\$ per insertion (or \$O(r \cdot \log k + k)\$ if you use binary search), where \$k\$ is the number of items in a single row (so, likely in the range of \$k \approx \sqrt n\$ where \$n\$ is the total number of labels on screen), and \$r\$ is the number of rows you check, which gives you a controllable trade-off between placement quality and search complexity. All the steps can be done with simple interval arithmetic, so you don't need to do any boxcasting along the way.