java - 碰撞检测 - 任何语言

Question

我现在正在编写一个简单的游戏，我需要能够检测许多对象之间的碰撞(检查 10 个对象是否与任何 20 个其他对象发生碰撞，但不在两组之间发生碰撞)。我编写了一些简单的代码，现在可以运行，但在检测到碰撞后会导致游戏速度极度减慢(顺便说一下，在 Java 中):

        //Check for collisions between tanks and bullets
        ArrayList<Object> objectsToRemove = new ArrayList<Object>();
        for (int i = 0; i < tanksOnScreen.size(); i += 1) {
            //Get tank
            Tank tank = tanksOnScreen.get(i);

            for (int e = 0; e < bulletsOnScreen.size(); e += 1) {
                //Get bullet
                Bullet bullet = bulletsOnScreen.get(e);

                //Check for collision
                if (tank.collides(bullet.x, bullet.y, 10, 10)) {
                    System.out.println("Collide");
                    objectsToRemove.add(bullet);
                    objectsToRemove.add(tank);
                    break;
                }
            }
        }

        for (Object obj:objectsToRemove) {
            if (obj.getClass().equals(Bullet.class)) {
                bulletsOnScreen.remove(bulletsOnScreen.indexOf(obj));
            } else if (obj.getClass().equals(Tank.class)) {
                tanksOnScreen.remove(tanksOnScreen.indexOf(obj));
            }
        }

还有坦克的collides()方法:

public boolean collides(float px, float py, float pwidth, float pheight) {
    // If the distance between the two centers of the lines on x and y axis
    // Is less than the distance of half the w and h added together, the objects
    // Are colliding
    float x1 = (px > x) ? x : px, x2 = (px > x) ? px : x, y1 = (py > y) ? y : py, y2 = (py > y) ? py : y;
    float w1 = (x1 < x2) ? width : pwidth, w2 = (x1 < x2) ? pwidth : width, h1 = (y1 < y2) ? height : pheight, h2 = (y1 < y2) ? pheight : height;
    if ((x2 + w2/2) - (x1 + w1/2) < (w1/2 + w2/2)&&(y2 + h2/2) - (y1 + h1/2) < (h1/2 + h2/2)) {
        return true;
    } else {
        return false;
    }
}

我认为延迟是由于双 for 循环(迭代对象)造成的。我不确定如何消除这些 for 循环或如何在屏幕的某个区域获取项目符号，并且只检查这些项目符号而不使用另一个 for 循环(我认为是隔离)。谁能指出我与许多物体进行碰撞检测的正确方向？我不介意答案使用什么语言，即使它是伪代码。

谢谢

本

编辑 1

我现在正在使用 Java 的 Slick 图形 API，它为您提供了更新和渲染方法来添加渲染和游戏逻辑。我将这个碰撞检测放在 update 方法中(每帧都会调用该方法 - 每秒大约 60 次)。碰撞发生后，速度变慢，并且物体从屏幕上移除——我觉得很奇怪。也许删除 for 循环中的对象后使用 break 命令可以将其根除？

编辑2

感谢大家的回答，这些引用资料对 future 有很大帮助。我只是通过将子弹和坦克换成循环来解决这个问题，所以子弹被摧毁后它不会继续循环。我不应该问这个问题，因为最终解决起来很容易。 Dave 和 Banthar 说得对，问题不在于代码，而应该是即时的。

Answer 1

一个好主意是使用 octree 。由于子弹会移动，我假设您需要它的动力学版本 - 互联网上有很多关于动力学数据结构的文章。

此外，如果您想检测更复杂的凸多边形之间的碰撞，我建议您使用 gjk算法对于这种计算来说非常快。请注意，这只会加快一对对象的碰撞检测时间，对的数量仍将保持不变。