«Чистое» C-дерево для использования в целях обнаружения столкновений - PullRequest
Новая
       8

«Чистое» C-дерево для использования в целях обнаружения столкновений

2 голосов
/ 03 августа 2011

Я изучал квадродерева и их использование для обнаружения столкновений в коде видеоигры.

Тем не менее, все реализации до сих пор полагаются на объектно-ориентированные возможности C ++, C #, javascript и Lua для выполнения каждого узла, и у меня нет абсолютно никакой идеи о том, как перевести это в необработанный C.

Цель состоит в том, чтобы протестировать несколько объектов (выстрелов) против действующих лиц (постоянно движущихся) и местности (статических). Затем актеры с местности. Поскольку я не могу найти пример, который могу прочитать в «чистых» терминах C (то есть, не используя методы или объекты, ссылающиеся на себя), я даже не могу понять основную идею, как его кодировать, хотя я понимаю идею, лежащую в основе алгоритм. Я не знаю, как его настроить, как ссылаться на него, какие типы данных я должен использовать или что-то вообще. Я абсолютно ничего не знаю о C ++, что делает его перевод на C невозможным.

Также я буду использовать мозаичные карты для ландшафта и хочу делать такие вещи, как карты высокого или широкого размера, а не идеальные квадраты. Quadtree все еще работает с такой картой?

Кроме того, будет множество движущихся элементов, поскольку рельеф является единственной статичной частью в игре (такие элементы, как движущиеся блоки или двери являются отдельными объектами). Стоит ли использовать квадродерево, если обновления будут требоваться часто? Нужно ли вообще делать это глобальными данными? (может также быть подделан внутри некоторой функции и затем передан, когда столкновения включены). Нужно ли выделять для этого память в таком случае?

Ответы [ 2 ]

2 голосов
/ 03 августа 2011

Поскольку вы просите о помощи, не имея абсолютно ничего для начала, я покажу вам несколько примеров структур данных, которые могут работать, а также API.

В C можно реализовать узлы со структурами,Примерно так: 

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

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

А затем, чтобы прикрепить объекты в дереве quadtree, вы можете добавить несколько дополнительных полей. 

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

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

Интерфейс дерева quadtree даст вам несколько основных операций: 

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, тогда квад-дерево может оказаться плохим выбором для первого проекта из-за его умеренной сложности.

1 голос
/ 03 августа 2011

Если все ваши примеры, используемые для «объектной ориентации», являются вызовами методов, очень легко перевести вещи в 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);
}

Как уже упоминалось в комментариях, вам, вероятно, следует сначала попытаться создать более простую структуру данных, например, связанный список, чтобы научиться обращаться с указателями и т. Д. Основные идеи эмуляции «ОО» остаются прежними.

...