Ok, given the following problem, how would I determine the final positions of the entities involved? Unit A is at position 20x20 and has a width and height of 30 giving it a rectangle of 5x5 - 35x35. Unit B is at position 15x15 and has a width and height of 10 giving it a rectangle of 10x10 - 20x20. Unit B is the "stacker" (causing the stack scenario to occur) and must move. The answer needs to work in recursive situations... namely, once Unit B is placed, Unit C comes along with the same dimensions as Unit B and stops at the same position that Unit B originally stopped (15x15). Where does Unit C go? Etc... This has been kicking my butt for HOURS and HOURS. It needs to get resolved. ;) -E

What type of game is this, and how does the movement system work? How do units become stacked?

Hmm... not sure how giving you that information will help resolve the issue.

The answer that I am looking for is basically how to calculate a 2D block map such that rectangles can be placed near the original position.

One really good way to understand the problem is to grab a handful of coins (quarters, dimes, pennies, etc...) and pile them into a single stack. Then, starting at the top of the stack and working until there is only one coin left in the stack, remove the top coin and position it as close to the original position as possible without stacking it on an already existing coin.

OK, so it's like units popping out of a factory in some rts games. One simple solution that was used by warcraft 2 and starcraft is to search around the spot in a spiral pattern or something similiar for the next space where the entity fits. The search pattern ensures that the closest possible open space will be found.

Quote: Original post by EnochDagor
Hmm... not sure how giving you that information will help resolve the issue.

...and restricting information limits the responses you will get. If people cannot understand what your problem actually is (because, believe me, your explanation was terse to say the least) then they generally won't bother trying to help. The members here aren't going to steal your ideas for your game... we all generally have too much on our plates to worry about trying to make someone else's game for them.

Quote: The answer that I am looking for is basically how to calculate a 2D block map such that rectangles can be placed near the original position.

So you're asking how to place an ordered sequence of rectangles of varying size
close to a given point, such that no rectangles overlap and presumably so you minimise the amount of wasted space (or some other cost metric). Is that correct?

If so, you have a multi-objective optimisation problem with no globally optimal solution unless you know the future sequence of rectangles. The best you can do is use some heuristics to estimate the future costs for a finite length sequence and select based on that, or ignore the future and just create a local optima given the prior sequence already placed and the current rectangle.

Regards,

Timkin

Vorpy: Thanks, that is the approach I eventually went with... and it is funny you mentioned Starcraft because that is what eventually made me realize what to do. When you sent a bunch of wraiths or scouts or whatever to a spot, they would all get there and stack but then scatter. I was just hoping there might have been a better alternative than the try...fail system for the scatter pattern. However, I was able to do some prediction analysis etc... basically "reserving" the routes of units which made things much better. In the end, I consistently move away from the starting location in circular patterns to determine where to place the unit and it doesn't hurt performance at all (which surprised me).

Timkin: My initial post was a bit cryptic which is why I used the coin analogy. I don't foresee people stealing my ideas or game designs but it does require a tremendous amount more effort to put those details into the post when they are not relevant to the problem. By not putting that data into the question, I ensure that I get the responses that I am looking for. Changing the movement engine and precalculating collisions is not an option in the scenario that I am in, otherwise, they would have been changed instead. :)

-E