c - "Pure"用于碰撞检测的 C 四叉树

Question

我一直在研究四叉树及其在视频游戏代码中的碰撞检测中的用法。

但是，到目前为止，所有实现都依赖于 C++、C#、javascript 和 Lua 的面向对象特性来完成每个节点，我完全不知道如何将其转换为原始 C。

目标是针对 Actor (不断移动)和地形(静态)测试多个对象(镜头)。然后是带地形的 Actor 。
由于我找不到可以用“纯”C 术语阅读的示例(即不使用方法或自引用对象)，因此我什至无法掌握如何对其进行编码的基本思想，但我确实理解背后的思想算法。我不知道如何设置它，如何引用它，我应该使用什么数据类型，或者任何东西。我对 C++ 一无所知，这使得将其翻译成 C 是不可能的。

同样，我将使用地形贴图，我想做一些高或宽的 map ，而不是完美的正方形。四叉树仍然适用于这样的 map 吗？

此外，还会有许多移动元素，地形是游戏中唯一的静态部分(移动 block 或门等元素是单独的实体)。如果经常需要更新，是否值得使用四叉树？我什至需要将其设为全局数据吗？ (也可以在某些函数内部伪造，然后在启用碰撞时传递)。在这种情况下我需要为它分配内存吗？

Answer 1

因为您是在毫无开始的情况下寻求帮助，所以我将向您展示一些可能有效的示例数据结构以及 API。

在 C 语言中，可以使用结构来实现节点。像这样的东西:

struct quadtree {
    int size;
    struct node *root;
};

struct node {
    struct node *children[4];
};

然后要将对象粘贴到四叉树中，您可以添加一些额外的字段。

struct object {
    int x, y;
    // plus extra info not related to quadtree
};

struct node {
    struct node *children[4];
    int nobjects;
    struct object *objects;
};

四叉树接口(interface)将为您提供一些基本操作:

void quadtree_insert(struct quadtree *q, struct object *obj);
void quadtree_remove(struct quadtree *q, struct object *obj);
// Equivalent to remove + insert, but more efficient
void quadtree_move(struct quadtree *q, struct object *obj, int x, int y);
int quadtree_query(struct quadtree *q, struct object **obj, int max,
                   int x0, int y0, int x1, int y1);

基本上就是这样。但实现不会是微不足道的。请注意，此四叉树的最大深度约为 32，这可以在一定程度上简化实现。

如果您在这里遇到问题，我建议您退后一步，先处理一个类似但更简单的数据结构。例如，尝试在不使用源代码作为引用的情况下实现 Red-Black 或 AVL 树。如果您不太精通 C 编程，那么四叉树可能不是第一个项目的糟糕选择，因为它的复杂性适中。