什么是粗网格搜索和细网格搜索？

Question

我正在阅读这个答案

用于 2D 碰撞检测的四叉树的高效（并得到很好的解释）实现

并遇到这一段

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

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

我有点困惑，因为我会直觉地使用一个或可能是 3 个 std::map< operator()来减少它的内存占用，但我不确定它会这么快，因为查询 AABB 意味着堆叠几次访问都是 O(log n)。

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

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

Answer 1

这是我自己的报价。但这是基于我在个人经验中遇到的一个常见模式。此外，像“父”和“子”这样的术语是我在谈论网格时基本上会丢弃的术语。你刚刚得到了一个大的二维或 N 维表/矩阵存储的东西。没有真正涉及的层次结构——这些数据结构更像是数组而不是树。

“粗”与“细”

关于“粗略”和“精细”，我的意思是“粗略”搜索查询往往更便宜，但会产生更多误报。较粗的网格将是网格分辨率较低的网格（更少、更大的单元格）。粗略搜索可能涉及遍历/搜索更少和更大的网格单元。例如，假设我们想查看一个元素是否与一个巨大单元格中的点/点相交（想象一下，模拟中只有一个 1x1 网格存储所有内容）。如果点与单元格相交，我们可能会在该单元格中返回大量元素，但可能只有一个或没有一个元素与点相交。

因此，“粗略”查询是广泛而简单的，但在缩小候选人（或“嫌疑人”）名单方面不是很精确。它可能会返回太多结果，并且仍然需要进行大量处理以缩小与搜索参数实际相交的范围*。

就像在那些侦探节目中，当他们在数据库中搜索可能的杀手时，放入“白人男性”可能不需要太多处理来列出结果，但可能会给出太多结果以适当缩小嫌疑人的范围。“好”则相反，可能需要对数据库进行更多处理，但将结果缩小到只有一个嫌疑人。这是一个粗略且有缺陷的类比，但我希望它有所帮助。

通常，在我们讨论内存优化之类的事情之前，广泛优化空间索引的关键是在“粗略”和“精细”之间找到一个很好的平衡，无论我们是在谈论空间哈希还是四叉树。太“好”了，我们可能会花太多时间遍历数据结构（在统一网格中搜索许多小单元格，或者花太多时间在四叉树等自适应网格的树遍历上）。太“粗糙”，空间索引可能会返回太多结果，从而显着减少进一步处理所需的时间。对于空间散列（一种我个人不太喜欢的数据结构，但它们在游戏开发中非常流行），在确定要使用的最佳单元格大小时通常需要进行大量的思考、实验和测量。

使用统一的 NxM 网格，它们的“粗糙”或“精细”（大或小单元格以及高或低网格分辨率）不仅会影响查询的搜索时间，而且如果元素大于观点。如果网格太细，可能需要将单个大中型元素插入到许多微小的单元格中并从许多微小的单元格中移除，使用大量额外的内存和处理。如果它太粗糙，则可能只需要在一个大单元格中插入和删除元素，但代价是数据结构将搜索查询返回的候选数量缩小到最低限度的能力。不小心，变得过于“精细/颗粒状” 在实践中可能会变得非常瓶颈，开发人员可能会发现他的网格结构使用 GB 的 RAM 来实现适度的输入大小。对于像四叉树这样的树变体，如果允许的最大树深度太高，当四叉树的叶节点存储最小的单元格大小（我们甚至可以开始运行浮点如果允许将单元格细分为树中的太小尺寸，则会破坏性能的精度错误）。

使用空间索引加速性能的本质通常是这种平衡行为。例如，我们通常不想将视锥体剔除应用于在计算机图形中渲染的单个多边形，因为这通常不仅与硬件在剪辑阶段已经完成的工作相比是多余的，而且它也太“精细/颗粒化”并且需要太多与仅请求渲染一个或多个多边形所需的时间相比，它本身需要进行大量处理。但是我们可能会通过一些“更粗糙”的东西获得巨大的性能改进，例如将截锥体剔除应用于整个生物或太空船（整个模型/网格），使我们能够避免请求通过一次测试一次渲染多个多边形。所以我经常使用术语，“粗”和“细/颗粒”

统一与自适应网格

