问题标签 [space-partitioning]

我正在为我的毕业项目制作一个 2D 角色扮演游戏，并且我正处于想要随机生成我的地牢的地步。
我正在按照本教程http://www.rombdn.com/blog/2018/01/12/random-dungeon-bsp-unity/制作一个随机生成的地牢。

经过大量研究，我发现 BSP 算法可以生成我想要的游戏地牢设计。我已按照链接中提供的教程逐步进行。我提供了我的脚本供您查看：

房间正在完美创建，没有错误消息。我注意到 CreateCorridorBetween 没有被从任何地方调用，即使是在作者的博客上；因此，没有创建走廊。如何在我的代码中调用它？

我正在阅读这个答案

用于 2D 碰撞检测的四叉树的高效（且解释良好）实现

遇到了这一段

好吧，实际上四叉树并不是我最喜欢的数据结构。我倾向于使用网格层次结构，例如世界的粗网格，区域的更精细的网格，以及子区域的更精细的网格（3 个固定级别的密集网格，并且不涉及树），具有行-基于优化，因此其中没有实体的行将被释放并变成空指针，同样完全空的区域或子区域变成空值。虽然这个在一个线程中运行的四叉树的简单实现可以在我的 i7 上以 60+ FPS 处理 10 万个代理，但我已经实现了可以处理在旧硬件（i3）上每帧相互反弹的几百万个代理的网格。此外，我一直很喜欢网格如何让预测它们需要多少内存变得非常容易，因为它们不会细分单元格。

这种类型的网格看起来很直观，听起来有点像“N 阶”网格，其中每个父节点有 N 个子节点，而不是 4 个子节点。N^3 可以比 4^3 走得更远，这可以提高精度，可能（我猜）更少的分支（因为要分支的节点要少得多）。

我有点困惑，因为我会直观地使用单个或 3 个 std::map 和正确的< operator()，以减少其内存占用，但我不确定它会这么快，因为查询 AABB 意味着堆叠几个 O(log n) 的访问。

他所说的那些基于行的优化究竟是什么？这种类型的网格搜索常见吗？

我对az阶曲线有一些了解，对四叉树并不完全满意。

我们是否能够在我们的空间中有一些区域的应用程序中使用 KD-Trees，这些区域中没有点。例如，在二维空间中，在某些矩形区域中我们将无法拥有点，因此在使用分割平面进行切割时要考虑它们。根据 Wikipedia：

kd 树是二叉空间划分树的一种特殊情况。

在二进制空间分区中，有很多应用程序可能会出现这种情况，例如机器人技术中的路径规划，我已经找到了有关这方面的出版物，但没有像 kD 树这样的文章，它是 BSP 的一个特例。

• 甚至可以为此目的使用 kD Trees 实现吗？
• 我们算法的结果是什么？
• 一个修改后的 kd 树数据结构会是什么样子来表示这种情况？

我正在学习数据结构课程，最近了解了kd 树，它通过用超平面划分空间来划分空间。

我想知道是否存在将空间划分为“内部”和“外部”区域的数据结构，其中超球体将节点连接到最近的节点。这允许以更直观的方式找到最接近包含在球形区域内的某个点的节点。

每个节点都需要跟踪它在空间中的位置、插入时到最近节点的半径/距离，以及它的内部和外部子节点。

这自然适用于二叉树状结构，其中每个节点都有一个内部和外部子节点，红黑树（或其他机制）可以保持这种平衡。它优于 kd 树，因为每个链接不必通过正交超平面划分，而是可以以与其他节点相同的方式使用超球面。

我发现这个想法的类似数据结构包括M-trees，但它们与我想象的有一些重大差异，因为通过使用红黑树作为底层结构，没有必要对一个区域的圈数。还有球树和有利位置树，但它们也各不相同。

这是一个（非常粗略的）谷歌幻灯片演示，详细说明了我的一些想法。

这个数据结构叫什么？