3

Conways Game of Life のコーディングに忙しく、ライフサイクルごとにチェックする必要があるセルを記録するデータ構造を使用して最適化しようとしています。

すべての生きているセルとその隣接セルの記録を保持するために、arrayList を動的データ構造として使用しています。ゲームの速度を向上させる、より良いデータ構造またはより短いリストを保持する方法はありますか?

多くのセルがチェックされても変更されないことが多いため、これを尋ねます。そのため、実装を改善できると感じています。

4

2 に答える 2

4

Hashlifeアルゴリズムが役立つと思います。

四分木(各内部ノードが正確に 4 つの子を持つツリー データ構造) を使用してデータを保持し、ハッシュ テーブルを使用して四分木のノードを格納するというアイデアを提供します。

さらに読むために、 Eric Burnett によって書かれたこの投稿は、 Hashlifeがどのように機能するか、そのパフォーマンスと実装 (ただし Python で)についての優れた洞察を提供します。一読の価値ありです。

于 2013-09-13T19:43:37.607 に答える
2

私は、2Mhz 6800 8 ビット コンピューターを使用して、1970 年代にスクリーン ピクセルに直接マッピングされた 256x512 ビット グリッドで動作する Life エンジンを構築しました。結果を確認したかったのですが、Life 画像をディスプレイにコピーする意味がわからなかったので、ディスプレイ ピクセル (1 ビット オン/オフ ホワイト/ブラック) で直接実行しました。

その基本的なトリックは、通常のように生きている隣人を数えるのではなく、生命のルールに基づいて「このセルがオン」のブール論理式を評価する問題の 1 つとして問題を扱うことでした。この式は非常に簡単に理解できるので、宿題として残します。高速化したのは、ブール式がビットごとに計算され、一度に 8 ビットを処理したことです。画面を下方向にスイープして行を横切る場合、本質的に、非常に低いオーバーヘッドで N ビット (6800 では 8、最新の PC では 64) を一度に評価できます。気が狂った場合は、SIMD ベクトル拡張を使用して、「一度に」256 ビット以上を実行できる可能性があります。一番上は、GPUでこれを行うことです。

6800 バージョンは、約 0.5 秒で完全な画面を処理します。更新が画面を上から下に波及するのを見ることができます (60 Hz リフレッシュ)。クロック レートの 1000 倍 (1 GHz は非常に簡単に取得できます) で、一度に 64 ビットの最新の CPU では、毎秒数千のフレームを生成できるはずです。速すぎて走っているのが見えない :-{

有用な観察は、ライフ ワールドの多くが死んでおり (空白)、その部分を処理することでより多くの死細胞が生成されることです。これは、スパース表現を使用することを示唆しています。別のポスターは四分木を提案しましたが、これは非常に良い提案だと思います。四分木領域も正方形である必要はありません。

この 2 つのアイデアを組み合わせると、非空白領域の四分木と、四分木によって指定されたビットのブロックのビットレベル処理を組み合わせることで、驚くほど高速な Life アルゴリズムが得られる可能性があります。

于 2013-09-13T19:55:58.940 に答える