Pythonで迷路を描いてみよう（ビビパズコラボ）

Marupeke-IKD

　僕は別のマガジン「ビビッと感じる数学パズル」通称「ビビパズ」で数学を主題とした問題を色々と出しています。マガジンと問題リストは以下のリンクにありますので、ご興味のある方は是非ご覧下さい(^-^)

　先日「迷路を作る内壁の枚数は何枚必要？」という問題を出しました：

頭の体操になりますのでお暇でしたらチャレンジしてみて下さい(^-^)。

　その問題の解答を説明している記事につけた深堀話で、迷路を作るアルゴリズムを取り上げました。迷路を作るアルゴリズムは沢山あるのですが、その中で簡単な方法として「棒倒し法」を紹介しました。

　ビビパズは数学のマガジンなので「そういう方法があるよ」というだけに留めましたが、こちらはバキバキにプログラムのマガジンです。ならやりましょうって話です(^-^)

棒倒し法のアルゴリズム

　ビビパズの記事中でも説明していますが、棒倒し法のアルゴリズムについて簡単に紹介します。縦横適当な数のマス目を想定し、その交点に着目します。

　左上の交点の上下左右の壁を一つ選びます：

　次は右の点に移動して同じ事をするのですが、点の左に既に壁があった場合はべつの壁を選択します：

　この操作を右端まで続けたら一段下に移ります。一段下は右下左の3つの壁から選択します：

　上の壁を除く理由はそれを含めると到達出来ない部屋が出来てしまうためです。2段目2つ目も上の壁は除きます。また左に壁が既にある場合は別の壁を選択します：

後は同様にして右へ移動、そして下段に移動を繰り返して最下段まで終えると迷路が出来上がっているんです。

　このアルゴリズムをプログラムしてみましょう。

Tkinterで線を引く

　ではプログラムです。画面に線を引けるプログラム言語は沢山ありますが、今回はどの環境でも動作するPythonを使います。PythonならWindowsでもMacでもUbuntuでもRaspberry Piでも同じコードで動きます！

　Pythonで線を描画する方法も色々あります。その中でデフォルトのPythonに入っているTkinterを採用します。デフォルトならべっとライブラリを用意しなくても即使えますからね(^-^)

　まず以下のベースとなるテンプレートコードを作ります：

import tkinter

# メインウィンドウ
root = tkinter.Tk()
root.geometry( "800x600" )
root.title( "Maze" )

# キャンバス
canvas = tkinter.Canvas( root, width=800, height=600 )

# ライン（テスト）
canvas.create_line( 100, 100, 400, 300 )

canvas.pack()   # キャンバスを表示
root.mainloop() # メインウィンドウ動作開始

これをmaze.pyというテキストファイルとして保存します。で、お使いのOSのターミナル（Windowsはコマンドプロンプト）で保存したフォルダに移動して、

python ./maze.py

と打つと即実行されます。Windowsの場合は拡張子判断してくれてファイルをダブルクリックするだけで実行してくれるかもしれません。

　実際実行すると、

こういう線が1本描かれたウィンドウが出ます！非常に短いコードで線を描画できるのですからお手軽です。

　細かい所は端折るとして、ポイントは以下の1行です：

# ライン（テスト）
canvas.create_line( 100, 100, 400, 300 )

canvas.create_line( x0, y0, x1, y1 )で(x0,y0)から(x1,y1)まで線が1本引けます。これで迷路を描くんです。

マスの大きさと縦横マスの数で初期化

　迷路は方眼紙のような正方形のマスの辺に描く事を前提とします。様々なサイズの迷路を描きたいので、マスの大きさと縦横マスの数を変えられるように変数として扱う事にしましょう。

　マスの大きさをeL、マスの縦数をN(w,h)とします。また迷路の左上の座標もmLT(x,y)と定義しておきましょう：

# 初期値
eL  = 15          # マスの辺の長さ（ピクセル）
N   = ( 30, 15 )  # マスの横縦
mLT = ( 10, 10 )  # 迷路の描画オフセット(x,y)

棒倒しアルゴリズムを実装

点の位置ごとの壁番号の選択

　では一番楽しい所である棒倒しアルゴリズムの実装です。まず壁の向きを以下のように定めておきましょう：

　先のアルゴリズムのお話で、点上で棒を倒せる方向には以下の4パターンがあります：

　これはうまい事条件分けが出来ます。まず最上段であれば0が含まれます。また左端点なら3が含まれません。これを乱数を取る範囲に反映させるんです。

　Pythonの乱数であるrandomモジュールには範囲指定した整数からランダムで数値を取り出せるrandom.randint関数があります：

improt random

startInt = 5
lastInt  = 12
v = random.randint( startInt, lastInt )

例えば上の場合は5～12までの整数から一つランダムで値が返ります。

　選択すべき壁の番号の範囲は以下のような条件範囲の指定になります：

import random
 
for i in range( N[ 1 ] - 1 ):
    preW = 0
    for j in range( N[ 0 ] - 1 ):
        dir = random.randint( 0 if i == 0 else 1, 2 if preW == 1 else 3 )
        preW = dir

　iは点の行番号で最上段はi=0です。その場合は0を含めるのでした。ですから開始整数は、

 0 if i == 0 else 1

