16

私はコンウェイのライフ ゲームをいじっており、最近、Hashlife や Golly などの驚くほど高速な実装を発見しました。(Golly のダウンロードはこちら - http://golly.sourceforge.net/ )

私が理解できないことの 1 つは、コーダーが無限グリッドをどのように実装するのかということです。何の無限の配列を保持することはできません. ゴリゴリと走って数機のグライダーが端を通り過ぎて飛び立ち、数分待ってすぐにズームアウトすると、グライダーがまだ宇宙に逃げているのが見えます.それでは、神の名において、この無限の概念はプログラムでどのように処理されるのでしょうか? よく文書化されたパターンはありますか？

どうもありがとう

4

2 に答える 2

7

この状況では、生きているノードをある種の疎行列で表すことができます。たとえば、それぞれが生きているか死んでいるか(LivingNode, Coordinate)の配列の代わりにペアのリストを保存する場合、配列のサイズを大きくするのではなく、単純に変更しています。したがって、これに必要なスペースは の数に比例します。NodesCoordinatesLivingNodes

このソリューションは、生きているノードの数が絶えず増加している州では機能しませんが、グライダーでは非常にうまく機能します。

編集：それは私の頭のてっぺんから外れていました。ウィキペディアには、よりよく考え抜かれた解決策を示す記事があることがわかりました。しかたがない！：） 楽しみ。

于 2009-09-26T23:32:42.787 に答える
6

ウィキペディアで説明しています。基本的な考え方は、コンウェイのライフ ゲームは局所性を示すというものです。これは、情報がパターン サイズに比べて低速で移動し、塗りつぶされたセルの最大密度が任意の領域のセルの約 1/2 であるためです。(より多くは、過密状態のために細胞を殺します。)

局所性があるため、フィールドを異なるセクションに分けて、各セクションを個別にシミュレートできます。地域をうまく選べば、同じパターンがよく見られます。それらがどのように進化し、結果をルックアップ テーブルに保存するかをシミュレートできるため、同じパターンの他のインスタンスを複数回シミュレートする必要はありません。隣接するパターンをより大きな「メタパターン」に結合すると、それらも事前に計算できます。

于 2009-09-26T23:31:03.103 に答える