Hi! I´m working on an RTS game, in which units move around in small battalions. I've been writing some code so that units sort of keep formation when given orders, unless the units are too spread, as it happens in Starcraft 2 for example. However, doing this with battalion mechanics (instead of individual units) presents the issue that battalions tend to clump and mix quite a lot, so it looks kind of messy.

These are a couple screenshots of a debug visualization, which represents the battalion destination points as rectangles (will be units in the actual game).

As it is visible, two the battalions will overlap. I figured out that the best way to make things less messy, would be to calculate and resolve the rectangle collisions when the order is given, so that when units actually move and arrive at their destination, it is less cluttered. For example, the two battalions could be slightly separated to look like:

My question is: Since the rectangles are aligned relative to themselves, AABB collision detection could be performed, by:

1. Rotating the set of points to align with an axis
2. Calculating and resolving the collisions
3. Rotating it back finally.

On the other hand, I don´t know if it would be easier/more performant to use other polygon collision detection algorithm (such as separating axis theorem) and solve the collisions directly with rotated rectangles.

Thanks for reading!

MaxPowerReforged said:
On the other hand, I don´t know if it would be easier/more performant to use other polygon collision detection algorithm (such as separating axis theorem) and solve the collisions directly with rotated rectangles.

No, if all your rectangles share the same orientation, axis aligned rectangle detection and resolve will be simpler and faster.

But it looks you could also use capsule / pill shapes:

The shape drawn in blue. The test would be to find the closest points on two (red) lines, and measuring if the distance between them (black line) is shorter than the sum of both radii.
That's even simpler than rectangles because it has less cases (corner-corner, corner-edge, edge-edge).
For the same reasons, behavior is also smoother and more predictable.

Here some code example for the test: https://github.com/davideberly/GeometricTools/blob/master/GTE/Mathematics/DistLineLine.h​