2D Group Collision Detection

Question

I'm trying to implement collision detection in my game, but what seemed easy at first has mutated into a monster I can't quite tackle without some help.

The game will be an RTS at some point, but right now it's only a bunch of units which can be told to move to a particular location on the screen. But, the units keep disappearing into only one unit, so I defined bounding boxes for each unit and tested for collision between the units after moving them in the game loop so as to separate them.

That didn't work because I had not implemented a way of knowing that the particular unit I am shifting does not take some other unit's place (which I had already iterated through).

I tried to maintain positions (or regions) already occupied so as to shift where there are no units. But this also does not work in some cases, such as when a unit is shifted in any of the four corners of the screen, it can't go beyond the screen's bounds and also cannot occupy the regions occupied the units it is colliding with.

I'm still pretty sure I'm overly complicating something which can be done easily with a different approach.

Each unit has it's own bounding sphere, position, direction vector and velocity vector.

class Unit {
    friend class Party;
    protected:
        float xPos, yPos;
        float destX, destY;
        float detectionRange;
        Vector *vel;
        Vector *dest;

        int dir;
        int offset;
        int width, height;

        Circle *circle;                 //Bounding Circle
        ...
    public:
        ...
};

//Collision Checking
void Party::checkCollisions() {
    bool noCol;
    float dx, dy;
    Circle *mCircle = NULL;
    Circle *sCircle = NULL;

    do {
        noCol = true;
        for(int i=0; i<numUnits; i++) {
            mCircle = units[i]->getCircle();
            for(int j=0; j<numUnits; j++) {
                if(j==i) {
                    continue;
                }

                sCircle = units[j]->getCircle();
                if(mCircle->isColliding(sCircle)) {
                    noCol = false;
                   mCircle->getShifts(sCircle, &dx, &dy);
                   units[i]->shift(dx, dy);
                   units[j]->shift(-dx, -dy);
                }
            }
        }
    } while(noCol == false);
}

//IsColliding. This is overriden for isColliding(Circle *circle), but here
//you see the actual algorithm.
bool Circle::isColliding(float X, float Y, int rad) {
    float mag = sqrt((X-x)*(X-x) + (Y-y)*(Y-y));

    if(mag <= (radius + rad)){
        return true;
    }

    return false;
}

//Get Shifts
void Circle::getShifts(Circle *c, float *dx, float *dy) {
    float x1 = x - c->x;
    float y1 = y - c->y;

    if(x1 > -1 && x1 < 1) {
        x1 = 1;
    }

    if(y1 > -1 && y1 < 1) {
        y1 = 1;
    }

    *dx = x1/fabs(x1);
    *dy = y1/fabs(y1);
}

This video shows what I have got so far, but it's apparent that it is extremely glitched and has unnecessary unit movements.

What I want is that when two or more units come together, they flock naturally. But all units will not form one flock at all times. Since each unit has a different detection range, it is possible to separate one or more units from a flock. I want this so that later I can select and move different groups of units.

Answer 1

1. For every unit store a location where this unit wants to be.
2. Keep moving the unit into to that location.
3. For ALL units (you process ALL units in this step): When collision occurs, push the unit away from the collision, by a SMALL distance. i.e. if you need to move unit by (x:10.0; y:10.0) to avoid collision, move it by (x:1.0; y:1.0) instead. When two units collide you can push them both away from point of collision at once, but keep step small, even if it doesn't immediately resolve collision.
4. Repeat #3 N times (N should be around 10..50) or until no collision occurs for any unit.

This is a dumb approach that will automatically handle all your problems. This algorithm is also useful when you have many object placed on same spot and you want to move them away to some reasonable positions where they no longer collide.

Alternatively you could study boids. Java demo is available here. This would handle unit collision/formation without abusing collision detection.

---

struct Vec2{
    float x;
    float y;
    Vec2(){
    }
    Vec2(float x_, float y_)
    :x(x_), y(y_){
    }
    Vec2(const Vec2& other)
    :x(other.x), y(other.y){
    }
    Vec2& operator*=(const float f){
        x *= f; y *= f;
        return *this;
    }
};

struct Circle{
    Vec2 pos; 
    float radius;
};

float dot(const Vec2& arg1, const Vec2& arg2){
    return arg1.x*arg2.x + arg1.y*arg2.y;
}

float length(const Vec2& arg){
   return sqrtf(dot(arg, arg));
}

Vec2 operator-(const Vec2& arg1, const Vec2& arg2){
   return Vec2(arg1.x - arg2.x, arg1.y - arg2.y);
}

Vec2 scale(const Vec2& arg, const float scale){
   return Vec2(arg.x*scale, arg.y*scale);
}

bool collide(const Circle& c1, const Circle& c2){
    Vec2 diff = c1.pos - c2.pos;
    float maxSquareDistance = c1.radius+c2.radius;
    maxSquareDistance *= maxSquareDistance;
    return (dot(diff, diff) < maxSquareDistance);
}

Vec getShiftVector(const Circle& c1, const Circle& c2){
    diff = c2.pos - c1.pos;
    maxSquareDistance = c1.radius + c2.radius;
    maxSquareDistance *= maxSquareDistance;
    float squareDistance = dot(diff, diff);
    if (squareDistance > maxSquareDistance)
       return Vec2(0, 0);

    float distance = sqrtf(squareDistance)
    if (distance){
        diff.x /= distance;
        diff.y /= distance;
    }
    else{
        diff = Vec2(1, 0);
    }

    float scaleFactor = c1.radius + c2.radius - distance;

    diff.x *= scaleFactor;
    diff.y *= scaleFactor;

    return diff;        
}

Answer 2

Why not apply a direction vector to every unit and have them head towards that vector relatively? For example, if you generate vector that points 45 degrees northeast and is 30 meters away from your group's current location (the current location should be either the location average of the entire group or by some scheme such as one that concerns the closest unit) just move each unit, relative to it's own position, to that location. Now, you should have a collision system setup in order to allow you to handle something such as an enemy unit charging through your group or your group coming into contact with some stationary object. Now , as for your corner collision problem, you should add an extra collision check to make sure that the unit the colliding unit is touching is able to relocate itself (i.e. he's not surrounded on all 4 sides) if you want to have the touching unit push the touched unit. Otherwise you could just have your touching unit simply stop in place.

You could use this as a reference: http://www.gamespp.com/algorithms/collisiondetection/

Answer 3

It sort of sounds like your collision code is off. What are your bounding volumes, boxes? Rotated boxes?

Try using Circles for the units bounding volume. Most games use circle on units since it's cheaper and accurate. Plus the circle->circle collision code is pretty cheap.

If all units are told to move to a specific location, they should keep pushing into other units and not move inside eachother. I can picture some wierd situaions happening with large groups, like units popping through others, but deal with that later.

Just make sure that once a unit is colliding with an object, the code "pushes" that units position back out. Or, push it back by its direction * speed.