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

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 であり、実装をいくらか簡素化できることに注意してください。

ここで問題が発生した場合は、一歩下がって、類似しているがより単純なデータ構造に最初に取り組むことをお勧めします。たとえば、ソース コードを参照せずに Red-Black または AVL ツリーを実装してみてください。C プログラミングにある程度精通していない場合、クアッド ツリーは適度に複雑であるため、最初のプロジェクトには適していない可能性があります。

于 2011-08-02T22:06:30.607 に答える
1

「オブジェクト指向」に使用するすべての例がメソッド呼び出しである場合、物事を C に変換するのは非常に簡単です。ポリモーフィズム (同じ名前のメソッドを持つ 2 つの異なるサブクラス) や継承などを実装する必要がある場合にのみ、少し難しくなります。 .

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 に答える