c++ - 2D 群组碰撞检测

Question

我正在尝试在我的游戏中实现碰撞检测，但一开始看起来很容易的事情已经变成了一个怪物，如果没有一些帮助我无法完全解决。

该游戏在某个时候会成为 RTS，但现在只有一堆单位可以被告知移动到屏幕上的特定位置。但是，单位不断消失，只剩下一个单位，所以我为每个单位定义了边界框，并在游戏循环中移动它们后测试单位之间的碰撞，以便将它们分开。

那没有用，因为我没有实现一种方法来知道我正在移动的特定单元不会取代其他单元的位置(我已经迭代过)。

我试图保持已经占据的位置(或区域)，以便转移到没有单位的地方。但这在某些情况下也不起作用，例如当一个单位在屏幕四个角中的任何一个移动时，它不能超出屏幕的边界，也不能占据与其碰撞的单位所占据的区域。

我仍然很确定我过于复杂化了一些可以通过不同方法轻松完成的事情。

每个单元都有自己的包围球、位置、方向 vector 和速度 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显示了我到目前为止所得到的，但很明显它存在严重的故障并且有不必要的单位移动。

我想要的是，当两个或多个单元聚在一起时，它们自然会蜂拥而至。但是所有的单位都不会一直结成一个群。由于每个单元具有不同的检测范围，因此可以将一个或多个单元从鸡群中分离出来。我想要这个以便以后我可以选择和移动不同的单位组。

Answer 1

1. 为每个单元存储一个该单元想要出现的位置。
2. 继续将单位移动到该位置。
3. 对于 ALL 单位(您在此步骤中处理所有单位):发生碰撞时，将单位推离碰撞，距离SMALL。即，如果您需要将单位移动 (x:10.0; y:10.0) 以避免碰撞，请将其移动 (x:1.0; y:1.0)。当两个单位发生碰撞时，您可以立即将它们推离碰撞点，但要保持小步，即使它不会立即解决碰撞。
4. 重复 #3 N 次(N 应该在 10..50 左右)或直到任何单元都没有发生碰撞。

这是一种可以自动处理所有问题的愚蠢方法。当您将多个对象放置在同一个位置并且您希望将它们移开到它们不再碰撞的某个合理位置时，此算法也很有用。

或者你可以学习 boids . Java 演示可用 here .这将在不滥用碰撞检测的情况下处理单元碰撞/编队。

---

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;        
}