すっかり遅刻ですが、 Elm2 Advent Calendar 2017 の 17日目15日目の記事です。
去年のカレンダーにもライフゲームの実装が既にありますし、今年もライフゲームに触れた記事があり既に何番煎じかわかりませんが、思いつきで書いてみました。
まぁ、近傍のセルを求めるのにメモリを食うし読みにくいちょっとした工夫をしただけです。
デモとソースコード
デモ : https://mather.github.io/elm-lifegame/
ソースコード : https://github.com/mather/elm-lifegame
やってみたかったこと
- グラフライブラリとか使うのもいいけど、シンプルにリストだけでやってみたい
- 二次元リスト上の位置を指定して要素を取得しない
ライフゲーム
標準的なルールは以下の通り
- あるセルの周囲8マスのセルの生存数をチェック
- 周囲の生存数が2であり、対象のセルが生存している => 次の世代も生存
- 周囲の生存数が3 => 次の世代は生存（誕生？）
- それ以外は死亡
周囲に8マス存在しない境界領域に関しては2つの定義方法があります。
- 常に死亡したセルとみなす
- 上下左右でループさせる
それではライフゲームの肝である一世代の評価について見ていきましょう。
世代更新
一世代進める関数を nextGen : EdgeStrategy -> LifeGame -> LifeGame としました。
EdgeStrategy で周辺領域に関する定義（戦略）をしています。
type EdgeStrategy
= DeadPadding
| Loop
LifeGame は幅と高さと二次元リストのデータです。幅と高さをリストから取得することもできますが、初期化したあとは変更しないので参照可能な値として持たせておくことにしました。
type alias LifeGame =
{ w : Int
, h : Int
, table : List (List Cell)
}
(0,0) 地点のセルの上に隣接する (0, -1) セルを取得する時に領域外なのでストラテジに沿った値を返す関数などを作りたくなりますが、ちょっと堪えて別の発想をします。
次の世代を評価するのに必要なセルは自身とその周囲8マスなので、その9マスをひとかたまりとした二次元リストを生成できれば都合が良いはずです。
ただ、前の世代の二次元リストから9マスブロックのリストを求めようとすると境界部分の判定を都度考える必要が出てきてしまい条件分岐がややこしいです。そのため、前段階で境界領域のセルを追加する変換を行います。
ループする二次元リストを表現する
DeadPadding の場合は Dead セルで埋めていけば良いので特に問題はありません。
Loop の場合は、関数型の汎用性のある関数が考えられます。それが extendListWithLoop 関数です。
extendListWithLoop : List a -> List a
extendListWithLoop list =
let
n =
List.length list
in
List.drop (n - 1) list ++ list ++ List.take 1 list
やっていることは単純でリストの最後の要素を先頭に、リストの最初の要素を最後尾に追加するだけです。
任意のリストに使用できる汎用性があるので、二次元リストには次のように適用できます。
edgeFramedTableWithLoop : LifeGame -> List (List Cell)
edgeFramedTableWithLoop lifegame =
lifegame.table
|> List.map extendListWithLoop
|> extendListWithLoop
各行( List Cell )に適用して、最後に行を表現するリスト( List (List Cell) )そのものにも適用します。
3 x 3 のブロックに分解する
境界領域を拡張した二次元リストを 3 x 3 のブロックに変換する方法を考えます。
とはいえ一つのセルの周辺を集めるために異なる行を行ったり来たりするのは得策ではありません。
もっとシンプルな方法で実現したいです。
全体の仕組みがどうなるか考えるより、まずは小さくシンプルなところから仕組みを考えてみましょう。
リストを1要素ずつスライドしながらn要素ずつのブロックに分ける関数です。
window : Int -> List a -> List (List a)
window n list =
if List.length list < n then
[]
else
List.take n list :: window n (List.drop 1 list)
これは各行にも適用できます。
出来上がるイメージは次のようになります。
この関数を列と行に適用して考えてみると、リストの階層が深くて複雑ですが次のようなデータ変換が見えてきます。
ここで、 transpose : List (List a) -> List (List a) はいわゆる転置行列を作る関数として作成したのですが、よくよく見るとネストしたリストの階層を入れ替える処理にもなっているのです。
このようにして元のセルに対して周辺セルを集めた9マスのセル集合が二次元リストの要素として表現できたので、あとはルールに従って評価すれば終わりです。
描画について
描画などの定義についてはあまり力を入れていないので説明を省略しますｗ
まとめ
ということで、グラフライブラリなどを使わずにライフゲームのセルの評価をしてみました。
途中段階の型をもっとうまく表現すればわかりやすいかなーと思うのですが、時間もないのでこの辺で。