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

Efficient (and well explained) implementation of a Quadtree for 2D collision detection

我一直在努力将四叉树添加到我正在编写的程序中，但我不禁注意到很少有 explained/performing 关于我正在寻找的实现的教程对于.

具体来说，我是四叉树（检索、插入、删除等）中常用的方法列表和伪代码，用于说明如何实现它们（或只是描述它们的过程）寻找，以及一些提高性能的技巧。这是为了碰撞检测，所以最好用二维矩形来解释，因为它们是将要存储的对象。

  1. 高效四叉树

好的，我会尝试一下。首先是一个预告片，展示我将提议的涉及​​ 20,000 个代理的结果（这只是我针对这个特定问题快速提出的内容）：

GIF 的帧率和分辨率都大大降低，以适应该站点的最大 2 MB。如果你想以接近全速的速度观看这个东西，这里有一个视频：https://streamable.com/3pgmn。

还有一个 100k 的 GIF，虽然我不得不 fiddle 用它这么多，不得不关闭四叉树线（似乎不想压缩那么多）以及改变代理人希望它适合 2 兆字节的方式（我希望制作 GIF 就像编写四叉树一样简单）：

20k 代理的模拟需要大约 3 兆字节的 RAM。我还可以在不牺牲帧速率的情况下轻松处理 100k 较小的代理，尽管它会导致屏幕上有点混乱，以至于您几乎看不到上面的 GIF 中发生了什么。这就是我 i7 上的一个线程中的全部 运行，根据 VTune，我几乎花了一半时间在屏幕上绘制这些东西（只是使用一些基本的标量指令一次一个像素地绘制东西CPU).

And here's a video with 100,000 agents though it's hard to see what's going on. It's kind of a big video and I couldn't find any decent way to compress it without the whole video turning into a mush (might need to download or cache it first to see it stream at reasonable FPS). With 100k agents the simulation takes around 4.5 megabytes of RAM and the memory use is very stable after running the simulation for about 5 seconds (stops going up or down since it ceases to heap allocate). Same thing in slow motion.

用于碰撞检测的高效四叉树

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

请注意，我不会深入探讨数据结构的完整理论。我假设您已经知道这一点并且有兴趣提高性能。我也只是用我个人的方式来解决这个问题，它似乎胜过我在网上为我的案例找到的大多数解决方案，但有很多不错的方法，这些解决方案对我的用例来说 tailor-fitted（非常大量输入，每帧都在移动，用于电影和电视中的视觉效果）。其他人可能会针对不同的用例进行优化。特别是在谈到空间索引结构时，我真的认为解决方案的效率比数据结构更能告诉你实现者的信息。同样，我将提出的加快速度的相同策略也适用于八叉树的 3 维。

节点表示

所以首先，让我们介绍一下节点表示：

// Represents a node in the quadtree.
struct QuadNode
{
    // Points to the first child if this node is a branch or the first
    // element if this node is a leaf.
    int32_t first_child;

    // Stores the number of elements in the leaf or -1 if it this node is
    // not a leaf.
    int32_t count;
};

一共8个字节，这个非常重要，是速度的关键部分。我实际上使用了一个较小的（每个节点 6 个字节），但我将把它作为练习留给 reader.

你或许可以不用 count。我将其包括在病理情况下，以避免线性遍历元素并在每次叶节点可能分裂时对它们进行计数。在大多数常见情况下，一个节点不应存储那么多元素。但是，我从事视觉 FX 工作，病态案例并不一定罕见。您可能会遇到艺术家使用大量重合点、跨越整个场景的大量多边形等来创建内容，所以我最终存储了一个 count.

AABB在哪里？

所以人们可能首先想知道的事情之一是节点的边界框（矩形）在哪里。我不存储它们。我即时计算它们。我有点惊讶大多数人在我看到的代码中没有这样做。对我来说，它们仅以树结构存储（根基本上只有一个 AABB）。

即时计算这些似乎更昂贵，但减少节点的内存使用可以在遍历树时按比例减少缓存未命中，并且这些缓存未命中的减少往往是比在遍历过程中必须进行几次位移和一些 additions/subtractions 更重要。遍历看起来像这样：

static QuadNodeList find_leaves(const Quadtree& tree, const QuadNodeData& root, const int rect[4])
{
    QuadNodeList leaves, to_process;
    to_process.push_back(root);
    while (to_process.size() > 0)
    {
        const QuadNodeData nd = to_process.pop_back();

        // If this node is a leaf, insert it to the list.
        if (tree.nodes[nd.index].count != -1)
            leaves.push_back(nd);
        else
        {
            // Otherwise push the children that intersect the rectangle.
            const int mx = nd.crect[0], my = nd.crect[1];
            const int hx = nd.crect[2] >> 1, hy = nd.crect[3] >> 1;
            const int fc = tree.nodes[nd.index].first_child;
            const int l = mx-hx, t = my-hx, r = mx+hx, b = my+hy;

            if (rect[1] <= my)
            {
                if (rect[0] <= mx)
                    to_process.push_back(child_data(l,t, hx, hy, fc+0, nd.depth+1));
                if (rect[2] > mx)
                    to_process.push_back(child_data(r,t, hx, hy, fc+1, nd.depth+1));
            }
            if (rect[3] > my)
            {
                if (rect[0] <= mx)
                    to_process.push_back(child_data(l,b, hx, hy, fc+2, nd.depth+1));
                if (rect[2] > mx)
                    to_process.push_back(child_data(r,b, hx, hy, fc+3, nd.depth+1));
            }
        }
    }
    return leaves;
}

省略 AABB 是我做的最不寻常的事情之一（我一直在寻找其他人这样做只是为了找到一个同行并且失败了），但我已经测量了之前和之后并且它确实大大减少了时间，至少在非常大的输入上，大幅压缩四叉树节点，并在 tr 期间动态计算 AABB通用的。 Space 和时间并不总是截然相反的。考虑到如今内存层次结构主导了多少性能，有时减少 space 也意味着减少时间。我什至通过将数据压缩为内存使用的四分之一并即时解压缩，加快了应用于大量输入的一些现实世界操作。

我不知道为什么很多人选择缓存 AABB：是为了编程方便还是在他们的情况下真的更快。然而，对于像常规四叉树和八叉树这样在中心均匀分布的数据结构，我建议测量省略 AABB 并即时计算它们的影响。你可能会很惊讶。当然，为像 Kd-trees 和 BVH 以及松散的四叉树这样的不均匀分割的结构存储 AABB 是有意义的。

Floating-Point

我不使用 floating-point 作为空间索引，也许这就是为什么我看到性能提高的原因只是动态计算 AABB，右移除以 2 等等。也就是说，至少现在 SPFP 看起来真的很快。我不知道，因为我还没有测量差异。我只是优先使用整数，即使我通常使用 floating-point 输入（网格顶点、粒子等）。为了分区和执行空间查询，我最终将它们转换为整数坐标。我不确定这样做是否有任何主要的速度优势。这只是一种习惯和偏好，因为我发现更容易推理整数而不必考虑非规范化的 FP 和所有这些。

居中 AABB

虽然我只为根存储一个边界框，但它有助于使用存储中心和节点一半大小的表示，同时使用 left/top/right/bottom 表示查询，以最大限度地减少涉及的算术量。

连续Children

这同样是关键，如果我们返回节点代表：

struct QuadNode
{
    int32_t first_child;
    ...
};

我们不需要存储 children 的数组，因为所有 4 children 都是 contiguous:

first_child+0 = index to 1st child (TL)
first_child+1 = index to 2nd child (TR)
first_child+2 = index to 3nd child (BL)
first_child+3 = index to 4th child (BR)

这不仅显着减少了遍历时的缓存未命中，而且还允许我们显着缩小节点，从而进一步减少缓存未命中，仅存储一个 32 位索引（4 字节）而不是 4 位数组（16 字节） .

这确实意味着如果你需要将元素转移到 parent 分裂时的几个象限，它仍然必须分配所有 4 个 child 叶子来将元素存储在两个象限中象限，同时有两个空叶作为 children。然而，trade-off 比 performance-wise 至少在我的用例中更值得，并且请记住，考虑到我们已经压缩了多少，一个节点只需要 8 个字节。

释放children时，我们一次释放所有四个。我在 constant-time 中使用索引空闲列表执行此操作，如下所示：

除了我们正在汇集包含 4 个连续元素的内存块，而不是一次一个。这使得我们通常不需要在模拟过程中涉及任何堆分配或释放。一组 4 个节点被标记为不可分割地释放，然后在另一个叶节点的后续拆分中被不可分割地回收。

延迟清理

我没有在删除元素后立即更新四叉树的结构。当我删除一个元素时，我只是沿着树下降到它占据的 child 节点，然后删除该元素，但即使叶子变空了，我也懒得再做任何事情。

相反，我像这样进行延迟清理：

void Quadtree::cleanup()
{
    // Only process the root if it's not a leaf.
    SmallList<int> to_process;
    if (nodes[0].count == -1)
        to_process.push_back(0);

    while (to_process.size() > 0)
    {
        const int node_index = to_process.pop_back();
        QuadNode& node = nodes[node_index];

        // Loop through the children.
        int num_empty_leaves = 0;
        for (int j=0; j < 4; ++j)
        {
            const int child_index = node.first_child + j;
            const QuadNode& child = nodes[child_index];

            // Increment empty leaf count if the child is an empty 
            // leaf. Otherwise if the child is a branch, add it to
            // the stack to be processed in the next iteration.
            if (child.count == 0)
                ++num_empty_leaves;
            else if (child.count == -1)
                to_process.push_back(child_index);
        }

        // If all the children were empty leaves, remove them and 
        // make this node the new empty leaf.
        if (num_empty_leaves == 4)
        {
            // Push all 4 children to the free list.
            nodes[node.first_child].first_child = free_node;
            free_node = node.first_child;

            // Make this node the new empty leaf.
            node.first_child = -1;
            node.count = 0;
        }
    }
}

在移动所有代理后，在每一帧结束时调用它。我之所以在多次迭代中延迟删除空叶节点，而不是在删除单个元素的过程中一次全部删除，是因为元素 A 可能会移动到节点 N2，使得 N1 空。但是，元素 B 可能会在同一帧中移动到 N1，使其再次被占用。

通过延迟清理，我们可以处理这种情况，而不会不必要地删除 children 只是在另一个元素移动到该象限时将它们添加回来。

在我的例子中移动元素很简单：1) 删除元素，2) 移动它，3) 将它重新插入四叉树。在我们移动所有元素之后，在一帧结束时（不是时间步长，每帧可能有多个时间步长），上面的 cleanup 函数被调用以从 children 中删除 parent 有 4 个空叶作为 children，这有效地将 parent 变成新的空叶，然后可以在下一帧中通过后续的 cleanup 调用进行清理（或者如果东西被插入或者如果空叶的兄弟姐妹是non-empty）。

让我们直观地看一下延迟清理：

从这里开始，假设我们删除了一些元素树上的 nts 给我们留下了 4 个空叶：

这时候，如果我们调用cleanup，如果发现4片空的child叶子，它会移除4片叶子，并将parent变成一片空叶子，像这样：

假设我们删除了更多元素：

...然后再次调用cleanup：

如果我们再次调用它，我们会得到这样的结果：

...此时根本身变成了一片空叶。但是，清理方法永远不会删除根（它只会删除 children）。同样，以这种方式延迟并分多个步骤进行的主要目的是减少每个时间步可能发生的潜在冗余工作量（可能很多），如果我们每次从中删除元素时都立即执行此操作那个树。它还有助于跨帧分发作品以避免卡顿。

TBH，我最初是出于纯粹的懒惰在我用 C 编写的 DOS 游戏中应用了这种“延迟清理”技术！当时我不想费心沿着树向下移动，删除元素，然后以 bottom-up 的方式删除节点，因为我最初编写树是为了支持 top-down 遍历（而不是 top-down 并再次备份）并且真的认为这个懒惰的解决方案是生产力妥协（牺牲最佳性能以更快地实施）。然而，多年后，我实际上开始以立即开始删除节点的方式实施四叉树删除，令我惊讶的是，我实际上以更不可预测和更不稳定的帧速率显着降低了它的速度。延迟清理，尽管最初是受到我程序员懒惰的启发，实际上（并且意外地）对动态场景进行了非常有效的优化。

Singly-Linked 元素索引列表

对于元素，我使用这种表示：

// Represents an element in the quadtree.
struct QuadElt
{
    // Stores the ID for the element (can be used to
    // refer to external data).
    int id;

    // Stores the rectangle for the element.
    int x1, y1, x2, y2;
};

