Download

Is it viable to handle packing of a large number of rectangles with BP?

Hey!
I’ve started to work on a little arpg-but-it’s-turnbased prototype recently to test out what I can achieve with blueprints.
Like most arpg type games, it’s likely that players run into situations with a lot of items on the ground which they want to pre-inspect, to see if it’s even worth picking them up.
So I’ve spent yesterday and today trying to add toggleable item-labels for all ground-items.

While displaying the names is not really a problem, the dynamic layouting of said names turned out to be a lot more difficult than I anticipated.

My current attempt that I am working with is basically a function that fires once when there is no camera movement since it takes too long to calculate while moving.

Right now it works like this:

  1. Iterate through all label-widgets and check if they collide with any other labels.
  2. if collision is detected, store them for later since we know they need to move.
  3. Once all collisions have been detected, I iterate through all labels with collision.
  4. For each colliding label, I start pushing it away from the middle in incremental steps and check if it’s still colliding with something. Which of course is yet another loop we are working with.

Once all that is done. I most of the time get some semi-acceptable result.
Video of that monstrosity in action.

But I feel like there must be a better way to do this.
Right now, I am either not experienced enough with these kind of problems, or I’ve hit a point where relearning c++ would be my best option since I suspect this graph would run a lot faster as script.

(I don’t know how to properly share this in a legible way :slight_smile: )

So my question here is basically just.
Should I do more reading into some obscure real time rectangle packing papers or did I make something in BP that I should probably have rather done with c++.

Or did I approach this in a fundamentally wrong way. I’m very much a beginner when it comes to UE/gamedev. I’m normally more on the web-dev side of things, our rectangles don’t move that much :slight_smile:

EDIT: After some more research I found out that I am dealing with a problem that is literally called “Automatic-Label-Placement”. This is definitely an algorithm issue not a BP issue.
I’ve yet to stumble across a paper or something that discusses speed / implementations in games but I think it got me on the right track to figure out a more efficient way to do it. :+1:

EDIT2: I found a way to make it work. I posted my solution below.

I might be totally missing the point here, but… Are you just trying to do an inspection system?

There are a lot of vids on youtube about this, also the free horror engine does this kind of thing pretty well:

If you want a world location widget to appear over the item, this only needs to written once as a BP type, and then all your items in the game will be descendents of this BP.

Not quite unfortunately. I got the inspection system down already luckily :slight_smile:

I’m trying to build something like this where the player can show all names of the items on the ground.

(example)

As long as there are not too many items on the ground, I can get away with just putting the labels at the item’s world location.
At a certain point / at certain angles though, that stops being viable since labels bunch up and create messy clusters of un-readable widget piles.

The issue is arranging the labels if they are overlapping another label. (Like the screenshot from Path of Exile I posted above.)

Looks like a nightmare system to me :wink:

You can probably do something with translucency sort priority.

Or maybe measure the distance between the camera on the object and only display if they are near?

Oh yeah totally. Thanks for the idea. But limiting the number of displayed labels is going to be my last resort :slight_smile:

But of course that would totally work. At this point I’m trying to push for the classic “Text-All-Over-The-Screen” feel most arpgs have when it comes to loot. Who knew a so seemingly simple feature could be such a headache :stuck_out_tongue:

Well, what they’ve apparently done in your picture is two things

  1. The labels are in screen space, but over the item they concern

  2. The size of the labels in dependent on the number of labelled objects on the screen

Yes and no. It’s a bit hard to see I know because there is so much going on as well as there are some special cases missing on that image.

Here is a better example:

Labels try to be over the item they concern (1)
If there are items that are too close together, labels start moving to not overlap one another. (2)
This seems to work even with differently sized labels (3)

Of course my end result does not be this one to one.
I’m just wondering if trying to create a system like this with Blueprints is something worth pursuing :slight_smile:

I’ll try playing around with approaching the generation of the layout in a different way. Maybe generating it while adding the labels to the container and making sure they already lay themselves out correctly during generation might give me some improvements. Maybe I can get rid of a couple of loops that iterate through 40+ objects. That would help I guess ^^

Yes, can’t be much help I’m afraid. I can tell you it’s definitely possible with blueprints ( and efficiently ).

No worries! Thanks for helping me explain the issue better though.
I’ll keep working on it and see where the flow-(graphs) take me :stuck_out_tongue:

1 Like

Alright. I’ve figured out a solution that will work for me for now.

Now it looks like this

What I am doing now is the following:

  1. Iterate through all labels
  2. For each label, check if it’s colliding with another label.
  3. If not, move on to the next one. If yes, push the label either up or down depending on it’s position.
  4. If it still is colliding with something, I don’t keep pushing the label I just pushed but repeat step 3 for the label that is colliding with the label we just pushed.
  5. Now that we kept stacking labels in either y or -y we at some point run out of labels to push. So we return to step one. If we pushed labels around somewhere in step 1-4, we restart from step 1 and keep doing this until nothing collides.

This has some pros and cons I noticed
Pros:

  • Large, dense clusters of labels stack in a neat column, especially if labels are in the same position.
  • Any item that is not in those large clusters and gets added later inserts itself into the column at the closest possible position to the item’s world position on screen.
  • Works with labels of different dimensions.
  • Reasonably fast as long as the density and quantity of items on screen is low.

Cons:

  • Layout changes drastically every time the function runs with different camera angles.
  • Not cripplingly slow but still pretty slow with a lot of items since it’s gotta run through a lot of stuff.
  • Since we only move up and down, we get a lot of free space where labels could get packed into.
  • Stacks can go off-screen.

I could probably add distribution in the x-axis as well pretty easily by changing the push-vector depending on the position of the item but I think for now I’ll avoid anything that bring performance down even more.

There also probably is some way to set it up so it does not need to recheck everything after something has moved or a way to reduce the number of loops needed but I’ve reached my motivation and brain capacity on this one for now.

Maybe once I actually need to fix that I’ll go back and have a better look at it ^^

If anybody is interested, here is the widget-component. Just needs some children it can arrange.
WIDGET_Label_Container.uasset (372.2 KB)