ラングトンのアリを実装してみた[Python]

『心はプログラムできるか』の話の続き。
ライフゲームの話とともに，ラングトンのアリも紹介されていたので実装してみた。この先生蟻コロニー最適化も本の中で紹介してるしアリ好きだな（笑）。というか本の中でアリを飼っている話が出てきていた。

1.ラングトンのアリ

詳細はWikipediaがあるので引用。

平面が格子状に構成され、各マスが白または黒で塗られる。ここで、1つのマスを「アリ」とする。アリは各ステップで上下左右のいずれかのマスに移動することができる。アリは以下の規則に従って移動する。

• 黒いマスにアリがいた場合、90°右に方向転換し、そのマスの色を反転させ、1マス前進する。
• 白いマスにアリがいた場合、90°左に方向転換し、そのマスの色を反転させ、1マス前進する。

この単純な規則で驚くほど複雑な動作をする。

ルールが非常に単純（プログラム書くのも簡単）。なのに結構複雑な動きをする。まさに複雑系(よく理解していないケド)。

実際の動画はこんな感じ。

ラングトンのアリやってみた。黒いマスなら色を変えて右へ，そうでなければ色を変えて左へ進む。チューリング完全なら好きな絵を描かせられるかもしれないけどどうなんだろう。 pic.twitter.com/45yYSGxoub

— TonyMooori (@TonyMooori) 2016, 1月 7

ツイートにも書いたけど，これで自由に絵がかけたら面白いんだけれどなぁ。Wikipediaには二次元チューリングマシンって書いてあるけれど，チューリング完全ってことで良いのだろうか。もし仮にそうならば，ある程度絵がかけるとは思うけど……まぁ良いや。

追記
巻き戻す方向にルールを決めてやればいいだけの話でした。

2.プログラム

こちらのサイトを参考にしました。
ライフゲーム - 人工知能に関する断創録

Processingでライフゲームを実装[Processing]

　プログラマーなら誰しも一度はハマるライフゲーム。知ってる人も知らない人も見てってくださいな。

1.ライフゲームとは

　ライフゲームはよく「最も単純な人工生命」とか言われる。まぁ見方によっては間違っていないけれど，どちらかと言うとパズルみたいなもの。

　基本的には細胞（セル・Cell）の生き死にを，ルールに従って決める。ルールは大まかにいうと，

・寂しいと死んじゃう（周囲に生きているセルが無いと死ぬ）
・暑苦しいと死んじゃう（周囲にセルが多すぎると死ぬ）
・環境が良ければ子供が生まれる（周囲に生きているセルがそこそこあれば生まれる）

　という感じ。もう少し詳しく言うと。

・自分が生きていて，周り8マスに生きているセルが2か3なら生きられる。
・自分が死んでいてい，周り8マスに生きているセルが3つなら生まれる。
・上記以外の場合は死ぬ。

　というもの。実際の例で示す。

　緑色の部分が生きているセル。上の図の赤く囲った部分のセルは，周囲に4つ生きているセルがあるので「暑苦しく」て死ぬ（黒くなる）。

　逆に，生まれるケースはこんな感じ。

　この図では自分が死んでいていて（黒くて），周りに生きているセルが3つなので生まれます（緑になる）。
　とこんな感じになるが，実際に見てみればわかると思います。

追記
ライフゲームに関する動画で非常に面白い動画があったので貼っておきます。

2.ソースコード

　上の文章を読まずにソースコードコピペするのが割りと賢い判断かもね。

boolean[][] board;      /* 現在の状態を保存する変数 */
boolean[][] temp_board; /* 次の状態を保存する変数 */
int N = 64;            /* 一辺の数 */


void setup() {
  size(512, 512);

  /* ボードの作成 */
  board = new boolean[N][N];
  temp_board = new boolean[N][N];
  for (int i = 0; i < N * N; i++ )
    board[i/N][i%N] = int(random(2)) == 0 ;

  frameRate(10);
}

void draw() {
  background(0);

  /* 四角形の幅を決める */
  int w = width/N;

  /* 生き死にを決める */
  step();
  /* マウスで状態を変える */
  edit_board();

  /* 色を指定 */
  fill(0, 255, 0);
  stroke(0, 255, 0);
  
  for (int i = 0; i < N; i++ ) {
    for (int j = 0; j < N; j++ ) {
      /* board[i][j]がtrueすなわち生きている場合描画 */
      if ( board[i][j] )
        rect(i*w, j*w, w, w);
    }
  }
}

/* 生き死にを決める関数 */
void step() {
  /* temp_boardにとりあえずその後の状態を保存 */
  for (int i = 0; i < N; i++ ) 
    for (int j = 0; j < N; j++ ) 
      temp_board[i][j] = is_alive(i, j);
      
  /* ボードをコピー */
  for (int i = 0; i < N; i++ ) 
    for (int j = 0; j < N; j++ ) 
      board[i][j] = temp_board[i][j];
}

boolean is_alive(int x, int y) {
  int count = 0;
  
  /* 周囲8マスを見る */
  for (int i = -1; i <= 1; i++ ) 
    for (int j = -1; j <= 1; j++ ) 
      if ( in_range(x+i, y+j) )
        if ( i != 0 || j != 0 )
          if ( board[x+i][y+j] )
            count++;

  
  if ( board[x][y] && ( count == 2 || count == 3 ) )
    return true;/* 生きていて周りに友達がいるから生き残れる */
  else if ( board[x][y] == false && count == 3 )
    return true;/* それなりに人がいるから新しい子供が生まれる */
  else 
    return false;/* それ以外は生き残れない */
}

boolean in_range(int x, int y) {
  if ( x < 0 || x >= N || y < 0 || y >= N )
    return false;
  return true;
}

void edit_board() {
  int x = mouseX * N / width;
  int y = mouseY * N / height;

  if ( in_range(x, y) )
    board[x][y] = !board[x][y];
}