2D游戏碰撞的高效算法？

我正在编程一个炸弹人在Java教程之后（这是我的第一场比赛）。本教程提供了以下用于检测碰撞的代码。2D游戏碰撞的高效算法？

 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游戏中碰撞相关的其他问题。非常感谢。

来源

2011-07-25 Rama

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

然后我会建议你的炸弹人级别作为一个瓷砖的集合逻辑建模。每个贴图代表您的关卡中的一个离散位置，并且在逻辑上可能永远在瓷砖“之间”或同时占用两个贴图。每个瓦片可以跟踪当前的地形特征，以及它是否是玩家的有效目标瓦片（以及敌人，如果允许敌人穿越通常不可通行的地形，则每个瓦片可能具有不同的规则为玩家）。

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

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

来源

2011-07-25 04:38:53 aroth

非常感谢您的回答，这非常明确和有用:)现在我将阅读文章。 – Rama

网格碰撞可以减少从数百个矩形检查到几个布尔检查的碰撞计算。它也像它有自己的内置碰撞检测方向。如果不是成千上万，速度可能快数百倍。我使用的系统允许在空格子内自由移动。只有遇到的问题是对角线进入格子。你的文章给了我一个想法，但解决这个问题。 – WVrock

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

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

注意：在上面的网格检查例子，我用布尔值的2维数组设置不可逾越的网格坐标以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).

他们已经进入，他们不应该。否则，只需将它们返回到之前的网格。

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

来源

2014-10-29 08:01:52 WVrock

2D游戏碰撞的高效算法？

回答

相关问题