No two boxes overlap.

That looks like a non-trivial problem (if I'm understanding it correctly). The folks in math & physics might have some ideas; you could also try other forums such as comp.graphics.algorithms.

As a from-scratch problem, it seems a bin-packing algorithm would be applicable. But it looks like what you want to do is 'relax' the boxes into a non-intersecting state. For certain configurations there may be no single optimal solution, or perhaps even no solution at all. It seems whatever method was applied would have to take these cases into account.

Just from looking at your diagram, it doesn't seem obvious how you'd generalize a progression from the top example to the bottom. If the boxes are added one at a time though, the problem might be more manageable.

You could always hard-code it. By that i mean that you could resize the boxes and put them in columns and rows like the icons on a Windows desktop. That's certainly the fastest way.

Looking into bin-packing would be good too, as suggested. I'm sure it's been done before and there's probably free code to be had as well.

Other than that, the only other thing i could think of would be to add a natural "repulsion" of the boxes. When i was working with the Separation Axis algorithm for my collision detection scheme, i noticed that if a put a bunch of polygons in a "box" area (much like what you are doing) and applied "gravity" plus the normal repulsion provided by the collision detection algorithm, the polygons would strangely align themselves at the bottom of the screen. If i made them spheres (16-sided polygons) i actually ended up with perfect little stacks like oranges at the grocery store, all without interacting with them. It's a sort of "discovered behavior".

That's more work than you are probably willing to put forth, but for kicks you might try something really simple like a "natural repulsion" sort of thing. Have every box make an attempt to move away from the other local boxes and also from the common center of the boxes in general, much like boids in a flocking demo. You may find that they naturally align themselves into your required "relaxed state" and that's good enough. If after X number of iterations trying to get no box to overlap, just call it "good enough" and don't worry about it since it doesn't seem like it would impact the performance of your project.

I don't see what has to be hard about this. If the boxes are all the same size there really isn't much optimization to be done in the solution. Just start at the top left corner (or the corner of your choosing) and place them in a row until there is no more space. Then begin a new row.

Or maybe you want something that is 'prettier'? There may not exist a solution that keeps the boxes near where they started, for all possible arrangement of boxes. What I would do is give each box a nudge of a few pixels away from any other boxes it is touching. Do that until there is no more overlapping, or a max of not-too-many iterations. If you want to have the boxes lined up, first snap the box positions to some grid, say 10 pixels, then do the process, but only moving the boxes in increments of 10 pixels.

Quote:

Original post by wendigo23 I don't see what has to be hard about this. If the boxes are all the same size there really isn't much optimization to be done in the solution. Just start at the top left corner (or the corner of your choosing) and place them in a row until there is no more space. Then begin a new row.

Does your solution match the behavior illustrated in the OP's diagram? :-)

Quote:

Original post by leiavoia You could always hard-code it. By that i mean that you could resize the boxes and put them in columns and rows like the icons on a Windows desktop. That's certainly the fastest way.

What bothers me is that I picture a player standing in a middle of an open field, saying "Hello fellows" and finding that his text doesn't appear precisely above his head.

Quote:

Original post by leiavoia Looking into bin-packing would be good too, as suggested. I'm sure it's been done before and there's probably free code to be had as well.

I don't believe bin-packing is what I'm after; my boxes are all the same size, and my goal is not to 'fit' them, but to attempt to perserve their original location.

Quote:

Original post by leiavoia but for kicks you might try something really simple like a "natural repulsion" sort of thing. Have every box make an attempt to move away from the other local boxes and also from the common center of the boxes in general, much like boids in a flocking demo. You may find that they naturally align themselves into your required "relaxed state" and that's good enough. If after X number of iterations trying to get no box to overlap, just call it "good enough" and don't worry about it since it doesn't seem like it would impact the performance of your project.

I really like this idea. Its simple, elegant, and, as you say, is unlikey to impact performance.