Об алгоритмах обнаружения столкновений в AS3 - PullRequest
Новая
       5

Об алгоритмах обнаружения столкновений в AS3

0 голосов
/ 16 августа 2011

Хорошо. Таким образом, существует несколько методов для реализации обнаружения столкновений, таких как R-деревья, Quadtrees, BSP деревья Рекурсивная кластеризация (RDC). Или, может быть, больше.

Моя проблема в том, что у меня на сцене около 6-8 врагов, некоторые из них движутся, некоторые из них неподвижны, а также у меня есть Герой, который стреляет из трех типов ракет одновременно. Таким образом, я получаю на сцене около 70-100 объектов одновременно.

У меня вопрос: какой алгоритм использовать для этого типа проблемы, и какой является обычной практикой? Также, что является самым эффективным?

Я думал о реализации Quad-деревьев, но я читал, что они могут быть медленными, или я ошибаюсь?

ps: Могу ли я использовать восьмеричные деревья или они строго для 3D?

Ответы [ 3 ]

2 голосов
/ 16 августа 2011

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

В зависимости от скорости вашей игры, вам может потребоваться проверка на наличие коллизий каждый второй кадр (или даже реже) вместо каждого кадра. Это даст вам 100% прирост производительности при обнаружении столкновений.

Я рекомендую просто сделать это: 

for each(var enemy:Enemy in _enemies){
    for each(var bullet:Bullet in _bullets){
         if(bullet.x > enemy.x - enemy.width / 2 && 
            bullet.x < enemy.x + enemy.width / 2 &&
            bullet.y > enemy.y - enemy.height / 2 && 
            bullet.y < enemy.y + enemy.height / 2){
                trace("collision!");
         }
     }
}
1 голос
/ 16 августа 2011

Во-первых, вы делаете флеш игру. Во-вторых, ваши боеприпасы взрываются. Вам не нужно точное обнаружение столкновений. Если ваши методы лаконичны, более 100 объектов не будут вам мешать.

Перебери врагов и проверь расстояние. Если расстояние меньше X, взорвитесь, снова обойдите врагов, используя расстояние для относительного урона. 

// class variables
var baseDamage:Number = 50;
var splashMinDistance:Number = 72;
var splashMaxDistance:Number = 144;

var enemies:Array = // array of enemies
var ammunition:Array = // array of live ammo

function checkForContact() {
    var enemy:Enemy;
    var ammo:Ammo;

    var i:int, ic:int = enemies.length;
    var j:int, jc:int = ammo.length;

    for (i=0; i<ic; i++) {
        enemy = enemies[i];
            if (enemy == NULL) continue;
        for (j=0; j<jc; j++) {
            ammo = ammunition[j];
                    if (ammo == NULL) continue;
            if (contact(ammo, enemy)) {
                explode(ammo);
                ammo = NULL;
            }
        }
    }

    // sort ammo to remove nulls now that we're past
    // the time-sensitive part
}

function contact(ammo:Ammo, enemy:Enemy):Boolean {
    return (distance(ammo, enemy) < splashMinDistance);
}

function explode(ammo:Ammo) {
    var enemy:Enemy;
    var distance:Number;

    var i:int, ic:int = enemies.length;

    for (i=0; i<ic; i++) {
        enemy = enemies[i];
        distance = clamp(distance(ammo, enemy), splashMinDistance, Math.INT_MAX);
        if (distance > splashMaxDistance) continue;
        damageRatio = ((distance-splashMinDistance) / (splashMaxDistance-splashMinDistance));
        enemy.health -= baseDamage * damageRatio;
        if (enemy.health < 0) kill(enemy);
    }
}


function distance (o:Object, o2:Object) {
    var dx=o.x-o2.x;
    var dy=o.y-o2.y;
    return Math.sqrt(dx*dx+dy*dy);
}

Наконец, вам не нужно проверять наличие столкновений в каждом кадре. Опять же, вы делаете флеш игру. Управляйте своими ожиданиями.

1 голос
/ 16 августа 2011

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

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

Надеюсь, этого достаточно, чтобы быть полезным.

...