我正在开发一款具有相当大的方形 2d 游戏区域的游戏。游戏区没有瓷砖，边有界(没有环绕)。我试图弄清楚如何最好地划分这个世界以提高碰撞检测的性能。与其检查每个实体是否与所有其他实体发生碰撞，我只想检查附近实体是否发生碰撞和避障。
我对这个游戏世界有一些特别的担忧……
我有兴趣使用类似于此处答案中描述的内容:Quadtree vs Red-Black tree for a game in C++?
我担心的是，世界的树分割能够处理实体中的大尺寸差异的能力如何？为了将世界划分为足够小的实体，较大的实体需要占据大量区域，我担心这将如何影响系统的性能。
我的另一个主要关注点是如何正确地使占用区域列表保持最新。由于有很多移动的实体，还有一些非常大的实体，似乎将世界分开会产生大量开销来跟踪哪些实体占据哪些区域。
我主要是在寻找任何有助于减少碰撞检测和避障计算的好算法或想法。
最佳答案
如果我是你，我会从实现一个简单的 BSP(二进制空间分区)树开始。由于您在 2D 中工作，因此绑定(bind)框检查非常快。你基本上需要三个类:CBspTree、CBspNode 和 CBspCut(不是真的需要)
通往分割世界的接口(interface)将通过树类，如果您想用例如替换 BSP 解决方案，在此之上再创建一个层可能是一个非常好的主意。四叉树。一旦你掌握了窍门。但根据我的经验，BSP 就可以了。
如何在树中存储您的项目有不同的策略。我的意思是你可以选择拥有例如每个节点中的某种容器，其中包含对占据该区域的对象的引用。这意味着(正如您问自己的那样)大项目将占据许多叶子，即会有很多对大对象的引用，而非常小的项目将出现在单个叶子上。
根据我的经验，这没有那么大的影响。当然这很重要，但你必须做一些测试来检查它是否真的有问题。您可以通过简单地将这些项目留在树中的分支节点上来解决这个问题，即您不会将它们存储在“叶级”上。这意味着您会在遍历树时快速找到这些对象。
当谈到你的第一个问题时。如果您只想将此分割用于碰撞测试而不是其他任何东西，我建议永远不会碰撞的东西永远不会被插入到树中。例如，如您所说，导弹不能与另一枚导弹相撞。这意味着您甚至不必将导弹存放在树中。
但是，您可能还想将 bsp 用于其他用途，您没有指定，但请记住这一点(例如使用鼠标拾取对象)。否则，我建议您将所有内容都存储在 bsp 中，稍后再解决冲突。只需询问特定区域中对象列表的 bsp 以获得一组有限的可能碰撞候选对象，然后执行检查(假设对象知道它们可以碰撞什么，或其他一些外部机制)。
如果你想加快速度，你还需要照顾合并 和 拆分 ，即当从树中删除事物时，许多节点将变为空或低于某个节点级别的项目数量将减少到某个合并阈值以下。然后您想将两个子树合并为一个包含所有项目的节点。当您将项目插入世界时，就会发生拆分。因此，当项目数量超过某个分割阈值时，您会引入一个新的切割，将世界一分为二。这些合并和拆分阈值应该是两个常量，您可以使用它们来调整树的效率。
合并和拆分主要用于保持树平衡并确保它根据其规范尽可能高效地工作。这确实是您需要担心的。从一个位置移动事物并因此更新树非常快。但是在合并和拆分时，如果您经常这样做，它可能会变得昂贵。
这可以通过引入某种惰性合并和拆分系统来避免，即您有某种脏标记或修改计数。批处理所有可以批处理的操作，即移动 10 个对象并插入 5 个可能是一个批处理。一旦这批操作完成，您检查树是否脏，然后执行所需的合并和/或拆分操作。
如果你想让我进一步解释，请发表一些评论。
干杯!
编辑
树中有很多可以优化的东西。但如您所知，过早优化是万恶之源。所以从简单的开始。例如，您可以创建一些可以在遍历树时使用的通用回调系统。通过这种方式，您不必查询树来获取与绑定(bind)框“问题”匹配的对象列表，相反，您只需遍历树并在每次遇到某些东西时执行该回调。 “如果我提供的这个绑定(bind)框与你相交，那么用这些参数执行这个回调”
关于data-structures - 如何分割 2d 游戏世界以获得更好的碰撞检测，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/899778/