[Python] 難しい迷路を自動生成する

Python
2025.03.16

迷路の作り方は色々なアルゴリズム（作るための手続き）としてまとまっています。
Pythonなどのプログラミング言語で迷路を作成する場合は、このアルゴリズムを実装することになります。

最近はアルゴリズムを知らなくても、ChatGPTなどのAIを使って、簡単に必要なコードが手に入ります。

りお
りお

びっくりするぐらい簡単に、精度の高いコードを教えてくれます。

迷路を作るためのアルゴリズム

迷路を作るための代表的なアルゴリズムとしては以下が挙げられます。

1. 深さ優先探索（DFS / Depth-First Search）

  • 再帰やスタックを使って探索を行い、道を掘り進める方法。
  • できる迷路は「一本の長い道が多い」傾向にある。
  • シンプルで実装しやすい。

2. 幅優先探索（BFS / Breadth-First Search）

  • キューを使って探索し、迷路を生成する方法。
  • 生成された迷路の道が比較的均等に分布する。
  • 迷路生成よりも解探索によく使われる。

3. Prim法（プリムのアルゴリズム）

  • 最小全域木（Minimum Spanning Tree, MST）を作るアルゴリズムの一種。
  • 壁のリストを使ってランダムに道を掘り進める。
  • できる迷路は「広がりのある自然な形状」になりやすい。

4. Kruskal法（クラスカルのアルゴリズム）

  • グラフの最小全域木を構築する方法。
  • 各セルを独立した集合とし、ランダムに壁を取り除いていく。
  • 比較的「網目状の迷路」になることが多い。

5. Eller’s Algorithm（エラーのアルゴリズム）

  • 迷路を一行ずつ処理しながら作成する方法。
  • ストリーム処理が可能で、無限に続く迷路を生成できる。

6. Recursive Division（再帰的分割法）

  • 壁を作って領域を分割しながら迷路を作成。
  • 直線的な壁が多く、部屋っぽい迷路ができる。

プログラミングスクールのリンク集です。
おすすめできるスクールのみに絞っています。

サンプルコード

ChatGPTで生成されたコードとその実行結果をまとめておきます。
深さ優先探索と比べて、Kruskal法で作った迷路の方が難しいと思います。

深さ優先探索アルゴリズムのサンプル

シンプルなアルゴリズムで、迷路の難易度も低めです。
コードもそれほど複雑ではありません。

import random

WIDTH, HEIGHT = 41, 41
maze = [[1] * WIDTH for _ in range(HEIGHT)]
ddx = [0, 0, 2, -2]
ddy = [-2, 2, 0, 0]

def is_valid(nx, ny):
    return 1 <= nx < WIDTH-1 and 1 <= ny < HEIGHT-1 and maze[ny][nx] == 1