// Represents an element node in the quadtree.
struct QuadEltNode
{
    // Points to the next element in the leaf node. A value of -1 
    // indicates the end of the list.
    int next;

    // Stores the element index.
    int element;
};

我使用与“元素”分开的“元素节点”。一个元素只插入一次四叉树，不管它占据了多少个单元格。但是，对于它占据的每个单元格，都会插入一个索引该元素的“元素节点”。

元素节点是singly-linked索引列表节点成数组，也是用上面的free list方法。与为叶子连续存储所有元素相比，这会导致更多缓存未命中。然而，鉴于此四叉树适用于每一个时间步都在移动和碰撞的非常动态的数据，它通常需要比为叶元素寻找完美连续表示所节省的处理时间更多的处理时间（您实际上必须实现 variable-sized 内存分配器，它非常快，而且这绝非易事）。所以我使用 singly-linked 索引列表，它允许一个自由列表 constant-time 方法到 allocation/deallocation。当您使用该表示时，只需更改几个整数即可将元素从拆分 parent 转移到新的叶子。

SmallList<T>

哦，我应该提一下这个。如果您不堆分配只是为了存储用于 non-recursive 遍历的临时节点堆栈，自然会有所帮助。 SmallList<T> 与 vector<T> 类似，只是它不会涉及堆分配，直到您向其中插入超过 128 个元素。它类似于 C++ 标准库中的 SBO 字符串优化。这是我实施并使用了很长时间的东西，它确实有助于确保您尽可能使用堆栈。

树表示法

这是四叉树本身的表示：

struct Quadtree
{
    // Stores all the elements in the quadtree.
    FreeList<QuadElt> elts;

    // Stores all the element nodes in the quadtree.
    FreeList<QuadEltNode> elt_nodes;

    // Stores all the nodes in the quadtree. The first node in this
    // sequence is always the root.
    std::vector<QuadNode> nodes;

    // Stores the quadtree extents.
    QuadCRect root_rect;

    // Stores the first free node in the quadtree to be reclaimed as 4
    // contiguous nodes at once. A value of -1 indicates that the free
    // list is empty, at which point we simply insert 4 nodes to the
    // back of the nodes array.
    int free_node;

    // Stores the maximum depth allowed for the quadtree.
    int max_depth;
};

如上所述，我们为根 (root_rect) 存储了一个矩形。所有 sub-rects 都是即时计算的。所有节点与元素和元素节点（在 FreeList<T> 中）一起连续存储在数组 (std::vector<QuadNode>) 中。

FreeList<T>

我使用了一个 FreeList 数据结构，它基本上是一个数组（和 random-access 序列），可以让你从 constant-time 中的任何地方删除元素（留下空洞，在这些空洞后面得到回收） constant-time 中的后续插入）。这是一个简化的版本，它不处理 non-trivial 数据类型（不使用放置新的或手动销毁调用）：

/// Provides an indexed free list with constant-time removals from anywhere
/// in the list without invalidating indices. T must be trivially constructible 
/// and destructible.
template <class T>
class FreeList
{
public:
    /// Creates a new free list.
    FreeList();

    /// Inserts an element to the free list and returns an index to it.
    int insert(const T& element);

    // Removes the nth element from the free list.
    void erase(int n);

    // Removes all elements from the free list.
    void clear();

    // Returns the range of valid indices.
    int range() const;

    // Returns the nth element.
    T& operator[](int n);

    // Returns the nth element.
    const T& operator[](int n) const;

private:
    union FreeElement
    {
        T element;
        int next;
    };
    std::vector<FreeElement> data;
    int first_free;
};

template <class T>
FreeList<T>::FreeList(): first_free(-1)
{
}

template <class T>
int FreeList<T>::insert(const T& element)
{
    if (first_free != -1)
    {
        const int index = first_free;
        first_free = data[first_free].next;
        data[index].element = element;
        return index;
    }
    else
    {
        FreeElement fe;
        fe.element = element;
        data.push_back(fe);
        return static_cast<int>(data.size() - 1);
    }
}

template <class T>
void FreeList<T>::erase(int n)
{
    data[n].next = first_free;
    first_free = n;
}

template <class T>
void FreeList<T>::clear()
{
    data.clear();
    first_free = -1;
}

template <class T>
int FreeList<T>::range() const
{
    return static_cast<int>(data.size());
}

template <class T>
T& FreeList<T>::operator[](int n)
{
    return data[n].element;
}

template <class T>
const T& FreeList<T>::operator[](int n) const
{
    return data[n].element;
}

我有一个可以与 non-trivial 类型一起工作并提供迭代器等，但涉及更多。这些天我倾向于更多地使用琐碎的 constructible/destructible C-style 结构（只使用 non-trivial user-defined 类型来处理 high-level 东西）。

最大树深度

我通过指定允许的最大深度来防止树细分太多。对于快速模拟，我使用了 8。对我来说，这再次至关重要，因为在 VFX 中，我遇到了很多病态案例，包括艺术家创建的具有大量重合或重叠元素的内容，如果没有最大树深度限制，可能想要无限细分

如果您希望在允许的最大深度方面获得最佳性能，以及在叶子分裂为 4 children 之前允许存储在叶子中的元素数量，则有一点 fine-tuning。我倾向于发现最佳结果是在分裂之前每个节点最多 8 个元素，并设置最大深度，以便最小单元格大小略大于平均代理的大小（否则可以插入更多单个代理）分成多片叶子）。

碰撞与查询

有几种方法可以进行碰撞检测和查询。我经常看到人们这样做：

for each element in scene:
     use quad tree to check for collision against other elements

这非常简单，但这种方法的问题是场景中的第一个元素可能与第二个元素位于世界中完全不同的位置。结果，我们取下四叉树的路径可能完全是零星的。我们可能会遍历一条路径到达一片叶子，然后想要针对第一个元素（例如第 50,000 个元素）再次沿着相同的路径前进。此时，该路径中涉及的节点可能已经从 CPU 缓存中逐出。所以我建议这样做：

traversed = {}
gather quadtree leaves
for each leaf in leaves:
{
     for each element in leaf:
     {
          if not traversed[element]:
          {
              use quad tree to check for collision against other elements
              traversed[element] = true                  
          }
     }
}

虽然这是相当多的代码并且需要我们保留一个 traversed 位集或某种并行数组以避免处理元素两次（因为它们可能被插入到多个叶子中），但它有助于使确保我们在整个循环中沿着四叉树的相同路径下降。这有助于保持更多 cache-friendly。此外，如果在时间步中尝试移动元素后，它仍然完全包含在该叶节点中，我们甚至不需要从根节点再次返回（我们可以只检查一个叶节点）。

常见的低效率：要避免的事情

虽然有很多方法可以解决问题并实现有效的解决方案，但有一种通用方法可以实现非常低效的 解决方案。在我从事 VFX 的职业生涯中，我遇到过 非常低效的 四叉树、kd 树和八叉树。我们谈论的是 1 GB 的内存使用仅用于划分具有 100k 三角形的网格，同时需要 30 秒来构建，而一个体面的实现应该能够每秒执行数百次相同的操作并且只需要几兆。有很多人提出这些来解决问题，他们是理论奇才，但不太注意内存效率。

所以我看到的绝对最常见的 no-no 是为每个树节点存储一个或多个 full-blown 容器。 full-blown 容器是指拥有、分配和释放自己的内存的东西，如下所示：

struct Node
{
     ...

     // Stores the elements in the node.
     List<Element> elements;
};

而List<Element>可能是Python中的列表，Java或C#中的ArrayList，C++中的std::vector等：一些数据结构管理自己的 memory/resources.

这里的问题是，虽然这样的容器可以非常有效地存储大量元素，但是如果实例化大量元素，所有 所有语言中的所有元素都非常低效它们只在每个中存储一些元素。原因之一是容器元数据在单个树节点的这种粒度级别上的内存使用量往往会非常爆炸。容器可能需要存储大小、容量、pointer/reference 到它分配的数据等，所有这些都是为了通用目的，因此它可能使用 64 位整数来表示大小和容量。因此，仅用于空容器的元数据可能是 24 字节，这已经是我提出的整个节点表示的 3 倍，而且这仅适用于设计用于在叶子中存储元素的空容器。

此外，每个容器通常希望在插入时 heap/GC-allocate 或者提前需要更多的预分配内存（此时仅容器本身就可能需要 64 字节）。因此，要么因为所有分配而变慢（请注意，在某些实现（如 JVM）中，GC 分配最初确实很快，但这仅适用于初始突发 Eden 周期），或者因为我们正在招致大量缓存未命中，因为节点是如此之大，以至于在遍历时几乎无法放入 CPU 缓存的较低级别，或两者兼而有之。

然而，这是一种非常自然的倾向并且具有直觉意义，因为我们在理论上使用类似“元素存储在叶子中”的语言讨论这些结构，这表明存储容器叶节点中的元素。不幸的是，它在内存使用和处理方面具有爆炸性的成本。因此，如果希望创造出相当高效的东西，请避免这种情况。使 Node 共享并指向（引用）或为整个树分配和存储的索引内存，而不是为每个单独的节点分配和存储。实际上，元素不应该存储在叶子中。

Elements should be stored in the tree and leaf nodes should index or point to those elements.

结论

呸，这些是我为实现目标所做的主要事情充分考虑了 decent-performing 解决方案。我希望这有帮助。请注意，对于已经至少实施过一次或两次四叉树的人，我的目标是稍微高级一些。有问题随时拍

由于这个问题有点宽泛，我可能会来编辑它并随着时间的推移不断调整和扩展它，如果它没有被关闭（我喜欢这些类型的问题，因为它们给了我们写的借口我们在该领域工作的经验，但网站并不总是喜欢它们）。我也希望有高手 可能会跳入我可以学习的替代解决方案，并可能用来进一步改进我的解决方案。

再说一遍，四叉树实际上并不是我最喜欢的数据结构，适用于像这样的极其动态的碰撞场景。因此，我可能需要向那些为此目的而偏爱四叉树并且多年来一直在调整和调整它们的人学习一两件事。大多数情况下，我将四叉树用于不会在每一帧周围移动的静态数据，对于那些我使用与上面提出的非常不同的表示。

3。便携式 C 实现

我希望人们不介意另一个答案，但我 运行 超出了 30k 的限制。我今天在想我的第一个答案是如何与语言无关的。我在谈论内存分配策略、class 模板等，并非所有语言都允许这样的事情。

所以我花了一些时间思考一个几乎普遍适用的高效实现（函数式语言除外）。所以我最终将我的四叉树以某种方式移植到 C 中，这样它所需要的只是 int 的数组来存储所有内容。

结果不是很好，但在允许您存储 int 的连续数组的任何语言上都应该非常有效。对于 Python，numpy 中有像 ndarray 这样的库。对于 JS 有 typed arrays。对于 Java 和 C#，我们可以使用 int 数组（不是 Integer，这些数组不保证 运行 连续存储，并且它们使用的内存比普通旧数组多得多int).

C IntList

所以我使用 one 辅助结构构建在整个四叉树的 int 数组上，以便尽可能容易地移植到其他语言。它结合了一个 stack/free 列表。这就是我们需要以有效的方式实施其他答案中讨论的所有内容。

#ifndef INT_LIST_H
#define INT_LIST_H

#ifdef __cplusplus
    #define IL_FUNC extern "C"
#else
    #define IL_FUNC
#endif

typedef struct IntList IntList;
enum {il_fixed_cap = 128};

struct IntList
{
    // Stores a fixed-size buffer in advance to avoid requiring
    // a heap allocation until we run out of space.
    int fixed[il_fixed_cap];

    // Points to the buffer used by the list. Initially this will
    // point to 'fixed'.
    int* data;

    // Stores how many integer fields each element has.
    int num_fields;

    // Stores the number of elements in the list.
    int num;

    // Stores the capacity of the array.
    int cap;

    // Stores an index to the free element or -1 if the free list
    // is empty.
    int free_element;
};

// ---------------------------------------------------------------------------------
// List Interface
// ---------------------------------------------------------------------------------
// Creates a new list of elements which each consist of integer fields.
// 'num_fields' specifies the number of integer fields each element has.
IL_FUNC void il_create(IntList* il, int num_fields);

// Destroys the specified list.
IL_FUNC void il_destroy(IntList* il);

// Returns the number of elements in the list.
IL_FUNC int il_size(const IntList* il);

// Returns the value of the specified field for the nth element.
IL_FUNC int il_get(const IntList* il, int n, int field);

// Sets the value of the specified field for the nth element.
IL_FUNC void il_set(IntList* il, int n, int field, int val);

// Clears the specified list, making it empty.
IL_FUNC void il_clear(IntList* il);

