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

到目前为止，entities是一个包含敌人和玩家的数组列表。由于我也希望检测玩家是否与墙壁碰撞，所以我应该将每个单独的墙壁或砖块平铺到实体数组列表中吗？如果是这样，那么这个算法不是非常低效吗？这些瓷砖不会与其他瓷砖碰撞，因此我想在不同的列表中管理游戏实体。你有什么建议吗？是否有更有效的算法来解决这个问题？

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

- Rama

Answer 1

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

接下来，我建议将Bomberman的关卡逻辑建模为一个瓷砖集合。每个瓷砖代表您的关卡中的一个离散位置，不可能处于“两个瓷砖之间”或同时占据两个瓷砖。每个瓷砖可以跟踪当前所在位置的地形特征，并确定它是否是玩家（和敌人）的有效目标位置（如果允许敌人穿过通常对玩家不可通过的地形，则每个敌人可能都有不同的规则）。

因此，您不需要为世界上的每个对象编写碰撞检测算法。当敌人移动时，或者用户尝试移动他们的角色时，您只需检查所有与其当前瓷砖相邻的瓷砖（4个瓷砖，如果允许对角线移动，则最多为8个），查看每个瓷砖是否代表有效的移动方向，并阻止该移动如果不在有效方向中。

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

- aroth

---

非常感谢你的回答，它非常清晰和有用 :) 我现在会阅读这篇文章。 - Rama

网格碰撞可以将数百个矩形检查的碰撞计算减少到几个布尔检查。它也像具有其自己的碰撞检查方向一样内置。如果不是千倍，那么它可能比之前快上百倍。 我正在使用一个允许在空白网格内自由移动的系统。唯一遇到的问题是对角线进入网格。 不过，你的帖子给了我解决这个问题的想法。 - WVrock

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). 

如果你希望实体在网格内自由移动（网格大小大于它们可以移动的最小距离），那么你需要将它们放置在它们进入但不应该进入的网格旁边。否则，将它们返回到上一个网格。

如果你希望它们从墙壁反弹，仍然可以使用这个方法，但我不确定像这样的碰撞系统可以添加多少功能。

- WVrock

Answer 3

我可以推荐我的项目，但它仍在开发中。 https://github.com/YagaoDirac/Dirac-2d-collision-detection-for-games 它基于四叉树，可以很好地处理稀疏数据。 它提供了碰撞组。这个概念也被应用在UE和Unity中。 目前它只支持圆形与圆形的重叠检测（截至2022年2月22日）。

我计划至少实现AABB，以及防止角色离开地图的碰撞检测。

我还可能提供另一个基于固定网格的系统。

- YagaoDirac