什么是粗格和细格搜索？
What is a coarse and fine grid search?
我正在阅读这个答案
又遇到了这段
All right, so actually quadtrees are not my favorite data structure for this purpose. I tend to prefer a grid hierarchy, like a coarse grid for the world, a finer grid for a region, and an even finer grid for a sub-region (3 fixed levels of dense grids, and no trees involved), with row-based optimizations so that a row that has no entities in it will be deallocated and turned into a null pointer, and likewise completely empty regions or sub-regions turned into nulls. While this simple implementation of the quadtree running in one thread can handle 100k agents on my i7 at 60+ FPS, I've implemented grids that can handle a couple million agents bouncing off each other every frame on older hardware (an i3). Also I always liked how grids made it very easy to predict how much memory they'll require, since they don't subdivide cells. But I'll try to cover how to implement a reasonably efficient quadtree.
这种类型的网格看起来很直观，听起来有点像 "N-order" 网格，其中每个父节点有 N 个子节点，而不是 4 个子节点。 N^3 可以比 4^3 走得更远，这允许更好的精度，可能（我猜）更少的分支（因为要分支的节点要少得多）。
我有点困惑，因为我会凭直觉使用一个，或者可能是 3 个 std::map 和适当的 < operator()，来减少它的内存占用，但我不确定它是否会如此之快，因为查询 AABB 意味着堆叠多个 O(log n) 的访问。
他所说的那些基于行的优化到底是什么？这种网格搜索常见吗？
我对z阶曲线有一些了解，我对四叉树不是很满意。
这是我自己的名言。但这是基于我在个人经历中遇到的一种常见模式。此外，像 "parent" 和 "child" 这样的术语是我在谈论网格时主要丢弃的术语。你刚刚得到了一个大的二维或 N-dimensional table/matrix 存储东西。根本不涉及任何层次结构——这些数据结构更像是数组而不是树。
"Coarse" 和 "Fine"
在 "coarse" 和 "fine" 上，我的意思是 "coarse" 搜索查询往往更便宜，但会产生更多误报。较粗的网格是网格分辨率较低的网格（更少、更大的单元格）。粗略搜索可能涉及 traversing/searching 更少和更大的网格单元。例如，假设我们想查看一个元素是否与一个巨大单元格中的 point/dot 相交（想象一下只有一个 1x1 网格存储模拟中的所有内容）。如果点与单元格相交，我们可能会在该单元格中得到大量元素 return，但实际上可能只有一个或 none 元素与点相交。
因此，"coarse" 查询广泛而简单，但在缩小候选列表（或 "suspects"）方面不是很精确。它可能 return 结果太多，但仍然需要进行大量处理以缩小实际与搜索参数相交的范围*。
It's like in those detective shows when they search a database for a
possible killer, putting in "white male" might not require much
processing to list the results but might give way too many results to
properly narrow down the suspects. "Fine" would be the opposite and might require more processing of the database but narrow down the result to just one suspect.
This is a crude and flawed analogy but I hope it helps.
通常，在我们讨论内存优化之类的事情之前，广泛优化空间索引的关键是在 "coarse" 和 "fine" 之间找到一个很好的平衡。太 "fine" 并且我们可能会花费太多时间遍历数据结构（在统一网格中搜索许多小单元，或者在四叉树等自适应网格的树遍历中花费太多时间）。太多 "coarse" 并且空间索引可能会返回太多结果，无法显着减少进一步处理所需的时间。对于空间哈希（一种我个人不太喜欢的数据结构，但它们在 gamedev 中非常流行），通常需要大量的思考、实验和测量来确定要使用的最佳单元格大小。
对于统一的 NxM 网格，"coarse" 或 "fine" 它们的大小（大或小单元格以及高或低网格分辨率）不仅会影响查询的搜索时间，还会影响插入和如果元素大于一个点，则移除时间。如果网格太细，单个大元素或 medium-sized 元素可能必须插入到许多小单元格中并从许多小单元格中删除，使用大量额外的内存和处理。如果它太粗略，元素可能只需要插入和删除 to/from 一个大单元格，但数据结构的代价是缩小候选者数量的能力 returned 从搜索查询到最低限度。如果不小心，太 "fine/granular" 可能会在实践中成为非常大的瓶颈，并且开发人员可能会发现他的网格结构使用千兆字节的 RAM 来获得适度的输入大小。对于像四叉树这样的树变体，如果允许的最大树深度太高，当四叉树的叶节点存储最小的单元格大小时，导致爆炸性内存使用和处理的值会发生类似的事情（我们甚至可以开始 运行进入 floating-point 精度错误，如果允许将单元格细分为树中太小的大小，则会破坏性能。
通过空间索引加速性能的本质通常是这种平衡行为。例如，我们通常不想将截锥体剔除应用于在计算机图形中渲染的单个多边形，因为这通常不仅与硬件在裁剪阶段已经完成的工作是多余的，而且它也 "fine/granular" 并且需要太多与仅请求渲染一个或多个多边形所需的时间相比，它本身有很多处理。但是我们可能会通过一些 "coarser" 的东西来获得巨大的性能改进，比如对整个生物或 space 船（整个 model/mesh）应用截锥体剔除，从而避免请求渲染许多一次测试一次多边形。所以我经常在这类讨论中经常使用 "coarse" 和 "fine/granular" 这两个术语（直到我找到更好的术语让更多人可以轻松理解）。
统一与自适应网格
您可以将四叉树想象成一个 "adaptive" 网格，其中自适应网格单元大小按层次排列（从“粗略”到 "fine"，因为我们在单个智能中从根向下钻取到叶和自适应数据结构）而不是简单的 NxM "uniform" 网格。
tree-based 结构的自适应特性非常智能，可以处理广泛的用例（尽管通常需要调整最大树深度 and/or 允许的最小单元格大小以及可能如何处理许多最大元素在细分之前存储在 cell/node 中）。然而，优化树数据结构可能会更加困难，因为层次结构的性质不太适合那种连续的内存布局r 硬件和内存层次结构是如此 well-suited 遍历。所以我经常发现不涉及树的数据结构更容易优化，就像优化散列 table 可能比优化 red-black 树更简单一样，尤其是当我们可以预期很多关于我们要提前存储的数据类型。
Another reason I tend to favor simpler, more contiguous data structures in lots of contexts is that the performance requirements of a realtime simulation often want not just fast frame rates, but consistent and predictable frame rates. The consistency is important because even if a video game has very high frame rates for most of the game but some part of the game causes the frame rates to drop substantially for even a brief period of time, the player may die and game over as a result of it. It was often very important in my case to avoid these types of scenarios and have data structures largely absent pathological worst-case performance scenarios. In general, I find it easier to predict the performance characteristics of lots of simpler data structures that don't involve an adaptive hierarchy and are kind of on the "dumber" side. Very often I find the consistency and predictability of frame rates to be roughly tied to how easily I can predict the data structure's overall memory usage and how stable that is. If the memory usage is wildly unpredictable and sporadic, I often (not always, but often) find the frame rates will likewise be sporadic.
所以我个人经常使用网格找到更好的结果，但如果在特定模拟上下文中确定用于网格的单个最佳单元大小很棘手，我只使用它们的多个实例：一个具有较大单元的实例"coarse" 搜索的大小（例如 10x10），"finer" 搜索的大小更小（例如 100x100），甚至 "finest" 搜索的单元可能更小（例如 1000x1000）。如果在粗略搜索中没有结果 return，那么我不会继续进行更精细的搜索。这样我就平衡了四叉树和网格的好处。
我过去使用这些类型的表示时所做的是不在所有三个网格实例中存储单个元素。这将使这些结构中元素 entry/node 的内存使用量增加三倍。相反，我所做的是将更精细网格的占用单元格的索引插入到更粗糙的网格中，因为占用单元格通常比模拟中的元素总数少得多。只有具有最小单元格大小的最好的 highest-resolution 网格才能存储该元素。最细网格中的单元格类似于四叉树的叶节点。
"loose-tight double grid" 正如我在该问题的一个答案中所说的那样，它是对 multi-grid 想法的扩展。不同之处在于，更精细的网格实际上是松散的，并且单元格大小会根据插入的元素进行扩展和收缩，始终保证单个元素，无论大小，只需要插入到网格中的一个单元格中.较粗的网格存储较细网格的占用单元格，导致两个 constant-time 查询（一个在较粗的紧密网格中，另一个在较细的松散网格中）到 return 与搜索匹配的潜在候选元素列表范围。它还具有最多的 stable 和 predictable 内存使用（不一定是最少的内存使用，因为 fine/loose 单元需要存储一个 axis-aligned 边界框 expands/shrinks 将另外 16 个字节左右添加到一个单元格）和相应的 stable 帧速率，因为一个元素总是插入到一个单元格中，并且除了它自己的元素数据之外不需要任何额外的内存来存储它例外情况是当它的插入导致松散的单元格扩展到必须将其插入到较粗网格中的其他单元格时（这应该是一个相当 rare-case 的场景）。
用于其他目的的多个网格
I'm a little puzzled because I would intuitively use a single, or maybe 3 std::map with the proper operator(), to reduce its memory footprint, but I'm not sure it would be so fast, since querying an AABB would mean stacking several accesses that are O(log n).
我认为这是我们许多人的直觉，也可能是一种潜意识的愿望，即只依靠一个解决方案来解决所有问题，因为编程可能会变得非常乏味和重复，最好只实现一次并重用它对于一切：一个 "one-size-fits-all" t-shirt。但是一件 one-sized-fits-all 衬衫可能剪裁得不好，无法适应我们非常宽大而肌肉发达的程序员身体*。因此，有时使用小号、中号和大号的类比会有所帮助。
- This is a very possibly poor attempt at humor on my part to make my long-winded texts less boring to read.
例如，如果您将 std::map 用于空间散列之类的东西，那么可能需要进行大量思考和摆弄才能找到最佳像元大小。在视频游戏中，人们可能会做出妥协，例如让单元格大小相对于游戏中普通人的大小（可能更小或更大），因为游戏中的许多 models/sprites 可能是设计好的供人类使用。但它可能会变得非常繁琐，对于小东西来说非常 sub-optimal 而对于巨大的东西来说非常 sub-optimal 。在那种情况下，我们可能会很好地抵制我们的直觉和愿望，只使用一个解决方案并使用多个解决方案（它仍然可以是相同的代码，但只是相同 class 实例的多个实例，用于构造不同的数据结构参数）。
至于搜索多个数据结构而不是单个数据结构的开销，这是最好衡量的东西，值得记住的是每个容器的输入大小因此会更小，从而减少每次搜索的成本并且非常可能会改善参考地点。它可能超过需要像 std::map 这样的对数搜索时间的层次结构的好处（或者不需要，最好只是测量和比较），但我倾向于使用更多的数据结构在 constant-time 中执行此操作（网格或散列 tables）。在我的案例中，我发现好处远远超过要求多次搜索来执行单个查询的额外成本，尤其是当元素大小发生根本变化时，或者我想要一些类似于具有 2 个或更多 NxM 网格的层次结构的基本事物，范围从 "coarse" 到 "fine".
Row-Based 优化
至于"row-based optimizations"，那非常特定于统一 fixed-sized 网格而不是树。它指的是每行使用单独的 variable-sized list/container 而不是对整个网格使用一个单独的行。除了可能减少空行的内存使用而无需分配内存块，它还可以节省大量处理并改进内存访问模式。
如果我们为整个网格存储一个列表，那么当元素移动、粒子诞生等时，我们必须不断地从该共享列表中插入和删除。这可能会导致更多堆 allocations/deallocations 增加和缩小容器，但也增加了从该列表中的一个元素到下一个元素的平均内存步幅，由于更多不相关的数据被加载到缓存行中，这往往会转化为更多的缓存未命中。此外，如今我们拥有如此多的核心，因此为整个网格使用一个共享容器可能会降低并行处理网格的能力（例如：搜索一行，同时插入另一行）。它还会导致结构使用更多的净内存，因为如果我们使用像 std::vector 或 ArrayList 这样的连续序列，它们通常可以存储两倍于减少所需元素的内存容量通过保持过剩容量，最大限度地减少重新分配和复制 linear-time 中以前的元素的需要，将插入时间摊销为固定时间。
通过为每个网格行或每列关联一个单独的 medium-sized 容器，而不是为整个网格关联一个巨大的容器，我们可以在某些情况下减轻这些成本*。
- This is the type of thing you definitely measure before and after though to make sure it actually improves overall frame rates, and probably attempt in response to a first attempt storing a single list for the entire grid revealing many non-compulsory cache misses in the profiler.
这可能会引出一个问题，即为什么我们不为网格中的每个单元格使用单独的小型列表容器。这是一种平衡行为。如果我们存储那么多容器（例如：1000x1000 网格的 std::vector 的一百万个实例可能每个存储很少或没有元素），它将允许最大并行度并最小化从单元格中的一个元素到单元中的下一个，但这在内存使用方面可能会非常爆炸，并引入大量额外的处理和堆开销。
特别是在我的例子中，我最好的网格可能存储一百万个或更多的单元格，但我每个单元格只需要 4 个字节。在 64 位架构上，每个单元格的 variable-sized 序列通常会爆炸到每个单元格至少 24 个字节或更多（通常更多）以存储容器数据（通常是一个指针和几个额外的整数，或者heap-allocated 内存块顶部的三个指针），但最重要的是，插入空单元格的每个元素都可能需要堆分配和强制缓存未命中和页面错误，并且由于缺乏时间性而非常频繁地点。因此，我发现在我的 best-measured 实现中，平衡点和最佳点通常是每行一个列表容器。
我使用所谓的 "singly-linked array list" 将元素存储在网格行中并允许 constant-time 插入和删除，同时仍然允许一定程度的空间局部性，其中许多元素是连续的。可以这样描述：
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 位 single-precision floating-point 或 16 位 half-floats.
非正统？
关于这个问题：
Is this type of grid search common?
我不确定！我倾向于用术语来解决一些问题，我将不得不请求人们的原谅和沟通的耐心。我在互联网普及之前的 1980 年代幼儿时期就开始编程，因此我开始依赖于发明很多自己的技术并使用自己的粗糙术语。大约 15 年后，我 20 多岁时获得了计算机科学学位，并纠正了我的一些术语和误解，但多年来我一直在推出自己的解决方案。所以我经常不确定其他人是否遇到过一些相同的解决方案，以及它们是否有正式的名称和术语。
这使得与其他程序员的交流变得困难，有时对我们俩来说都非常令人沮丧，我不得不要求很大的耐心来解释我的想法。我已经养成了在会议上总是开始展示一些非常有希望的结果的习惯，这往往会让人们对我对他们工作方式的粗略和 long-winded 解释更有耐心。如果我从展示结果开始，他们往往会给我的想法更多的机会，但我通常对这个行业中普遍存在的正统观念和教条主义感到非常沮丧，这些观念有时会比执行和实际结果更优先考虑概念。我本质上是一个实用主义者，所以我不考虑 "what is the best data structure?" 我认为考虑到我们的优势和劣势，我们可以有效地个人实施什么，什么是直觉和 counter-intuitive 对我们和我愿意在概念的纯度上无休止地妥协，以支持更简单、问题更少的执行。我只是喜欢好的、可靠的解决方案，无论它们是多么正统或非正统，它们都能自然地从我们的指尖滚动，但我的很多方法结果可能是非正统的（或者不是，我可能还没有找到做过的人一样的东西）。我发现这个网站在极少数情况下很有用，可以找到像 "Oh, I've done that too! I found the best results if we do this [...]" 或有人指出像 "What you are proposing is called [...]."
的同龄人
在 performance-critical 上下文中，粗略地说，我有点让探查器为我提出数据结构。也就是说，我会想出一些快速的初稿（通常是非常正统的）并使用分析器对其进行测量，然后让分析器的结果为我提供第二稿的想法，直到我收敛到既简单又高效且可适当扩展的东西对于要求（一路上可能会变得非常不正统）。我很高兴放弃很多想法，因为我认为我们必须在淘汰过程中剔除很多不好的想法才能提出一个好的想法，所以我倾向于循环大量的实现和想法，并且已经来了成为一个真正快速的原型制作者（我有一种心理倾向，顽固地爱上我花了很多时间的解决方案，所以为了反击，我学会了在解决方案上花费绝对最少的时间，直到它非常非常有前途） .
You can see my exact methodology at work in the very answers to that
question where I iteratively converged through lots of profiling and
measuring over the course of a few days and prototyping from a fairly orthodox quadtree to that
unorthodox "loose-tight double grid" solution that handled the largest
number of agents at the most stable frame rates and was, for me
anyway, much faster and simpler to implement than all the structures
before it. I had to go through lots of orthodox solutions and measure them though to generate the final idea for the unusual loose-tight variant. I always start off with and favor the orthodox solutions and start off inside the box because they're well-documented and understood and just very gently and timidly venture outside, but I do often find myself a bit outside the box when the requirements are steep enough. I'm no stranger to the steepest requirements since in my industry and as a fairly low-level type working on engines, the ability to handle more data at good frame rates often translates not only to greater interactivity for the user but also allows artists to create more detailed content of higher visual quality than ever before. We're always chasing higher and higher visual quality at good frame rates, and that often boils down to a combination of both performance and getting away with crude approximations whenever possible. This inevitably leads to some degree of unorthodoxy with lots of in-house solutions very unique to a particular engine, and each engine tends to have its own very unique strengths and weaknesses as you find comparing something like CryEngine to Unreal Engine to Frostbite to Unity.
比如我有这个从小就用的数据结构，不知道叫什么名字。这是一个简单的概念，它只是一个分层位集，它允许在简单工作的尽可能少的几次迭代中找到潜在的数百万个元素的集合交集，并且只需几次迭代（少于linear-time 要求仅通过数据结构本身遍历集合中的所有内容，returns 范围占用 elements/set 位而不是单个 elements/bit 索引）。但我不知道这个名字是什么，因为它只是我推出的东西，而且我从未遇到过任何人在计算机科学中谈论它。我倾向于将其称为 "hierarchical bitset"。最初我称它为 "sparse bitset tree" 但这似乎有点冗长。这根本不是一个特别聪明的概念，我不会感到惊讶或失望（实际上很高兴）发现其他人在我之前发现了相同的解决方案，但我发现人们从未使用或谈论过一个。它只是扩展了规则的平面位集的优势，通过按位或快速找到集合交集，并使用 FFZ/FFS 快速遍历所有集合位，但将两者的 linear-time 要求降低到对数（对数base 是一个比 2) 大得多的数字。
无论如何，如果其中一些解决方案非常不正统，我不会感到惊讶，但如果它们相当正统，我也不会感到惊讶，我只是没能找到这些技术的正确名称和术语.对我来说，此类网站的很多吸引力在于孤独地寻找其他使用过类似技术的人，并试图为他们找到合适的名称和术语，但往往以失败告终。我也希望提高我解释它们的能力，尽管我一直很糟糕并且long-winded在这里。我发现使用图片对我有很大帮助，因为我发现人类语言充满了歧义。我也喜欢故意不精确的比喻语言，它包含并庆祝隐喻和类比以及幽默夸张等歧义，但我没有发现它是程序员由于缺乏精确性而倾向于欣赏的类型。但我从来没有发现精确度有那么重要，只要我们可以传达内容丰富的内容以及关于一个想法的 "cool" 是什么，同时他们可以对其余部分做出自己的解释。对整个解释表示歉意，但希望这能澄清一些关于我的粗略术语和我用来获得这些技术的整体方法的一些事情。英语也不是我的第一语言，所以增加了另一层卷积，我必须将我的想法翻译成英语单词并为此付出很多努力。
我正在阅读这个答案
又遇到了这段
All right, so actually quadtrees are not my favorite data structure for this purpose. I tend to prefer a grid hierarchy, like a coarse grid for the world, a finer grid for a region, and an even finer grid for a sub-region (3 fixed levels of dense grids, and no trees involved), with row-based optimizations so that a row that has no entities in it will be deallocated and turned into a null pointer, and likewise completely empty regions or sub-regions turned into nulls. While this simple implementation of the quadtree running in one thread can handle 100k agents on my i7 at 60+ FPS, I've implemented grids that can handle a couple million agents bouncing off each other every frame on older hardware (an i3). Also I always liked how grids made it very easy to predict how much memory they'll require, since they don't subdivide cells. But I'll try to cover how to implement a reasonably efficient quadtree.
这种类型的网格看起来很直观，听起来有点像 "N-order" 网格，其中每个父节点有 N 个子节点，而不是 4 个子节点。 N^3 可以比 4^3 走得更远，这允许更好的精度，可能（我猜）更少的分支（因为要分支的节点要少得多）。
我有点困惑，因为我会凭直觉使用一个，或者可能是 3 个 std::map 和适当的 < operator()，来减少它的内存占用，但我不确定它是否会如此之快，因为查询 AABB 意味着堆叠多个 O(log n) 的访问。
他所说的那些基于行的优化到底是什么？这种网格搜索常见吗？
我对z阶曲线有一些了解，我对四叉树不是很满意。
这是我自己的名言。但这是基于我在个人经历中遇到的一种常见模式。此外，像 "parent" 和 "child" 这样的术语是我在谈论网格时主要丢弃的术语。你刚刚得到了一个大的二维或 N-dimensional table/matrix 存储东西。根本不涉及任何层次结构——这些数据结构更像是数组而不是树。
"Coarse" 和 "Fine"
在 "coarse" 和 "fine" 上，我的意思是 "coarse" 搜索查询往往更便宜，但会产生更多误报。较粗的网格是网格分辨率较低的网格（更少、更大的单元格）。粗略搜索可能涉及 traversing/searching 更少和更大的网格单元。例如，假设我们想查看一个元素是否与一个巨大单元格中的 point/dot 相交（想象一下只有一个 1x1 网格存储模拟中的所有内容）。如果点与单元格相交，我们可能会在该单元格中得到大量元素 return，但实际上可能只有一个或 none 元素与点相交。
因此，"coarse" 查询广泛而简单，但在缩小候选列表（或 "suspects"）方面不是很精确。它可能 return 结果太多，但仍然需要进行大量处理以缩小实际与搜索参数相交的范围*。
It's like in those detective shows when they search a database for a possible killer, putting in "white male" might not require much processing to list the results but might give way too many results to properly narrow down the suspects. "Fine" would be the opposite and might require more processing of the database but narrow down the result to just one suspect. This is a crude and flawed analogy but I hope it helps.
通常，在我们讨论内存优化之类的事情之前，广泛优化空间索引的关键是在 "coarse" 和 "fine" 之间找到一个很好的平衡。太 "fine" 并且我们可能会花费太多时间遍历数据结构（在统一网格中搜索许多小单元，或者在四叉树等自适应网格的树遍历中花费太多时间）。太多 "coarse" 并且空间索引可能会返回太多结果，无法显着减少进一步处理所需的时间。对于空间哈希（一种我个人不太喜欢的数据结构，但它们在 gamedev 中非常流行），通常需要大量的思考、实验和测量来确定要使用的最佳单元格大小。
对于统一的 NxM 网格，"coarse" 或 "fine" 它们的大小（大或小单元格以及高或低网格分辨率）不仅会影响查询的搜索时间，还会影响插入和如果元素大于一个点，则移除时间。如果网格太细，单个大元素或 medium-sized 元素可能必须插入到许多小单元格中并从许多小单元格中删除，使用大量额外的内存和处理。如果它太粗略，元素可能只需要插入和删除 to/from 一个大单元格，但数据结构的代价是缩小候选者数量的能力 returned 从搜索查询到最低限度。如果不小心，太 "fine/granular" 可能会在实践中成为非常大的瓶颈，并且开发人员可能会发现他的网格结构使用千兆字节的 RAM 来获得适度的输入大小。对于像四叉树这样的树变体，如果允许的最大树深度太高，当四叉树的叶节点存储最小的单元格大小时，导致爆炸性内存使用和处理的值会发生类似的事情（我们甚至可以开始 运行进入 floating-point 精度错误，如果允许将单元格细分为树中太小的大小，则会破坏性能。
通过空间索引加速性能的本质通常是这种平衡行为。例如，我们通常不想将截锥体剔除应用于在计算机图形中渲染的单个多边形，因为这通常不仅与硬件在裁剪阶段已经完成的工作是多余的，而且它也 "fine/granular" 并且需要太多与仅请求渲染一个或多个多边形所需的时间相比，它本身有很多处理。但是我们可能会通过一些 "coarser" 的东西来获得巨大的性能改进，比如对整个生物或 space 船（整个 model/mesh）应用截锥体剔除，从而避免请求渲染许多一次测试一次多边形。所以我经常在这类讨论中经常使用 "coarse" 和 "fine/granular" 这两个术语（直到我找到更好的术语让更多人可以轻松理解）。
统一与自适应网格
您可以将四叉树想象成一个 "adaptive" 网格，其中自适应网格单元大小按层次排列（从“粗略”到 "fine"，因为我们在单个智能中从根向下钻取到叶和自适应数据结构）而不是简单的 NxM "uniform" 网格。
tree-based 结构的自适应特性非常智能，可以处理广泛的用例（尽管通常需要调整最大树深度 and/or 允许的最小单元格大小以及可能如何处理许多最大元素在细分之前存储在 cell/node 中）。然而，优化树数据结构可能会更加困难，因为层次结构的性质不太适合那种连续的内存布局r 硬件和内存层次结构是如此 well-suited 遍历。所以我经常发现不涉及树的数据结构更容易优化，就像优化散列 table 可能比优化 red-black 树更简单一样，尤其是当我们可以预期很多关于我们要提前存储的数据类型。
Another reason I tend to favor simpler, more contiguous data structures in lots of contexts is that the performance requirements of a realtime simulation often want not just fast frame rates, but consistent and predictable frame rates. The consistency is important because even if a video game has very high frame rates for most of the game but some part of the game causes the frame rates to drop substantially for even a brief period of time, the player may die and game over as a result of it. It was often very important in my case to avoid these types of scenarios and have data structures largely absent pathological worst-case performance scenarios. In general, I find it easier to predict the performance characteristics of lots of simpler data structures that don't involve an adaptive hierarchy and are kind of on the "dumber" side. Very often I find the consistency and predictability of frame rates to be roughly tied to how easily I can predict the data structure's overall memory usage and how stable that is. If the memory usage is wildly unpredictable and sporadic, I often (not always, but often) find the frame rates will likewise be sporadic.
所以我个人经常使用网格找到更好的结果，但如果在特定模拟上下文中确定用于网格的单个最佳单元大小很棘手，我只使用它们的多个实例：一个具有较大单元的实例"coarse" 搜索的大小（例如 10x10），"finer" 搜索的大小更小（例如 100x100），甚至 "finest" 搜索的单元可能更小（例如 1000x1000）。如果在粗略搜索中没有结果 return，那么我不会继续进行更精细的搜索。这样我就平衡了四叉树和网格的好处。
我过去使用这些类型的表示时所做的是不在所有三个网格实例中存储单个元素。这将使这些结构中元素 entry/node 的内存使用量增加三倍。相反，我所做的是将更精细网格的占用单元格的索引插入到更粗糙的网格中，因为占用单元格通常比模拟中的元素总数少得多。只有具有最小单元格大小的最好的 highest-resolution 网格才能存储该元素。最细网格中的单元格类似于四叉树的叶节点。
"loose-tight double grid" 正如我在该问题的一个答案中所说的那样，它是对 multi-grid 想法的扩展。不同之处在于，更精细的网格实际上是松散的，并且单元格大小会根据插入的元素进行扩展和收缩，始终保证单个元素，无论大小，只需要插入到网格中的一个单元格中.较粗的网格存储较细网格的占用单元格，导致两个 constant-time 查询（一个在较粗的紧密网格中，另一个在较细的松散网格中）到 return 与搜索匹配的潜在候选元素列表范围。它还具有最多的 stable 和 predictable 内存使用（不一定是最少的内存使用，因为 fine/loose 单元需要存储一个 axis-aligned 边界框 expands/shrinks 将另外 16 个字节左右添加到一个单元格）和相应的 stable 帧速率，因为一个元素总是插入到一个单元格中，并且除了它自己的元素数据之外不需要任何额外的内存来存储它例外情况是当它的插入导致松散的单元格扩展到必须将其插入到较粗网格中的其他单元格时（这应该是一个相当 rare-case 的场景）。
用于其他目的的多个网格
I'm a little puzzled because I would intuitively use a single, or maybe 3 std::map with the proper operator(), to reduce its memory footprint, but I'm not sure it would be so fast, since querying an AABB would mean stacking several accesses that are O(log n).
我认为这是我们许多人的直觉，也可能是一种潜意识的愿望，即只依靠一个解决方案来解决所有问题，因为编程可能会变得非常乏味和重复，最好只实现一次并重用它对于一切：一个 "one-size-fits-all" t-shirt。但是一件 one-sized-fits-all 衬衫可能剪裁得不好，无法适应我们非常宽大而肌肉发达的程序员身体*。因此，有时使用小号、中号和大号的类比会有所帮助。
- This is a very possibly poor attempt at humor on my part to make my long-winded texts less boring to read.
例如，如果您将 std::map 用于空间散列之类的东西，那么可能需要进行大量思考和摆弄才能找到最佳像元大小。在视频游戏中，人们可能会做出妥协，例如让单元格大小相对于游戏中普通人的大小（可能更小或更大），因为游戏中的许多 models/sprites 可能是设计好的供人类使用。但它可能会变得非常繁琐，对于小东西来说非常 sub-optimal 而对于巨大的东西来说非常 sub-optimal 。在那种情况下，我们可能会很好地抵制我们的直觉和愿望，只使用一个解决方案并使用多个解决方案（它仍然可以是相同的代码，但只是相同 class 实例的多个实例，用于构造不同的数据结构参数）。
至于搜索多个数据结构而不是单个数据结构的开销，这是最好衡量的东西，值得记住的是每个容器的输入大小因此会更小，从而减少每次搜索的成本并且非常可能会改善参考地点。它可能超过需要像 std::map 这样的对数搜索时间的层次结构的好处（或者不需要，最好只是测量和比较），但我倾向于使用更多的数据结构在 constant-time 中执行此操作（网格或散列 tables）。在我的案例中，我发现好处远远超过要求多次搜索来执行单个查询的额外成本，尤其是当元素大小发生根本变化时，或者我想要一些类似于具有 2 个或更多 NxM 网格的层次结构的基本事物，范围从 "coarse" 到 "fine".
Row-Based 优化
至于"row-based optimizations"，那非常特定于统一 fixed-sized 网格而不是树。它指的是每行使用单独的 variable-sized list/container 而不是对整个网格使用一个单独的行。除了可能减少空行的内存使用而无需分配内存块，它还可以节省大量处理并改进内存访问模式。
如果我们为整个网格存储一个列表，那么当元素移动、粒子诞生等时，我们必须不断地从该共享列表中插入和删除。这可能会导致更多堆 allocations/deallocations 增加和缩小容器，但也增加了从该列表中的一个元素到下一个元素的平均内存步幅，由于更多不相关的数据被加载到缓存行中，这往往会转化为更多的缓存未命中。此外，如今我们拥有如此多的核心，因此为整个网格使用一个共享容器可能会降低并行处理网格的能力（例如：搜索一行，同时插入另一行）。它还会导致结构使用更多的净内存，因为如果我们使用像 std::vector 或 ArrayList 这样的连续序列，它们通常可以存储两倍于减少所需元素的内存容量通过保持过剩容量，最大限度地减少重新分配和复制 linear-time 中以前的元素的需要，将插入时间摊销为固定时间。
通过为每个网格行或每列关联一个单独的 medium-sized 容器，而不是为整个网格关联一个巨大的容器，我们可以在某些情况下减轻这些成本*。
- This is the type of thing you definitely measure before and after though to make sure it actually improves overall frame rates, and probably attempt in response to a first attempt storing a single list for the entire grid revealing many non-compulsory cache misses in the profiler.
这可能会引出一个问题，即为什么我们不为网格中的每个单元格使用单独的小型列表容器。这是一种平衡行为。如果我们存储那么多容器（例如：1000x1000 网格的 std::vector 的一百万个实例可能每个存储很少或没有元素），它将允许最大并行度并最小化从单元格中的一个元素到单元中的下一个，但这在内存使用方面可能会非常爆炸，并引入大量额外的处理和堆开销。
特别是在我的例子中，我最好的网格可能存储一百万个或更多的单元格，但我每个单元格只需要 4 个字节。在 64 位架构上，每个单元格的 variable-sized 序列通常会爆炸到每个单元格至少 24 个字节或更多（通常更多）以存储容器数据（通常是一个指针和几个额外的整数，或者heap-allocated 内存块顶部的三个指针），但最重要的是，插入空单元格的每个元素都可能需要堆分配和强制缓存未命中和页面错误，并且由于缺乏时间性而非常频繁地点。因此，我发现在我的 best-measured 实现中，平衡点和最佳点通常是每行一个列表容器。
我使用所谓的 "singly-linked array list" 将元素存储在网格行中并允许 constant-time 插入和删除，同时仍然允许一定程度的空间局部性，其中许多元素是连续的。可以这样描述：
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 位 single-precision floating-point 或 16 位 half-floats.
非正统？
关于这个问题：
Is this type of grid search common?
我不确定！我倾向于用术语来解决一些问题，我将不得不请求人们的原谅和沟通的耐心。我在互联网普及之前的 1980 年代幼儿时期就开始编程，因此我开始依赖于发明很多自己的技术并使用自己的粗糙术语。大约 15 年后，我 20 多岁时获得了计算机科学学位，并纠正了我的一些术语和误解，但多年来我一直在推出自己的解决方案。所以我经常不确定其他人是否遇到过一些相同的解决方案，以及它们是否有正式的名称和术语。
这使得与其他程序员的交流变得困难，有时对我们俩来说都非常令人沮丧，我不得不要求很大的耐心来解释我的想法。我已经养成了在会议上总是开始展示一些非常有希望的结果的习惯，这往往会让人们对我对他们工作方式的粗略和 long-winded 解释更有耐心。如果我从展示结果开始，他们往往会给我的想法更多的机会，但我通常对这个行业中普遍存在的正统观念和教条主义感到非常沮丧，这些观念有时会比执行和实际结果更优先考虑概念。我本质上是一个实用主义者，所以我不考虑 "what is the best data structure?" 我认为考虑到我们的优势和劣势，我们可以有效地个人实施什么，什么是直觉和 counter-intuitive 对我们和我愿意在概念的纯度上无休止地妥协，以支持更简单、问题更少的执行。我只是喜欢好的、可靠的解决方案，无论它们是多么正统或非正统，它们都能自然地从我们的指尖滚动，但我的很多方法结果可能是非正统的（或者不是，我可能还没有找到做过的人一样的东西）。我发现这个网站在极少数情况下很有用，可以找到像 "Oh, I've done that too! I found the best results if we do this [...]" 或有人指出像 "What you are proposing is called [...]."
的同龄人在 performance-critical 上下文中，粗略地说，我有点让探查器为我提出数据结构。也就是说，我会想出一些快速的初稿（通常是非常正统的）并使用分析器对其进行测量，然后让分析器的结果为我提供第二稿的想法，直到我收敛到既简单又高效且可适当扩展的东西对于要求（一路上可能会变得非常不正统）。我很高兴放弃很多想法，因为我认为我们必须在淘汰过程中剔除很多不好的想法才能提出一个好的想法，所以我倾向于循环大量的实现和想法，并且已经来了成为一个真正快速的原型制作者（我有一种心理倾向，顽固地爱上我花了很多时间的解决方案，所以为了反击，我学会了在解决方案上花费绝对最少的时间，直到它非常非常有前途） .
You can see my exact methodology at work in the very answers to that question where I iteratively converged through lots of profiling and measuring over the course of a few days and prototyping from a fairly orthodox quadtree to that unorthodox "loose-tight double grid" solution that handled the largest number of agents at the most stable frame rates and was, for me anyway, much faster and simpler to implement than all the structures before it. I had to go through lots of orthodox solutions and measure them though to generate the final idea for the unusual loose-tight variant. I always start off with and favor the orthodox solutions and start off inside the box because they're well-documented and understood and just very gently and timidly venture outside, but I do often find myself a bit outside the box when the requirements are steep enough. I'm no stranger to the steepest requirements since in my industry and as a fairly low-level type working on engines, the ability to handle more data at good frame rates often translates not only to greater interactivity for the user but also allows artists to create more detailed content of higher visual quality than ever before. We're always chasing higher and higher visual quality at good frame rates, and that often boils down to a combination of both performance and getting away with crude approximations whenever possible. This inevitably leads to some degree of unorthodoxy with lots of in-house solutions very unique to a particular engine, and each engine tends to have its own very unique strengths and weaknesses as you find comparing something like CryEngine to Unreal Engine to Frostbite to Unity.
比如我有这个从小就用的数据结构，不知道叫什么名字。这是一个简单的概念，它只是一个分层位集，它允许在简单工作的尽可能少的几次迭代中找到潜在的数百万个元素的集合交集，并且只需几次迭代（少于linear-time 要求仅通过数据结构本身遍历集合中的所有内容，returns 范围占用 elements/set 位而不是单个 elements/bit 索引）。但我不知道这个名字是什么，因为它只是我推出的东西，而且我从未遇到过任何人在计算机科学中谈论它。我倾向于将其称为 "hierarchical bitset"。最初我称它为 "sparse bitset tree" 但这似乎有点冗长。这根本不是一个特别聪明的概念，我不会感到惊讶或失望（实际上很高兴）发现其他人在我之前发现了相同的解决方案，但我发现人们从未使用或谈论过一个。它只是扩展了规则的平面位集的优势，通过按位或快速找到集合交集，并使用 FFZ/FFS 快速遍历所有集合位，但将两者的 linear-time 要求降低到对数（对数base 是一个比 2) 大得多的数字。
无论如何，如果其中一些解决方案非常不正统，我不会感到惊讶，但如果它们相当正统，我也不会感到惊讶，我只是没能找到这些技术的正确名称和术语.对我来说，此类网站的很多吸引力在于孤独地寻找其他使用过类似技术的人，并试图为他们找到合适的名称和术语，但往往以失败告终。我也希望提高我解释它们的能力，尽管我一直很糟糕并且long-winded在这里。我发现使用图片对我有很大帮助，因为我发现人类语言充满了歧义。我也喜欢故意不精确的比喻语言，它包含并庆祝隐喻和类比以及幽默夸张等歧义，但我没有发现它是程序员由于缺乏精确性而倾向于欣赏的类型。但我从来没有发现精确度有那么重要，只要我们可以传达内容丰富的内容以及关于一个想法的 "cool" 是什么，同时他们可以对其余部分做出自己的解释。对整个解释表示歉意，但希望这能澄清一些关于我的粗略术语和我用来获得这些技术的整体方法的一些事情。英语也不是我的第一语言，所以增加了另一层卷积，我必须将我的想法翻译成英语单词并为此付出很多努力。