// ---------------------------------------------------------------------------------
// Stack Interface (do not mix with free list usage; use one or the other)
// ---------------------------------------------------------------------------------
// Inserts an element to the back of the list and returns an index to it.
IL_FUNC int il_push_back(IntList* il);

// Removes the element at the back of the list.
IL_FUNC void il_pop_back(IntList* il);

// ---------------------------------------------------------------------------------
// Free List Interface (do not mix with stack usage; use one or the other)
// ---------------------------------------------------------------------------------
// Inserts an element to a vacant position in the list and returns an index to it.
IL_FUNC int il_insert(IntList* il);

// Removes the nth element in the list.
IL_FUNC void il_erase(IntList* il, int n);

#endif

#include "IntList.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void il_create(IntList* il, int num_fields)
{
    il->data = il->fixed;
    il->num = 0;
    il->cap = il_fixed_cap;
    il->num_fields = num_fields;
    il->free_element = -1;
}

void il_destroy(IntList* il)
{
    // Free the buffer only if it was heap allocated.
    if (il->data != il->fixed)
        free(il->data);
}

void il_clear(IntList* il)
{
    il->num = 0;
    il->free_element = -1;
}

int il_size(const IntList* il)
{
    return il->num;
}

int il_get(const IntList* il, int n, int field)
{
    assert(n >= 0 && n < il->num);
    return il->data[n*il->num_fields + field];
}

void il_set(IntList* il, int n, int field, int val)
{
    assert(n >= 0 && n < il->num);
    il->data[n*il->num_fields + field] = val;
}

int il_push_back(IntList* il)
{
    const int new_pos = (il->num+1) * il->num_fields;

    // If the list is full, we need to reallocate the buffer to make room
    // for the new element.
    if (new_pos > il->cap)
    {
        // Use double the size for the new capacity.
        const int new_cap = new_pos * 2;

        // If we're pointing to the fixed buffer, allocate a new array on the
        // heap and copy the fixed buffer contents to it.
        if (il->cap == il_fixed_cap)
        {
            il->data = malloc(new_cap * sizeof(*il->data));
            memcpy(il->data, il->fixed, sizeof(il->fixed));
        }
        else
        {
            // Otherwise reallocate the heap buffer to the new size.
            il->data = realloc(il->data, new_cap * sizeof(*il->data));
        }
        // Set the old capacity to the new capacity.
        il->cap = new_cap;
    }
    return il->num++;
}

void il_pop_back(IntList* il)
{
    // Just decrement the list size.
    assert(il->num > 0);
    --il->num;
}

int il_insert(IntList* il)
{
    // If there's a free index in the free list, pop that and use it.
    if (il->free_element != -1)
    {
        const int index = il->free_element;
        const int pos = index * il->num_fields;

        // Set the free index to the next free index.
        il->free_element = il->data[pos];

        // Return the free index.
        return index;
    }
    // Otherwise insert to the back of the array.
    return il_push_back(il);
}

void il_erase(IntList* il, int n)
{
    // Push the element to the free list.
    const int pos = n * il->num_fields;
    il->data[pos] = il->free_element;
    il->free_element = n;
}

使用 IntList

使用此数据结构来实现所有内容并不能产生最漂亮的代码。而不是像这样访问元素和字段：

elements[n].field = elements[n].field + 1;

...我们最终会这样做：

il_set(&elements, n, idx_field, il_get(&elements, n, idx_field) + 1);

... 这很恶心，我知道，但这段代码的重点是尽可能高效和可移植，而不是尽可能易于维护。希望人们可以将这个四叉树直接用于他们的项目，而无需更改或维护它。

哦，请随意使用此代码 post 随心所欲，即使是用于商业项目。如果人们觉得它有用，请告诉我，我会非常高兴，但请按照您的意愿行事。

C四叉树

好吧，那么使用上面的数据结构，这里就是C:

中的四叉树 
#ifndef QUADTREE_H
#define QUADTREE_H

#include "IntList.h"

#ifdef __cplusplus
    #define QTREE_FUNC extern "C"
#else
    #define QTREE_FUNC
#endif

typedef struct Quadtree Quadtree;

struct Quadtree
{
    // Stores all the nodes in the quadtree. The first node in this
    // sequence is always the root.
    IntList nodes;

    // Stores all the elements in the quadtree.
    IntList elts;

    // Stores all the element nodes in the quadtree.
    IntList enodes;

    // Stores the quadtree extents.
    int root_mx, root_my, root_sx, root_sy;

    // Maximum allowed elements in a leaf before the leaf is subdivided/split unless
    // the leaf is at the maximum allowed tree depth.
    int max_elements;

    // Stores the maximum depth allowed for the quadtree.
    int max_depth;

    // Temporary buffer used for queries.
    char* temp;

    // Stores the size of the temporary buffer.
    int temp_size;
};

// Function signature used for traversing a tree node.
typedef void QtNodeFunc(Quadtree* qt, void* user_data, int node, int depth, int mx, int my, int sx, int sy);

// Creates a quadtree with the requested extents, maximum elements per leaf, and maximum tree depth.
QTREE_FUNC void qt_create(Quadtree* qt, int width, int height, int max_elements, int max_depth);

// Destroys the quadtree.
QTREE_FUNC void qt_destroy(Quadtree* qt);

// Inserts a new element to the tree.
// Returns an index to the new element.
QTREE_FUNC int qt_insert(Quadtree* qt, int id, float x1, float y1, float x2, float y2);

// Removes the specified element from the tree.
QTREE_FUNC void qt_remove(Quadtree* qt, int element);

// Cleans up the tree, removing empty leaves.
QTREE_FUNC void qt_cleanup(Quadtree* qt);

// Outputs a list of elements found in the specified rectangle.
QTREE_FUNC void qt_query(Quadtree* qt, IntList* out, float x1, float y1, float x2, float y2, int omit_element);

// Traverses all the nodes in the tree, calling 'branch' for branch nodes and 'leaf' 
// for leaf nodes.
QTREE_FUNC void qt_traverse(Quadtree* qt, void* user_data, QtNodeFunc* branch, QtNodeFunc* leaf);

#endif

#include "Quadtree.h"
#include <stdlib.h>

enum
{
    // ----------------------------------------------------------------------------------------
    // Element node fields:
    // ----------------------------------------------------------------------------------------
    enode_num = 2,

    // Points to the next element in the leaf node. A value of -1 
    // indicates the end of the list.
    enode_idx_next = 0,

    // Stores the element index.
    enode_idx_elt = 1,

    // ----------------------------------------------------------------------------------------
    // Element fields:
    // ----------------------------------------------------------------------------------------
    elt_num = 5,

    // Stores the rectangle encompassing the element.
    elt_idx_lft = 0, elt_idx_top = 1, elt_idx_rgt = 2, elt_idx_btm = 3,

    // Stores the ID of the element.
    elt_idx_id = 4,

    // ----------------------------------------------------------------------------------------
    // Node fields:
    // ----------------------------------------------------------------------------------------
    node_num = 2,

    // Points to the first child if this node is a branch or the first element
    // if this node is a leaf.
    node_idx_fc = 0,

    // Stores the number of elements in the node or -1 if it is not a leaf.
    node_idx_num = 1,

    // ----------------------------------------------------------------------------------------
    // Node data fields:
    // ----------------------------------------------------------------------------------------
    nd_num = 6,

    // Stores the extents of the node using a centered rectangle and half-size.
    nd_idx_mx = 0, nd_idx_my = 1, nd_idx_sx = 2, nd_idx_sy = 3,

    // Stores the index of the node.
    nd_idx_index = 4,

    // Stores the depth of the node.
    nd_idx_depth = 5,
};

static void node_insert(Quadtree* qt, int index, int depth, int mx, int my, int sx, int sy, int element);

static int floor_int(float val)
{
    return (int)val;
}

static int intersect(int l1, int t1, int r1, int b1,
                     int l2, int t2, int r2, int b2)
{
    return l2 <= r1 && r2 >= l1 && t2 <= b1 && b2 >= t1;
}

void leaf_insert(Quadtree* qt, int node, int depth, int mx, int my, int sx, int sy, int element)
{
    // Insert the element node to the leaf.
    const int nd_fc = il_get(&qt->nodes, node, node_idx_fc);
    il_set(&qt->nodes, node, node_idx_fc, il_insert(&qt->enodes));
    il_set(&qt->enodes, il_get(&qt->nodes, node, node_idx_fc), enode_idx_next, nd_fc);
    il_set(&qt->enodes, il_get(&qt->nodes, node, node_idx_fc), enode_idx_elt, element);

    // If the leaf is full, split it.
    if (il_get(&qt->nodes, node, node_idx_num) == qt->max_elements && depth < qt->max_depth)
    {
        int fc = 0, j = 0;
        IntList elts = {0};
        il_create(&elts, 1);

        // Transfer elements from the leaf node to a list of elements.
        while (il_get(&qt->nodes, node, node_idx_fc) != -1)
        {
            const int index = il_get(&qt->nodes, node, node_idx_fc);
            const int next_index = il_get(&qt->enodes, index, enode_idx_next);
            const int elt = il_get(&qt->enodes, index, enode_idx_elt);

            // Pop off the element node from the leaf and remove it from the qt.
            il_set(&qt->nodes, node, node_idx_fc, next_index);
            il_erase(&qt->enodes, index);

            // Insert element to the list.
            il_set(&elts, il_push_back(&elts), 0, elt);
        }

        // Start by allocating 4 child nodes.
        fc = il_insert(&qt->nodes);
        il_insert(&qt->nodes);
        il_insert(&qt->nodes);
        il_insert(&qt->nodes);
        il_set(&qt->nodes, node, node_idx_fc, fc);

        // Initialize the new child nodes.
        for (j=0; j < 4; ++j)
        {
            il_set(&qt->nodes, fc+j, node_idx_fc, -1);
            il_set(&qt->nodes, fc+j, node_idx_num, 0);
        }

        // Transfer the elements in the former leaf node to its new children.
        il_set(&qt->nodes, node, node_idx_num, -1);
        for (j=0; j < il_size(&elts); ++j)
            node_insert(qt, node, depth, mx, my, sx, sy, il_get(&elts, j, 0));
        il_destroy(&elts);
    }
    else
    {
        // Increment the leaf element count.
        il_set(&qt->nodes, node, node_idx_num, il_get(&qt->nodes, node, node_idx_num) + 1);
    }
}

static void push_node(IntList* nodes, int nd_index, int nd_depth, int nd_mx, int nd_my, int nd_sx, int nd_sy)
{
    const int back_idx = il_push_back(nodes);
    il_set(nodes, back_idx, nd_idx_mx, nd_mx);
    il_set(nodes, back_idx, nd_idx_my, nd_my);
    il_set(nodes, back_idx, nd_idx_sx, nd_sx);
    il_set(nodes, back_idx, nd_idx_sy, nd_sy);
    il_set(nodes, back_idx, nd_idx_index, nd_index);
    il_set(nodes, back_idx, nd_idx_depth, nd_depth);
}