となっています。これはPythonの3項演算子です。英語的な読み順になっていて「0です。もしi=0ならば。そうでなければ1」というニュアンスです。

　jは列番号でj=0は左端を意味します。preWというのは左の点の壁の番号を表しています。これが1の場合は3番の壁を入れないのでした。よって、

2 if preW == 1 else 3

こういう3項演算子で最後尾の整数を指定できます。

　方向dirを決めたらそれでpreWを上書きして次の点の判定に備えておきます。

上下左右に線を引く

　上の乱数で決まった方向dirに向かって壁を描けば迷路ができるわけですが、それをべたに書くとこんな条件分岐を書く嵌めになります：

if dir == 0:
    canvas.create_line( x, y, x, y - eL )
elif dir == 1:
    canvas.create_line( x, y, x + eL, y )
elif dir == 2:
    canvas.create_line( x, y, x, y + eL )
elif dir == 3:
    canvas.create_line( x, y, x - eL, y )

まぁ実直ではあるんですが、ちょっと芸が無いかな～という印象です。こういう個所こそテーブルの出番です。描く方向の情報を配列に格納しておけば、よりすっきり記述できます：

# 上下左右終点オフセット値
ofs = [ ( 0, -eL ), ( eL , 0 ), ( 0, eL ), ( -eL, 0 ) ]
canvas.create_line( x, y, x + ofs[ dir ][ 0 ], y + ofs[ dir ][ 1 ] )

　こうする事で条件判断せずに上下左右に線を引けます。

点をイテレートして壁を描こう

　では実際に左上から右下の点を移動しながら壁を作っていきましょう。もう全コードを見た方が早いですね。下記のコードは即実行できます：

<maze.py>

import tkinter
import random

# メインウィンドウ
root = tkinter.Tk()
root.geometry( "800x600" )
root.title( "Maze" )

# キャンバス
canvas = tkinter.Canvas( root, width=800, height=600 )

# 初期値
eL  = 20          # マスの辺の長さ（ピクセル）
N   = ( 25, 20 )  # マスの横縦
mLT = ( 10, 10 )  # 迷路の描画オフセット(x, y)

# 上下左右終点オフセット値
# 上右下左の順
ofs = [ ( 0, -eL ), ( eL , 0 ), ( 0, eL ), ( -eL, 0 ) ]

# 壁作成
for i in range( N[ 1 ] - 1 ):
    y = eL * ( i + 1 ) + mLT[ 1 ]
    preW = 0
    for j in range( N[ 0 ] - 1 ):
        dir = random.randint( 0 if i == 0 else 1, 2 if preW == 1 else 3 )
        preW = dir

        # 内壁描画
        x = eL * ( j + 1 ) + mLT[ 0 ]
        canvas.create_line( x, y, x + ofs[ dir ][ 0 ], y + ofs[ dir ][ 1 ] )
    
# 外壁描画
canvas.create_rectangle( mLT[ 0 ], mLT[ 1 ], mLT[ 0 ] + eL * N[ 0 ], mLT[ 1 ] + eL * N[ 1 ] )

canvas.pack()   # キャンバスを表示
root.mainloop() # メインウィンドウ動作開始

　こんなに短いコードで済みます！これでウィンドウを表示して迷路を作成して描画するまで出来ています。実際Windowsで動かすと：

ちゃんと迷路が描けていますね(^-^)/。同じコードをRaspberry Piで動かしてもちゃんと迷路を描いてくれました：

この気軽さと移植性の高さがPythonの魅力ですね。

棒倒し法の欠点

　棒倒し法はこのように非常に短いコードで迷路を描けます。ただ、この方法はちょっと欠点もあるんです。最上段を見るとなーんとなくスカスカ感があります。これは1段目と2段目で「2つ連続で縦に並ぶ事が無い」からです：

　左のように上が選択された場合は下が空き、下が選択された場合は上が空いてしまうため、上も下も塞がる事が無いんですね。「ほんじゃ塞ぐようにもすれば？」と思う訳ですが、そうすると迷路の上下が完全に壁で塞がれてしまう事が起きる為迷路自体が破綻してしまいます。

　別の欠点として迷路が割と単調なのも挙げられます。最上段の列が塞がる事が無い為「上列を右端まで行って下に行くとゴール」というパターンが多くなりがちです。人が作る迷路にある「迷わせてやるぜ！」という意図を組み込めないんですね。

　とはいえこの超短いコードで迷路が作れるのは魅力です。単調とは言えこれを3D視点の迷路にするとすさまじく難しくなる事は想像に難くありません。もちろんパラメータを変えて無茶苦茶細かい迷路にすると難易度爆上がりです：

Tkinterの線描画コスト

　Tkinterは気軽に図形を描画出来ますが、描画速度は速くありません。上のような込み入った迷路だとウィンドウサイズの変更で相当な遅延が発生しました。これは1つ1つの壁（線）がオブジェクトとして個別管理されてしまうからです。ですからこの2Dの迷路の絵をベースに何かしたい場合は、一度絵をPNGなどの画像データ（ラスタライズデータ）に変換して表示するようにした方が良いです。

　という事でPythonで迷路を描いてみるの回でした。ではまた(^-^)/

いいなと思ったら応援しよう！