关于AS3中的碰撞检测算法

Question

好的。因此，有几种方法可以实现碰撞检测，如R树、四叉树、BSP树、递归维数聚类(RDC)。或者更多。

我的问题是，我在舞台上有大约6-8个敌人，其中一些是静止的，还有英雄，他同时使用三种类型的导弹射击。所以我一次在舞台上得到大约70-100个物体。

我的问题是，对于这种类型的问题，应该使用哪种算法，以及常见的做法是什么？还有，哪一个是最有效的？

我正在考虑实现四叉树，但我读到它可能很慢，或者我错了？

附言:我可以使用八进制树，或者它们只适用于3D吗？

Answer 1

如果你只有十个敌人和一百颗子弹，我怀疑任何复杂的空间结构都会让你受益良多。检查每一颗子弹对抗每一个敌人相当于一千次检查，在我看来，与维护更复杂的结构相比，性能上的收益太小了。

根据游戏的速度，你可以每隔一帧(甚至更少)检查一次碰撞，而不是每一帧。这将给你的碰撞检测带来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!");
         }
     }
}

Answer 2

我猜我可能没有受过良好的教育，无法理解空间索引数据结构如何解决两个多边形相交的问题。也许你要检查一个区域中其他多边形周围的每个多边形是否相交？

但我提出的一个解决方案是使用Minkowski求和。尤其是如果你所有的点击框都是凸形的。你可以将你的导弹的hitbox加到敌人的hitbox上，并将问题简化为导弹对每个敌人的点成员测试，但如果你的导弹/敌人旋转，这将成为一个更困难的问题。

希望这些信息足够对我们有所帮助。

Answer 3

第一，你在做一个flash游戏。第二，你的弹药会爆炸。你不需要精确的碰撞检测。如果你的方法很简洁，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);
}

最后，您不必检查每个帧的碰撞。再说一次，你在做一个flash游戏。管理你的期望。