Jon*_*lsh 14 collision-detection data-structures
我正在开发一款具有相当大的正方形2D游戏区域的游戏.游戏区域是无框的,有边界(没有缠绕).我试图找出如何最好地划分这个世界以提高碰撞检测的性能.我不想检查每个实体是否与所有其他实体发生碰撞,而只是检查附近的实体是否存在碰撞和避障.
我对这个游戏世界有一些特别关注......
我希望能够同时在游戏世界中使用大量实体.但是,%的实体不会与相同类型的实体发生冲突.例如,射弹不会与其他射弹碰撞.
我希望能够使用大量的实体大小.我希望最小实体和最大实体之间存在非常大的差异.
游戏世界中很少有静态或非移动实体.
我有兴趣使用类似于答案中描述的内容:Qualeree vs Red-Black树用于C++游戏？
我担心的是,世界的树细分能够处理实体中的大尺寸差异吗？为了让较小的实体足够分裂世界,较大的实体需要占据大量的区域,我担心这将如何影响系统的性能.
我的另一个主要问题是如何正确地保持被占领区列表的最新状态.由于存在大量移动实体和一些非常大的移动实体,看起来分割世界将产生大量开销以跟踪哪些实体占据哪些区域.
我主要寻找任何有助于减少碰撞检测次数和避障计算的好算法或想法.
如果我是你,我首先要实现一个简单的BSP(二进制空间分区)树.由于您在2D中工作,因此绑定框检查非常快.你基本上需要三个类:CBspTree,CBspNode和CBspCut(不是真的需要)
面向分裂世界的界面将通过树类,如果您想用例如四叉树替换BSP解决方案,那么在此基础上再创建一个层可能是一个非常好的主意.一旦你掌握了它.但根据我的经验,BSP会做得很好.
有关如何在树中存储项目的不同策略.我的意思是,您可以选择在每个节点中包含某种容器,其中包含对占用该区域的对象的引用.这意味着(正如你在问自己)大型物品会占据很多叶子,即会有很多对大型物体的引用,而非常小的物品会出现在单叶上.
根据我的经验,这并没有那么大的影响.当然这很重要,但你必须做一些测试来检查它是否真的是一个问题.您可以通过简单地将这些项目留在树中的分支节点来解决这个问题,即您不会将它们存储在"叶级"上.这意味着您可以在遍历树时快速找到这些对象.
谈到你的第一个问题.如果您只是将这个细分用于碰撞测试而没有其他任何东西,我建议永远不会碰撞的东西都会插入到树中.例如,如你所说的导弹不能与另一枚导弹发生碰撞.这意味着你甚至不必将导弹存放在树上.
但是,您可能也希望将bsp用于其他事情,您没有指定,但请记住这一点(用于使用鼠标选择对象).否则,我建议您将所有内容存储在bsp中,并在以后解决冲突.只需要询问某个区域中某个对象列表的bsp就可以得到一组有限的可能碰撞候选者,并在此之后执行检查(假设对象知道它们可以碰撞什么,或者其他一些外部机制).
如果你想加快速度,你还需要注意合并和拆分,即当从树中移除东西时,很多节点将变空或者某个节点级别以下的项目数量将减少到某个合并阈值以下.然后,您希望将两个子树合并为一个包含所有项目的节点.将项目插入世界时会发生拆分.因此,当项目数量超过某个分裂阈值时,您会引入一个新的切割,将世界分成两部分.这些合并和拆分阈值应该是两个常量,可用于调整树的效率.
合并和拆分主要用于保持树的平衡,并确保它根据其规格尽可能高效地工作.这真的是你需要担心的.从一个位置移动东西,从而更新树是非常快的.但是当涉及到合并和拆分时,如果你经常这样做,它可能会变得昂贵.
这可以通过引入某种延迟合并和拆分系统来避免,即你有某种脏标记或修改计数.批量可以批量处理的所有操作,即移动10个对象,插入5个可能是一个批次.完成该批操作后,检查树是否为脏,然后执行所需的合并和/或拆分操作.
如果您希望我进一步解释,请发表一些评论.
干杯!
编辑
树中可以优化很多东西.但是如你所知,过早的优化是所有邪恶的根源.所以从简单开始吧.例如,您可以创建一些可在遍历树时使用的通用回调系统.这样你就不必查询树来获得与绑定框"问题"匹配的对象列表,而是只需遍历树并在每次点击时执行该回调."如果我提供的这个绑定框与你相交,那么用这些参数执行这个回调"