c++ - 2D Group Collision Detection -

i'm trying implement collision detection in game, seemed easy @ first has mutated monster can't quite tackle without help.

the game rts @ point, right it's bunch of units can told move particular location on screen. but, units keep disappearing 1 unit, defined bounding boxes each unit , tested collision between units after moving them in game loop separate them.

that didn't work because had not implemented way of knowing particular unit shifting not take other unit's place (which had iterated through).

i tried maintain positions (or regions) occupied shift there no units. not work in cases, such when unit shifted in of 4 corners of screen, can't go beyond screen's bounds , cannot occupy regions occupied units colliding with.

i'm still pretty sure i'm overly complicating can done different approach.

each unit has it's own bounding sphere, position, direction vector , 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;      {         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. overriden iscolliding(circle *circle), here //you see 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 have got far, it's apparent extremely glitched , has unnecessary unit movements.

what want when 2 or more units come together, flock naturally. units not form 1 flock @ times. since each unit has different detection range, possible separate 1 or more units flock. want later can select , move different groups of units.

1. for every unit store location unit wants be.
2. keep moving unit location.
3. for all units (you process units in step): when collision occurs, push unit away collision, small distance. i.e. if need move unit (x:10.0; y:10.0) avoid collision, move (x:1.0; y:1.0) instead. when 2 units collide can push them both away point of collision @ once, keep step small, if doesn't resolve collision.
4. repeat #3 n times (n should around 10..50) or until no collision occurs unit.

this dumb approach automatically handle problems. algorithm useful when have many object placed on same spot , want move them away reasonable positions no longer collide.

alternatively study boids. java demo available here. 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;         }