Pythonで迷路を作ろう！

穴掘り法を使って迷路を作ろう - Qiita

 Colabで動かしてみるとエラーが出てしまうので、

setrecursionlimit(10**6)

を削除してから実行します。

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# S     #   #                                   #   #       #
# # #   #   #   # # # # #   # # # # # # # # #   #   #   #   #
#   #   #       #   #       #               #       #   #   #
#   #   #   # # #   #   # # #   # # # # #   # # # # #   #   #
#       #           #           #       #   #           #   #
#   # # # # #   # # # # #   # # #   # # #   #   # # # # #   #
#   #       #   #       #       #       #   #   #           #
#   #   #   # # #   #   # # #   # # #   #   #   #   # # #   #
#       #           #   #   #           #       #   #       #
# # # # # # # # # # #   #   #   # # # # # # #   #   # # # # #
#               #       #       #           #   #           #
#   #   # # # # #   # # # # #   #   # # #   #   # # # # #   #
#   #           #   #       #   #       #   #   #       #   #
#   # # # # #   #   #   #   # # # # #   #   # # #   #   #   #
#   #           #   #   #           #   #   #       #   #   #
#   #   # # # # #   #   # # # # #   #   #   #   # # #   #   #
#   #   #       #   #       #   #   #   #       #   #       #
# # #   #   #   #   # # #   #   #   #   # # # # #   # # #   #
#       #   #   #       #   #           #               #   #
#   # # #   #   # # #   #   # # # # # # # # # # #   #   #   #
#   #       #   #       #       #                   #   #   #
#   #   # # #   #   # # # # #   #   # # # # # # # # # # #   #
#   #       #   #   #           #                       #   #
#   #   # # #   #   #   # # # # #   # # # # # # # # #   #   #
#       #       #   #   #       #   #           #       #   #
#   # # #   # # #   #   # # #   #   # # # # #   #   #   #   #
#       #   #       #       #   #   #       #   #   #   #   #
# # #   #   #   # # # # #   #   #   #   #   #   #   # # #   #
#       #                   #           #       #           #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

と出てきます。立派な迷路ができています。表示するまでのコードを見ていきます。

まず最小限の迷路を作っていく"マス"の部分のみ表示してみます。

import random

height, width = 11, 11
maze_base = [["#"]*width for _ in range(height)]


for i in maze_base:
    print(*i)

これを実行すると

# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # #

print(*i)　　→　print(i)

として実行すると

['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']

よく見慣れたリストの姿となります。

maze_base = [["#"]*width for _ in range(height)]

をもっと簡単にしてみます。

maze_base = []

for i in range(10):
    row = []
    for j in range(10):
        row.append(" #")
    maze_base.append(row)


for i in maze_base:
    print(i)

となります。こうするとコードは長くなりますがわかりやすいです。

次に初期設定でスタート地点と、そこから上下左右に動かすときに使う変数を作っておきます。

maze_base[1][1] = " " #初期地点

dx = [(1,2), (-1,-2), (0,0), (0,0)] #x軸のベクトル
dy = [(0,0), (0,0), (1,2), (-1,-2)] #y軸のベクトル

あとは再帰関数で連続的に穴を掘っていきます。" "をランダムにしかも規則的に入れていきます。

(1) 開始地点から上・下・左・右の4方向の開いている地点(外に突き抜けないように)に2マスずつ進みながら通路を作っていく。

(2) 4方向全て行き止まりになってしまったら前のマスへ戻りそこから掘れる場所を掘っていく

def make_maze(ny, nx):

    array = list(range(4)) 
    random.shuffle(array) #ランダムに行く方向を決める

    for i in array:

        if ny+dy[i][1]<1 or ny+dy[i][1]>=height: #周りの壁を越えていたらスルー
            continue

        if nx+dx[i][1]<1 or nx+dx[i][1]>=width: #周りの壁を越えていたらスルー
            continue

        if maze_base[ny+dy[i][1]][nx+dx[i][1]]==" ": #2つ先のマスがすでに開いていたらスルー
            continue

        for j in range(2): #通路を掘る
            maze_base[ny+dy[i][j]][nx+dx[i][j]] = " "

        make_maze(ny+dy[i][1], nx+dx[i][1]) #掘った先のところに移動

あとは実行するのみなので

make_maze(1, 1).    //   スタート地点。ここから穴掘りを始めます。
maze_base[1][1] = "S"　　　// スタート地点に"S"を入れます。

とすると配列"maze_base"に迷路のデータが入っていきます。そして

for i in maze_base:
    print(*i)

で出力すると配列のデータが出力され迷路ができあがります。

全体のコードは

import random

height, width = 31, 31
maze_base = [["#"]*width for _ in range(height)]

maze_base[1][1] = " " #初期地点
dx = [(1,2), (-1,-2), (0,0), (0,0)] #x軸のベクトル
dy = [(0,0), (0,0), (1,2), (-1,-2)] #y軸のベクトル

def make_maze(ny, nx):

    array = list(range(4)) 
    random.shuffle(array) #ランダムに行く方向を決める

    for i in array:

        if ny+dy[i][1]<1 or ny+dy[i][1]>=height: #周りの壁を越えていたらスルー
            continue

        if nx+dx[i][1]<1 or nx+dx[i][1]>=width: #周りの壁を越えていたらスルー
            continue

        if maze_base[ny+dy[i][1]][nx+dx[i][1]]==" ": #2つ先のマスがすでに開いていたらスルー
            continue

        for j in range(2): #通路を掘る
            maze_base[ny+dy[i][j]][nx+dx[i][j]] = " "

        make_maze(ny+dy[i][1], nx+dx[i][1]) #掘った先のところに移動

make_maze(1, 1)
maze_base[1][1] = "S"

for i in maze_base:
    print(*i)

となっています。