numpyで実装したライフゲームで簡単な迷路を解いてみた。

はじめに

前回、ライフゲームをnumpyを使って実装してみたという記事を投稿した。このライフゲームを使って迷路探索を行うこともできると聞いたので、前回のプログラムを改造して簡単な迷路を解いてみた。

ライフゲームと迷路探索

　まず、ライフゲームは、格子状の空間に、生物のいるセル(黒)と生物のいないセル（白)が存在し、周辺のセルの状態から次の世代のセルの状態が決まるというものだった。具体的には以下の3つのルールに従い、セルの状態が決まる。

1. 中央のセルが白いときにその周辺に3つの黒いセルが存在するとき次の世代で中央のセルは黒いセルになる(生命の誕生)。
2. 中央のセルが黒いとき、そのセルの周囲に2つか3つの黒いセルがある場合、次の世代でも黒いセルになる(維持)。
3. 1, 2 以外のとき、次の世代で中央のセルが白くなる(淘汰)。

　ところで、迷路を解くという作業は、まずスタート地点から、壁や行き止まりにぶち当たったら引き返し、を繰り返しながら、ゴール地点まで到達することを目指すことを意味する。これをライフゲームの枠組みに置き換えていくと、壁は生物のいるセル(黒)、スタート地点とゴール地点までを生物のいないセルで繋ぐことが、迷路探索の成功を意味する。

実際に迷路を解くために考慮すべきこと

　上記の3つのルールのままでは、いくつか問題が残っている。まず、このルールを適用するとスタート地点とゴール地点も壁になってしまい迷路として成り立たなくなる可能性が挙げられる。また、今回はスタート地点からゴール地点までを無駄のない一本の道で繋ぐことが目的であるので、不要な枝葉のルートを消滅させる(壁に変える)ようなルールに変更する必要がある。

　まず前者について、すくなくとも上記3つのルールでは周囲に壁が2つか3つあれば、次の世代で壁となってしまう。そのため、スタート地点とゴール地点は別な扱いにする必要がある。今回はこの2地点は第三のセルの状態ということで、上記のルールに依らず常に白いセルとして取り扱っている。

　余分な枝葉を壁に変えるにはどのようなルールに作り変えればいいのかを考えていく。前提として、セル上での斜め方向の移動はできないものとすると、考えるべき$3\times3$のブロックは図のようなものになる。

この中央のセルが白セルで、このセルを通り、入ってきたところと違う方へ通り抜けるには、上下左右のすくなくとも2つ以上が白セルである必要がある。もし、中央のセル以外に白セルが1つしかない場合は、図のように行き止まりになるので、ここは探索不要な「枝葉の道」であることがわかる。このような「枝葉の道」をひたすら壁にしていくことで、一本道が得られるようになる。

また、当然ながらすでに壁である場所(黒セル)を道(白セル)に変える必要はないので、3の淘汰のルールは不要である。
結局のところ、必要なルールは、

１. 中央のセルが白セルであった場合に、ブロック内に上下左右方向に白セルが2つ以上存在する場合のみ、次の世代でも白セルのまま維持する。
2. それ以外はすべて次の世代は黒セルになる。

これだけである。

実装

　基本的にライフゲームを実装してみたのコードをそのまま使えるが、いくつか変更する点があるので、そこを中心に述べる。前回のライフゲームとの違いは以下の4つである。

1. スタート地点とゴール地点という常に白セルであり続ける必要があるセルがある
2. 初期条件にスタート地点とゴール地点と迷路の道を与えてあげる必要がある
3. 白セルから黒セルに変更、白セルを維持するルールが変更されている
4. スタート地点から白セルをたどりゴール地点についたら、その経路を表示する

まず、今回解く迷路は図に示したもので、以下のように与えることにした。

スタート地点とゴール地点に2,道に1,壁を0とした。これは、通常のライフゲームが着眼しているのが黒セル(生物のいるセル)であるのに対し、迷路探索では白セルに注目しているため、このようにしている。

# 迷路の入力
new_maze = np.array([[2,0,0,0,1,1],
                     [1,1,0,1,1,0],
                     [0,1,1,1,0,0],
                     [1,1,0,1,1,1],
                     [0,1,1,0,1,0],
                     [1,1,0,1,1,2]])

既存の枠組みでは壁を1(黒セル)として考えているので入力を反転させる関数が必要になる。以下の関数で道(本来の白セル)を0にし、スタート地点とゴール地点はそのまま2にしている。

# セルの反転
def reversed_binary_mat(matrix_input):
    base = np.ones_like(matrix_input)
    base[matrix_input==1] = 0
    base[matrix_input==2] = 2
    return base

先程の入力をこの関数で処理すると以下のようになるので、これに対して先程までのルールを適用していく。

[[2 1 1 1 0 0]
 [0 0 1 0 0 1]
 [1 0 0 0 1 1]
 [0 0 1 0 0 0]
 [1 0 0 1 0 1]
 [0 0 1 0 0 2]]