您可以将四叉树视为具有分层排列的自适应网格单元格大小的“自适应”网格（当我们在单个智能和自适应数据结构中从根向下钻取时从“粗”到“细”工作），而不是简单的 NxM“统一”网格。

基于树的结构的自适应特性非常智能，可以处理广泛的用例（尽管通常需要对最大树深度和/或允许的最小单元格大小进行一些调整，以及可能在单元格中存储多少最大元素/细分之前的节点）。但是，优化树数据结构可能会更加困难，因为层次结构本身并不容易适用于我们的硬件和内存层次结构非常适合遍历的那种连续内存布局。所以我经常发现不涉及树的数据结构更容易优化，就像优化哈希表可能比优化红黑树更简单一样，尤其是当我们可以预测很多数据类型时我们将提前存储。

在很多情况下，我倾向于更简单、更连续的数据结构的另一个原因是实时模拟的性能要求通常不仅需要快速的帧速率，而且需要一致和可预测的帧速率。一致性很重要，因为即使视频游戏在游戏的大部分时间都具有非常高的帧率，但游戏的某些部分会导致帧率在短时间内大幅下降，玩家也可能会死亡并游戏结束它的结果。在我的案例中，避免这些类型的场景并且数据结构基本上没有病态的最坏情况性能场景通常非常重要。一般来说，我发现更容易预测许多不涉及自适应层次结构的更简单数据结构的性能特征，并且有点“笨”。我经常发现帧速率的一致性和可预测性与我预测数据结构的整体内存使用情况的难易程度和稳定性大致相关。

因此，我经常亲自使用网格找到更好的结果，但是如果在特定模拟上下文中确定用于网格的单个最佳单元格大小很棘手，我只使用它们的多个实例：一个具有较大单元格大小的实例用于“粗糙”搜索（比如 10x10），一个带有较小的用于“更精细”的搜索（比如 100x100），甚至可能带有更小的单元格用于“最好的”搜索（比如 1000x1000）。如果在粗略搜索中没有返回结果，那么我不会继续进行更精细的搜索。我通过这种方式在四叉树和网格的好处之间取得了一些平衡。

我过去使用这些类型的表示时所做的不是在所有三个网格实例中存储单个元素。这将使元素条目/节点在这些结构中的内存使用增加三倍。相反，我所做的是将较细网格的占用单元格的索引插入到较粗网格中，因为通常占用的单元格比模拟中的元素总数少得多。只有具有最小单元尺寸的最精细、最高分辨率的网格才能存储元素。最细网格中的单元类似于四叉树的叶节点。

我在该问题的一个答案中称之为“松紧双网格”是对这种多网格想法的扩展。不同之处在于，更细的网格实际上是松散的，并且单元格大小会根据插入的元素进行扩展和收缩，始终保证单个元素，无论大小，都只需要插入到网格中的一个单元格中. 较粗的网格存储较细网格的占用单元格，导致两个恒定时间查询（一个在较粗的紧密网格中，另一个在较细的松散网格中）以返回与搜索参数匹配的潜在候选者的元素列表。

用于其他目的的多个网格

我有点困惑，因为我会直觉地使用一个或可能是 3 个 std::map 和适当的 operator() 来减少它的内存占用，但我不确定它会这么快，因为查询 AABB将意味着堆叠多个 O(log n) 的访问。

我认为这是我们许多人都有的一种直觉，也可能是潜意识里希望只依靠一个解决方案来解决所有问题，因为编程可能会变得非常乏味和重复，而且只实现一次并重复使用它是理想的选择：“一刀切”T 恤。但是，一件通用的衬衫可能很难剪裁以适合我们非常宽阔而肌肉发达的程序员身体*。因此，有时使用小、中和大尺寸的类比会有所帮助。

• 就我而言，这很可能是一种很糟糕的幽默尝试，目的是让我冗长的文本不那么无聊。

例如，如果您正在使用std::map诸如空间散列之类的东西，那么可能会有很多思考和摆弄试图找到最佳单元格大小。在视频游戏中，人们可能会做出妥协，比如让单元格的大小与游戏中普通人的大小（可能稍微小一点或大一点）有关，因为游戏中的许多模型/精灵可能是为人类设计的用。但它可能会变得非常繁琐，对于微小的事物来说非常次优，对于巨大的事物来说非常次优。在这种情况下，我们可能会很好地抵制我们的直觉和只使用一种解决方案并使用多种解决方案的愿望（对于使用不同参数构造的数据结构，它仍然可以是相同的代码，但只是同一类实例的多个实例）。

