overlaping rectangles issue
jice
I've been fighting with an issue on the Chronicles of Doryen and I
wonder if someone here has a solution.
I have a bunch of small rectangles positioned randomly on a much
bigger rectangle. I'm trying to find how to move the small rectangles
so that :
- they stay inside the bigger one
- they do not overlap
in a way that minimize the movement of each small rectangle.
I'm currently using a cheesy macgyverly solution, but there is
probably an algorithm to do this in a smarter way...
Thanks in advance for your help...
--
jice
Krice
> - they stay inside the bigger one
> - they do not overlap
> in a way that minimize the movement of each small rectangle.
What do you mean about "movement"? Does the rectangles move
somewhere during the gameplay?
Anyway.. it shouldn't be too hard to check if they are
outside the bigger one or overlapping other rectangles.
You can minimize the misses by listing only free locations
and re-scanning them after one rectangle is created.
ps. Could also help if you tell what you actually
try to do with those rectangles.
jice
by minimizing the movement, I mean that each small rectangle must be
as closer as possible from its initial position.
Checking that the rectangle are outside the big one or overlapping is
easy, but if you simply move one rectangle because it's overlapping
another one without taking into account every rectangles, you may end
with a new overlapping zone.
In fact, this is a very simple 2D rigid body collision problem with
axis-aligned boxes. But writing a constraint solver for this is a bit
scary. There is probably a simpler, more pragmatic solution.
Concerning it's use, it's only to print text on screen (like
characters names or shops names) so that the texts do not overlap,
each text stays as close as possible to it's attached object.
--
jice
Kenneth 'Bessarion' Boyd
> Hi all,
>
> I've been fighting with an issue on the Chronicles of Doryen and I
> wonder if someone here has a solution.
>
> I have a bunch of small rectangles positioned randomly on a much
> bigger rectangle. I'm trying to find how to move the small rectangles
> so that :
> - they stay inside the bigger one
> - they do not overlap
> in a way that minimize the movement of each small rectangle.
Instance of the packing problem; NP-complete in the number of small rectangles.
> I'm currently using a cheesy macgyverly solution, but there is
> probably an algorithm to do this in a smarter way...
I think you want better-applied cheese :)
As I'm too lazy to actually read the libcod source to see if this algorithm is
already there, just some general questions:
* Is the current algorithm "fast enough" in the common use case?
* how much auxilliary data are you using (there are at least two vector data
items I'd be tracking as functions of two rectangles; I'd also be precalculating
legal position ranges for the rectangles)
* As the problem is already intrinsically slow, I'd prefer arrays/std::vector's
properly sized at the beginning the algorithm, to control memory manager issues.
jice
wrote:
> On 2008-02-28 20:39:26, jice <jice.nos...@gmail.com> wrote:
>
> > Hi all,
>
> > I've been fighting with an issue on the Chronicles of Doryen and I
> > wonder if someone here has a solution.
>
> > I have a bunch of small rectangles positioned randomly on a much
> > bigger rectangle. I'm trying to find how to move the small rectangles
> > so that :
> > - they stay inside the bigger one
> > - they do not overlap
> > in a way that minimize the movement of each small rectangle.
>
> Instance of the packing problem; NP-complete in the number of small rectangles.
Ok, I didn't know the packing problem. Checking literature on it...
>
> > I'm currently using a cheesy macgyverly solution, but there is
> > probably an algorithm to do this in a smarter way...
>
> I think you want better-applied cheese :)
>
> As I'm too lazy to actually read the libcod source to see if this algorithm is
> already there, just some general questions:
No, it's not yet in the library. I try not to put cheesy things in
it :)
> * Is the current algorithm "fast enough" in the common use case?
Yes, the speed is not the issue. There are generally no more than 10
rectangles on the screen at the same time. But the current algorithm
only solve easy cases. I still get overlapping rectangles in most
cases.
> * how much auxilliary data are you using (there are at least two vector data
> items I'd be tracking as functions of two rectangles; I'd also be precalculating
> legal position ranges for the rectangles)
The only data I'm currently using is the big rectangle position/size
and a list of small rectangles position/size. The big rectangle
represent the part of the console where the main game view is.
Concerning precalculation, the problem is that some rectangles may
move at any moment. For example, there is one rectangle around the
player position so that he can't be hidden by texts. Thus, when the
player moves, the texts (the rectangles) move around him.
--
jice
Simon Richard Clarkstone
> On 28 fév, 23:06, Kenneth 'Bessarion' Boyd <zaim...@zaimoni.com>
> wrote:
>> On 2008-02-28 20:39:26, jice <jice.nos...@gmail.com> wrote:
>>
>>> Hi all,
>>> I've been fighting with an issue on the Chronicles of Doryen and I
>>> wonder if someone here has a solution.
>>> I have a bunch of small rectangles positioned randomly on a much
>>> bigger rectangle. I'm trying to find how to move the small rectangles
>>> so that :
>>> - they stay inside the bigger one
>>> - they do not overlap
>>> in a way that minimize the movement of each small rectangle.
>> Instance of the packing problem; NP-complete in the number of small rectangles.
>
> Ok, I didn't know the packing problem. Checking literature on it...
>
>> items I'd be tracking as functions of two rectangles; I'd also be precalculating
>> legal position ranges for the rectangles)
>
> The only data I'm currently using is the big rectangle position/size
> and a list of small rectangles position/size. The big rectangle
> represent the part of the console where the main game view is.
> Concerning precalculation, the problem is that some rectangles may
> move at any moment. For example, there is one rectangle around the
> player position so that he can't be hidden by texts. Thus, when the
> player moves, the texts (the rectangles) move around him.
I see two possible algorithms.
The first is to work outwards from the player, putting each box in turn
as close as you can to where it is supposed to be. This is fast.
The second is to quantize the positions of the boxes a bit more, then
keep shuffling the boxes about one unit at a time until they don't
overlap. It is best to start with the outer ones, and if a box is
pushed up against another, it can push it along, and that can push more
boxes along, and so on. This might produce better results, but will
likely be slower.
These algorithms could be used for map generation too.
--
Simon Richard Clarkstone:
s?m?n_cl?rkst?n?@yahoo.co.uk/s?m?n.cl?rkst?n?@hotmail.com
"August 9 - I just made my signature file. Its only 6 pages long.
I will have to work on it some more." -- _Diary of an AOL User_
jice
<s.r.clarkst...@dunelm.org.uk> wrote:
> >> On 2008-02-28 20:39:26, jice <jice.nos...@gmail.com> wrote:
>
> >>> I have a bunch of small rectangles positioned randomly on a much
> >>> bigger rectangle. I'm trying to find how to move the small rectangles
> >>> so that :
> >>> - they stay inside the bigger one
> >>> - they do not overlap
> >>> in a way that minimize the movement of each small rectangle.
>
>
> The first is to work outwards from the player, putting each box in turn
> as close as you can to where it is supposed to be. This is fast.
>
> The second is to quantize the positions of the boxes a bit more, then
> keep shuffling the boxes about one unit at a time until they don't
> overlap. It is best to start with the outer ones, and if a box is
> pushed up against another, it can push it along, and that can push more
> boxes along, and so on. This might produce better results, but will
> likely be slower.
>
I'm currently using something like the second algorithm. The first may
be better. I'll give it a try. Thanks for the suggestion.
--
jice
Kenneth 'Bessarion' Boyd
> On 28 f=E9v, 23:06, Kenneth 'Bessarion' Boyd
> wrote:
> > On 2008-02-28 20:39:26, jice wrote:
> > * how much auxilliary data are you using (there are at least two vector da=
> ta
> > items I'd be tracking as functions of two rectangles; I'd also be precalcu=
> lating
> > legal position ranges for the rectangles)
>
> The only data I'm currently using is the big rectangle position/size
> and a list of small rectangles position/size. The big rectangle
> represent the part of the console where the main game view is.
That is, no auxillary data at all.
I like Simon's suggestion (surely the PC's rectangle is non-negotiable). That
simplifies things a little bit because you have a clear starting point.
> Concerning precalculation, the problem is that some rectangles may
> move at any moment. For example, there is one rectangle around the
> player position so that he can't be hidden by texts. Thus, when the
> player moves, the texts (the rectangles) move around him.
I don't see that as much of a problem. (I'm visualizing a while loop whose
continue condition is "some rectangles are overlapping preventably".) Say we
have a count of how many active overlaps there are.
So if the loop actually iterates:
* shove rectangles off of the @, if any
* find "outermost rectangles with nothing between them and the edges" other than
@ in overlap, and shove them closer to the edges. Rectangles on edges are
considered "pinned" in that direction.
* Apply further MacGyver layers of special cases until behavior is reasonable.
konijn_
> On 28 fév, 23:06, Kenneth 'Bessarion' Boyd <zaim...@zaimoni.com>
> wrote:
>
> > On 2008-02-28 20:39:26, jice <jice.nos...@gmail.com> wrote:
>
> > > Hi all,
>
> > > I've been fighting with an issue on the Chronicles of Doryen and I
> > > wonder if someone here has a solution.
>
> > > I have a bunch of small rectangles positioned randomly on a much
> > > bigger rectangle. I'm trying to find how to move the small rectangles
> > > so that :
> > > - they stay inside the bigger one
> > > - they do not overlap
> > > in a way that minimize the movement of each small rectangle.
>
> > Instance of the packing problem; NP-complete in the number of small rectangles.
>
> Ok, I didn't know the packing problem. Checking literature on it...
>
Ah, if you are of the literature checking kind, also check out 'radial
layouts'. It would in my mind be something typically CoD like ;-)
Cheers,
T.
PS : A good example of radial layouts would be : www.visualthesaurus.com
jice
> >>> I have a bunch of small rectangles positioned randomly on a much
> >>> bigger rectangle. I'm trying to find how to move the small rectangles
> >>> so that :
> >>> - they stay inside the bigger one
> >>> - they do not overlap
> >>> in a way that minimize the movement of each small rectangle.
>
>
> The first is to work outwards from the player, putting each box in turn
> as close as you can to where it is supposed to be. This is fast.
>
Ok, this one works fine ! For anyone interrested, here is how to do :
I store the available screen space in a list of rectangles. At the
beginning, there is only a single rectangle covering the whole
available screen space.
Each time I add a small rectangle on the screen, I check if it is
inside one of those empty rectangles. In that case, I can add it
without moving it.
If not, I move it inside the closer empty rectangle by looping through
all of them.
When I add a small rectangle, I replace all the empty rectangles
containing it by 2, 3 or 4 sub rectangles so that the place occupied
by the small rectangle is no more in the empty rectangle list (2 if
the small rectangle is in a corner, 3 if it is o a border, 4 if it is
inside the empty rectangle).
That's it. I'll probably add this to libtcod 1.3 since it can be used
in a wide range of roguelike problems like placing non-overlapping
rooms in a map, houses and streets in a city, text on the screen, ...
Thanks again Simon :)
--
jice
jice
> Ah, if you are of the literature checking kind, also check out 'radial
> layouts'. It would in my mind be something typically CoD like ;-)
>
> Cheers,
> T.
>
> PS : A good example of radial layouts would be :www.visualthesaurus.com
awesome, amazing, astonishing, astounding, dumbfounding ! :o)
indeed, it's quite cool, but an implementation on a console would
loose the smooth text movement. Yet, something to dig into... A radial
layout inventory or skill tree ?
--
jice
Simon Richard Clarkstone
Thanks. However, I think it will fail in an infuriating manner
sometimes. For example, suppose you have a 3x3 space, and you want to
fit these rectangle on it: 1x1, 2x1, 2x1, 1x2, 1x2. An answer is:
+-+---+
| | |
| +-+-+
| | | |
+-+-+ |
| | |
+---+-+
But I don't think your algorithm can produce it, even given the
upper-left rectangle as fixed, because of the way it divides space up.
I might be misunderstanding it though.
--
src/
jice
<s.r.clarkst...@dunelm.org.uk> wrote:
> jice wrote:
> >> jice wrote:
> >>>>> I have a bunch of small rectangles positioned randomly on a much
> >>>>> bigger rectangle. I'm trying to find how to move the small rectangles
> >>>>> so that :
> >>>>> - they stay inside the bigger one
> >>>>> - they do not overlap
> >>>>> in a way that minimize the movement of each small rectangle.
>
Right, it's not supposed to solve the packing problem. You need more
space than the sum of the rectangles surfaces and you need to give a
starting position to each rectangle. If you give it too much
rectangles, there will be no more available space and the last
rectangles will be simply rejected. But it works for the kind of
problems I mentioned. After all, it's only to print a few shop
names :)
--
jice
jot...@hotmail.com
> Right, it's not supposed to solve the packing problem. You need more
> space than the sum of the rectangles surfaces and you need to give a
> starting position to each rectangle. If you give it too much
> rectangles, there will be no more available space and the last
> rectangles will be simply rejected. But it works for the kind of
> problems I mentioned. After all, it's only to print a few shop
> names :)
>
> --
> jice
I see you're satisfied with this solution for the purpose of printing
shop names, but I can think of an extension that will probably work
even in the most difficult scenarios :)
The main problem, as I see it, is that you can make a bad decision
early on in the process of assigning positions and only realize it
much later, when there isn't enough room for the boxes placed last.
So we need to modify the main loop with some sort of backtracking. The
easiest way IMO is to just pick up your favorite A* implementation and
let it explore the possibilities, by making each step of the main loop
become one step of the A* algorithm. (I like MicroPather, it's a
freely available piece of code and it's designed to be small and
fast.)
The heuristic: It should be the sum of the distances from each box to
its initial position. The algorithm will attempt to minimize this.
Better yet, make it the sum of the squares of the distances, so two
moderate distances are better than a big one and a small one. (This is
the rationale behind least-squares fitting, as I understand it.)
The decision: It could be "choose a box to move, and a position to
move it" but that would make the state-space too big to explore. I
think a simpler alternative would be "choose which box will be moved
closer to the center". If the order isn't quite right and the next box
is placed too far away, A* will backtrack to the next best option, as
it usually does when used for path-finding.
That's it, it should work even for demanding uses such as room
placement :)
Jotaf
jice
> On 29 Fev, 23:41, jice <jice.nos...@gmail.com> wrote:
>
> > Right, it's not supposed to solve the packing problem. You need more
> > space than the sum of the rectangles surfaces and you need to give a
> > starting position to each rectangle. If you give it too much
> > rectangles, there will be no more available space and the last
> > rectangles will be simply rejected. But it works for the kind of
> > problems I mentioned. After all, it's only to print a few shop
> > names :)
>
>
Wow ! Things get a bit complicated for me :) As I understand it, A*
works because both the heuristic and the cost functions leads it
naturally to the right solution. But here, we have the cost function
(sum of the box distance) but no heuristic to find the next step. How
can we assure that moving a rectangle to the center will lead to a
solution in a finite amount of time ?
I think the only perfect and fast solution is the one I mentioned
earlier : attach each rectangle to its initial position with a spring,
use a 2D AABB collision and a simplified constraint solver. For
someone used to writing physics engine, it should be a piece of cake,
but not for me... !
--
jice
Kenneth 'Bessarion' Boyd
> Wow ! Things get a bit complicated for me :) As I understand it, A*
> works because both the heuristic and the cost functions leads it
> naturally to the right solution.
Actually, the cost function is enough. The heuristic is what distinguishes A*
from Djikstra.
> But here, we have the cost function
> (sum of the box distance) but no heuristic to find the next step.
The cost function should give a very high cost to boxes that won't fit.
> How
> can we assure that moving a rectangle to the center will lead to a
> solution in a finite amount of time ?
Without a heuristic, A* transforms to Djikstra.
The problem isn't "finite amount of time", it's "making the time non-exponential
in problem size". Which A* does nothing about in this case.
jot...@hotmail.com
> On 2008-03-03 17:49:41, jice <jice.nos...@gmail.com> wrote:
>
> > Wow ! Things get a bit complicated for me :) As I understand it, A*
> > works because both the heuristic and the cost functions leads it
> > naturally to the right solution.
>
> Actually, the cost function is enough. The heuristic is what distinguishes A*
> from Djikstra.
>
> > But here, we have the cost function
> > (sum of the box distance) but no heuristic to find the next step.
>
> The cost function should give a very high cost to boxes that won't fit.
Right, I should've mentioned that, it was kinda obvious :)
But I wouldn't impose such a harsh limit for the simple fact that
usually the player is mostly interested in things near the center of
the screen. And with a crowded screen, boxes that are far away from
their initial positions can just be so far away that they're out of
the screen completely and are effectively invisible. In this extreme
situation you don't wanna force the algorithm to find a way to cram
them in there... the player will be baffled enough with what he's got
there already.
>
> > How
> > can we assure that moving a rectangle to the center will lead to a
> > solution in a finite amount of time ?
>
> Without a heuristic, A* transforms to Djikstra.
True, and I should've said "cost function" instead of "heuristic". I
was thinking of using the same function for both purposes, the sum of
the squares of distances. (I'll explain this right after the next
paragraph.)
And I should've clarified what I thought was a "next step". My idea
for a next step was to place the next box as close as possible to its
initial position (obviously!), and if another box was overlapping, it
would radiate *outwards* from the center. That's what I understood was
happening in each step of Simon's first algorithm. I thought it was a
good "operation" in that you only need to choose *which* box will be
moved (good to reduce the state-space, there isn't an infinite amount
of possibilities to consider).
This brings me back to the matter of the heuristic. When choosing
between a number of different next steps (which box to move?), you can
just re-calculate the total cost (sum of distances) as if you had made
that move. I don't know if formally it would still classify as a
"heuristic"... it's just a damn cost function and we're trying to
minimize it! :)
>
> The problem isn't "finite amount of time", it's "making the time non-exponential
> in problem size". Which A* does nothing about in this case.
Yes, but worst-case is not always the best metric to define an
algorithm. A* is good because it outperforms other algorithms in most
applications that require a state-space search.
All in all, this would potentially be easier to code than a physics
constraint solver (using out-of-the-box A* code), we could avoid the
major headaches that these solvers usually have (they don't deal well
with local minima, which our A* does), and if there's a solution it's
guaranteed to find it.
Jotaf
Gerry Quinn
> The problem isn't "finite amount of time", it's "making the time non-exponential
> in problem size". Which A* does nothing about in this case.
That is the problem if the OP wants to generate an arbitrarily large
image of an arbitrarily crowded shopping centre, in which it is critical
that the shop names have individual rectangles.
On the other hand, if he wants something that works reasonably well in a
typical game situation, it seems very unlikely to be the problem at all.
- Gerry Quinn
Kenneth 'Bessarion' Boyd
> On 3 Mar, 18:48, Kenneth 'Bessarion' Boyd wrote:
> > On 2008-03-03 17:49:41, jice wrote:
> >
> > > Wow ! Things get a bit complicated for me :) As I understand it, A*
> > > works because both the heuristic and the cost functions leads it
> > > naturally to the right solution.
> >
> > Actually, the cost function is enough. The heuristic is what distinguishes A*
> > from Djikstra.
> >
> > > But here, we have the cost function
> > > (sum of the box distance) but no heuristic to find the next step.
> >
> > The cost function should give a very high cost to boxes that won't fit.
>
> Right, I should've mentioned that, it was kinda obvious :)
> But I wouldn't impose such a harsh limit for the simple fact that
> usually the player is mostly interested in things near the center of
> the screen. And with a crowded screen, boxes that are far away from
> their initial positions can just be so far away that they're out of
> the screen completely and are effectively invisible. In this extreme
> situation you don't wanna force the algorithm to find a way to cram
> them in there... the player will be baffled enough with what he's got
> there already.
True: not fitting more distant boxes should be "less expensive" than not fitting
nearer boxes.
> ....
> This brings me back to the matter of the heuristic. When choosing
> between a number of different next steps (which box to move?), you can
> just re-calculate the total cost (sum of distances) as if you had made
> that move. I don't know if formally it would still classify as a
> "heuristic"... it's just a damn cost function and we're trying to
> minimize it! :)
It counts. (Alpha-beta heuristic pruning does the same thing.)
> > The problem isn't "finite amount of time", it's "making the time non-exponential
> > in problem size". Which A* does nothing about in this case.
>
> Yes, but worst-case is not always the best metric to define an
> algorithm. A* is good because it outperforms other algorithms in most
> applications that require a state-space search.
Yes. If the special cases that aren't awful go off first, frequently, that
works.
> All in all, this would potentially be easier to code than a physics
> constraint solver (using out-of-the-box A* code), we could avoid the
> major headaches that these solvers usually have (they don't deal well
> with local minima, which our A* does), and if there's a solution it's
> guaranteed to find it.
In C++, I expect to use A* as a physics constraint solver when nothing
canonically simpler applies (e.g., binary search).
This doesn't work so well in other static-typed programming languages, as I'd be
instantiating an A* template function/class. I'd guess it'd work well enough in
LISP/Haskell/etc.
jice
> In article <fqhh5t$2tg...@news.vol.cz>, zaim...@zaimoni.com says...
>
> > The problem isn't "finite amount of time", it's "making the time non-exponential
> > in problem size". Which A* does nothing about in this case.
>
> That is the problem if the OP wants to generate an arbitrarily large
> image of an arbitrarily crowded shopping centre, in which it is critical
> that the shop names have individual rectangles.
>
> On the other hand, if he wants something that works reasonably well in a
> typical game situation, it seems very unlikely to be the problem at all.
>
It depends on the game. Look at some Guild Wars or Ragnarok Online
screenshots of crowded cities. The game screen is litterally covered
with text boxes. Guild Wars layout algorithm works very well. I think
it pushes the boxes to the top instead of trying to find the nearest
available place. The result is less messy than in most other mmorpg.
Of course, in the case of a single player roguelike, this kind of
situation should rarely happen except if you simulate a multiplayer
mmorpg...
--
jice