collision-detection - 四叉树与仅用于碰撞检测的网格

Question

我正在考虑使用四叉树对 2D 矩形进行碰撞检测，但当存在所有不同的尺寸时试图找到矩形接触的每个象限似乎有点过于复杂，甚至计算出每个象限应该有多少象限深度.

我决定只在整个区域上设置一个小网格，然后通过对 4 个角中的每一个角执行行 = x/单元格宽度、列 = y/单元格高度，然后检查碰撞来找到每个对象所在的单元格与这些单元格中的每个其他对象。我还对其进行了一些优化，以防止它重新检查相同的对象

我用 32x32 网格和 5000 个移动物体对它进行了暴力测试，结果速度提高了大约 20 倍，碰撞检查减少了 200 倍。所以我想知道使用四叉树比我这样做有什么优势？真的会快很多吗？

Answer 1

当对象的大小变化很大时(由于单个对象移动时需要更新很多很多网格单元)，或者当它们非常小且非常稀疏(这需要大量的网格内存)时，网格就会出现问题存储大部分空单元格)。这些是四叉树等基于树的分区结构大放异彩的情况。