別のGame of Life質問（無限グリッド）？

Question

私はConwayのGame of lifeで遊んでいて、最近はHashlifeやGollyのような驚くほど速い実装を発見しました。 （ここでGollyをダウンロードしてください - http://golly.sourceforge.net/）

私が頭を奪うことのできないことの1つは、コーダーが無限グリッドをどのように実装するのでしょうか？あなたがゴリを走らせて、いくつかのグライダーを取得してエッジから飛び出し、数分待ってすぐにズームアウトすると、宇宙に飛び出している宇宙にグライダーがまだ残っているのを見ると、無限の配列を保つことはできません。どのように神の名前でこの無限の概念は、プログラムで扱われるのですか？十分に文書化されたパターンがありますか？

ありがとうございました

Answer 1

Wikipedia explains itです。 基本的な考え方は、情報がパターンサイズに比べて遅い速度で移動し、充填された細胞の最大密度がどの領域の細胞の約1/2であるため、ConwayのGame of Lifeが局所性を示すことです。 （Moreは混雑により細胞を殺します。）

局所性があるため、異なるセクションでフィールドを区切り、それぞれのセクションを個別にシミュレートすることができます。あなたの地域をよく選ぶと、同じパターンがよく見えます。それらのパターンをルックアップテーブルに展開して格納する方法をシミュレートすることで、同じパターンの他のインスタンスを複数回シミュレートする必要はありません。隣接するパターンをより大きな「メタパターン」に組み合わせることで、それらをあらかじめ計算することができます。

Answer 2

この状況では、いくつかの種類の疎な行列を持つリビングノードを表すことができます。たとえば、Nodesの配列の代わりに(LivingNode, Coordinate)のペアのリストを格納する場合、配列のサイズを増やすのではなく、Coordinatesを単に変更しています。したがって、これに必要なスペースはLivingNodesの数に比例します。

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

EDIT：これは私の頭の上から外れていたので。よりよく考えられた解決策を示すWikipedia has an articleが出ています。しかたがない！ ：） 楽しい。