Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

How To Prevent Multiple Rects From Overlapping

Discussion in 'Scripting' started by John-B, Feb 18, 2020.

  1. John-B

    John-B

    Joined:
    Nov 14, 2009
    Posts:
    1,259
    I have UI text labels that identify various objects in the 3D scene. The labels follow the objects around (translating world to canvas coordinates), appearing just below the objects (in screen space). The problem is when two or more objects are close together, their ID labels overlap.

    Detecting the overlap is not a problem, adjusting the positions of the labels so no one overlaps another is giving me trouble. I use a nested loop to compare each label rect with every other. With just two labels, it works. When there's overlap, each is moved in opposite directions relative to the smallest overlap. For example, if the two label rects overlap by 10 vertically and 100 horizontally, one is moved up by 5 and one down by 5. Each is moved just enough so they no longer overlap.

    But with 3 or more labels, it no longer works. Which makes sense, since labels moved early in the loop don't get checked again after later labels are moved. I'm not sure how to fix it. I'm not sure if moving each one the minimum distance is the problem, or it's the nested loop making each comparison only once. Any suggestions?
     
  2. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    The obvious extension to your current algorithm would be to repeat the entire process until things stop changing. But this could get very expensive in some cases, and I'm not sure if it's even guaranteed to terminate at all. Still, you could try it, and it might be good enough for your case. (Make sure to include a maximum number of iterations as a safety.)


    You might find things work better if you put your objects in some priority order and never move a higher-priority object for the sake of a lower-priority one. So it looks something like:
    • Item 0 is highest-priority, so it goes exactly where it wants to go and doesn't move for anything
    • Item 1 moves until it doesn't overlap with item 0
    • Item 2 moves until it doesn't overlap with items 0 or 1
    • Item 3 moves until it doesn't overlap with items 0, 1, or 2
    • etc.
    This way, once you "finish" with a given item, it gets locked in and never has to move again. This avoids ever needing to start the entire process over from scratch.

    However, it's still possible when you move item 3 out of the way of item 2 that you'll move it back into conflict with item 0 or item 1. So for each item, you need to either repeatedly check against all higher-priority items until things stop changing OR work out an algorithm that finds a single location that avoids conflicts with all other items "simultaneously".

    This alternative also has the downside that you are more likely to get caught in an infinite loop. Suppose that item 2 is trying to fit between items 0 and 1, but there isn't enough space between them. In your original algorithm where you move both items in a conflict, items 0 and 1 get pushed farther apart, and if you repeat the whole algorithm enough times they'll eventually get far enough apart that item 2 can fit between them. But if items 0 and 1 are locked in place (since they're higher-priority), item 2 could potentially bounce back and forth endlessly and never find a space. You'd need to either give up after a while (probably resulting in item 2 being hidden and not showing up at all) or figure out some algorithm that takes a "god's-eye view" and considers all restrictions at once.


    An example of such a "god's-eye" approach would be to make a "stencil" of the screen where you block off all the space that is already occupied by higher-priority items, and then the current item needs to pick a space that is big enough without going into any of the blocked-off regions. But finding the "best" available space might be expensive. You could do something dumb like "pick a direction and move in that direction until there's enough space" but it could be that you happen to pick a direction that forces you off the edge of the screen when there was plenty of space in another direction. You could try moving in an outward spiral until you find space but there are quantization issues that create a speed/fidelity trade-off.
     
  3. unit_dev123

    unit_dev123

    Joined:
    Feb 10, 2020
    Posts:
    989
    i recommend not using ui in 3d space
     
  4. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    This doesn't sound like it really has anything in particular to do with 3D space. If you're trying to dynamically add labels to a collection of moving objects, you can get the same problem in 2D.

    I'm also not sure why you would recommend against using UI in 3d, or what you'd suggest people do instead.
     
    Menion-Leah likes this.
  5. unit_dev123

    unit_dev123

    Joined:
    Feb 10, 2020
    Posts:
    989
    not use ui in 3d it's horrible in my opinon. but i understand the issue still arise - just in 2d space.

    not easy problem to resolve, seems like the standard bird flocking algorithm in someway. where every bird / boid moves distance from other to accommodate space that way neither intersect or cross path
     
    Last edited: Feb 18, 2020
  6. StarManta

    StarManta

    Joined:
    Oct 23, 2006
    Posts:
    8,773
    Hey @unit_dev123, the comment before yours was detailed, specific to the question, and useful. Yours is none of those things and contributed nothing valuable to this thread.

    I don't mean to hijack @John-B's help thread with something offtopic so if this turns into a whole conversation we should take this into PM's, but: I've seen you popping up a LOT around the forums the last few days. Usually answering questions, and usually not very well. I glanced at your post history and you started learning Unity development 8 days ago, and the quality of the advice you've given since then is exactly what you'd expect from a user who's been using a professional tool for a week. (I've found exactly one thread where your reply was useful to the person asking the question, and even that was just linking to a Youtube video that held the actual answer.)

    Your advice is not just inexperienced, but when it's not useful, it's distracting and actively makes the forum less useful for people seeking advice. When I mean is this: When a lot of experienced people with useful advice to give browse the forums, we are instantly drawn to posts with zero replies, because it means the person still needs help. When you leave a reply that's not useful, that will actively prevent the person you've replied to from getting useful advice, because the people that could actually help may skim right past it. And that's just where the advice is not useful - if the advice you're giving is so wrong as to become confusing, it's worse. The way you've been replying, your presence is not making the forums better.

    I would advise you to take a few steps back in terms of answering posts.
    Avoid posting general opinions about the usefulness of various aspects of the engine, as you've done here - a week is simply not enough time to develop opinions like this. (If you phrase this sort of thing as a question instead - "Is it a good idea to use UI in 3D space?" for this one, for example - that will get your point across while making it clear to the asker that this isn't something to be taken as gospel, while also inviting others to help you learn Unity better.)
    Read all the replies and see if the question you're answering already has an answer that is more useful than yours is.
    Take a look at the stats of the people around you. Notice that the vast majority of people giving advice on Unity have been using it for years. Unity is a big, complex tool that takes months to learn and years to master, and you're on Day Eight.
     
  7. unit_dev123

    unit_dev123

    Joined:
    Feb 10, 2020
    Posts:
    989
    thank u for advice starmanta, i just trying to help.
     
  8. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    Hey unit_dev123! Please post something that will convince me that you are not a chat bot. What are you trying to make in Unity?
     
  9. unit_dev123

    unit_dev123

    Joined:
    Feb 10, 2020
    Posts:
    989
  10. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    Thanks.
     
  11. John-B

    John-B

    Joined:
    Nov 14, 2009
    Posts:
    1,259
    Thanks for your thoughtful answer.

    I tried doing this in a while loop, repeating the overlap checks until nothing overlaps. After having to restart Unity a few times, I realized what you described is what happens — the loop never terminates. The labels just keep moving back and forth. I tried moving each more than the minimum amount, same result.

    I've also tried moving just one label when there's overlap (instead of moving each in opposite directions), but again, same result. Also, some labels end up far away from their objects, while others are right on.

    I've thought about locking each label's position once it's moved, as you suggested, but haven't been able to get that to work. I don't know how to make a "stencil" of the screen (a mask?), and checking for overlap is cumbersome. Just getting a UI Text object's global rect coordinates requires multiple steps.

    I've also thought about putting the labels in 3D space, but the problem is still the same. And that would require adjusting the label size as the objects moved closer and further from the camera.
     
    Last edited: Feb 19, 2020
  12. Antistone

    Antistone

    Joined:
    Feb 22, 2014
    Posts:
    2,836
    That's why I suggested that you set a maximum number of iterations, so that it is guaranteed to stop even if it doesn't succeed.

    Conceptually, you divide the screen into a grid, and then have a bool for each gridspace saying whether it's open or blocked. (At the extreme end, you can make each gridspace the size of 1 pixel, but you might want to go bigger than that for efficiency.) Note that if you choose a grid that is smaller than your labels, then each label will take up multiple grid spaces, so you'll need to account for that both when marking which spaces are blocked and when checking if there's enough space for a new label.
     
  13. orionsyndrome

    orionsyndrome

    Joined:
    May 4, 2014
    Posts:
    3,070
    That problem, of dynamically partitioning space, is, as far as I know, one of the infamous NP problems. It's basically non-computable with a deterministic algorithm. The only other possibility is to iteratively approximate the solution, like Antistone suggested.

    All good advice by him, I'd have nothing else to add really. Maybe that having a dynamic grid system (or quadtree) might help you tremendously, when you're trying to find a vacant spot quickly, but quadtree may also help you determine overlaps in optimal time.

    Coincidentally, this was my first "professional" programming task. Little did I know... Well, that was 30 years ago, and I ended up making an editor that lets you manually partition the 2D space / collage the boxes. I still got paid for the effort, but I was really cheap, you don't expect much from a kid anyway.

    [edit]
    Oh this is btw an example of a chaotic system. Even the slightest changes in the initial setup can yield vastly different results. So if that's already the case, you can also probe the problem space stochastically -- meaning you get to use RNG ;)

    Anyhow, try looking for a bounds quadtree. Bounds in Unity is a struct that stores the confined 2D area, so called axis-aligned bounding box (or AABB in short). So you basically need an AABB Quad Tree (as opposed to one working with point data).

    [edit2]
    Or, sorry, AABB in 2D is also known as Rect.
     
    Last edited: Feb 20, 2020
    Braza likes this.
  14. John-B

    John-B

    Joined:
    Nov 14, 2009
    Posts:
    1,259
    I just tried repeating until there are no more overlaps or a maximum of 5 iterations, and that results in a lot of flickering. When the labels start to overlap, they start jumping around, back and forth. And the result is still overlapping labels when there are more than 2. Not a good solution.
     
  15. ben-rasooli

    ben-rasooli

    Joined:
    May 1, 2014
    Posts:
    40
    Why not using the Rigidbody-2D and Collider-2D and letting the 2D Physics Engine do the rest. As far as I know, rigidbodies won't overlap. Of course, you still need to write some code to make it work for your situation, but a big chunk of the work is now done by the physics engine.
     
    Braza likes this.
  16. irshadgirachirshu

    irshadgirachirshu

    Joined:
    Sep 14, 2020
    Posts:
    7
    You can use a grid system that has certain limit of label boxes you can store at a time, say 100. You can snap the labels to the grid position and this will save you alot of computation and effort. Just an idea, may or may not work
     
  17. Braza

    Braza

    Joined:
    Oct 11, 2013
    Posts:
    136
    That's what I did in my project but we need to have timeScale=0 for planning phase, that halts physics and making this solution useless.