至于搜索多个数据结构而不是单个数据结构的开销，这是最好的衡量标准，值得记住的是，每个容器的输入大小将因此更小，从而降低每次搜索的成本，并且很可能提高引用的局部性. 它可能会超过需要对数搜索时间的分层结构的好处，例如std::map（或不是，最好只测量和比较），但我倾向于使用更多的数据结构，它们在恒定时间（网格或哈希表）中执行此操作。就我而言，我发现其好处远远超过了需要多次搜索来执行单个查询的额外成本，尤其是当元素大小变化很大时，或者我想要一些类似于具有 2 个或更多 NxM 网格的层次结构的基本事物，范围从“粗略” “ 罚款”。

基于行的优化

至于“基于行的优化”，这是非常特定于统一固定大小的网格而不是树的。它指的是每行使用一个单独的可变大小的列表/容器，而不是整个网格的单个列表/容器。除了可能减少空行的内存使用量之外，这些空行不需要分配的内存块就变成空行，它还可以节省大量处理并改进内存访问模式。

如果我们为整个网格存储一个列表，那么我们必须在元素四处移动、粒子诞生等时不断地从该共享列表中插入和删除。这可能导致更多的堆分配/释放增加和缩小容器，但是还增加了从该列表中的一个元素到下一个元素的平均内存步幅，这将倾向于转化为更多的缓存未命中，因为更多不相关的数据被加载到缓存行中。此外，如今我们拥有如此多的核心，因此为整个网格使用单个共享容器可能会降低并行处理网格的能力（例如：搜索一行的同时插入另一行）。它还可能导致结构使用更多的净内存，因为如果我们使用像std::vector或ArrayList，这些通常可以存储两倍于将插入时间减少到摊销常数时间所需的元素的内存容量，方法是通过保持多余的容量来最大限度地减少在线性时间内重新分配和复制前一个元素的需要。

通过为每个网格行或每列关联一个单独的中型容器，而不是为整个网格关联一个巨大的容器，我们可以在某些情况下降低这些成本*。

• 这是您之前和之后肯定会测量的类型，以确保它确实提高了整体帧速率，并且可能尝试响应第一次尝试存储整个网格的单个列表，从而揭示分析器中的许多非强制性缓存未命中.

这可能会引出一个问题，即为什么我们不对网格中的每个单元格使用单独的小列表容器。这是一种平衡行为。如果我们存储那么多容器（例如：std::vector1000x1000 网格的一百万个实例，每个实例可能存储很少或没有元素），它将允许最大并行度并最小化从单元格中的一个元素到单元格中的下一个元素的步幅单元，但这在内存使用中可能会非常爆炸，并引入大量额外的处理和堆开销。

特别是在我的情况下，我最好的网格可能存储一百万或更多的单元格，但我每个单元格只需要 4 个字节。在 64 位架构上，每个单元的可变大小序列通常会爆炸到至少 24 字节或更多（通常更多），以存储容器数据（通常是一个指针和几个额外的整数，或三个指针）在堆分配的内存块之上），但最重要的是，插入到空单元格的每个元素都可能需要堆分配和强制缓存未命中和页面错误，并且由于缺乏时间局部性而非常频繁。因此，我发现平衡点和最佳位置是每行一个列表容器，这通常是我衡量过的最佳实现之一。

我使用我所谓的“单向数组列表”将元素存储在网格行中，并允许恒定时间插入和删除，同时仍然允许一定程度的空间局部性，许多元素是连续的。可以这样描述：

struct GridRow
{
     struct Node
     {
         // Element data
         ...

         // Stores the index into the 'nodes' array of the next element
         // in the cell or the next removed element. -1 indicates end of
         // list.
         int next = -1;
     };

     // Stores all the nodes in the row.
     std::vector<Node> nodes;

     // Stores the index of the first removed element or -1
     // if there are no removed elements.
     int free_element = -1;
};

