“纯"用于冲突检测的C四叉树 [英] "Pure" C quadtree to use for collision detection purposes

问题描述

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

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

目标是针对角色(不断移动)和地形(静态)测试多个对象(镜头).然后是演员们的地形. 由于找不到我可以用纯" C术语(即不使用方法或自引用对象)阅读的示例，因此，即使我确实理解了C背后的思想，我也什至无法掌握如何编写它的基本思想.算法.我不知道如何设置它，如何引用它，我应该使用什么数据类型或什么都没有.我对C ++完全一无所知，这使得将其转换为C成为不可能.

同样，我将使用图块地形图，并且我想做一些像高或宽的地图，而不是完美的正方形的事情.四叉树仍然可以与这样的地图一起使用吗?

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

解决方案

由于您从一开始就没有任何帮助，因此我将向您展示一些可能有效的示例数据结构以及一个API./p>

在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编程，那么由于第一个项目的复杂程度适中，因此四叉树可能不是一个好的选择.

I have been studying about quadtrees and their usage in collision detection in videogame code.

However, all the implementations so far rely on object-oriented features of C++,C#, javascript and Lua to do every node, and I have absolutely no idea of how to translate that to raw C.

The objective is to test multiple objects (shots) against actors (constantly moving) and terrain (static). Then actors with terrain. Since I cannot find an example I can read in "pure" C terms (that is, not using methods or self-referencing objects), I cannot even grasp the basic idea of how to code it, while I do understand the idea behind the algorithm. I don't know how to set it up, how to reference it, what datatypes should I use, or anything at all. I know absolutely nothing of C++, which makes translating it to C impossible.

As well, I will be using tilemaps for terrain, and I want to do things like maps that are tall or wide, not perfect squares. A quadtree still works with such a map?

Also, there will be a number of moving elements, being the terrain the only static part in play (elements like moving blocks or doors are separate entities). Is it worth it using a quadtree if updates will be required often? Do I even need to make it global data? (could as well be forged inside some function and then passed around when collisions are enabled). Do I need to allocate memory for it in such a case?

解决方案

Because you are asking for help with absolutely nothing to start with, I'll show you some example data structures that might work, as well as an API.

In C, one would implement nodes with structures. Something like this:

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

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

And then to stick objects in the quadtree, you can add some extra fields.

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

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

The quadtree interface would give you some basic operations:

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);

That's it, basically. But the implementation will not be trivial. Note that the maximum depth of this quadtree is about 32, which can simplify the implementation somewhat.

If you're having problems here, I suggest taking a step back and tackling a similar but simpler data structure first. For example, try implementing a Red-Black or AVL tree without using source code as a reference. If you're not somewhat well-versed in C programming, then a quad tree may be a poor choice for a first project due to its moderate complexity.

这篇关于“纯"用于冲突检测的C四叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！