def carve_maze(x, y):
    maze[y][x] = 0 
    directions = list(zip(ddx, ddy))
    random.shuffle(directions) 
    for dx, dy in directions:
        nx, ny = x + dx, y + dy  
        if is_valid(nx, ny):
            maze[y + dy//2][x + dx//2] = 0  
            carve_maze(nx, ny) 

carve_maze(1, 1)

for row in maze:
    print("".join("█" if cell else " " for cell in row))

簡単にサンプルコードを解説します。

WIDTH, HEIGHT = 41, 41
maze = [[1] * WIDTH for _ in range(HEIGHT)]
ddx = [0, 0, 2, -2]  
ddy = [-2, 2, 0, 0]

WIDTHとHEIGHTで迷路のサイズを決めます。この値は奇数である必要があります。

maze変数は2次元配列で迷路を表現します。1=壁、0=通路を表現しています。初期状態ではすべてが壁（1）で埋まった状態です。

ddx配列とddy配列は、上下左右への移動を表現する配列です。一度に2マスずつ移動するのが特徴で、奇数座標が通路、偶数座標が壁になります。

def is_valid(nx, ny):
    return 1 <= nx < WIDTH-1 and 1 <= ny < HEIGHT-1 and maze[ny][nx] == 1

次に進むセルが有効かどうかを判定する関数です。

def carve_maze(x, y):
    maze[y][x] = 0 
    directions = list(zip(ddx, ddy))
    random.shuffle(directions) 
    for dx, dy in directions:
        nx, ny = x + dx, y + dy  
        if is_valid(nx, ny):
            maze[y + dy//2][x + dx//2] = 0  
            carve_maze(nx, ny) 

carve_maze(1, 1)

再帰的に迷路を掘り進める関数です。
maze[y][x]で、現在のセルを通路(0)に設定します。
上下左右の4方向をランダムな順序で試行し、未訪問なら進みます。
この時に現在のセルと次のセルの間の壁を壊します。

carve_maze(1, 1) を実行することで、再帰的に次のセルを掘り進めていき、迷路として自動生成されます。

for row in maze:
    print("".join("█" if cell else " " for cell in row))

迷路を表示します。壁（1）を■で表示し、通路（0）を” “（半角スペース)で出力しています。

実行結果は以下となります。
実行する度に異なる迷路が自動的に作られます。

迷路を見てもらうと分かりますが、分岐してもすぐに行き止まりになるなど、比較的簡単な迷路になっているかと思います。

Kruskal法アルゴリズムのサンプル（その1）

深さ優先探索アルゴリズムと比べると若干複雑にはなっていますが、それでもコード量としては多くないです。
そこそこ難易度の高い迷路を作ることができます。

import random

WIDTH, HEIGHT = 41, 41
maze = [[1] * WIDTH for _ in range(HEIGHT)]
sets = {(x, y): (x, y) for x in range(1, WIDTH, 2) for y in range(1, HEIGHT, 2)}

def find(cell):
    if sets[cell] != cell:
        sets[cell] = find(sets[cell])
    return sets[cell]

def union(cell1, cell2):
    root1, root2 = find(cell1), find(cell2)
    if root1 != root2:
        sets[root2] = root1
        return True
    return False

edges = []
for x in range(1, WIDTH, 2):
    for y in range(1, HEIGHT, 2):
        if x + 2 < WIDTH:
            edges.append(((x, y), (x + 2, y)))
        if y + 2 < HEIGHT:
            edges.append(((x, y), (x, y + 2)))

random.shuffle(edges)

for (x1, y1), (x2, y2) in edges:
    if union((x1, y1), (x2, y2)):
        maze[y1][x1] = 0
        maze[y2][x2] = 0
        maze[(y1 + y2) // 2][(x1 + x2) // 2] = 0

for row in maze:
    print("".join("█" if cell else " " for cell in row))

簡単にサンプルコードを解説します。

WIDTH, HEIGHT = 41, 41
maze = [[1] * WIDTH for _ in range(HEIGHT)]
sets = {(x, y): (x, y) for x in range(1, WIDTH, 2) for y in range(1, HEIGHT, 2)}

WIDTHとHEIGHTで迷路のサイズを決めます。この値は奇数である必要があります。

maze変数は2次元配列で迷路を表現します。1=壁、0=通路を表現しています。初期状態ではすべてが壁（1）で埋まった状態です。

sets変数は、各セル（通路となる場所）を Union-Find木（Disjoint Set）で管理します。どのセルがどの集合に属しているかを追跡することができます。

def find(cell):
    if sets[cell] != cell:
        sets[cell] = find(sets[cell])
    return sets[cell]

find関数は、再帰的に集合の代表（ルート）を探す処理です。

def union(cell1, cell2):
    root1, root2 = find(cell1), find(cell2)
    if root1 != root2:
        sets[root2] = root1
        return True
    return False

union関数は、2つのセルが異なるグループにいる場合、1つのグループに統合する処理です。壁を壊す（通路を作る）条件が決まります。

edges = []
for x in range(1, WIDTH, 2):
    for y in range(1, HEIGHT, 2):
        if x + 2 < WIDTH:
            edges.append(((x, y), (x + 2, y)))
        if y + 2 < HEIGHT:
            edges.append(((x, y), (x, y + 2)))

edges変数は各セルから右と下に対する 壁の位置を保存する配列です。迷路内のセル間を結ぶ候補の壁を格納しています。

random.shuffle(edges)

edgesの順番をランダム化します。ランダム性を与えるために、壁を壊す順序をシャフルしています。

for (x1, y1), (x2, y2) in edges:
    if union((x1, y1), (x2, y2)):
        maze[y1][x1] = 0
        maze[y2][x2] = 0
        maze[(y1 + y2) // 2][(x1 + x2) // 2] = 0

壁を壊して通路を作ります。各エッジに対してunion関数を呼び出し、異なるグループなら壁を壊して通路に、同じグループなら壁を残します（ループを防ぐため）。

for row in maze:
    print("".join("█" if cell else " " for cell in row))

迷路を表示します。壁（1）を■で表示し、通路（0）を” “（半角スペース)で出力しています。

実行結果は以下となります。
実行する度に異なる迷路が自動的に作られます。

深さ優先探索アルゴリズムで作った迷路と比較すると、分岐も多く、深く探索しないと行き止まりにならないため、難易度はかなり上がっています。

Kruskal法アルゴリズムのサンプル（その2）

その1のサンプルコードを応用して、円形の迷路を作成できます。

import math
import random

def find(cell):
    if sets[cell] != cell:
        sets[cell] = find(sets[cell])
    return sets[cell]

def union(cell1, cell2):
    root1, root2 = find(cell1), find(cell2)
    if root1 != root2:
        sets[root2] = root1
        return True
    return False

def is_in_circle(x, y, R):
    if round(math.sqrt((x-R)**2 + (y-R)**2)) <= R:
        return True
    else:
        return False

R = 20
WIDTH, HEIGHT = R * 2 + 1, R * 2 + 1
maze = [[1] * WIDTH for _ in range(HEIGHT)]
sets = {}

for x in range(1, 2 * R + 1, 2):
    for y in range(1, 2 * R + 1, 2):
        if round(math.sqrt((x-R)**2 + (y-R)**2)) <= R:
            sets[(x, y)] = (x, y)

for x in range(0, 2 * R + 1):
    for y in range(0, 2 * R + 1):
        if round(math.sqrt((x-R)**2 + (y-R)**2)) > R + 1:
            maze[x][y] = 0

edges = []
for x in range(1, 2 * R + 1, 2):
    for y in range(1, 2 * R + 1, 2):
        if is_in_circle(x, y, R) and is_in_circle(x + 2, y, R):
            edges.append(((x, y), (x + 2, y)))
        if is_in_circle(x, y, R) and is_in_circle(x, y + 2, R):
            edges.append(((x, y), (x, y + 2)))

random.shuffle(edges)

for (x1, y1), (x2, y2) in edges:
    if union((x1, y1), (x2, y2)):
        maze[y1][x1] = 0
        maze[y2][x2] = 0
        maze[(y1 + y2) // 2][(x1 + x2) // 2] = 0

for row in maze:
    print("".join("█" if cell else " " for cell in row))

実行結果は以下となります。
まだまだ色々応用できそうです。

まとめ

本記事では、プログラミングによる迷路の作り方として、Pythonコードを示しました。
また、コード生成においてはChatGPTがかなり優れていることを実感できます。

小学生から大人まで、おすすめできるプログラミングスクールをまとめました。
目的別に紹介していますので、ぜひ参考にしてみてください。

小学生・中学生・高校生におすすめ！エンジニアが選ぶ最新プログラミングスクール15選【2024年版】
小学校でのプログラミング教育必修化など、プログラミング学習への関心が高まってきています。 同時に様々なプログラミングスクールも立ち上がってきていますので、 小中高学生向けのプログラミングスクール一覧をまとめました。 特徴あるプログラミングスクールも出てきていますので、お子さんに合ったスクールを見つけてもらえればと思います。
infomisc.blog
2024.11.14
大学生＆社会人向け！エンジニアが選ぶ最新プログラミングスクール22選【2024年版】
本ページでは大学生や社会人の方向けに、エンジニア目線でのプログラミングスクールをまとめています。 何を目的とするかによっても選ぶべきスクールが変わってきますので、 ここでは5つのカテゴリに分けて、プログラミングスクールを紹介しています。 初学者向け：プログラミング未経験の方向け。入門的な位置づけ。 エンジニア向け：今後ITエンジニアとして転職などを考えている方向け。 Webアプリ開発者向け：Web制作やWebデザインを目的にプログラミングを学習していきたい方向け。 AI技術者＋データサイエンティスト向け：ChatGPTを代表としたAIの活用やデータサイエンティストを目指すことを目的にプログラミングを学習していきたい方向け。 ゲーム開発者向け：ゲームの作成を中心にプログラミングを学習していきたい方向け。
infomisc.blog
2024.11.20

コメント

タイトルとURLをコピーしました