セルラーオートマトンの高速化

Question

何らかのアルゴリズムなどを使えば、セルオートマトンを高速化することは可能でしょうか？使っています XNA で作成された Conway のライフ ゲームの実装 それは完璧に動作しますが、問題は、128x128 セルより大きいグリッドを使用すると、非常に遅くなるということです。

コードや XNA がテクスチャや描画を処理する方法とは関係ないと思いますが、非常に多くのセルを更新するという事実 (つまり、隣接するセルのそれぞれを評価し、それに基づいて新しい状態を取得します)。 多く 計算の。

もちろん、理想的なセルオートマトンは無限に大きくなければなりませんが、現実にはそれは不可能です。しかし、私の意見では、128x128 は実際にシステムがどのように動作するかを確認するには小さすぎます。

助けていただければ幸いです。

Answer 1

もし、あんたが これを試して 何度か繰り返すと、時間の経過がわかります。

推測すべきではありませんが、私の推測では、基本的にすべての時間はレンダリングに費やされていると考えられます。近傍の評価は多くのコードのように見えるかもしれませんが、おそらく非常に単純です。変更されていないセルの再レンダリングを回避する方法があれば、大幅な節約になる可能性があります。

Answer 2

OpenGLとGLSLを使用することをお勧めします。これにより、CPUからGPUへのデータ転送を排除し、10倍以上の素晴らしいスピードアップを獲得できます。

Answer 3

HashLifeアルゴリズムは、クアッドツリー、ハッシュ、および暗記を使用して、パフォーマンスの大幅な増加のためにCAの時間と空間を圧縮します。チェックアウト ゴリー 実装の例。

私はまだ自分でそれを理解し、良いライブラリを探しています。

ここには良い説明があります（コードの例を使用）： http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478.