这是我自己的报价。但这是基于我在个人经历中遇到的一种常见模式。此外，像“父”和“子”这样的术语是我在谈论网格时基本上会丢弃的术语。你刚刚得到了一个大的二维或 N 维表/矩阵来存储东西。没有真正涉及到层次结构——这些数据结构更类似于数组而不是树。
“粗”与“细”
关于“粗略”和“精细”，我的意思是“粗略”搜索查询往往更便宜，但会产生更多误报。较粗的网格将是网格分辨率较低的网格（更少、更大的单元格）。粗略搜索可能涉及遍历/搜索更少和更大的网格单元。例如，假设我们想查看一个元素是否与一个巨大单元格中的一个点/点相交（想象一个 1x1 网格存储模拟中的所有内容）。如果点与单元格相交，我们可能会在该单元格中返回大量元素，但可能只有一个元素或没有一个元素实际上与点相交。
因此，“粗略”查询广泛而简单，但在缩小候选人（或“嫌疑人”）列表时不是很精确。它可能会返回太多结果，但仍然需要进行大量处理以缩小实际与搜索参数相交的范围*。
就像在那些侦探节目中，当他们在数据库中搜索可能的杀手时，输入“白人男性”可能不需要太多的处理来列出结果，但可能会给出太多的结果来适当地缩小嫌疑人的范围。“很好”则相反，可能需要对数据库进行更多处理，但将结果缩小到只有一个嫌疑人。这是一个粗略且有缺陷的类比，但我希望它有所帮助。
通常，在我们讨论诸如空间散列或四叉树之类的内存优化之前，广泛优化空间索引的关键是在“粗略”和“精细”之间找到一个很好的平衡。太“好”了，我们可能会花费太多时间遍历数据结构（在统一网格中搜索许多小单元，或者在树遍历上花费太多时间来遍历四叉树等自适应网格）。太“粗糙”并且空间索引可能会返回太多结果，从而显着减少进一步处理所需的时间。对于空间散列（我个人不太喜欢的一种数据结构，但它们在游戏开发中非常流行），在确定要使用的最佳单元大小时通常需要大量的思考、实验和测量。
对于统一的 NxM 网格，它们的“粗”或“细”（大或小单元格以及高或低网格分辨率）不仅会影响查询的搜索时间，而且如果元素大于观点。如果网格太细，则可能必须将单个大型或中型元素插入到许多微小单元中并从许多微小单元中删除，这会使用大量额外的内存和处理。如果它太粗略，则可能只需要在一个大单元格中插入和删除该元素，但代价是数据结构将搜索查询返回的候选者数量缩小到最低限度的能力。不小心，太“细/颗粒” 在实践中可能会成为非常瓶颈，开发人员可能会发现他的网格结构使用千兆字节的 RAM 来实现适度的输入大小。对于像四叉树这样的树变体，如果允许的最大树深度值太高，当四叉树的叶节点存储最小的单元格大小时，会发生类似的事情，从而导致爆炸性内存使用和处理（我们甚至可以开始运行浮点如果允许将单元格细分到树中的太小尺寸，则会破坏性能的精度错误）。
使用空间索引加速性能的本质通常是这种平衡行为。例如，我们通常不想将平截头体剔除应用于在计算机图形中渲染的单个多边形，因为这通常不仅与硬件在裁剪阶段已经完成的工作相比是多余的，而且它也太“精细/精细”并且也需要与仅请求渲染一个或多个多边形所需的时间相比，它本身需要进行大量处理。但是我们可能会通过一些“更粗略”的东西来获得巨大的性能改进，例如将截锥体剔除应用于整个生物或太空船（整个模型/网格），从而使我们能够避免通过一次测试请求一次渲染多个多边形。所以我经常使用术语，“粗”和“细/颗粒”
均匀网格与自适应网格
您可以将四叉树视为具有分层排列的自适应网格单元大小的“自适应”网格（当我们在单个智能和自适应数据结构中从根向下钻取到叶时，从“粗略”到“精细”工作），而不是简单的 NxM“统一”网格。
基于树的结构的自适应特性非常智能，可以处理广泛的用例（尽管通常需要调整最大树深度和/或允许的最小单元格大小以及可能在一个单元格中存储多少个最大元素/细分之前的节点）。但是，优化树数据结构可能会更加困难，因为层次结构本身并不容易适应我们的硬件和内存层次结构非常适合遍历的那种连续内存布局。所以很多时候我发现不涉及树的数据结构更容易优化，就像优化哈希表可能比优化红黑树更简单，尤其是当我们可以预测很多关于数据类型的时候我们将提前存储。
在很多情况下，我倾向于更简单、更连续的数据结构的另一个原因是，实时模拟的性能要求通常不仅需要快速的帧速率，还需要一致的和可预测的帧速率。一致性很重要，因为即使视频游戏在大部分游戏中的帧速率都非常高，但游戏的某些部分会导致帧速率在很短的时间内大幅下降，玩家可能会死亡并作为游戏结束它的结果。在我的案例中，避免这些类型的场景并让数据结构在很大程度上不存在病态的最坏情况下的性能场景通常非常重要。一般来说，我发现更容易预测许多不涉及自适应层次结构并且有点“笨拙”的简单数据结构的性能特征。很多时候，我发现帧速率的一致性和可预测性大致与我预测数据结构的整体内存使用量和稳定性的难易程度有关。
所以我经常亲自使用网格找到更好的结果，但如果在特定模拟上下文中确定用于网格的单个最佳单元格大小很棘手，我只使用它们的多个实例：一个具有较大单元格大小的实例用于“粗略”搜索（比如 10x10），一个用于“更精细”的搜索（比如 100x100）的较小单元格，甚至可能还有一个用于“最佳”搜索的更小的单元格（比如 1000x1000）。如果在粗略搜索中没有返回任何结果，那么我不会继续进行更精细的搜索。通过这种方式，我可以平衡四叉树和网格的好处。
我过去使用这些类型的表示时所做的不是在所有三个网格实例中存储单个元素。这将使这些结构中元素条目/节点的内存使用增加三倍。相反，我所做的是将较细网格的占用单元格的索引插入到较粗略的网格中，因为占用单元格的数量通常远少于模拟中的元素总数。只有具有最小像元大小的最精细、最高分辨率的网格才能存储元素。最细网格中的单元格类似于四叉树的叶节点。
我在该问题的答案之一中称其为“松紧双网格”，是对这种多网格思想的扩展。不同的是，更精细的网格实际上是松散的，并且单元格的大小会根据插入其中的元素进行扩展和缩小，始终保证单个元素，无论大小，只需要插入网格中的一个单元格. 较粗的网格存储较细网格的占用单元，导致两个恒定时间查询（一个在较粗的紧密网格中，另一个在较细的松散网格中）以返回与搜索参数匹配的潜在候选者的元素列表。
用于其他目的的多个网格
我有点困惑，因为我会直观地使用一个或 3 个 std::map 和适当的 operator() 来减少它的内存占用，但我不确定它会这么快，因为查询 AABB这意味着堆叠几个 O(log n) 的访问。
我认为这是我们许多人的直觉，也可能是一种潜意识的愿望，即只依靠一个解决方案来解决所有问题，因为编程可能会变得非常乏味和重复，最好只实现一次并在所有事情上重用它：a“一刀切”的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)。
无论如何，如果其中一些解决方案非常不正统，我不会感到惊讶，但如果它们相当正统并且我只是未能找到这些技术的正确名称和术语，我也不会感到惊讶。对我来说，像这样的网站的很多吸引力在于孤独地寻找使用过类似技术的其他人，并尝试为他们找到合适的名称和术语，但往往以挫败感告终。我也希望提高我解释它们的能力，尽管我在这里一直很糟糕和啰嗦。我发现使用图片对我有很大帮助，因为我发现人类语言充满了歧义。我也喜欢刻意不精确的比喻性语言，它包含并赞美隐喻、类比和幽默夸张等模棱两可的东西，但我没有找到它 s 由于缺乏精确性，程序员往往会非常欣赏这种东西。但我从来没有发现精确性如此重要，只要我们能传达出丰富的内容和关于一个想法的“酷”之处，而他们可以对其余部分做出自己的解释。对整个解释表示歉意，但希望能澄清我粗略的术语和我用来获得这些技术的整体方法。英语也不是我的第一语言，所以这增加了另一层卷积，我必须将我的想法翻译成英语单词，并为此付出很多努力。关于一个想法，而他们可以对其余部分做出自己的解释。对整个解释表示歉意，但希望能澄清我粗略的术语和我用来获得这些技术的整体方法。英语也不是我的第一语言，所以这增加了另一层卷积，我必须将我的想法翻译成英语单词，并为此付出很多努力。关于一个想法，而他们可以对其余部分做出自己的解释。对整个解释表示歉意，但希望能澄清我粗略的术语和我用来获得这些技术的整体方法。英语也不是我的第一语言，所以这增加了另一层卷积，我必须将我的想法翻译成英语单词，并为此付出很多努力。