１. 中央のセルが白セルであった場合に、ブロック内に上下左右方向に白セルが2つ以上存在する場合のみ、次の世代でも白セルのまま維持する。
2. それ以外はすべて次の世代は黒セルになる。

に関しては、以下のような配列をフィルタとして定義し、その配列と0,1を再度反転させた$3\times3$の配列の要素積をとり、得られた配列の合計値で上下左右方向の白セルの数を求める。

cross_mat = np.array([[0,1,0],
                      [1,1,1],
                      [0,1,0]])

# 中央のセルの値を除いたセルの合計値を求める
def count(a):
    copy_a = np.copy(a)
    copy_a[1,1] = 0
    copy_a[copy_a == 2] = 0
    return copy_a.sum()

# 中央のセルの状態を変化させる
def change(a):
    x = a[1,1]
    copy_a = np.copy(a)
    copy_a[copy_a==2] = 0
    cross_mat = np.array([[0,1,0],[1,1,1],[0,1,0]])
    if (x==0 and count(reversed_binary_mat(copy_a)*cross_mat)<2):
        a[1,1] = 1
    return a

これを用いて前回作成したchange_state()でセルの状態を変更する。

# matrix すべての状態を変化させる
def change_state(matrix_input):
    width = matrix_input.shape[0]+2
    matrix_pad = np.ones(width**2).reshape(width,width)
    new_matrix = np.zeros(width**2).reshape(width,width)
    matrix_pad[1:width-1,1:width-1] = matrix_pad[1:width-1,1:width-1] * matrix_input
    for i in range(width-2):
        for j in range(width-2):
            mat = np.copy(matrix_pad[i:i+3,j:j+3])
            new_matrix[i+1,j+1] = change(mat)[1,1]
    return np.array(new_matrix[1:width-1,1:width-1])

描画する関数もほとんど同じだが、新たにセルの値が2: スタート地点、ゴール地点のときと 3:探索された経路を表す時の処理を追加している。

# http://aidiary.hatenablog.com/entry/20120113/1326464820
def render(results, filename="ca.png"):
    """セルオートマトンを描画"""
    width = len(results[0])
    height = len(results)
    img = Image.new("RGB", (width, height), (255,255,255))
    draw = ImageDraw.Draw(img)
    for y in range(height):
        for x in range(width):
            if results[y][x] == 1:
                draw.point((x, y), (0, 0, 0))
            if results[y][x] == 2:
                draw.point((x,y),(255,0,0))
            if results[y][x] == 3:
                draw.point((x,y),(0,255,255))
    return img

def __updated_plot(i):
    return plt.imshow(images[i])

あとは、ライフゲーム同様、世代を進めていき、セルの状態が変化しなくなったら、そのときに白セルの場所に色をつけてあげればよい。

これらの一連の処理をまとめて迷路探索を行う関数を作成した。

# 迷路探索
def maze_solver(new_maze, max_try_times=100):
    images = []
    input_matrix = reversed_binary_mat(new_maze)
    image = render(input_matrix)
    images.append(image)
    new_matrix = input_matrix
    last_matrix = np.zeros_like(new_matrix)
    for i in range(max_try_times):
        new_matrix = change_state(new_matrix)
        # 変化がなくなったら、現在の0を3に変えて状態を確定させる
        if ((new_matrix == last_matrix).all()):
           new_matrix[new_matrix==0] = 3
           image = render(new_matrix)
           images.append(image)
           break
        image = render(new_matrix)
        last_matrix = new_matrix
        images.append(image)
    return images

この関数は以下のようにして使用する。動画として出力すると結構おもしろいので、今回も出力してみた。

# 迷路探索をやってみる
input_matrix = np.array([[2,0,0,0,1,1],
                         [1,1,0,1,1,0],
                         [0,1,1,1,0,0],
                         [1,1,0,1,1,1],
                         [0,1,1,0,1,0],
                         [1,1,0,1,1,2]])
images = maze_solver(input_matrix)
fig = plt.figure()
anim = FuncAnimation(fig, __updated_plot, frames=len(images), interval=1000)
HTML(anim.to_html5_video())

簡単な迷路も解くことができると聞いたので... pic.twitter.com/2Ehem2iIfd

— Blackcat⛅ (横山雅季) (@myblackcat7112) August 3, 2019

一連の流れはcolabratoryで作成した。試したい方はこちら。

おわりに

新卒の勉強会で、ライフゲームについて学び、それをせっかくだから自分の理解を深めるためにまとめてみた。
本当は、同じ仕組みで迷路を自作して、自作した迷路に対して今回のmaze_solverを走らせてみたかったが、一筋縄には行かなかった。引き続きチャレンジしていきたい。

参考

セルオートマトンについて
GPUとセルオートマトンで経路探索問題を解いてみる