“纯”C四叉树用于碰撞检测目的
我一直在研究四面体及其在video游戏代码中的碰撞检测中的用法。
但是，到目前为止，所有实现依赖于C ++，C＃，javascript和Lua的面向对象特性来完成每个节点，而我完全不知道如何将其转换为原始C。
目标是针对演员（不断移动）和地形（静态）测试多个对象（镜头）。 然后演员与地形。 由于我找不到一个例子，我可以用“纯”C语言（即不使用方法或自引用对象）阅读，我甚至无法掌握如何编码它的基本思想，而我确实理解了背后的想法。算法。 我不知道如何设置它，如何引用它，我应该使用什么数据类型，或者任何东西。 我完全不知道C ++，这使得将它转换为C是不可能的。
同样，我将使用瓷砖地图作为地形，我想做的事情，如高或宽的地图，而不是完美的正方形。 四叉树仍然适用于这样的地图？
此外，还会有许多移动元素，即地形是游戏中唯一的静态部分（移动块或门等元素是独立的实体）。 如果经常需要更新，是否值得使用四叉树？ 我甚至需要制作全球数据吗？ （也可以在某个函数中伪造，然后在启用碰撞时传递）。 在这种情况下，我是否需要为它分配内存？
因为您一开始就无需寻求帮助，所以我将向您展示一些可能有用的示例数据结构以及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编程，那么由于其中等复杂性，四叉树可能是第一个项目的不良选择。
如果您的所有示例都用于“面向对象”，则方法调用很容易将事物转换为C.如果您需要实现诸如多态（具有相同名称的方法的两个不同子类）或inheritance之类的东西，那将变得更加困难。
要在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”的基本思想保持不变。