2

小さなプロジェクトに取り組んでいますが、マップを効率的にすることを考えています。私は数字のグリッドを持っています

100110
011011
010110

ダンジョンキーパーをプレイしたことがある場合、0は平らな掘り出された正方形であり、1はまだ立っている正方形であるという考えです。グリッドレイアウトを利用して、使用する頂点の数を最小限に抑えたいと考えています。したがって、次のような領域に個別のキューブを使用する代わりに、

1111
1111
1111

私は8を使いたいだけです。これへの最善のアプローチについて何かアイデアはありますか？または、使用するアルゴリズムのタイプの名前を知っているだけです。ボトルネックレンダリングを行わないように、オンザフライですばやく実行できるものが望ましいでしょう。

4

1 に答える 1

2

これはおそらくパフォーマンスの問題ではないことに同意しますが、(わずかに変更された) 不均衡な Quad-tree を使用して、圧縮されたマップでマップを表すことができます。

  • 1 だけで構成されるマップから始めます。これをサイズ n*n のボックスとしてツリーのルート ノードに格納できます。

  • ボックスの 1 つを掘り出したい場合は、ツリーを再帰的にたどり、デフォルトのクワッド ツリー ルールを使用して n*n ボックス (またはそこにあるもの) を分割します (= n*n ボックスを 4 つの n/2* に分割します)。 n/2 ボックスなど)。ある時点で、単一のボックス (掘り出したいボックス) のみを含むツリーの葉に到達し、それを 1 から 0 に変更できます。

  • さらに、リーフが変更され、再帰呼び出しが返された後 (= ルート ノードに向かってツリーを上って戻る)、隣接するボックスをチェックして、それらがマージされるかどうかを確認できます。(両方とも掘り出された 2 つの隣接するボックスがある場合は、それらをマージできます)。

このような低次元データにインデックスを付けるときに使用されることがあるもう 1 つの手法は、空間充填曲線です。平均局所性が高く可逆的なものは、ヒルベルト曲線です。基本的に、スペース充填曲線に沿ってボックス (掘り出したものと塗りつぶしたもの) を列挙し、単純なランレングス圧縮を使用することができます。

ツリーのアイデアにより、レンダリングされるジオメトリの数を減らすことができます (テクスチャなどを再スケーリングして、単一の大きなボックスで n*n ボックスをエミュレートできます)。スペース充填曲線は、おそらくメモリを節約するだけです。

于 2012-07-06T16:46:47.220 に答える