这结合了使用空闲列表分配器的链表的一些好处，但不需要管理单独的分配器和数据结构实现，我发现这对于我的目的来说太通用和笨拙了。此外，这样做允许我们将指针的大小减半到 64 位架构上的 32 位数组索引，我发现在我的用例中，当元素数据的对齐要求相结合时，这是一个很大的胜利使用 32 位索引不需要额外的 32 位填充，class/struct这对我来说很常见，因为我经常使用 32 位或更小的整数和 32 位单精度浮点或 16 位半浮标。

非正统？

关于这个问题：

这种类型的网格搜索常见吗？

我不确定！我倾向于在术语上有点挣扎，我不得不在交流中请求人们的原谅和耐心。在 1980 年代互联网普及之前，我从孩提时代就开始编程，因此我开始依赖于发明许多自己的技术并使用自己的粗略术语。大约 15 年后，当我 20 多岁时，我获得了计算机科学学位并纠正了我的一些术语和误解，但多年来我一直在推出自己的解决方案。所以我经常不确定其他人是否遇到过一些相同的解决方案，以及他们是否有正式的名称和术语。

这使得与其他程序员的交流变得困难，有时让我们双方都感到非常沮丧，我不得不要求很多耐心来解释我的想法。我在会议上养成了一个习惯，总是从展示一些非常有希望的结果开始，这往往会让人们对我粗暴而冗长的工作方式解释更加耐心。如果我从展示结果开始，他们往往会给我的想法更多的机会，但我经常对这个行业中普遍存在的正统和教条主义感到非常沮丧，这些教条有时会优先考虑概念而不是执行和实际结果. 我本质上是一个实用主义者，所以我不会考虑“什么是最好的数据结构？” 我认为，考虑到我们的优势和劣势，我们可以有效地个人实施什么，以及对我们来说直觉和反直觉的东西，我愿意在概念的纯度上无休止地妥协，以支持更简单、问题更少的执行。我只是喜欢好的、可靠的解决方案，无论它们多么正统或非正统，都能自然而然地从我们的指尖滚滚而来，但我的很多方法可能因此是非正统的（或者不是，我可能只是还没有找到做过的人）一样的东西）。我发现这个网站在极少数情况下非常有用，可以找到像“哦，我也这样做过！如果我们这样做的话，我发现了最好的结果 [...]”或有人指出，“什么你提议的名字叫[...]。” 我愿意在概念的纯度上不断妥协，以支持更简单、问题更少的执行。我只是喜欢好的、可靠的解决方案，无论它们多么正统或非正统，都能自然而然地从我们的指尖滚滚而来，但我的很多方法可能因此是非正统的（或者不是，我可能只是还没有找到做过的人）一样的东西）。我发现这个网站在极少数情况下非常有用，可以找到像“哦，我也这样做过！如果我们这样做的话，我发现了最好的结果 [...]”或有人指出，“什么你提议的名字叫[...]。” 我愿意在概念的纯度上不断妥协，以支持更简单、问题更少的执行。我只是喜欢好的、可靠的解决方案，无论它们多么正统或非正统，都能自然而然地从我们的指尖滚滚而来，但我的很多方法可能因此是非正统的（或者不是，我可能只是还没有找到做过的人）一样的东西）。我发现这个网站在极少数情况下非常有用，可以找到像“哦，我也这样做过！如果我们这样做的话，我发现了最好的结果 [...]”或有人指出，“什么你提议的名字叫[...]。” 但结果我的很多方法可能是非正统的（或者不是，我可能还没有找到做过同样事情的人）。我发现这个网站在极少数情况下非常有用，可以找到像“哦，我也这样做过！如果我们这样做的话，我发现了最好的结果 [...]”或有人指出，“什么你提议的名字叫[...]。” 但结果我的很多方法可能是非正统的（或者不是，我可能还没有找到做过同样事情的人）。我发现这个网站在极少数情况下非常有用，可以找到像“哦，我也这样做过！如果我们这样做的话，我发现了最好的结果 [...]”或有人指出，“什么你提议的名字叫[...]。”

在性能关键的上下文中，我有点让分析器为我提出数据结构，粗略地说。也就是说，我会想出一些快速的初稿（通常非常正统）并使用分析器对其进行测量，然后让分析器的结果为我提供有关第二稿的想法，直到我收敛到既简单又高效且具有适当可扩展性的东西对于要求（在此过程中可能会变得非常非正统）。我很高兴放弃很多想法，因为我认为我们必须在淘汰过程中剔除很多不好的想法才能提出一个好的想法，所以我倾向于循环通过大量的实现和想法，然后成为一个真正快速的原型制作者（我有一种心理倾向，顽固地爱上我花了很多时间的解决方案，所以为了反驳我'

