2

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

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

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

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

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

4

2 回答 2

2

因为您是在毫无开始的情况下寻求帮助，所以我将向您展示一些可能有效的示例数据结构以及 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;
};

四叉树接口将为您提供一些基本操作：

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 编程，那么四叉树可能不是第一个项目的糟糕选择，因为它的复杂性适中。

于 2011-08-02T22:06:30.607 回答
1

如果您用于“面向对象”的所有示例都是方法调用，那么将事物转换为 C 非常容易。如果您需要实现多态性（具有相同名称的两个不同子类）或继承之类的东西，它只会变得更加困难.

在 C 中创建一个类：

//Define your struct, containing all instance attributes
typedef struct Tree{
    int something;
    struct Tree * child; //must use the long "struct Tree*" here, long story...
} Tree;

//to create a method, just make a normal function that receives a pointer to the
// object as the first parameter

void init_tree(Tree* this, /*arguments*/)
{
    //constructor logic would come here

    //Note that "this" is NOT a magic/reserved word in C.
    //I'm only using it to make the correspondence with the OO
    // stuff more obvious.
}

void insert(Tree* this, /*whatever the arguments are*/)
{
    //You can acess the properties of a struct pointer with "->"
    this->child = /*...*/;
}

//Using the class:
int main(){
    Tree * my_tree = malloc(sizeof Tree);
    init_tree(my_tree);
    ...
    free(my_tree);
}

正如评论中已经提到的那样，您可能应该首先尝试制作一个更简单的数据结构，例如链接列表，以学习如何处理指针等。模拟“OO”的基本思想保持不变。

于 2011-08-02T22:06:09.840 回答