static void find_leaves(IntList* out, const Quadtree* qt, int node, int depth, 
                        int mx, int my, int sx, int sy, 
                        int lft, int top, int rgt, int btm)
{
    IntList to_process = {0};
    il_create(&to_process, nd_num);
    push_node(&to_process, node, depth, mx, my, sx, sy);

    while (il_size(&to_process) > 0)
    {
        const int back_idx = il_size(&to_process) - 1;
        const int nd_mx = il_get(&to_process, back_idx, nd_idx_mx);
        const int nd_my = il_get(&to_process, back_idx, nd_idx_my);
        const int nd_sx = il_get(&to_process, back_idx, nd_idx_sx);
        const int nd_sy = il_get(&to_process, back_idx, nd_idx_sy);
        const int nd_index = il_get(&to_process, back_idx, nd_idx_index);
        const int nd_depth = il_get(&to_process, back_idx, nd_idx_depth);
        il_pop_back(&to_process);

        // If this node is a leaf, insert it to the list.
        if (il_get(&qt->nodes, nd_index, node_idx_num) != -1)
            push_node(out, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
        else
        {
            // Otherwise push the children that intersect the rectangle.
            const int fc = il_get(&qt->nodes, nd_index, node_idx_fc);
            const int hx = nd_sx >> 1, hy = nd_sy >> 1;
            const int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;

            if (top <= nd_my)
            {
                if (lft <= nd_mx)
                    push_node(&to_process, fc+0, nd_depth+1, l,t,hx,hy);
                if (rgt > nd_mx)
                    push_node(&to_process, fc+1, nd_depth+1, r,t,hx,hy);
            }
            if (btm > nd_my)
            {
                if (lft <= nd_mx)
                    push_node(&to_process, fc+2, nd_depth+1, l,b,hx,hy);
                if (rgt > nd_mx)
                    push_node(&to_process, fc+3, nd_depth+1, r,b,hx,hy);
            }
        }
    }
    il_destroy(&to_process);
}

static void node_insert(Quadtree* qt, int index, int depth, int mx, int my, int sx, int sy, int element)
{
    // Find the leaves and insert the element to all the leaves found.
    int j = 0;
    IntList leaves = {0};
    
    const int lft = il_get(&qt->elts, element, elt_idx_lft);
    const int top = il_get(&qt->elts, element, elt_idx_top);
    const int rgt = il_get(&qt->elts, element, elt_idx_rgt);
    const int btm = il_get(&qt->elts, element, elt_idx_btm);

    il_create(&leaves, nd_num);
    find_leaves(&leaves, qt, index, depth, mx, my, sx, sy, lft, top, rgt, btm);
    for (j=0; j < il_size(&leaves); ++j)
    {
        const int nd_mx = il_get(&leaves, j, nd_idx_mx);
        const int nd_my = il_get(&leaves, j, nd_idx_my);
        const int nd_sx = il_get(&leaves, j, nd_idx_sx);
        const int nd_sy = il_get(&leaves, j, nd_idx_sy);
        const int nd_index = il_get(&leaves, j, nd_idx_index);
        const int nd_depth = il_get(&leaves, j, nd_idx_depth);
        leaf_insert(qt, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy, element);
    }
    il_destroy(&leaves);
}

void qt_create(Quadtree* qt, int width, int height, int max_elements, int max_depth)
{
    qt->max_elements = max_elements;
    qt->max_depth = max_depth;
    qt->temp = 0;
    qt->temp_size = 0;
    il_create(&qt->nodes, node_num);
    il_create(&qt->elts, elt_num);
    il_create(&qt->enodes, enode_num);

    // Insert the root node to the qt.
    il_insert(&qt->nodes);
    il_set(&qt->nodes, 0, node_idx_fc, -1);
    il_set(&qt->nodes, 0, node_idx_num, 0);

    // Set the extents of the root node.
    qt->root_mx = width >> 1;
    qt->root_my = height >> 1;
    qt->root_sx = qt->root_mx;
    qt->root_sy = qt->root_my;
}

void qt_destroy(Quadtree* qt)
{
    il_destroy(&qt->nodes);
    il_destroy(&qt->elts);
    il_destroy(&qt->enodes);
    free(qt->temp);
}

int qt_insert(Quadtree* qt, int id, float x1, float y1, float x2, float y2)
{
    // Insert a new element.
    const int new_element = il_insert(&qt->elts);

    // Set the fields of the new element.
    il_set(&qt->elts, new_element, elt_idx_lft, floor_int(x1));
    il_set(&qt->elts, new_element, elt_idx_top, floor_int(y1));
    il_set(&qt->elts, new_element, elt_idx_rgt, floor_int(x2));
    il_set(&qt->elts, new_element, elt_idx_btm, floor_int(y2));
    il_set(&qt->elts, new_element, elt_idx_id, id);

    // Insert the element to the appropriate leaf node(s).
    node_insert(qt, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy, new_element);
    return new_element;
}

void qt_remove(Quadtree* qt, int element)
{
    // Find the leaves.
    int j = 0;
    IntList leaves = {0};

    const int lft = il_get(&qt->elts, element, elt_idx_lft);
    const int top = il_get(&qt->elts, element, elt_idx_top);
    const int rgt = il_get(&qt->elts, element, elt_idx_rgt);
    const int btm = il_get(&qt->elts, element, elt_idx_btm);

    il_create(&leaves, nd_num);
    find_leaves(&leaves, qt, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy, lft, top, rgt, btm);

    // For each leaf node, remove the element node.
    for (j=0; j < il_size(&leaves); ++j)
    {
        const int nd_index = il_get(&leaves, j, nd_idx_index);

        // Walk the list until we find the element node.
        int node_index = il_get(&qt->nodes, nd_index, node_idx_fc);
        int prev_index = -1;
        while (node_index != -1 && il_get(&qt->enodes, node_index, enode_idx_elt) != element)
        {
            prev_index = node_index;
            node_index = il_get(&qt->enodes, node_index, enode_idx_next);
        }

        if (node_index != -1)
        {
            // Remove the element node.
            const int next_index = il_get(&qt->enodes, node_index, enode_idx_next);
            if (prev_index == -1)
                il_set(&qt->nodes, nd_index, node_idx_fc, next_index);
            else
                il_set(&qt->enodes, prev_index, enode_idx_next, next_index);
            il_erase(&qt->enodes, node_index);

            // Decrement the leaf element count.
            il_set(&qt->nodes, nd_index, node_idx_num, il_get(&qt->nodes, nd_index, node_idx_num)-1);
        }
    }
    il_destroy(&leaves);

    // Remove the element.
    il_erase(&qt->elts, element);
}

void qt_query(Quadtree* qt, IntList* out, float x1, float y1, float x2, float y2, int omit_element)
{
    // Find the leaves that intersect the specified query rectangle.
    int j = 0;
    IntList leaves = {0};
    const int elt_cap = il_size(&qt->elts);

    const int qlft = floor_int(x1);
    const int qtop = floor_int(y1);
    const int qrgt = floor_int(x2);
    const int qbtm = floor_int(y2);

    if (qt->temp_size < elt_cap)
    {
        qt->temp_size = elt_cap;
        qt->temp = realloc(qt->temp, qt->temp_size * sizeof(*qt->temp));
        memset(qt->temp, 0, qt->temp_size * sizeof(*qt->temp));
    }

    // For each leaf node, look for elements that intersect.
    il_create(&leaves, nd_num);
    find_leaves(&leaves, qt, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy, qlft, qtop, qrgt, qbtm);

    il_clear(out);
    for (j=0; j < il_size(&leaves); ++j)
    {
        const int nd_index = il_get(&leaves, j, nd_idx_index);

        // Walk the list and add elements that intersect.
        int elt_node_index = il_get(&qt->nodes, nd_index, node_idx_fc);
        while (elt_node_index != -1)
        {
            const int element = il_get(&qt->enodes, elt_node_index, enode_idx_elt);
            const int lft = il_get(&qt->elts, element, elt_idx_lft);
            const int top = il_get(&qt->elts, element, elt_idx_top);
            const int rgt = il_get(&qt->elts, element, elt_idx_rgt);
            const int btm = il_get(&qt->elts, element, elt_idx_btm);
            if (!qt->temp[element] && element != omit_element && intersect(qlft,qtop,qrgt,qbtm, lft,top,rgt,btm))
            {
                il_set(out, il_push_back(out), 0, element);
                qt->temp[element] = 1;
            }
            elt_node_index = il_get(&qt->enodes, elt_node_index, enode_idx_next);
        }
    }
    il_destroy(&leaves);

    // Unmark the elements that were inserted.
    for (j=0; j < il_size(out); ++j)
        qt->temp[il_get(out, j, 0)] = 0;
}

void qt_cleanup(Quadtree* qt)
{
    IntList to_process = {0};
    il_create(&to_process, 1);

    // Only process the root if it's not a leaf.
    if (il_get(&qt->nodes, 0, node_idx_num) == -1)
    {
        // Push the root index to the stack.
        il_set(&to_process, il_push_back(&to_process), 0, 0);
    }

    while (il_size(&to_process) > 0)
    {
        // Pop a node from the stack.
        const int node = il_get(&to_process, il_size(&to_process)-1, 0);
        const int fc = il_get(&qt->nodes, node, node_idx_fc);
        int num_empty_leaves = 0;
        int j = 0;
        il_pop_back(&to_process);

        // Loop through the children.
        for (j=0; j < 4; ++j)
        {
            const int child = fc + j;

            // Increment empty leaf count if the child is an empty 
            // leaf. Otherwise if the child is a branch, add it to
            // the stack to be processed in the next iteration.
            if (il_get(&qt->nodes, child, node_idx_num) == 0)
                ++num_empty_leaves;
            else if (il_get(&qt->nodes, child, node_idx_num) == -1)
            {
                // Push the child index to the stack.
                il_set(&to_process, il_push_back(&to_process), 0, child);
            }
        }

        // If all the children were empty leaves, remove them and 
        // make this node the new empty leaf.
        if (num_empty_leaves == 4)
        {
            // Remove all 4 children in reverse order so that they 
            // can be reclaimed on subsequent insertions in proper
            // order.
            il_erase(&qt->nodes, fc + 3);
            il_erase(&qt->nodes, fc + 2);
            il_erase(&qt->nodes, fc + 1);
            il_erase(&qt->nodes, fc + 0);

            // Make this node the new empty leaf.
            il_set(&qt->nodes, node, node_idx_fc, -1);
            il_set(&qt->nodes, node, node_idx_num, 0);
        }
    }
    il_destroy(&to_process);
}

void qt_traverse(Quadtree* qt, void* user_data, QtNodeFunc* branch, QtNodeFunc* leaf)
{
    IntList to_process = {0};
    il_create(&to_process, nd_num);
    push_node(&to_process, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy);

    while (il_size(&to_process) > 0)
    {
        const int back_idx = il_size(&to_process) - 1;
        const int nd_mx = il_get(&to_process, back_idx, nd_idx_mx);
        const int nd_my = il_get(&to_process, back_idx, nd_idx_my);
        const int nd_sx = il_get(&to_process, back_idx, nd_idx_sx);
        const int nd_sy = il_get(&to_process, back_idx, nd_idx_sy);
        const int nd_index = il_get(&to_process, back_idx, nd_idx_index);
        const int nd_depth = il_get(&to_process, back_idx, nd_idx_depth);
        const int fc = il_get(&qt->nodes, nd_index, node_idx_fc);
        il_pop_back(&to_process);

        if (il_get(&qt->nodes, nd_index, node_idx_num) == -1)
        {
            // Push the children of the branch to the stack.
            const int hx = nd_sx >> 1, hy = nd_sy >> 1;
            const int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;
            push_node(&to_process, fc+0, nd_depth+1, l,t, hx,hy);
            push_node(&to_process, fc+1, nd_depth+1, r,t, hx,hy);
            push_node(&to_process, fc+2, nd_depth+1, l,b, hx,hy);
            push_node(&to_process, fc+3, nd_depth+1, r,b, hx,hy);
            if (branch)
                branch(qt, user_data, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
        }
        else if (leaf)
            leaf(qt, user_data, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
    }
    il_destroy(&to_process);
}

暂定

这不是一个很好的答案，但我会尝试回来继续编辑它。然而，上面的代码在几乎任何允许连续的普通旧整数数组的语言上应该是非常有效的。只要我们有那个连续的 gua运行tee，我们就可以想出一个非常缓存友好的四叉树，它使用非常小的内存占用空间。

整体思路请参考原回答

  1. Java IntList

我希望大家不要介意我发布第三个答案，但我 运行 又超出了字符数限制。我在 Java 的第二个答案中结束了 C 代码的移植。对于移植到面向对象语言的人来说，Java 端口可能更容易引用。

class IntList
{
    private int data[] = new int[128];
    private int num_fields = 0;
    private int num = 0;
    private int cap = 128;
    private int free_element = -1;

    // Creates a new list of elements which each consist of integer fields.
    // 'start_num_fields' specifies the number of integer fields each element has.
    public IntList(int start_num_fields)
    {
        num_fields = start_num_fields;
    }

    // Returns the number of elements in the list.
    int size()
    {
        return num;
    }

    // Returns the value of the specified field for the nth element.
    int get(int n, int field)
    {
        assert n >= 0 && n < num && field >= 0 && field < num_fields;
        return data[n*num_fields + field];
    }

    // Sets the value of the specified field for the nth element.
    void set(int n, int field, int val)
    {
        assert n >= 0 && n < num && field >= 0 && field < num_fields;
        data[n*num_fields + field] = val;
    }

    // Clears the list, making it empty.
    void clear()
    {
        num = 0;
        free_element = -1;
    }

    // Inserts an element to the back of the list and returns an index to it.
    int pushBack()
    {
        final int new_pos = (num+1) * num_fields;
        
        // If the list is full, we need to reallocate the buffer to make room
        // for the new element.
        if (new_pos > cap)
        {
            // Use double the size for the new capacity.
            final int new_cap = new_pos * 2;

            // Allocate new array and copy former contents.
            int new_array[] = new int[new_cap];
            System.arraycopy(data, 0, new_array, 0, cap);
            data = new_array;
    
            // Set the old capacity to the new capacity.
            cap = new_cap;
        }
        return num++;
    }
    
    // Removes the element at the back of the list.
    void popBack()
    {
        // Just decrement the list size.
        assert num > 0;
        --num;
    }

    // Inserts an element to a vacant position in the list and returns an index to it.
    int insert()
    {
        // If there's a free index in the free list, pop that and use it.
        if (free_element != -1)
        {
            final int index = free_element;
            final int pos = index * num_fields;
    
            // Set the free index to the next free index.
            free_element = data[pos];
    
            // Return the free index.
            return index;
        }
        // Otherwise insert to the back of the array.
        return pushBack();
    }

    // Removes the nth element in the list.
    void erase(int n)
    {
        // Push the element to the free list.
        final int pos = n * num_fields;
        data[pos] = free_element;
        free_element = n;
    }
}

Java 四叉树

这里是 Java 中的四叉树（抱歉，如果它不是很地道；我已经有大约十年没写 Java 了，忘记了很多东西）：

interface IQtVisitor
{
    // Called when traversing a branch node.
    // (mx, my) indicate the center of the node's AABB.
    // (sx, sy) indicate the half-size of the node's AABB.
    void branch(Quadtree qt, int node, int depth, int mx, int my, int sx, int sy);

    // Called when traversing a leaf node.
    // (mx, my) indicate the center of the node's AABB.
    // (sx, sy) indicate the half-size of the node's AABB.
    void leaf(Quadtree qt, int node, int depth, int mx, int my, int sx, int sy);
}

class Quadtree
{
    // Creates a quadtree with the requested extents, maximum elements per leaf, and maximum tree depth.
    Quadtree(int width, int height, int start_max_elements, int start_max_depth)
    {
        max_elements = start_max_elements;
        max_depth = start_max_depth;

        // Insert the root node to the qt.
        nodes.insert();
        nodes.set(0, node_idx_fc, -1);
        nodes.set(0, node_idx_num, 0);

        // Set the extents of the root node.
        root_mx = width / 2;
        root_my = height / 2;
        root_sx = root_mx;
        root_sy = root_my;
    }

    // Outputs a list of elements found in the specified rectangle.
    public int insert(int id, float x1, float y1, float x2, float y2)
    {
        // Insert a new element.
        final int new_element = elts.insert();
    
        // Set the fields of the new element.
        elts.set(new_element, elt_idx_lft, floor_int(x1));
        elts.set(new_element, elt_idx_top, floor_int(y1));
        elts.set(new_element, elt_idx_rgt, floor_int(x2));
        elts.set(new_element, elt_idx_btm, floor_int(y2));
        elts.set(new_element, elt_idx_id, id);
    
        // Insert the element to the appropriate leaf node(s).
        node_insert(0, 0, root_mx, root_my, root_sx, root_sy, new_element);
        return new_element;
    }

    // Removes the specified element from the tree.
    public void remove(int element)
    {
        // Find the leaves.
        final int lft = elts.get(element, elt_idx_lft);
        final int top = elts.get(element, elt_idx_top);
        final int rgt = elts.get(element, elt_idx_rgt);
        final int btm = elts.get(element, elt_idx_btm);
        IntList leaves = find_leaves(0, 0, root_mx, root_my, root_sx, root_sy, lft, top, rgt, btm);
    
        // For each leaf node, remove the element node.
        for (int j=0; j < leaves.size(); ++j)
        {
            final int nd_index = leaves.get(j, nd_idx_index);
    
            // Walk the list until we find the element node.
            int node_index = nodes.get(nd_index, node_idx_fc);
            int prev_index = -1;
            while (node_index != -1 && enodes.get(node_index, enode_idx_elt) != element)
            {
                prev_index = node_index;
                node_index = enodes.get(node_index, enode_idx_next);
            }
    
            if (node_index != -1)
            {
                // Remove the element node.
                final int next_index = enodes.get(node_index, enode_idx_next);
                if (prev_index == -1)
                    nodes.set(nd_index, node_idx_fc, next_index);
                else
                    enodes.set(prev_index, enode_idx_next, next_index);
                enodes.erase(node_index);

                // Decrement the leaf element count.
                nodes.set(nd_index, node_idx_num, nodes.get(nd_index, node_idx_num)-1);
            }
        }

        // Remove the element.
        elts.erase(element);
    }

    // Cleans up the tree, removing empty leaves.
    public void cleanup()
    {
        IntList to_process = new IntList(1);

        // Only process the root if it's not a leaf.
        if (nodes.get(0, node_idx_num) == -1)
        {
            // Push the root index to the stack.
            to_process.set(to_process.pushBack(), 0, 0);
        }
    
        while (to_process.size() > 0)
        {
            // Pop a node from the stack.
            final int node = to_process.get(to_process.size()-1, 0);
            final int fc = nodes.get(node, node_idx_fc);
            int num_empty_leaves = 0;
            to_process.popBack();
    
            // Loop through the children.
            for (int j=0; j < 4; ++j)
            {
                final int child = fc + j;
    
                // Increment empty leaf count if the child is an empty 
                // leaf. Otherwise if the child is a branch, add it to
                // the stack to be processed in the next iteration.
                if (nodes.get(child, node_idx_num) == 0)
                    ++num_empty_leaves;
                else if (nodes.get(child, node_idx_num) == -1)
                {
                    // Push the child index to the stack.
                    to_process.set(to_process.pushBack(), 0, child);
                }
            }
    
            // If all the children were empty leaves, remove them and 
            // make this node the new empty leaf.
            if (num_empty_leaves == 4)
            {
                // Remove all 4 children in reverse order so that they 
                // can be reclaimed on subsequent insertions in proper
                // order.
                nodes.erase(fc + 3);
                nodes.erase(fc + 2);
                nodes.erase(fc + 1);
                nodes.erase(fc + 0);
    
                // Make this node the new empty leaf.
                nodes.set(node, node_idx_fc, -1);
                nodes.set(node, node_idx_num, 0);
            }
        }
    }

    // Returns a list of elements found in the specified rectangle.
    public IntList query(float x1, float y1, float x2, float y2)
    {
        return query(x1, y1, x2, y2, -1);
    }
    
    // Returns a list of elements found in the specified rectangle excluding the
    // specified element to omit.
    public IntList query(float x1, float y1, float x2, float y2, int omit_element)
    {
        IntList out = new IntList(1);

        // Find the leaves that intersect the specified query rectangle.
        final int qlft = floor_int(x1);
        final int qtop = floor_int(y1);
        final int qrgt = floor_int(x2);
        final int qbtm = floor_int(y2);
        IntList leaves = find_leaves(0, 0, root_mx, root_my, root_sx, root_sy, qlft, qtop, qrgt, qbtm);

        if (temp_size < elts.size())
        {
            temp_size = elts.size();
            temp = new boolean[temp_size];;
        }
    
        // For each leaf node, look for elements that intersect.
        for (int j=0; j < leaves.size(); ++j)
        {
            final int nd_index = leaves.get(j, nd_idx_index);
    
            // Walk the list and add elements that intersect.
            int elt_node_index = nodes.get(nd_index, node_idx_fc);
            while (elt_node_index != -1)
            {
                final int element = enodes.get(elt_node_index, enode_idx_elt);
                final int lft = elts.get(element, elt_idx_lft);
                final int top = elts.get(element, elt_idx_top);
                final int rgt = elts.get(element, elt_idx_rgt);
                final int btm = elts.get(element, elt_idx_btm);
                if (!temp[element] && element != omit_element && intersect(qlft,qtop,qrgt,qbtm, lft,top,rgt,btm))
                {
                    out.set(out.pushBack(), 0, element);
                    temp[element] = true;
                }
                elt_node_index = enodes.get(elt_node_index, enode_idx_next);
            }
        }

        // Unmark the elements that were inserted.
        for (int j=0; j < out.size(); ++j)
            temp[out.get(j, 0)] = false;
        return out;
    }

    // Traverses all the nodes in the tree, calling 'branch' for branch nodes and 'leaf' 
    // for leaf nodes.
    public void traverse(IQtVisitor visitor)
    {
        IntList to_process = new IntList(nd_num);
        pushNode(to_process, 0, 0, root_mx, root_my, root_sx, root_sy);
    
        while (to_process.size() > 0)
        {
            final int back_idx = to_process.size() - 1;
            final int nd_mx = to_process.get(back_idx, nd_idx_mx);
            final int nd_my = to_process.get(back_idx, nd_idx_my);
            final int nd_sx = to_process.get(back_idx, nd_idx_sx);
            final int nd_sy = to_process.get(back_idx, nd_idx_sy);
            final int nd_index = to_process.get(back_idx, nd_idx_index);
            final int nd_depth = to_process.get(back_idx, nd_idx_depth);
            final int fc = nodes.get(nd_index, node_idx_fc);
            to_process.popBack();
    
            if (nodes.get(nd_index, node_idx_num) == -1)
            {
                // Push the children of the branch to the stack.
                final int hx = nd_sx >> 1, hy = nd_sy >> 1;
                final int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;
                pushNode(to_process, fc+0, nd_depth+1, l,t, hx,hy);
                pushNode(to_process, fc+1, nd_depth+1, r,t, hx,hy);
                pushNode(to_process, fc+2, nd_depth+1, l,b, hx,hy);
                pushNode(to_process, fc+3, nd_depth+1, r,b, hx,hy);
                visitor.branch(this, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
            }
            else
                visitor.leaf(this, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
        }
    }

    private static int floor_int(float val)
    {
        return (int)val;
    }
    
    private static boolean intersect(int l1, int t1, int r1, int b1,
                                     int l2, int t2, int r2, int b2)
    {
        return l2 <= r1 && r2 >= l1 && t2 <= b1 && b2 >= t1;
    }

    private static void pushNode(IntList nodes, int nd_index, int nd_depth, int nd_mx, int nd_my, int nd_sx, int nd_sy)
    {
        final int back_idx = nodes.pushBack();
        nodes.set(back_idx, nd_idx_mx, nd_mx);
        nodes.set(back_idx, nd_idx_my, nd_my);
        nodes.set(back_idx, nd_idx_sx, nd_sx);
        nodes.set(back_idx, nd_idx_sy, nd_sy);
        nodes.set(back_idx, nd_idx_index, nd_index);
        nodes.set(back_idx, nd_idx_depth, nd_depth);
    }

    private IntList find_leaves(int node, int depth, 
                                int mx, int my, int sx, int sy, 
                                int lft, int top, int rgt, int btm)
    {
        IntList leaves = new IntList(nd_num);
        IntList to_process = new IntList(nd_num);
        pushNode(to_process, node, depth, mx, my, sx, sy);
    
        while (to_process.size() > 0)
        {
            final int back_idx = to_process.size() - 1;
            final int nd_mx = to_process.get(back_idx, nd_idx_mx);
            final int nd_my = to_process.get(back_idx, nd_idx_my);
            final int nd_sx = to_process.get(back_idx, nd_idx_sx);
            final int nd_sy = to_process.get(back_idx, nd_idx_sy);
            final int nd_index = to_process.get(back_idx, nd_idx_index);
            final int nd_depth = to_process.get(back_idx, nd_idx_depth);
            to_process.popBack();

            // If this node is a leaf, insert it to the list.
            if (nodes.get(nd_index, node_idx_num) != -1)
                pushNode(leaves, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
            else
            {
                // Otherwise push the children that intersect the rectangle.
                final int fc = nodes.get(nd_index, node_idx_fc);
                final int hx = nd_sx / 2, hy = nd_sy / 2;
                final int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;
    
                if (top <= nd_my)
                {
                    if (lft <= nd_mx)
                        pushNode(to_process, fc+0, nd_depth+1, l,t,hx,hy);
                    if (rgt > nd_mx)
                        pushNode(to_process, fc+1, nd_depth+1, r,t,hx,hy);
                }
                if (btm > nd_my)
                {
                    if (lft <= nd_mx)
                        pushNode(to_process, fc+2, nd_depth+1, l,b,hx,hy);
                    if (rgt > nd_mx)
                        pushNode(to_process, fc+3, nd_depth+1, r,b,hx,hy);
                }
            }
        }
        return leaves;
    }

    private void node_insert(int index, int depth, int mx, int my, int sx, int sy, int element)
    {
        // Find the leaves and insert the element to all the leaves found.
        final int lft = elts.get(element, elt_idx_lft);
        final int top = elts.get(element, elt_idx_top);
        final int rgt = elts.get(element, elt_idx_rgt);
        final int btm = elts.get(element, elt_idx_btm);
        IntList leaves = find_leaves(index, depth, mx, my, sx, sy, lft, top, rgt, btm);

        for (int j=0; j < leaves.size(); ++j)
        {
            final int nd_mx = leaves.get(j, nd_idx_mx);
            final int nd_my = leaves.get(j, nd_idx_my);
            final int nd_sx = leaves.get(j, nd_idx_sx);
            final int nd_sy = leaves.get(j, nd_idx_sy);
            final int nd_index = leaves.get(j, nd_idx_index);
            final int nd_depth = leaves.get(j, nd_idx_depth);
            leaf_insert(nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy, element);
        }
    }

    private void leaf_insert(int node, int depth, int mx, int my, int sx, int sy, int element)
    {
        // Insert the element node to the leaf.
        final int nd_fc = nodes.get(node, node_idx_fc);
        nodes.set(node, node_idx_fc, enodes.insert());
        enodes.set(nodes.get(node, node_idx_fc), enode_idx_next, nd_fc);
        enodes.set(nodes.get(node, node_idx_fc), enode_idx_elt, element);
    
        // If the leaf is full, split it.
        if (nodes.get(node, node_idx_num) == max_elements && depth < max_depth)
        {
            // Transfer elements from the leaf node to a list of elements.
            IntList elts = new IntList(1);
            while (nodes.get(node, node_idx_fc) != -1)
            {
                final int index = nodes.get(node, node_idx_fc);
                final int next_index = enodes.get(index, enode_idx_next);
                final int elt = enodes.get(index, enode_idx_elt);
    
                // Pop off the element node from the leaf and remove it from the qt.
                nodes.set(node, node_idx_fc, next_index);
                enodes.erase(index);
    
                // Insert element to the list.
                elts.set(elts.pushBack(), 0, elt);
            }
    
            // Start by allocating 4 child nodes.
            final int fc = nodes.insert();
            nodes.insert();
            nodes.insert();
            nodes.insert();
            nodes.set(node, node_idx_fc, fc);
    
            // Initialize the new child nodes.
            for (int j=0; j < 4; ++j)
            {
                nodes.set(fc+j, node_idx_fc, -1);
                nodes.set(fc+j, node_idx_num, 0);
            }
    
            // Transfer the elements in the former leaf node to its new children.
            nodes.set(node, node_idx_num, -1);
            for (int j=0; j < elts.size(); ++j)
                node_insert(node, depth, mx, my, sx, sy, elts.get(j, 0));
        }
        else
        {
            // Increment the leaf element count.
            nodes.set(node, node_idx_num, nodes.get(node, node_idx_num) + 1);
        }
    }


    // ----------------------------------------------------------------------------------------
    // Element node fields:
    // ----------------------------------------------------------------------------------------
    // Points to the next element in the leaf node. A value of -1 
    // indicates the end of the list.
    static final int enode_idx_next = 0;

    // Stores the element index.
    static final int enode_idx_elt = 1;

    // Stores all the element nodes in the quadtree.
    private IntList enodes = new IntList(2);

    // ----------------------------------------------------------------------------------------
    // Element fields:
    // ----------------------------------------------------------------------------------------
    // Stores the rectangle encompassing the element.
    static final int elt_idx_lft = 0, elt_idx_top = 1, elt_idx_rgt = 2, elt_idx_btm = 3;

    // Stores the ID of the element.
    static final int elt_idx_id = 4;

    // Stores all the elements in the quadtree.
    private IntList elts = new IntList(5);

    // ----------------------------------------------------------------------------------------
    // Node fields:
    // ----------------------------------------------------------------------------------------
    // Points to the first child if this node is a branch or the first element
    // if this node is a leaf.
    static final int node_idx_fc = 0;

    // Stores the number of elements in the node or -1 if it is not a leaf.
    static final int node_idx_num = 1;

    // Stores all the nodes in the quadtree. The first node in this
    // sequence is always the root.
    private IntList nodes = new IntList(2);

    // ----------------------------------------------------------------------------------------
    // Node data fields:
    // ----------------------------------------------------------------------------------------
    static final int nd_num = 6;

    // Stores the extents of the node using a centered rectangle and half-size.
    static final int nd_idx_mx = 0, nd_idx_my = 1, nd_idx_sx = 2, nd_idx_sy = 3;

    // Stores the index of the node.
    static final int nd_idx_index = 4;

    // Stores the depth of the node.
    static final int nd_idx_depth = 5;

    // ----------------------------------------------------------------------------------------
    // Data Members
    // ----------------------------------------------------------------------------------------
    // Temporary buffer used for queries.
    private boolean temp[];

    // Stores the size of the temporary buffer.
    private int temp_size = 0;

    // Stores the quadtree extents.
    private int root_mx, root_my, root_sx, root_sy;

    // Maximum allowed elements in a leaf before the leaf is subdivided/split unless
    // the leaf is at the maximum allowed tree depth.
    private int max_elements;

    // Stores the maximum depth allowed for the quadtree.
    private int max_depth;
}

暂定

再次抱歉，这是一个代码转储答案。我会回来编辑它并尝试解释越来越多的东西。

整体思路请参考原回答

2。基础知识

对于这个答案（抱歉，我又 运行 超出了字符数限制），我将更多地关注针对这些结构新手的基础知识。

好吧，假设我们在 space:

中有一堆这样的元素

我们想知道鼠标光标下是什么元素，或者什么元素相互 intersect/collide，或者离另一个元素最近的元素是什么，或者诸如此类的东西。

在那种情况下，如果我们拥有的唯一数据是一堆元素位置和 space 中的 sizes/radii，我们将不得不遍历所有内容以找出元素在给定的搜索区域。对于碰撞检测，我们必须循环遍历每个元素，然后针对每个元素循环遍历所有其他元素，使其成为一种爆炸性的二次复杂度算法。这不会阻止 non-trivial 输入大小。

细分

那么对于这个问题我们能做些什么呢？一种直接的方法是将搜索 space（例如屏幕）细分为固定数量的单元格，如下所示：

现在假设您要查找鼠标光标下位于 (cx, cy) 位置的元素。在这种情况下，我们所要做的就是检查鼠标光标所在单元格中的元素：

grid_x = floor(cx / cell_size);
grid_y = floor(cy / cell_size);
for each element in cell(grid_x, grid_y):
{
     if element is under cx,cy:
         do something with element (hover highlight it, e.g)
}

碰撞检测类似。如果我们想查看哪些元素与给定元素相交（碰撞）：

grid_x1 = floor(element.x1 / cell_size);
grid_y1 = floor(element.y1 / cell_size);
grid_x2 = floor(element.x2 / cell_size);
grid_y2 = floor(element.y2 / cell_size);

for grid_y = grid_y1, grid_y2:
{
     for grid_x = grid_x1, grid_x2:
     {
         for each other_element in cell(grid_x, grid_y):
         {
             if element != other_element and collide(element, other_element):
             {
                 // The two elements intersect. Do something in response
                 // to the collision.
             }
         }
     }
}

并且我建议人们通过将 space/screen 划分为固定数量的网格单元（例如 10x10、100x100 甚至 1000x1000）来开始这种方式。有些人可能认为 1000x1000 在内存使用上会爆炸，但您可以使每个单元格只需要 4 个字节和 32 位整数，如下所示：

...此时即使是一百万个单元格也不到 4 兆字节。

Fixed-Resolution 网格的缺点

如果你问我（我个人最喜欢的碰撞检测），固定分辨率网格是解决这个问题的绝佳数据结构，但它确实有一些弱点。

假设您有一款指环王视频游戏。假设您的许多单位都是地图上的小单位，例如人类、兽人和精灵。然而，你也有一些巨大的单位，比如龙和树人。

网格固定分辨率的一个问题是，虽然你的单元格大小可能最适合存储那些大多数时候只占用 1 个单元格的小单位，如人类、精灵和兽人，但像龙这样的大家伙ents 可能想要占用许多单元格，例如 400 个单元格 (20x20)。结果我们不得不把那些大家伙塞进很多cell里，存储很多冗余数据。

另外假设您要在地图的一个大矩形区域中搜索感兴趣的单位。在这种情况下，您可能需要检查比理论上最佳更多的细胞。

这是固定分辨率网格的主要缺点*。我们最终可能不得不插入大的东西并将它们存储到比理想情况下应该存储的更多的单元格中，并且对于大搜索区域，我们可能必须检查比理想情况下应该搜索的更多的单元格。

  • That said, putting aside the theory, often you can work with grids in a way that is very cache-friendly in ways similar to image processing. As a result, while it has these theoretical disadvantages, in practice the simplicity and ease of implementing cache-friendly traversal patterns can make the grid a lot better than it sounds.

四叉树

所以四叉树是解决这个问题的一种方法。可以说，他们不是使用固定分辨率网格，而是根据某些标准调整分辨率，同时将 subdividing/splitting 分成 4 child 个单元格以提高分辨率。例如，如果给定单元格中有超过 2 children，我们可能会说一个单元格应该分裂。在那种情况下，这个：

最后变成这样：

现在我们有一个非常好的表示，其中没有单元格存储超过 2 个元素。同时让我们考虑如果我们插入一条巨龙会发生什么：

在这里，与固定分辨率网格不同，龙只能插入一个单元格，因为它占据的单元格中只有一个元素。同样，如果我们在地图上搜索一个很大的区域，我们就不必检查那么多单元格，除非有很多元素占据了这些单元格。

实施

那么我们如何实现这些东西之一呢？好吧，它最终是一棵树，而且是一棵 4 叉树。所以我们从 4 children 的根节点的概念开始，但它们目前是 null/nil 并且根现在也是叶子：

插入

让我们开始插入一些元素，再次为简单起见，假设一个节点在包含超过 2 个元素时应该拆分。所以我们将插入一个元素，当我们插入一个元素时，我们应该将它插入到它所属的叶子（单元格）中。在这种情况下，我们只有一个，根 node/cell，所以我们将把它插入那里：

... 让我们插入另一个：

...还有一个：

现在我们在一个叶节点中有两个以上的元素。现在应该分裂了。在这一点上，我们创建 4 children 到叶节点（在本例中为我们的根节点），然后 t运行sfer 将被拆分的叶节点（根节点）中的元素放入适当的 quad运行ts 基于 area/cell 每个元素在 space:

中占据

让我们插入另一个元素，并再次插入它所属的适当叶子：

...还有一个：

现在叶子中的元素又多于2个，所以我们应该把它分成4个quad运行ts (children):

这就是基本思想。您可能会注意到的一件事是，当我们插入不是无限小的点的元素时，它们很容易重叠多个 cells/nodes.

因此，如果我们有许多元素与单元格之间的许多边界重叠，它们最终可能会想要细分很多，可能无限细分。为了缓解这个问题，有些人选择拆分元素。如果您与一个元素相关联的只是一个矩形，那么将矩形切块是相当简单的。其他人可能只是对树的分裂程度设置了 depth/recursion 限制。对于这两者之间的碰撞检测场景，我倾向于选择后一种解决方案，因为我发现它至少更容易更有效地实施。然而，还有另一种选择：松散表示，这将在不同的部分中介绍。

此外，如果您的元素彼此重叠，那么即使您存储的是无限小的点，您的树也可能想要无限期地分裂。例如，如果在 space 中有 25 个点彼此重叠（这是我在 VFX 中经常遇到的情况），那么无论如何，您的树都将无限期分裂而没有 recursion/depth 限制.因此，为了处理病态情况，您可能需要深度限制，即使您将元素切块。

删除元素

第一个答案中介绍了删除元素以及删除节点以清理树并删除空叶。但基本上我们使用我提出的方法删除元素所做的只是沿着树下降到存储元素的 leaf/leaves 的位置（例如，您可以使用它的矩形来确定），然后从那些元素中删除它离开。

然后开始删除空叶节点，我们使用原始答案中介绍的延迟清理方法。

结论

我 运行 时间不够，但会尝试回到这个问题并不断改进答案。如果人们想要练习，我会建议实现一个普通的旧 fixed-resolution 网格，看看是否可以将它缩小到每个单元格只是一个 32 位整数的位置。在考虑四叉树之前先了解网格及其固有的问题，您可能会很好地处理网格。它甚至可能为您提供最佳解决方案，具体取决于您实施网格与四叉树的效率。

编辑：Fine/Coarse 网格和行优化

我对此有很多疑问，所以我将简要介绍一下。它实际上令人难以置信 dumb-simple 并且可能会让那些认为它很奇特的人失望。因此，让我们从一个简单的 fixed-resolution 网格表示开始。我将在这里使用指针使其尽可能简单（尽管我建议稍后使用数组和索引以更好地控制内存使用和访问模式）。

// Stores a node in a grid cell.
struct Node
{
    // Stores a pointer to the next node or null if we're at the end of
    // the list.
    Node* next = nullptr;

    // Stores a pointer to the element in the cell.
    Element* element = nullptr;
};

// Stores a 1000x1000 grid. Hard-coded for simple illustration.
Node* grid[1000][1000] = {};

如其他答案所述，fixed-resolution 网格实际上比它们看起来更体面，即使它们与具有可变分辨率的 tree-based 解决方案相比看起来很愚蠢。然而，它们确实有一个缺点，如果我们想搜索一个大参数（比如一个巨大的圆形或矩形区域），它们必须循环遍历许多网格单元。所以我们可以通过存储更粗糙的网格来降低成本：

// Stores a lower-resolution 500x500 parent grid (can use bitsets instead
// of bools). Stores true if one or more elements occupies the cell or
// false if the cell is empty.
bool parent_grid[500][500] = {};

// Stores an even lower-resolution 100x100 grid. It functions similarly
// as the parent grid, storing true if ane element occupies the cell or
// false otherwise.
bool grandparent_grid[100][100] = {};

我们可以继续，您可以根据需要调整分辨率和使用的网格数。通过这样做，当我们想要搜索一个大参数时，我们先检查 g运行dparent 网格，然后再搜索 parent 网格，然后再检查 parent我们检查 full-resolution 网格。我们只有在单元格不完全为空时才会继续。在很多涉及大搜索参数的情况下，这可以帮助我们从 highest-resolution 网格中排除一大堆要检查的单元格。

真的就这些了。与四叉树不同，它确实需要将所有 highest-resolution 单元存储在内存中，但我总是发现它更容易优化，因为我们不必追逐 pointers/indices 来遍历 children 每个树节点。相反，我们只是使用非常 cache-friendly.

的访问模式进行数组查找

Row-Based 优化

所以row-based优化也很简单（虽然只是ap当我们使用数组和索引而不是指向节点的指针时就存在*)。

  • Or custom memory allocators, but I really don't recommend using them for most purposes as it's quite unwieldy to have to deal with allocator and data structure separately. It is so much simpler for linked structures to emulate the effect of bulk allocation/deallocation and contiguous access patterns by just storing/reallocating arrays (ex: std::vector) and indices into them. For linked structures in particular and given that we now have 64-bit addressing, it's especially helpful to cut down the size of links to 32-bits or less by turning them into indices into a particular array unless you actually need to store more than 2^32-1 elements in your data structure.

如果我们想象这样一个网格：

... 因为我们将整个网格的所有节点都存储在一个列表结构中，所以从单元格中的一个元素到下一个元素的内存步幅可能非常大，导致我们跳过很多在内存中并因此导致更多缓存未命中（并且还将更多不相关的数据加载到缓存行中）。

我们可以通过为每个单元格存储一个完整的单独节点列表来完全消除这种情况（在这种情况下，一个单元格中的所有元素都可以完美连续地存储），但这在内存使用方面可能会非常爆炸并且效率非常低在其他方面。所以平衡是每行只存储一个单独的节点列表。我们通过这种方式改进了空间局部性，而没有大量单独的列表，因为与单元格总数相比，行数并不多 (rows * columns)。当你这样做时你可以做的另一件事是，当一行完全为空时，你甚至可以为整行的网格单元释放内存，并将整行变成空指针。

最后，这提供了更多并行化 insertion/removal/access 的机会，因为您可以保证 运行 它是安全的，前提是没有两个线程同时 modifying/accessing 同一行（某事这通常很容易确保）。

4。松四叉树

好吧，我想花一些时间来实现和解释松散四叉树，因为我发现它们非常有趣，甚至可能是最 well-balanced 对于涉及非常动态场景的最广泛用例。

所以我昨晚最终实现了一个，并花了一些时间调整、调整和分析它。这是一个有 25 万个动态代理的预告片，每个时间步都相互移动和反弹：

当我缩小以查看所有 25 万个代理以及松散四叉树的所有边界矩形时，帧速率开始受到影响，但这主要是由于我的绘图功能中的瓶颈。如果我缩小以同时在屏幕上绘制所有内容并且我根本懒得优化它们，它们就会开始成为热点。以下是它在基本层面上的工作原理，只需要很少的代理：

松四叉树

好吧，什么是松四叉树？它们基本上是四叉树，其节点没有完全沿着中心分成四个偶数象限。相反，它们的 AABB（边界矩形）可能会重叠并且比您将一个节点从中心完全拆分为 4 个象限时得到的更大或通常甚至更小。

所以在这种情况下，我们绝对必须存储每个节点的边界框，所以我这样表示：

struct LooseQuadNode
{
    // Stores the AABB of the node.
    float rect[4];

    // Stores the negative index to the first child for branches or the 
    // positive index to the element list for leaves.
    int children;
};

This time I tried to use single-precision floating point to see how it well performs, and it did a very decent job.

有什么意义？

好吧，那有什么意义呢？使用松散四叉树可以利用的主要事情是，为了插入和移除，您可以将插入到四叉树中的每个元素都视为一个点。因此，一个元素永远不会插入到整个树中的多个叶节点中，因为它被视为一个无限小的点。

但是，当我们将这些“元素点”插入到树中时，我们会扩展我们插入的每个节点的边界框，以包含元素的边界（例如，元素的矩形）。这使我们能够在执行搜索查询时可靠地找到这些元素（例如：搜索与矩形或圆形区域相交的所有元素）。

优点：

  • 即使是最大的代理也只需要插入一个叶节点，并且不会占用比最小的更多的内存。因此，它是 well-suited 对于元素大小变化很大的场景，这就是我在上面的 250k 代理演示中进行的压力测试。
  • 每个元素使用更少的内存，尤其是大元素。

缺点：

  • 虽然这加快了插入和删除的速度，但不可避免地减慢了对树的搜索速度。之前与节点的中心点进行一些基本比较以确定下降到哪个象限变成了一个循环，必须检查每个 child 的每个矩形以确定哪些与搜索区域相交。
  • 每个节点使用更多内存（在我的情况下多 5 倍）。

昂贵的查询

这第一个 con 对于静态元素来说是非常可怕的，因为我们所做的就是在这些情况下构建树并搜索它。我发现这个松散的四叉树，尽管花了几个小时来调整和调整它，但查询它有一个巨大的热点：

也就是说，这实际上是迄今为止我对动态场景四叉树的“个人最佳”实现（尽管请记住，我喜欢为此目的使用分层网格并且没有太多使用四叉树进行动态场景的经验场景）尽管有这个明显的骗局。这是因为至少对于动态场景，我们必须在每个时间步不断地移动元素，因此与树相比，除了查询它之外，还有很多事情要做。它必须一直更新，这实际上在这方面做得相当不错。

我喜欢松散四叉树的一点是，即使您除了一大堆最微小的元素外，还有一大堆大量的元素，您也会感到安全。大元素不会比小元素占用更多的内存。因此，如果我正在编写一个具有广阔世界的视频游戏，并且只想将所有内容都放入一个中央空间索引中以加速所有内容，而不像我通常那样打扰数据结构的层次结构，那么松散的四叉树和松散的八叉树可能是完美的平衡为“一个中央通用数据结构，如果我们要为整个动态世界只使用一个”。

内存使用

在内存使用方面，虽然元素占用的内存较少（尤其是大内存），但与我的节点甚至不需要存储 AABB 的实现相比，节点占用的内存要多得多。我总体上在各种测试用例中发现，包括那些具有许多巨大元素的测试用例，松散的uadtree 倾向于使用其结实的节点占用更多的内存（粗略估计大约多 33%）。也就是说，它比我原来的答案中的四叉树实现表现得更好。

从好的方面来说，内存使用更稳定（这往往会转化为更稳定和流畅的帧率）。在内存使用变得完全稳定之前，我的原始答案的四叉树花费了大约 5 秒以上。这个在启动后一两秒就会变得稳定，很可能是因为元素永远不必插入超过一次（如果小元素与两个或多个节点重叠，即使是小元素也可以在我的原始四叉树中插入两次在边界）。因此，数据结构可以快速发现所需的内存量来分配给所有情况，可以这么说。

理论

所以让我们介绍一下基本理论。我建议首先实现一个常规四叉树并在转向松散版本之前理解它，因为它们更难实现。当我们从一棵空树开始时，您可以想象它也有一个空矩形。

让我们插入一个元素：

因为我们现在只有一个根节点，它也是一个叶子，所以我们只是将它插入到那里。执行此操作后，根节点先前为空的矩形现在包含我们插入的元素（以红色虚线显示）。让我们插入另一个：

我们通过插入元素的 AABB 扩展我们插入时遍历的节点的 AABB（这次只是根节点）。让我们插入另一个，假设节点包含超过 2 个元素时应该拆分：

在这种情况下，我们在叶节点（我们的根）中有超过 2 个元素，因此我们应该将它分成 4 个象限。这与拆分常规 point-based 四叉树几乎相同，只是我们在传输 children 时再次扩展边界框。我们首先考虑被拆分节点的中心位置：

现在我们有 4 个 children 到我们的根节点，每个节点也存储它的 tight-fitting 边界框（以绿色显示）。让我们插入另一个元素：

在这里你可以看到插入这个元素不仅扩展了 lower-left child 的矩形，而且扩展了根（我们扩展了我们插入路径上的所有 AABB）。让我们插入另一个：

在这种情况下，我们在叶节点中再次有 3 个元素，因此我们应该拆分：

就是这样。现在左下方的那个圆圈呢？它似乎与 2 个象限相交。然而，我们只考虑元素的一个点（例如：它的中心）来确定它所属的象限。所以那个圆圈实际上只被插入到 lower-left 象限。

然而，lower-left 象限的边界框被扩展以包含其范围（以青色显示，希望你们不要介意，但我更改了 BG 颜色，因为它越来越难以看清颜色), 因此第 2 级节点的 AABB（以青色显示）实际上溢出到彼此的象限中。

每个象限都存储自己的矩形，该矩形始终保证包含其元素，这一事实使我们能够将元素插入到一个叶节点，即使它的区域与多个节点相交。相反，我们扩展叶节点的边界框，而不是将元素插入到多个节点。

正在更新 AABB

所以这可能会引出一个问题，AABBs 什么时候更新？如果我们只在插入元素时扩展 AABB，它们只会变得越来越大。当元素被移除时，我们如何缩小它们？有很多方法可以解决这个问题，但我是通过在我的原始答案中描述的“清理”方法中更新整个层次结构的边界框来实现的。这似乎足够快（甚至没有显示为热点）。

与网格比较

我似乎仍然无法像我的分层网格实现那样高效地实现碰撞检测，但同样，这可能更多地与我有关，而不是数据结构。我发现树结构的主要困难是很容易控制所有内容在内存中的位置以及访问方式。使用网格，您可以确保一行的所有列都是连续的并按顺序排列，例如，并确保您以顺序方式访问它们以及连续存储在该行中的元素。对于一棵树，内存访问在本质上往往有点零星，而且随着节点被分成多个 children，树想要更频繁地传输元素，内存访问也会迅速退化。也就是说，如果我想使用树状空间索引，到目前为止我真的在挖掘这些松散的变体，并且我的脑海中浮现出实施的想法一个“松散的网格”。

结论

简而言之，这就是松散的四叉树，它基本上具有常规四叉树的 insertion/removal 逻辑，它只存储点，除了它在途中 expands/updates AABB。为了进行搜索，我们最终遍历了矩形与我们的搜索区域相交的所有 child 个节点。

I hope people don't mind me posting so many lengthy answers. I'm really getting a kick out of writing them and it has been a useful exercise for me in revisiting quadtrees to attempt to write all these answers. I'm also contemplating a book on these topics at some point (though it'll be in Japanese) and writing some answers here, while hasty and in English, helps me kind of put everything together in my brain. Now I just need someone to ask for an explanation of how to write efficient octrees or grids for the purpose of collision detection to give me an excuse to do the same on those subjects.

5。 Loose/Tight 具有 50 万代理的双网格

上面是一个小 GIF，显示 500,000 个代理在每个时间步使用新的“loose/tight 网格”数据结构相互弹跳，这是我在写完有关松散四叉树的答案后受到启发而创建的。我会尝试复习一下它是如何工作的。

这是迄今为止我已经实现的所有数据结构中性能最好的数据结构（虽然它可能只是我），处理 50 万个代理比最初的四叉树处理 100k 更好，并且比松散的四叉树处理 250k 更好。它还需要最少的内存，并且在这三者中具有最稳定的内存使用。这一切仍然只在一个线程中工作，没有 SIMD 代码，没有花哨的微优化，因为我通常申请生产代码——只是几个小时工作的直接实现。

我还改进了绘图瓶颈，但没有改进我的光栅化代码。这是因为网格让我可以轻松地以一种对图像处理缓存友好的方式遍历它（在栅格化时，一个接一个地绘制网格单元格中的元素碰巧会导致非常缓存友好的图像处理模式）。

有趣的是，它的实现时间也是最短的（只有 2 小时，而我在松散四叉树上花了 5 或 6 个小时），而且它需要的代码量最少（可以说是最简单的代码） ).虽然这可能只是因为我积累了很多实施网格的经验。

Loose/Tight双网格

所以我在基础部分介绍了网格的工作原理（请参阅第 2 部分），但这是一个“松散的网格”。每个网格单元格都存储自己的边界框，该边界框可以随着元素的删除而缩小，并随着元素的添加而增大。因此，每个元素只需要根据其中心位置落在哪个单元格中插入一次网格，如下所示：

// Ideally use multiplication here with inv_cell_w or inv_cell_h.
int cell_x = clamp(floor(elt_x / cell_w), 0, num_cols-1);
int cell_y = clamp(floor(ely_y / cell_h), 0, num_rows-1);
int cell_idx = cell_y*num_rows + cell_x;
// Insert element to cell at 'cell_idx' and expand the loose cell's AABB.

单元格像这样存储元素和 AABB：

struct LGridLooseCell
{
    // Stores the index to the first element using an indexed SLL.
    int head;

    // Stores the extents of the grid cell relative to the upper-left corner
    // of the grid which expands and shrinks with the elements inserted and 
    // removed.
    float l, t, r, b;
};

然而，松散的单元会带来概念上的问题。鉴于它们具有这些可变大小的边界框，如果我们插入一个巨大的元素，这些边界框会变得很大，那么当我们想找出哪些松散的单元格和相应的元素与搜索矩形相交时，我们如何避免检查网格的每个异常单元格？可能会出现这样一种情况，我们正在搜索松散网格的右上角，但在左下角的另一侧有一个单元格已经变得足够大，也可以与该区域相交。如果没有解决此问题的方法，我们将不得不在线性时间内检查所有松散的单元格是否匹配。

... 解决方案是实际上这是一个“双网格”。松散的网格单元本身被划分为紧密的网格。当我们进行上面的类比搜索时，我们首先像这样查看紧密的网格：

tx1 = clamp(floor(search_x1 / cell_w), 0, num_cols-1);
tx2 = clamp(floor(search_x2 / cell_w), 0, num_cols-1);
ty1 = clamp(floor(search_y1 / cell_h), 0, num_rows-1);
ty2 = clamp(floor(search_y2 / cell_h), 0, num_rows-1);

for ty = ty1, ty2:
{
    trow = ty * num_cols
    for tx = tx1, tx2:
    {
        tight_cell = tight_cells[trow + tx];
        for each loose_cell in tight_cell:
        {
            if loose_cell intersects search area:
            {
                for each element in loose_cell:
                {
                    if element intersects search area:
                        add element to query results
                }
            }
        }
    }
}

紧密单元存储松散单元的单链接索引列表，如下所示：

struct LGridLooseCellNode
{
    // Points to the next loose cell node in the tight cell.
    int next;

    // Stores an index to the loose cell.
    int cell_idx;
};

struct LGridTightCell
{
    // Stores the index to the first loose cell node in the tight cell using 
    // an indexed SLL.
    int head;
};

瞧，这就是“松散双网格”的基本思想。当我们插入一个元素时，我们就像我们对松散四叉树所做的那样扩展松散单元的 AABB，只是在常数时间而不是对数时间。然而，我们也根据其矩形在常数时间内将松散的单元格插入到紧密的网格中（并且它可以插入多个单元格）。

这两者的组合（紧密网格可以快速找到松散的单元格，松散单元格可以快速找到元素）提供了一个非常可爱的数据结构，其中每个元素都被插入到一个单元格中，并具有恒定的时间搜索、插入和移除。

我看到的唯一大缺点是我们确实必须存储所有这些单元格并且可能仍然需要搜索比我们需要的更多的单元格，但它们仍然相当便宜（在我的例子中每个单元格 20 字节）并且以非常缓存友好的访问模式遍历搜索单元格很容易。

我建议尝试一下“松散网格”的想法。它可以说比四叉树和松散四叉树更容易实现，更重要的是，它可以优化，因为它立即适合缓存友好的内存布局。作为一个超级酷的奖励，如果你能提前预测你的世界中的代理数量，它几乎 100% 完美稳定并且在内存使用方面立即，因为一个元素总是恰好占据一个单元格，并且单元格总数是固定的（因为他们没有 subdivide/split）。内存使用中唯一的小不稳定性是那些松散的单元格可能会扩展并时不时地插入到较粗糙网格中的其他紧密单元格中，但这种情况应该很少见。结果，内存使用非常 stable/consistent/predictable 并且通常也是相应的帧速率。对于您想要提前预分配所有内存的某些硬件和软件来说，这可能是一个巨大的好处。

使用 SIMD 使用矢量化代码（除了多线程之外）同时执行多个连贯查询也非常容易，因为遍历，如果我们甚至可以这样称呼它的话，是平坦的（它只是一个常数-时间查找涉及一些算术的单元格索引）。因此，很容易应用类似于英特尔应用于其光线追踪 kernel/BVH (Embree) 的光线包的优化策略来同时测试多条相干光线（在我们的例子中，它们将是碰撞的“代理包”），除非没有这样的 fancy/complex 代码，因为网格“遍历”要简单得多。

关于内存使用和效率

我在有关高效四叉树的第 1 部分中对此进行了一些介绍，但如今减少内存使用通常是提高速度的关键，因为一旦您将数据放入 L1 或寄存器，我们的处理器就会非常快，但是DRAM 访问相对如此，如此之慢。即使我们有大量的慢速内存，我们仍然只有很少的宝贵快速内存。

我觉得我很幸运，当时我们不得不非常节俭地使用内存（虽然不像我之前的人那么多），即使是 1 兆字节的 DRAM 也被认为是惊人的。我当时学到的一些东西和养成的习惯（尽管我远非专家）恰好与表现相吻合。其中一些我不得不放弃，因为这些坏习惯会适得其反，而且我学会了在无关紧要的领域接受浪费。分析器和紧迫的最后期限的结合有助于让我保持高效，并且不会以过于混乱的优先事项结束。

因此，我要提供的一条关于一般效率的一般性建议，不仅仅是用于碰撞检测的空间索引，就是注意内存使用。如果它是爆炸性的，解决方案很可能不会非常有效。当然有一个灰色地带，为数据结构使用更多的内存可以大大减少处理到只考虑速度有益的程度，但很多时候减少数据结构所需的内存量，尤其是“热内存” " 被反复访问，可以转化为速度提高相当成比例。我在职业生涯中遇到的所有效率最低的空间索引都是内存使用最爆炸的。

查看您需要存储的数据量并至少粗略地计算理想情况下应该需要多少内存会很有帮助。然后将其与您实际需要的数量进行比较。如果两者相差 天壤之别 ，那么您可能会在减少内存使用量方面获得不错的提升，因为这通常会转化为从较慢形式的内存中加载内存块的时间更短在内存层次结构中。

肮脏的把戏：统一尺码

对于这个答案，我将介绍一个卑鄙的技巧，它可以让您的模拟 运行 在数据合适的情况下快一个数量级（例如，在许多视频游戏中通常会出现这种情况）。它可以让你从几万到几十万代理，或者几十万代理到几百万代理。到目前为止，我还没有在我的答案中显示的任何演示中应用它，因为它有点作弊，但我已经在生产中使用过它，它可以让世界变得不同。有趣的是，我没有看到它经常被讨论。其实我从来没见过有人讨论过有什么奇怪的。

让我们回到指环王的例子。我们有很多“人类大小”的单位，例如人类、精灵、矮人、兽人和霍比特人，我们也有一些巨大的单位，例如龙和树人。

“人性化大小”的单位大小变化不大。霍比特人可能有 4 英尺高，有点矮胖，兽人可能有 6 英尺 4 英寸高。有一些不同，但不是巨大的不同。这不是一个数量级的差异。

那么，如果我们在霍比特人周围放置一个边界 sphere/box，这是一个兽人边界 sphere/box 的大小，只是为了粗略的交集查询（在我们深入检查之前），会发生什么granular/fine 水平上更真实的碰撞）？有一点浪费的负面影响 space 但真正有趣的事情发生了。

如果我们可以预见常见情况单位的上限，我们可以将它们存储在一个数据结构中，该数据结构假定所有事物都具有 统一的上限大小 。在这种情况下会发生一些非常有趣的事情：

  1. 我们不必为每个元素存储大小。数据结构可以假定所有插入其中的元素都具有相同的统一大小（仅用于粗交集查询）。在许多情况下，这几乎可以将元素的内存使用量减半，并且当我们访问每个元素的 memory/data 较少时，它自然会加快遍历速度。
  2. 我们可以将元素存储在一个 cell/node中，即使对于没有存储在cells/nodes中的可变大小AABB的紧密表示也是如此。

只存储一个点

第二部分很棘手，但想象一下我们有这样的案例：

好吧，如果我们查看绿色圆圈并搜索其半径，如果蓝色圆圈仅作为单个点存储在我们的空间索引中，我们最终会错过蓝色圆圈的中心点。但是，如果我们搜索一个两倍于圆半径的区域呢？

在那种情况下，即使蓝色圆圈仅作为一个点存储在我们的空间索引中（橙色的中心点），我们也会找到交点。只是为了直观地表明这是可行的：

在这种情况下，圆没有相交，我们可以看到圆心甚至在扩大的双倍搜索半径之外。因此，只要我们在假设所有元素都具有统一上限大小的空间索引中搜索两倍半径，如果我们搜索两倍于上限半径的区域（或AABB 的矩形半尺寸的两倍）。

现在这看起来很浪费，因为它会在我们的搜索查询中检查 cells/nodes 超出必要的数量，但这只是因为我画图是为了说明目的。如果你使用这个策略，你会用它来处理尺寸通常是单个叶子尺寸的一小部分的元素 node/cell.

巨大的优化

因此，您可以应用的一个巨大优化是将您的内容分成 3 种不同的类型：

  1. 像人类、兽人、精灵和霍比特人一样具有常见上限的动态集（不断移动和动画）。我们基本上在所有这些代理周围设置了相同大小的边界 box/sphere。在这里，您可能会使用紧密表示，例如紧密四叉树或紧密网格，它只会为每个元素存储一个点。您还可以将同一结构的另一个实例用于超级小元素，例如具有不同常见大小写上限大小的仙女和小精灵。
  2. 比任何可预见的常见情况上限都大的动态集，例如具有非常不寻常大小的龙和实体。在这里您可以使用松散的表示形式，例如松散的四叉树或我的“loose/tight 双网格”。
  3. 一个静态集，您可以负担得起构建时间较长或更新效率非常低的结构，例如静态数据的四叉树，它以完全连续的方式存储所有内容。在这种情况下，只要数据结构提供最快的搜索查询，更新数据结构的效率有多低都无关紧要，因为您永远不会更新它。您可以将其用于您世界中的元素，例如城堡、路障和巨石。

因此，如果可以应用这种将具有统一上限范围（边界球体或边界框）的常见元素分开的想法，它可能是一种非常有用的优化策略。这也是一个我没有看到讨论的问题。我经常看到开发人员谈论分离动态和静态内容，但是通过进一步分组常见情况下大小相似的动态元素并将它们视为具有统一的上限大小，您可以获得同样多的改进，甚至更多粗碰撞测试的作用是允许它们像无限小的点一样存储，只插入到紧密数据结构中的一个叶节点。

论“作弊”的好处

所以这个解决方案不是特别聪明或有趣，但我觉得它背后的思维方式值得一提，至少对于像我这样的人来说是这样。我浪费了我职业生涯的很大一部分时间来寻找“超级”解决方案：一种适用于所有数据结构和算法的数据结构和算法可以很好地处理任何用例，希望能够提前花一点额外的时间来获得它正确，然后在遥远的未来和不同的用例中疯狂地重复使用它，更不用说与许多寻求相同的同事一起工作了。

并且在不能为了提高生产力而过度牺牲性能的情况下，热切地寻找此类解决方案既不会导致性能也不会提高生产力。因此，有时最好停下来看看软件特定数据要求的性质，看看我们是否可以“作弊”并针对这些特殊要求创建一些“量身定制”的、适用范围更窄的解决方案，如本例所示。有时，在不能为了另一个而过度妥协的情况下，这是获得性能和生产力的良好组合的最有用方法。