您可以在该问题的答案中看到我的确切方法论，我在几天的时间里通过大量分析和测量迭代收敛，并从相当正统的四叉树到非正统的“松紧双网格”解决方案进行原型设计它以最稳定的帧速率处理最多数量的代理，而且对我来说，比之前的所有结构更快、更容易实现。我不得不通过许多正统的解决方案并对其进行测量，以便为不寻常的松紧变体产生最终的想法。我总是从并支持正统的解决方案开始，然后从盒子里开始，因为它们有据可查和理解，并且非常温和和胆怯地冒险到外面，但是当要求足够高时，我确实经常发现自己有点跳出框框。我对最苛刻的要求并不陌生，因为在我的行业中，作为一个在引擎上工作的相当低级的类型，以良好的帧速率处理更多数据的能力通常不仅转化为用户的更大交互性，而且还允许艺术家创建比以往任何时候都具有更高视觉质量的更详细的内容。我们总是在良好的帧速率下追求越来越高的视觉质量，这通常归结为性能和尽可能避免粗略近似的结合。这不可避免地导致某种程度的非正统性，许多内部解决方案对于特定引擎非常独特，

例如，我有一个从小就在使用的数据结构，但我不知道它的名字。这是一个简单的概念，它只是一个分层的位集，它允许在简单工作的几次迭代中找到可能数百万个元素的集合交集，以及只需几次迭代（小于仅通过数据结构本身遍历集合中的所有内容的线性时间要求，该数据结构返回占用元素/集合位的范围，而不是单个元素/位索引）。但是我不知道它的名字是什么，因为它只是我滚动的东西，而且我从未在计算机科学中遇到过任何人谈论它。我倾向于将其称为“分层位集”。最初我称它为“ 没有找到使用或谈论过的人。它只是扩展了常规扁平位集的优势，可以快速找到按位 OR 的集合交集，并使用 FFZ/FFS 快速遍历所有集合位，但将两者的线性时间要求降低到对数（以对数为基数）远大于2）。没有找到使用或谈论过的人。它只是扩展了常规扁平位集的优势，可以快速找到按位 OR 的集合交集，并使用 FFZ/FFS 快速遍历所有集合位，但将两者的线性时间要求降低到对数（以对数为基数）远大于2）。

无论如何，如果这些解决方案中的一些非常非正统，我不会感到惊讶，但如果它们相当正统，我也不会感到惊讶，我只是未能找到这些技术的正确名称和术语。像这样的网站对我来说的很多吸引力是孤独地搜索使用类似技术的其他人，并试图为他们找到合适的名称和术语，但往往以沮丧告终。我也希望提高我解释它们的能力，尽管我在这里总是那么糟糕和啰嗦。我发现使用图片对我有很大帮助，因为我发现人类语言充满了歧义。我也喜欢故意不精确的比喻语言，它包含和庆祝隐喻、类比和幽默夸张等歧义，但我没有找到它' 由于缺乏精确性，程序员往往非常欣赏这种类型的东西。但我从来没有发现精确度如此重要，只要我们能够传达一个想法的内容和“酷”的地方，同时他们可以对其余部分做出自己的解释。对整个解释表示歉意，但希望能澄清一些关于我粗略的术语和我用来得出这些技术的整体方法的问题。英语也不是我的第一语言，因此增加了另一层卷积，我必须将我的想法翻译成英语单词并为此苦苦挣扎。关于一个想法，而他们可以对其余的做出自己的解释。对整个解释表示歉意，但希望能澄清一些关于我粗略的术语和我用来得出这些技术的整体方法的问题。英语也不是我的第一语言，因此增加了另一层卷积，我必须将我的想法翻译成英语单词并为此苦苦挣扎。关于一个想法，而他们可以对其余的做出自己的解释。对整个解释表示歉意，但希望能澄清一些关于我粗略的术语和我用来得出这些技术的整体方法的问题。英语也不是我的第一语言，因此增加了另一层卷积，我必须将我的想法翻译成英语单词并为此苦苦挣扎。