c - マップを表すテキスト ファイルを四分木構造に解析します

Question

学校の課題として疑似ウルフェンシュタイン 3D を作成する必要があり、マップを表す構造が必要です。すべての計算は 2 次元グリッドに基づいているため、四分木が必要だと考えました。

たとえば、これを含むファイルをどのように解析しますか。

1 1 1 1 1 1 1 1

1 0 0 0 0 0 0 1

1 0 0 1 0 0 0 1

1 0 0 1 0 0 0 1

1 0 0 1 0 0 0 1

1 1 1 1 1 1 1 1

1 は壁ブロックで、0 は空のブロックで、四分木構造になっていますか?

Answer 1

トップダウン方式でツリーを構築できます: 配列全体 (次元が 8x8 であるとしましょう) が 0 と 1 で構成されていると仮定して、たとえば 4x4 タイルに分割します。次に、各タイルに 1 のみ、0 のみ、または両方が含まれているかどうかを確認します。タイルに両方が含まれている場合は、再度分割 (2x2) して再チェックします。「ピクセル」レベル (1x1) になるまで繰り返します。これは、隣接する 4 つのタイルへのポインターを含む構造体に格納できます。

ウィキペディアのこの写真は、それがかなり良いことを示しています。

Answer 2

ここにはいくつかのオプションがあります。1 つの方法は、ファイル全体をメモリからある種の配列に読み込み、そこからトップダウンで四分木を構築することです。マップが非常に巨大でない限り、これがおそらく最も簡単な方法です。

別のオプションは、下部の個々のノードからボトムアップでツリーを構築することです。次に、読み取ったものから親ノードを形成するのに十分なノードを解析したら、そうします。この例では、読み取った値ごとにリーフ ノードを形成します。次に、偶数行の偶数列で、葉ノードを形成した後、そこから第 2 レベルのノードを形成します。

次のような構造が得られます。

1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2
1 1 1 1 1 1 1 1
1 2 1 3 1 2 1 3
1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2
1 1 1 1 1 1 1 1
1 2 1 3 1 2 1 4

各数字は、その位置の数字を読み取ると形成されるノードの最高レベルを表します。また、各レベルの下にすべてのレベルを形成します (つまり、レベル 3 では、レベル 2 ノードとリーフ (レベル 1) ノードも形成します)。