タイルデータをレイヤー複数レイヤーあたり1億個以上のタイルに保存する

Question

問題：マップクラスのタイルデータを保存しようとしています。私はレイヤーごとにパレットを使用するというアイデアを持っていました。パレットはレイヤー内のデータを記述し、各バイトがタイルタイプを表すバイト配列になります。

これは、1億のタイル1層が~96mbに等しいことを意味します。しかし、私は実際に1バイトにどれくらいのデータを格納できるのか見落としてしまい、もちろん256タイルしか格納できません。 256 *タイルサイズのテクスチャサイズの平方根になります（この場合、タイルサイズは16です）。 256 * 256のテクスチャサイズは、各パレットが1つのテクスチャしか持つことができないほど小さすぎます。私がレイヤーに持つことができるタイルを厳しく制限しています。

タイルデータを格納するために1バイトの代わりに2バイト（短い）を使用するかのようにバインドされています。メモリ使用量を2倍にして1レイヤあたり〜192MBになります。私は最低でも4つのレイヤーが必要です。最終製品を768MBのラムに膨らませた。私はまた、各バイトの配列オフセットもその位置の記述であるため、データ内のデータを記述することはできません。

私はこのデータをより効率的に保存する方法があります。最悪のシナリオでは、このすべてをディスクに保存し、ディスクからメモリにバッファリングする必要があります。しかし、私はそれを記憶しておくことを好むでしょう。

私は数時間で何かスマートに思いつくことができると思うが、私はこの問題に対処するために何も知られていない一般的な方法があるかどうかを尋ねると思った。

Answer 1

Hilbert curveのようなスペースの塗りつぶし曲線を使用して2次元平面にマッピングする配列でデータを表現することをお勧めします。

次に、Huffman codingとrun-length encodingの組み合わせを使用して圧縮します。これは、データがローカルで繰り返されることが多い（つまり、すべて同じタイルであるセクションが多数ある場合）、特に効果的です。

この圧縮は、たとえば256タイルのブロックで行います。次に、特定のバイト数が圧縮データのどのくらいの範囲にあるかを示すオフセットの配列を持ちます。例えば、バイト位置103、及び第3のブロック（タイル512）の開始時であるかもしれない第二のブロック（タイル256）の開始位置192

であるかもしれない

次にアクセスすると言いますこれは2番目のブロックからのものなので、2番目のブロック（この場合は103番目のバイトから191番目のバイトまで）を伸長し、400-256 = 144のタイルを取得します。この圧縮解除されたデータを現時点で保存（キャッシュ）しておけば、近くのタイルを取得している場合には、この圧縮解除されたブロックにも格納されます。おそらく、オフセットの配列では、最近ブロックされたブロックと、キャッシュ内のどこにブロックが含まれているかを含める必要があります。

変更を許可する場合は、データ構造を1つの大きな配列からベクトルのベクトルに変更する必要があります。圧縮されているかどうかにかかわらず、各ベクトルのインジケータがあります。変更を行うときは、ブロックの圧縮を解除して変更し、メモリが不足しているときに最も最近に変更されたブロックを再圧縮します。

---

または、ファイル全体に構造体をダンプするだけで、ファイルをmemory mapにすることができます。これははるかに簡単ですが、追加のI/Oに起因するデータとアクセスパターンの圧縮率によっては遅くなる場合があります。