Обнаружение столкновения 2D-группы

Question

Я пытаюсь реализовать обнаружение столкновений в своей игре, но то, что казалось легким, сначала превратилось в монстра, с которым я не могу справиться без какой-либо помощи.

В какой-то момент игра будет RTS, но сейчас это всего лишь куча юнитов, которые можно передать перемещению в определенное место на экране. Но единицы продолжают исчезать только в одном блоке, поэтому я определил ограничивающие поля для каждого блока и испытал на столкновение между единицами после их перемещения в игровом цикле, чтобы отделить их.

Это не сработало, потому что я не реализовал способ узнать, что конкретное устройство, которое я перемещаю, не занимает какое-то другое место (которое я уже повторил).

Я попытался сохранить позиции (или регионы), которые уже заняты, чтобы сдвинуться там, где нет единиц. Но это также не работает в некоторых случаях, например, когда блок перемещается в любом из четырех углов экрана, он не может выходить за пределы экрана и также не может занимать регионы, занятые подразделениями, с которыми он сталкивается.

Я по-прежнему уверен, что я слишком усложняю то, что можно сделать легко с другим подходом.

Каждый блок имеет собственную ограничительную сферу, положение, вектор направления и вектор скорости.

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. Для ВСЕ единиц (вы обрабатываете ВСЕ устройства на этом этапе): При столкновении, удалите устройство от столкновения, на расстоянии 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;   
} 

Answer 2

Почему бы не применить вектор направления к каждой единице и не повернуть их в сторону этого вектора относительно? Например, если вы создаете вектор, который указывает на 45 градусов на северо-восток и находится в 30 метрах от текущего местоположения вашей группы (текущее местоположение должно быть либо средним по местоположению всей группы, либо какой-либо схемой, такой как та, которая относится к ближайшей единице) переместите каждый блок по отношению к его собственной позиции в это место. Теперь у вас должна быть установка системы столкновений, чтобы вы могли обращаться с чем-то вроде вражеского подразделения, заряжающего вашу группу или вашу группу, соприкасающиеся с каким-то неподвижным объектом. Теперь, что касается проблемы с угловым столкновением, вы должны добавить дополнительную проверку на столкновение, чтобы убедиться, что устройство, с которым сталкивается сталкивающийся блок, может переместиться (т.е. он не окружен на всех четырех сторонах), если вы хотите иметь касание нажмите сенсорный блок. В противном случае вы могли бы просто отключить ваш трогательный блок.

Вы могли бы использовать это в качестве ссылки: http://www.gamespp.com/algorithms/collisiondetection/

Answer 3

Это своего рода звучит как ваш код столкновения выключен. Каковы ваши ограничивающие объемы, коробки? Повернутые коробки?

Попробуйте использовать Круги для ограничивающих объем единиц. Большинство игр используют круг на юнитах, поскольку он дешевле и точнее. Плюс коллизионный код круга -> довольно дешевый.

Если всем устройствам предлагается перемещаться в определенное место, они должны продолжать нажимать на другие блоки и не перемещаться внутри друг друга. Я могу представить некоторые странные ситуации, происходящие с большими группами, например, подразделения, которые появляются у других, но с этим можно поговорить позже.

Просто убедитесь, что, когда устройство сталкивается с объектом, код «толкает», что единицы позиции отступают. Или, отодвиньте его назад по своей скорости * скорости.