hashlife その2
前回のつづき。
今回は解説もしてみた。
使い方
環境はsbclで、quicklispがインストール済、かつlisp-builder-sdlが動く状態になっていること(これがちょっと面倒なんだけど…)。
$ ./hashlife.lisp
と打つとpuffer trainが動き出すはず。
キー操作は
- ↑↓←→: 移動
- Ctrl ↑/↓: ズームイン/アウト
- Shift ↑/↓: スピードアップ/ダウン
- スペース: 一時停止/解除
- f: フルスクリーンモード/解除
- c: クリア
- q: 終了
あとマウスでお絵描きができる。
右下を掴むと画面サイズが変えられるが、画面の内部で掴むとお絵描きも発動してしまうので気持ち画面の外側を掴んでもらえれば。
あと.rle形式と.lif形式のファイルが読めて、例えばGollyについてくる宇宙船ブリーダー*1は
$ ./hashlife.lisp ~Downloads/golly-2.6-mac109/Patterns/Life/Breeders/LWSS-breeder.rle
みたいな感じで動かせる。壮観。
puffer train(フルスクリーンモード)
そもそもhashlifeってなに
Gosperにより考案されたアルゴリズムで、フィールドを一つ一つの升目ではなく4分木として扱うのが特徴。
基本データ構造であるnodeは 2^n x 2^n の正方形のフィールドを表す。以下nをレベルと呼ぶ。各ノードは5つのフィールド: nw、ne、sw、se、RESULT を持つ。nw〜se は自身の1/4の大きさの子ノードで、例えば今考えているノードが 2^4 x 2^4 の大きさ(level 4)であれば子ノードは全て 2^3 x 2^3 の大きさ(level 3)である。RESULTも子ノードと同じ大きさのノードなのだが、後述。
+---------------+ +-------+-------+
| | | | |
| | | | |
| | | | |
| | | nw | ne | +-------+
| | | | | | |
| | | | | | |
| n n | | | | | |
node = | 2 x 2 | = +-------+-------+ | RESULT|
| | | | | | |
| | | | | | |
| | | | | | |
| | | sw | se | +-------+
| | | | |
| | | | |
| | | | |
+---------------+ +-------+-------+
規則的なパターンを扱うのであれば必要なノード数は非常に少なくなる。
例えば1024x1024の空のフィールドなら、1x1の空のノード(level 0)、それを4つ集めた2x2のノード(level 1)、それを4つ集めた4x4のノード(level 2)、...、それを4つ集めた2^10x2^10のノード(level 10)と、たった11個のノードを保持するだけで済んでしまう。この倍の大きさのフィールドを考えるにはもう1個ノードを使うだけでよい。こういうことをするためにはもう使われているノードとまだ使われてなくて新しく作る必要のあるノードを効率的に区別する必要があるが、これはハッシュテーブルを使うことで解決出来る(4つの子ノードをキーにする)。
"次"の世代を計算するにはどうするかだが、各ノードの情報だけでは自分自身が次どういうノードになるかわからない(端があるので)。そこで、2^n x 2^n のうち真ん中の 2^(n-1) x 2^(n-1) だけを計算する。
具体的には、まず自分の子ノードの子ノード(孫ノード)を組み合わせて、自分よりレベルが1つ下のノードを9つ作る。nw、se、sw、se はすでにあるので、こいつらの子を組み合わせる事で東西南北と真ん中(図の e、w、s、n、c) を作る。この9つが互いに重なり合っているのに注意。
(重なり合った9ノード) +-------+-------+ +---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+---+---+---+ nw n se | | | 分割 | | | | | | | | ・ | | | | | | | | 組む | | | | | +-------+-------+ → +---+---+---+---+ : w c e | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+---+---+---+ sw s se | | | | | | | | | | | | | | | | | | | | | | | | +-------+-------+ +---+---+---+---+
で、この9つについて、再帰的にそれぞれの"次の真ん中"が計算出来たとしよう。すると、うまい具合にちょうど重なりのない9つのノードになる。こいつらを組み合わせると重なり合った4つのノードになる。
(重なり合った9ノード) +---+---+---+---+ | | | | | (重ならない9ノード) (重なりあった4ノード) | | | | | +---+---+---+ +---+---+---+ | | | | | | | | | | | | | +---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | | | | | | +---+---+---+ +---+---+---+ nw ne | | | | | step | | | | 組む | | | | +---+---+---+---+ → | | | | → | | | | : | | | | | | | | | | | | | | | | | | +---+---+---+ +---+---+---+ sw se | | | | | | | | | | | | | +---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | | | | | | +---+---+---+ +---+---+---+ | | | | | +---+---+---+---+
で、この重なってる4ノードについて今と同じようにそれぞれの"次の真ん中"を計算して組み合わせれば、欲しかったノードが手に入る。
(重なり合った4ノード)
+---+---+---+
| | | | (重ならない4ノード)
| | | | +---+---+ +-------+
| | | | | | | | |
+---+---+---+ | | | | |
| | | | step | | | 組む | |
| | | | → +---+---+ → | | : 目標ノード
| | | | | | | | |
+---+---+---+ | | | | |
| | | | | | | | |
| | | | +---+---+ +-------+
| | | |
+---+---+---+
このやりかたの利点としてはノードのレベルによらず同じ手続きが使える事だ(一番下の数レベルを除けば)。そして、今の手続きに自分より1個下のレベルの"次"を求める作業が2回入っているのに注目してほしい。ノードのレベルが1個上がると、"次"というのは世代数にして倍になることがわかる。
再帰手続きの最後はどうなっているかというと、最終的にレベル2のノードで1世代先に進む:
(レベル2)
(レベル1)
....
OO.. step O.
O.O. → ..
O...
結局、レベル n のノードについて今の手続きを適用すると一度に 2^(n-2) 世代先まで計算する事になる。
この計算結果を RESULT に格納しておいて、次からは今の手続きを行わず単にこれを参照する。同じ形のフィールドが100回繰り返し出てくるような規則的なパターンを扱うとき、これによって実際には1回しか計算をしなくてよくなるわけだ。
こういうわけで、hashlifeは時間方向や空間方向に規則的なパターンについては非常に効率的に計算できる。
参考
- hashlife自体について
- python implementation http://davidbau.com/archives/2006/07/26/python_curses_life.html
- original paper http://www.sciencedirect.com/science/article/pii/0167278984902513 or https://www.lri.fr/~filliatr/m1/gol/gosper-84.pdf
- article at Dr. Dobbs http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478
- lispbuilder-sdl api https://code.google.com/p/lispbuilder/wiki/UsingLispbuilderSDL
- グライダーガンパターンとその表し方を使わせてもらった http://d.hatena.ne.jp/armbrust/20120930/1349020237
- gollyのファイルフォーマット http://golly.sourceforge.net/Help/formats.html
この実装はpython実装をかなり参考にしている。
あとあの後見つけたが和田氏による解説スライドがわかりやすいと思う。p.19〜 http://www.iijlab.net/~ew/slide2j.pdf
変更点
- 初期パターン配置部分を分離した。
- 前回は各nodeがハッシュテーブルを持っていたためものすごくメモリを食っていたのでリストに変更。
- 描画部分で一旦画面内の全生存セルのリストを作っていたのをやめて、直接再帰的に四分木をたどりつつ描画するようにしたらかなり速くなった。その時の表示スケールでは細かくて見えない部分の描画を打ち切れるようになったのも大きいはず。
コード
gistで貼れるようなのでそうしてみる
hashlife.lisp:
フォントもう少し小さくできないだろうか…
その他
metapixelなんかの.mc形式ファイルも読めるようにはしてみているのだけど、ズームアウトして行くと急に重くなってしまう。
引いてない状態では軽快に動くようなので描画部分の問題だと思うのだけど、プロファイラで見てもどれがボトルネックか判然としない。
違うGUIライブラリを試してみるのもいいかもしれない。
2014/10/5 追記: JIS/USキーボードの配列の違いに対処するため操作方法を変更。あと実装や環境によってはハッシュが衝突するようなので hash table の扱いをcommon lispに任せるように戻した。フルスクリーンモードも追加。
