规则空间哈希

这是一个实验，旨在确定是否可以通过修改二维空间哈希的算法来减少查询的空间。具体来说，不是查询立方体网格，而是使用规则三角形网格或六边形网格可能会带来一些好处，如下所示。

为什么是其他类型的规则镶嵌？

大多数实现使用立方体网格（右和红）。我们感兴趣的是提高围绕一个点的圆形查询的效率。具体目标是要最大化 query_radius/total_area_searched。由于 query_radius 是固定的，问题变成了最小化 total_area_searched。在某个半径内，只需要搜索直接相邻给定点块的邻居，所以这个案例是重点，因为许多用例，如粒子碰撞检测，使用固定半径。

对于正方形网格，面积效率是 r : 9r^2，这实际上是基线，因为它是最常见的。

对于六边形网格，面积效率是 r : 7 * 3√3/2 r^2 = 18.18。

而对于三角形网格，面积效率是 r : 13/√3 r^2 = 7.505 r^2。注意，这里的 r 对应于等边三角形的高度，而不是其边长。

因此，使用三角形网格可以提高面积效率的微小改进。

区域效率很重要，因为它与必须在一定距离内检查的点数直接相关。例如，如果点均匀分布，我们预计点的数量将与总搜索区域成正比。因此，通过减少给定查询的搜索区域，我们应该获得大约相等的加速。

区域效率真的重要吗？

现在的问题是，区域效率是否实际上对提高实际运行时间有影响，而不仅仅是理论上。

为什么可能不起作用？

• 额外的开销
  • 由于单个三角形有更多的邻居，哈希可能会成为开销
  • 由于邻居更多，可能会有更多的哈希冲突，因此有更多的误报。

由于有支持和反对的理由，因此有必要仅对其进行基准测试。

实践中的结果

注意：虽然这些结果很有趣，但对于第一次实现来说，从正方形切换过来可能没有太大的好处。

为了比较每种空间哈希的有效性，我制作了一个简单的plinko玩具，它在均匀分布的桩子之间掉落许多球。球（目前）不会相互碰撞，但会与桩子碰撞，因此必须在每一步检查它们的交集。为此，我使用空间哈希，我的实现使用枚举来指定使用哪种坐标系。然后，在运行时，它只需使用每组坐标初始化桩子，并运行演示。

在演示中，有3个报告值

1. FPS：每秒帧数，它与准备每帧的速度相关
2. #Checks：实际检查的交集对数，即使它们被拒绝
3. 以及每帧持续时间的毫秒数，它报告了计算每帧所需的时间。

我们发现#检查直接对应于区域差异，立方体大约为14k，三角形为11k，六边形为28k。因此，如果点对点交集检查是使用立方体空间哈希时的瓶颈，则切换到三角形坐标系可能是个好主意。

然而，我们发现这并不直接与演示的速度相关，发现六边形的速度最快，尽管需要更多的检查。这可能是由于对六边形的邻居进行哈希所需的时间是立方体的7/9，而三角形是13/9。由于球的数量相对较多，这也成为一个瓶颈。如果我们查询的是单个点与更多的桩子，我们可能会发现不同的结果。