Please note that I'm only giving a rough starting point for an algorithm here. I can't say for sure if it will work, and you'll have to do a bit of legwork to implement this.
First, a few quick things: What do you define as "lots of iterations"? The TinyKeep demo you linked does it in around 40-50. Also, given that you are working with something 2D grid based, you should probably be working with a pair of integers (X and Y axis), rather than a floating-point Vector3
.
Looking at your Separate()
method, you don't seem to be taking into account the size of the rooms. This seems to be the primary issue. Because you need to be considering the penetration distance between pairs of rooms (which requires the size).
You only need to consider each pair of rooms once, so use a loop like this:
for(int i = 0; i < count; i++)
for(int j = i+1; j < count; j++) // <- note how it starts at i+1
Here's a rough outline of the algorithm:
For each pair of rectangles, see if they intersect. Pick the axis with the minimum amount of penetration (so: left edge to right edge, right edge to left edge, top edge to bottom edge, bottom edge to top edge). Only use a single axis! Your current algorithm is considering both axes at once, based only on position.
In other words, if you only had two rectangles, this would be the smallest amount you would need to shift them to separate them. This amount could be split between the two rectangles in any ratio (but in opposite directions). This is a directional quantity, so store it as a vector (again: not as a vector3
, but as a pair of int
).
(This is basically a constrained version of the "separating axis theorem".)
The tricky bit, then, is to make this work for multiple rectangles in a way that can be iterated to a final solution. Without trying to implement it myself, I can't say for sure what this would look like. Here's what I would start with:
For each rectangle, store the maximum (or minimum?) separation vector by magnitude. When iterating over each pair, determine the minimum separation vector for that pair as explained above. Divide that separation vector evenly (or randomly?) between the two rectangles and replace the stored value for that rectangle if it is greater (or smaller?) in magnitude.
(Note: when dividing the integers, be aware that you must divide (for example) 5
into 3
and 2
. So divide for one value, and subtract that from the total for the other.)
And then, apply the stored separation vectors to each rectangle - similar to what you are already doing. Then iterate until all of the separation vectors are zero.
simple separation steering
(google for it). It is referenced by the author here : reddit.com/r/gamedev/comments/1dlwc4/… \$\endgroup\$ – tigrou Mar 24 '15 at 17:48