2D游戏中有效的碰撞算法？

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);
                }
            }

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

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

Answer 1

我建议阅读这篇关于幽灵运动和碰撞检测如何在PacMan中运作的优秀文章。

然后我建议将你的炸弹人水平逻辑建模为一组瓷砖。每个图块代表您关卡中的一个离散位置，并且逻辑上不可能永远是“之间”图块或同时占据两个图块。每个磁贴都可以跟踪当前在其上的地形特征类型，以及它是否是玩家的有效目标磁贴（以及敌人，如果允许敌人穿越通常无法通过的地形，则可能对每个玩家都有不同的规则为了球员）。

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

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

Answer 2

还有另一种方法可以将网格用于碰撞系统。我正在使用Aroth建议的更复杂版本并使用它来修复碰撞错误。

从理论上讲，这个系统是最快的（假设你正在检查if(Grid[x][y] ==true)），因为它只对每个实体使用一个布尔检查（可以移动的东西）。

注意：在上面的网格检查示例中，我使用了一个二维的布尔数组，它将不可通过的网格的坐标设置为false。

如果你不担心从墙上弹跳的物理，你可以使用：

1- Divide the map into grids. 
2- Making every entity only fill a tile would be better but not necessary. 
3- Store the previous position or the grid of the entities.
4- Whenever an entity moves, before visually updating their location (also before 
doing other calculations) check the grids they are in. If they are in grid 
that is not empty or simply in a grid that they are not supposed to 
be, return their position back to the previous position (which you have stored). 

如果你想允许实体在网格内自由移动（网格大于它们可以移动的最小距离），那么你需要将它们放在它们输入的网格旁边，而不是它们。否则只需将它们返回到上一个网格。

如果你想让它们从墙上反弹你仍然可以使用它，但我不确定有多少功能可以添加到这样的碰撞系统中。