我的问题是，我开发的一款游戏使用四叉树进行快速接近检测，用于武器射击时的距离检查。我使用的是经典的"4宽"四叉树，这意味着当我试图将第5个子节点添加到已经完整的父节点时，我会进行细分。
最初，一组可用的目标分布得相当均匀，因此四叉树运行得非常好。由于设计的变化，我们现在在相对较小的空间内获得大量敌人的集群，这导致了性能问题，因为四叉树变得明显不平衡。
我想到了两种可能的解决方案，要么修改四叉树来处理这个问题，要么切换到另一种表示方式。
我唯一熟悉的另一种表示是空间散列，对此我并不太熟悉。据我所知，这可能会遇到同样的问题，因为集群最终会包含相对较少的哈希桶。据我所知，BSP是一种可能的解决方案，它将比四叉树或空间哈希更好地处理不均匀分布。
不公平，我知道，实际上现在有三个问题。
-
我可以对四叉树进行任何修改吗，例如增加节点的"宽度"，这将有助于解决这个问题？
-
我花时间考虑一个空间散列值吗？
-
BSP或其他数据结构是处理不均匀分布的更好选择吗？
我通常使用每个节点至少有10个条目的四叉树，但您必须尝试一下。
我没有空间哈希的经验。
你可以研究的其他结构有：
- KD树：它们实现起来很简单，也很适合邻居搜索，但使用字符串聚类会变得更慢。它们更新有点慢，可能会变得不平衡
- R*Tree：更复杂，非常适合邻居搜索，但更新速度甚至比KD Trees慢。它们不会因为自动再平衡而变得不平衡。大部分情况下，重新平衡很快，但在极端情况下，它偶尔会进一步减慢速度
- PH树：实现起来相当复杂。好邻居搜索。具有非常好的更新速度(如四叉树)，最大深度受坐标的位宽限制(通常为32或64位)，因此它们不会真正变得不平衡。可以很好地扩展大型数据集(100万及以上)，我对小型数据集几乎没有经验
如果您使用的是Java，我在这里(R*Tree)和这里(PH-Tree)都有Apache许可版本。