我正在读这个答案
用于 2D 碰撞检测的四叉树的高效（且解释良好）实现 https://stackoverflow.com/questions/41946007/efficient-and-well-explained-implementation-of-a-quadtree-for-2d-collision-det/48384354#48384354
并遇到了这一段
好吧，实际上四叉树并不是我最喜欢的数据结构。我倾向于更喜欢网格层次结构，例如世界的粗网格，区域的更精细的网格，子区域的更精细的网格（3个固定级别的密集网格，不涉及树），具有行-基于优化，这样没有实体的行将被释放并变成空指针，同样完全空的区域或子区域变成空值。虽然在一个线程中运行的四叉树的这种简单实现可以在我的 i7 上以 60+ FPS 处理 10 万个代理，但我实现的网格可以处理旧硬件（i3）上每一帧相互反弹的几百万个代理。另外，我一直很喜欢网格如何使预测它们需要多少内存变得非常容易，因为它们不会细分单元格。但我将尝试介绍如何实现相当有效的四叉树。
这种类型的网格看起来很直观，听起来有点像“N 阶”网格，其中每个父节点有 N 个子节点，而不是 4 个子节点。 N^3 可以比 4^3 走得更远，这可以实现更好的精度，并且可能（我猜）更少的分支（因为要分支的节点要少得多）。
我有点困惑，因为我会直观地使用一个，或者可能是 3 个 std::map 以及适当的< operator()，以减少其内存占用，但我不确定它会这么快，因为查询 AABB 意味着堆叠多个 O(log n) 的访问。
他所说的基于行的优化到底是什么？这种类型的网格搜索常见吗？
我对 z 顺序曲线有一些了解，并且我对四叉树并不完全满意。
这是我自己的引言。但这是基于我在个人经历中遇到的常见模式。此外，在谈论网格时，我基本上会放弃诸如“父”和“子”之类的术语。你刚刚得到了一个大的 2 维或 N 维表/矩阵来存储东西。实际上并不涉及任何层次结构——这些数据结构更类似于数组而不是树。
“粗”与“细”
关于“粗略”和“精细”，我的意思是“粗略”搜索查询往往更便宜，但会产生更多误报。较粗的网格是网格分辨率较低的网格（单元较少、较大）。粗略搜索可能涉及遍历/搜索更少和更大的网格单元。例如，假设我们想查看一个元素是否与一个巨大单元格中的点/点相交（想象一下只有一个 1x1 网格存储模拟中的所有内容）。如果该点与单元格相交，我们可能会在该单元格中返回大量元素，但可能只有一个或没有一个元素实际上与该点相交。
因此，“粗略”查询是广泛而简单的，但在缩小候选者（或“嫌疑人”）列表方面并不十分精确。它可能会返回太多结果，并且仍然需要完成大量处理来缩小实际与搜索参数*相交的范围。
就像在那些侦探节目中，当他们在数据库中搜索某个人时 可能的杀手，放入“白人男性”可能不需要太多 正在处理列出结果，但可能会给出太多结果 适当缩小嫌疑人范围。 “很好”则相反，可能需要对数据库进行更多处理，但将结果缩小到只有一个嫌疑人。 这是一个粗略且有缺陷的类比，但我希望它能有所帮助。
在我们讨论内存优化之类的问题之前，无论我们谈论的是空间哈希还是四叉树，广泛优化空间索引的关键通常是在“粗略”和“精细”之间找到一个很好的平衡。太“精细”，我们可能会花费太多时间遍历数据结构（在统一网格中搜索许多小单元，或者在四叉树等自适应网格的树遍历上花费太多时间）。太“粗略”，空间索引可能会返回太多结果，从而显着减少进一步处理所需的时间。对于空间哈希（我个人不太喜欢的一种数据结构，但它们在游戏开发中非常流行），在确定要使用的最佳单元大小时通常需要进行大量的思考、实验和测量。
对于统一的 NxM 网格，它们的“粗”或“细”程度（单元格的大小以及网格分辨率的高或低）不仅会影响查询的搜索时间，而且如果元素大于一个元素，还会影响插入和删除时间。观点。如果网格太细，则可能必须将单个大型或中型元素插入许多微小单元中并从许多微小单元中删除，这会使用大量额外的内存和处理。如果太粗略，则可能只需将元素插入到一个大单元格或从一个大单元格中删除该元素，但代价是数据结构无法将搜索查询返回的候选数缩小到最低限度。如果不小心，过于“精细/粒度”在实践中可能会成为非常瓶颈，开发人员可能会发现他的网格结构使用千兆字节的 RAM 来实现适度的输入大小。对于像四叉树这样的树变体，如果允许的最大树深度太高，当四叉树的叶节点存储最小单元大小时，导致爆炸性内存使用和处理（我们甚至可能开始遇到浮点运算），就会发生类似的情况如果允许单元格在树中细分到太小的尺寸，则精度错误会破坏性能）。
通过空间索引加速性能的本质通常就是这种平衡行为。例如，我们通常不想将视锥体剔除应用于在计算机图形中渲染的单个多边形，因为这通常不仅与硬件在裁剪阶段已经执行的操作是多余的，而且它也太“精细/粒度”并且需要太多与仅请求渲染一个或多个多边形所需的时间相比，它本身需要大量处理。但我们可能会通过一些“更粗略”的东西来获得巨大的性能改进，例如将视锥体剔除应用于整个生物或太空飞船（整个模型/网格），从而使我们能够避免通过一次测试请求一次渲染许多多边形。因此，我经常在此类讨论中频繁使用术语“粗略”和“精细/粒度”（直到我找到更多人可以轻松理解的更好术语）。
统一网格与自适应网格
您可以将四叉树视为一个“自适应”网格，其自适应网格单元大小按层次排列（当我们在单个智能自适应数据结构中从根深入到叶子时，从“粗”到“细”工作），而不是简单的 NxM“统一”网格。
基于树的结构的自适应性质非常智能，可以处理广泛的用例（尽管通常需要调整最大树深度和/或允许的最小单元大小以及可能在单元中存储多少个最大元素/细分之前的节点）。然而，优化树数据结构可能会更加困难，因为层次性质并不容易适合我们的硬件和内存层次结构非常适合遍历的连续内存布局。因此，我经常发现不涉及树的数据结构更容易优化，就像优化哈希表可能比优化红黑树更简单一样，尤其是当我们可以预测很多有关数据类型的情况时我们要提前储存。
我在很多情况下倾向于更简单、更连续的数据结构的另一个原因是，实时模拟的性能要求通常不仅需要快速的帧速率，还需要持续的和可预测的帧速率。一致性很重要，因为即使视频游戏的大部分时间都具有非常高的帧速率，但游戏的某些部分会导致帧速率在短时间内大幅下降，玩家也可能会死亡并游戏结束它的结果。在我的例子中，避免这些类型的场景并让数据结构基本上不存在病态的最坏情况性能场景通常非常重要。一般来说，我发现更容易预测许多更简单的数据结构的性能特征，这些数据结构不涉及自适应层次结构，并且有点“愚蠢”。我经常发现帧速率的一致性和可预测性大致与我预测数据结构的整体内存使用情况的容易程度及其稳定性有关。如果内存使用情况非常不可预测且不稳定，我经常（并非总是，但经常）发现帧速率同样会不稳定。
因此，我经常亲自使用网格找到更好的结果，但如果在特定模拟环境中确定用于网格的单个最佳单元尺寸很棘手，我只需使用它们的多个实例：一个具有较大单元尺寸的实例用于“粗略”搜索（例如 10x10），较小的单元格用于“更精细”搜索（例如 100x100），甚至可能有更小的单元格用于“最佳”搜索（例如 1000x1000）。如果粗略搜索没有返回结果，那么我不会继续进行更精细的搜索。我通过这种方式平衡了四叉树和网格的优点。
我过去使用这些类型的表示时所做的并不是在所有三个网格实例中存储单个元素。这将使这些结构中元素条目/节点的内存使用量增加三倍。相反，我所做的是将较精细网格的占用单元的索引插入到较粗的网格中，因为占用的单元通常远少于模拟中的元素总数。只有具有最小单元尺寸的最精细、最高分辨率的网格才能存储该元素。最精细网格中的单元类似于四叉树的叶节点。
我在该问题的答案之一中所说的“松紧双网格”是对这种多网格想法的扩展。不同之处在于，更精细的网格实际上是松散的，单元格大小会根据插入的元素而扩展和缩小，始终保证单个元素，无论大小，只需要插入到网格中的一个单元格中。较粗的网格存储较细网格的占用单元，导致两个恒定时间查询（一个在较粗的紧密网格中，另一个在较细的松散网格中）以返回与搜索参数匹配的潜在候选者的元素列表。它还具有最稳定和可预测的内存使用（不一定是最小的内存使用，因为精细/松散的单元需要存储轴对齐的边界框，该边界框会扩展/收缩，从而向单元添加另外 16 个字节左右）和相应的稳定帧率，因为一个元素总是插入到一个单元格中，除了它自己的元素数据之外，不需要任何额外的内存来存储它，除非它的插入导致松散的单元格扩展到必须插入的点较粗网格中的其他单元格（这应该是相当罕见的情况）。
用于其他目的的多个网格
我有点困惑，因为我会直观地使用单个或可能 3 个 std::map 以及适当的运算符（）来减少其内存占用，但我不确定它会这么快，因为查询 AABB意味着堆叠多个 O(log n) 的访问。
我认为这是我们许多人都有的一种直觉，也可能是一种潜意识的愿望，希望所有事情都依赖一种解决方案，因为编程可能会变得非常乏味和重复，并且最好只实现一次某件事并在所有事情上重用它：“ “一刀切”T 恤。但是一件一刀切的衬衫可能剪裁得很差，无法适合我们非常宽大和肌肉发达的程序员身体*。所以有时使用小、中、大尺寸的类比会有所帮助。
- 对于我来说，这很可能是一次糟糕的幽默尝试，目的是让我冗长的文本读起来不那么无聊。
例如，如果您正在使用std::map对于像空间散列这样的东西，可能需要进行大量的思考和摆弄，试图找到最佳的单元格大小。在视频游戏中，人们可能会做出妥协，例如使细胞大小相对于游戏中普通人的大小（可能更小或更大），因为游戏中的许多模型/精灵可能是为人类设计的使用。但它可能会变得非常繁琐，对于微小的事物来说非常次优，对于巨大的事物也非常次优。在这种情况下，我们可能会很好地抵制我们的直觉，并希望只使用一种解决方案并使用多种解决方案（它仍然可以是相同的代码，但只是使用不同参数构造的数据结构的同一类实例的多个实例）。
至于搜索多个数据结构而不是单个数据结构的开销，这是最好衡量的，值得记住的是，每个容器的输入大小将因此而变小，从而减少每次搜索的成本，并很可能提高引用的局部性。它可能超出需要对数搜索时间的分层结构的好处，例如std::map（或者不是，最好只是测量和比较），但我倾向于使用更多的数据结构，这些数据结构在恒定时间（网格或哈希表）中执行此操作。在我的例子中，我发现好处远远超过了需要多次搜索来执行单个查询的额外成本，特别是当元素大小变化很大或者我想要一些类似于具有 2 个或更多 NxM 网格的层次结构的基本东西时，这些网格的范围从“粗略” “ 罚款”。
基于行的优化
至于“基于行的优化”，这是非常特定于统一的固定大小的网格而不是树。它是指每行使用单独的可变大小列表/容器，而不是整个网格使用单个列表/容器。除了可能减少空行的内存使用（无需分配内存块而直接变成空行）之外，它还可以节省大量处理并改进内存访问模式。
如果我们为整个网格存储一个列表，那么当元素移动、粒子诞生等时，我们必须不断地从该共享列表中插入和删除。这可能会导致更多的堆分配/解除分配，从而增大和缩小容器，但是还增加了从该列表中的一个元素到下一个元素的平均内存步幅，这往往会导致更多的缓存未命中，因为更多不相关的数据被加载到缓存行中。此外，现在我们有如此多的核心，因此为整个网格使用单个共享容器可能会降低并行处理网格的能力（例如：搜索一行，同时插入另一行）。它还可能导致结构使用更多的净内存，因为如果我们使用像这样的连续序列std::vector or ArrayList，这些通常可以存储两倍于所需元素的内存容量，通过保留多余的容量，最大限度地减少在线性时间内重新分配和复制前一个元素的需要，从而将插入时间减少到摊销常数时间。
通过为每个网格行或每列关联一个单独的中型容器而不是整个网格的巨大容器，我们可以在某些情况下减轻这些成本*。
- 这是您在前后肯定要测量的类型，以确保它确实提高了整体帧速率，并且可能会尝试响应第一次尝试为整个网格存储单个列表，从而在分析器中显示许多非强制缓存未命中。
这可能会引出一个问题：为什么我们不为网格中的每个单元格使用单独的小型列表容器。这是一种平衡行为。如果我们存储那么多容器（例如：一百万个实例）std::vector对于一个 1000x1000 的网格，每个网格可能存储很少或没有元素），它将允许最大并行度并最小化从单元格中的一个元素到单元格中的下一个元素的步幅，但这在内存使用方面可能会相当爆炸性并引入大量额外的处理和堆开销。
特别是在我的例子中，我最好的网格可能会存储一百万个单元或更多，但每个单元只需要 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 位半浮点数。
非正统？
关于这个问题：
这种类型的网格搜索常见吗？
我不知道！我往往会在术语上遇到一些困难，并且在沟通中我必须请求人们的原谅和耐心。我从 20 世纪 80 年代互联网普及之前的童年时期就开始编程，所以我开始依赖发明很多自己的技术并使用自己的粗略术语。大约十五年后，当我二十多岁的时候，我获得了计算机科学学位，并纠正了一些术语和误解，但我已经花了很多年的时间来推出自己的解决方案。因此，我经常不确定其他人是否遇到过一些相同的解决方案，以及它们是否有正式的名称和术语。
这使得与其他程序员的沟通变得困难，有时对我们俩来说都非常令人沮丧，我必须要求有很大的耐心来解释我的想法。我已经养成了在会议中总是先展示一些非常有希望的结果的习惯，这往往会让人们对我对他们如何工作的粗略而冗长的解释更加耐心。如果我一开始就展示结果，他们往往会给我的想法更多的机会，但我常常对这个行业中普遍存在的正统和教条主义感到非常沮丧，这些观念有时会优先考虑概念，而不是执行和实际结果。我本质上是一个实用主义者，所以我不会考虑“什么是最好的数据结构？”我认为，考虑到我们的优势和劣势，以及对我们来说直观和反直觉的内容，我们可以有效地亲自实施什么，我愿意在概念的纯粹性上不断妥协，以支持更简单、问题更少的执行。我只是喜欢好的、可靠的解决方案，无论它们是多么正统或非正统，它们都能自然地从我们的指尖滚滚而来，但我的很多方法可能因此而变得非正统（或者不是，我可能还没有找到这样做的人）相同的事情）。我发现这个网站在极少数情况下很有用，可以找到类似“哦，我也这样做过！如果我们这样做的话，我发现最好的结果[...]”，或者有人指出，“什么？”你提出的建议被称为[...]。”
粗略地说，在性能关键的环境中，我让分析器为我提供数据结构。也就是说，我将提出一些快速的初稿（通常非常正统），并使用分析器对其进行测量，并让分析器的结果为我提供第二稿的想法，直到我收敛到既简单又高性能且可适当扩展的东西以满足要求（一路上可能会变得非常不正统）。我很高兴放弃很多想法，因为我认为我们必须在淘汰过程中剔除很多不好的想法才能提出一个好的想法，所以我倾向于循环使用很多实现和想法，并得出了结论成为一个真正快速的原型师（我有一种心理倾向，顽固地爱上我花了很多时间的解决方案，所以反驳说，我已经学会在一个解决方案上花费绝对最少的时间，直到它非常非常有前途） 。
你可以在这个问题的答案中看到我的确切方法论 问题是我通过大量的分析和迭代迭代地收敛到哪里 经过几天的测量，并从一个相当正统的四叉树到这个原型 非正统的“松紧双网格”解决方案处理了最大的 最稳定帧速率下的代理数量，对我来说 无论如何，比所有结构实现起来更快更简单 在它之前。我必须经历许多正统的解决方案并对其进行测量，才能产生不寻常的松紧变体的最终想法。我总是从并喜欢正统的解决方案，并从框内开始，因为它们有详细的记录和理解，并且只是非常温和和胆怯地冒险，但当要求很高时，我确实经常发现自己有点框外足够的。我对最严格的要求并不陌生，因为在我的行业中，作为一个在引擎上工作的相当低级别的类型，以良好的帧速率处理更多数据的能力通常不仅会转化为用户更大的交互性，而且还允许艺术家创建比以往任何时候都具有更高视觉质量的更详细的内容。我们总是在良好的帧速率下追求越来越高的视觉质量，这通常可以归结为性能和尽可能避免粗略近似的结合。这不可避免地会导致某种程度的非正统，因为许多内部解决方案对于特定引擎来说非常独特，并且每个引擎往往都有自己非常独特的优点和缺点，当你比较 CryEngine、Unreal Engine、Frostbite 和 Unity 等引擎时，就会发现。
For example, I have this data structure I've been using since childhood and I don't know the name of it. It's a straightforward concept and it's just a hierarchical bitset that allows set intersections of potentially millions of elements to be found in as little as a few iterations of simple work as well as traverse millions of elements occupying the set with just a few iterations (less than linear-time requirements to traverse everything in the set just through the data structure itself which returns ranges of occupied elements/set bits instead of individual elements/bit indices). But I have no idea what the name is since it's just something I rolled and I've never encountered anyone talking about it in computer science. I tend to refer to it as a "hierarchical bitset". Originally I called it a "sparse bitset tree" but that seems a tad verbose. It's not a particularly clever concept at all and I wouldn't be surprised or disappointed (actually quite happy) to find someone else discovering the same solution before me but just one I don't find people using or talking about ever. It just expands on the strengths of a regular, flat bitset in rapidly finding set intersections with bitwise OR and rapidly traverse all set bits using FFZ/FFS but reducing the linear-time requirements of both down to logarithmic (with the logarithm base being a number much larger than 2).
不管怎样，如果其中一些解决方案非常非正统，我不会感到惊讶，但如果它们相当正统，而且我只是未能找到这些技术的正确名称和术语，我也不会感到惊讶。对我来说，此类网站的很多吸引力在于孤独地寻找其他使用过类似技术的人，并试图为他们找到合适的名称和术语，但常常以失败告终。我也希望提高我解释它们的能力，尽管我在这里总是表现得很糟糕而且啰嗦。我发现使用图片对我有很大帮助，因为我发现人类语言充满了歧义。我也喜欢故意不精确的比喻语言，它包含并庆祝隐喻、类比和幽默夸张等模糊性，但我没有发现它是程序员由于缺乏精确性而非常欣赏的类型。但我从来没有发现精确性那么重要，只要我们能够传达一个想法的实质内容和什么是“酷”的，而他们可以对其余的内容做出自己的解释。对整个解释表示歉意，但希望这可以澄清我的粗略术语和我用来实现这些技术的总体方法的一些问题。英语也不是我的母语，所以这增加了另一层卷积，我必须将我的想法翻译成英语单词，并为此付出很多努力。