java - 二维游戏中碰撞的高效算法？

Question

我正在按照教程使用 Java 编写炸弹人(这是我的第一款游戏)。本教程建议使用以下代码来检测碰撞。

        for (int p=0; p<entities.size(); p++) {
            for (int s=p+1; s<entities.size(); s++) {
                Entity me = (Entity) entities.get(p);
                Entity him = (Entity) entities.get(s);

                if (me.collidesWith(him)) {
                    me.collidedWith(him);
                    him.collidedWith(me);
                }
            }

到目前为止，entities 是一个包含敌人和玩家的数组列表。由于我还想检测玩家与墙壁的碰撞，我是否应该将关卡中的每一面墙或砖 block 放入实体数组列表中？如果是这样，这个算法是不是很低效？这些方 block 不会与其他方 block 发生碰撞，所以我在考虑管理不同列表中的游戏实体。你有什么建议？有更高效的算法吗？

注意:我已经阅读了与 2D 游戏中的碰撞相关的其他问题。非常感谢。

Answer 1

我建议阅读这篇关于幽灵移动和碰撞检测如何工作的优秀文章 PacMan .

然后我会建议将您的炸弹人关卡从逻辑上建模为一组图 block 。每个图 block 代表您关卡中的一个离散位置，从逻辑上讲不可能在图 block “之间”或同时占据两个图 block 。每个瓦片都可以跟踪当前在其上的地形特征类型，以及它是否是玩家(和敌人)的有效目标瓦片，如果允许敌人穿越通常无法通过的地形，则可能对每个瓦片有不同的规则为玩家)。

那么您就不需要为世界上的每个对象都使用碰撞检测算法。当敌人需要移动时，或者当用户试图移动他们的角色时，您所要做的就是检查与其当前图 block 相邻的所有图 block (如果允许对角线移动，则最多 4 个或 8 个)，查看每个图 block 是否代表有效的移动方向，如果不是有效方向则阻止移动。

回答你的问题，是的，在每次位置更新时迭代世界上的每个对象将是非常低效的。