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，这可以在一定程度上简化实现。

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