この記事では、Pythonを使って迷路を自動生成し、BFS（幅優先探索）アルゴリズムでスタートからゴールまでの最短ルートを求め、さらにその過程をアニメーションで可視化する方法を紹介します。
初心者でも実装できる構成で、アルゴリズムの「仕組み」と「動き」を同時に学べます。
ぜひご自身の環境で作成して動かしてみてください！
🔧 使用技術
- Python
- matplotlib（アニメーション表示と画像保存）
- numpy（迷路データの管理）
- BFSアルゴリズム（最短経路探索）
🧠 表示の構成
| 要素 | 表示方法 |
|---|---|
| 壁 | 黒（値 0） |
| 通路 | 白（値 1） |
| 探索位置 | 赤い点で表示 |
| スタート | 左上 (1, 1) |
| ゴール | 右下 (HEIGHT-2, WIDTH-2) |
🧩 実際につまづいたポイントと解決方法
実装時に遭遇した不具合と解決策を共有します。これから取り組む方が同じところでハマらないように参考にしてください。
- ① 赤い点（探索者）が表示されなかった
はじめ、ルートをたどる赤い点が見えませんでした。
原因： カラーマップをグレー系（cmap='gray'）にしていたため、赤が背景に埋もれていた。
解決：ax.plot(..., 'ro')と明示的に赤指定することで解決。GIF自体は正常に動いていました。 - ② 探索者が壁を通ってしまう
設計初期では赤い点が白い通路ではなく、黒い壁の上を進んでいました。
原因： BFS内で通路判定（maze[nx, ny] == 1）を忘れていた。
解決： 条件文に通路判定を追加することで、正しく動作するように修正。 - ③ GIFが動かないときの対処法
pillowがインストールされているか確認：pip install pillow- 保存時は
ani.save(..., writer='pillow')を明示 - Jupyter Notebookではノートブック内再生が不安定なため、生成されたGIFを直接開く
- 保存先フォルダの書き込み権限を確認
最初に赤い点が表示されなかったときは「コードは動いているのになぜ？」と悩みました。試行錯誤して原因を突き止めた瞬間、アルゴリズムと可視化の関係が理解でき、プログラミングの面白さを再認識しました。
🎞️ アニメーションGIF
以下が実際に生成されたアニメーションGIFです。探索者が白い通路を通ってゴールまで進む様子が赤い点で表示されます。
📸 実際の出力結果
以下は最終的に生成された迷路画像です。赤い点がスタートからゴールまでの最短ルートを示しています。
💻 実行方法
pip install matplotlib numpy pillow
🧩 Pythonスクリプト（最終版）
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import numpy as np
import random
from collections import deque
WIDTH, HEIGHT = 21, 21
DIRS = [(-2, 0), (2, 0), (0, -2), (0, 2)]
maze = np.zeros((HEIGHT, WIDTH), dtype=int)
def generate_maze():
stack = [(1, 1)]
maze[1, 1] = 1
while stack:
x, y = stack[-1]
neighbors = []
for dx, dy in DIRS:
nx, ny = x + dx, y + dy
if 0 < nx < HEIGHT and 0 < ny < WIDTH and maze[nx, ny] == 0:
neighbors.append((nx, ny))
if neighbors:
nx, ny = random.choice(neighbors)
maze[(x + nx)//2, (y + ny)//2] = 1
maze[nx, ny] = 1
stack.append((nx, ny))
else:
stack.pop()
def bfs_shortest_path():
start, goal = (1, 1), (HEIGHT-2, WIDTH-2)
queue = deque([start])
visited = set([start])
parent = {}
while queue:
x, y = queue.popleft()
if (x, y) == goal:
break
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x+dx, y+dy
if 0 <= nx < HEIGHT and 0 <= ny < WIDTH and maze[nx, ny] == 1 and (nx, ny) not in visited:
visited.add((nx, ny))
parent[(nx, ny)] = (x, y)
queue.append((nx, ny))
path, cur = [], goal
while cur != start:
path.append(cur)
cur = parent.get(cur)
if cur is None: return []
path.append(start)
path.reverse()
return path
generate_maze()
path = bfs_shortest_path()
fig, ax = plt.subplots()
img = ax.imshow(maze, cmap='gray', vmin=0, vmax=1, interpolation='none')
ax.set_title("Shortest Path from Start to Goal")
ax.axis('off')
def update(frame):
if frame < len(path):
x, y = path[frame]
ax.plot(y, x, 'ro', markersize=4)
return [img]
ani = animation.FuncAnimation(fig, update, frames=len(path), interval=100, blit=False)
ani.save("maze_solution.gif", writer='pillow', fps=10)
plt.imshow(maze, cmap='gray', vmin=0, vmax=1, interpolation='none')
for x, y in path:
plt.plot(y, x, 'ro', markersize=4)
plt.title("Final Maze with Shortest Path")
plt.axis('off')
plt.savefig("maze_solution.png", bbox_inches='tight', pad_inches=0.1)
plt.show()
📘 BFSアルゴリズムの仕組み
BFS（幅優先探索）は、探索範囲を「階層的に」広げていくアルゴリズムです。
隣接ノードをすべて同時に探索するため、最初にゴールへ到達した経路が常に最短になります。DFSとの違いは、BFSが「最短距離保証型」である点にあります。
🚀 応用例の紹介
この迷路探索アニメーションは、教育・ゲーム・アルゴリズム可視化など、幅広い分野に応用できます。単なるプログラミング練習にとどまらず、実践的なシミュレーションや教材としても役立ちます。
1. アルゴリズム学習教材
DFS（深さ優先探索）やA*アルゴリズムなど、他の探索手法と比較することで、探索順序・効率・経路長の違いを視覚的に理解できます。アルゴリズム教育では「可視化」によって抽象的な概念が具体化し、理解度が大幅に向上します。
2. ゲーム開発
迷路ゲームの自動生成エンジンとして活用したり、敵キャラクターの経路探索ロジックに応用することが可能です。探索の進行をリアルタイムで描画すれば、プレイヤーが「見て楽しめるAI挙動」を作ることもできます。
3. ロボットの経路計画シミュレーション
実際のロボット工学でも、障害物を避けながらゴールへ進む「経路計画（Path Planning）」が重要なテーマです。今回のBFS迷路探索は、その基本概念を理解するための優れた入門例になります。
4. データ構造・グラフ理論の可視化
迷路は本質的に「グラフ構造（ノードとエッジ）」として表現できます。グラフ探索アルゴリズムを迷路で視覚化することで、理論的な学習を直感的に理解できるようになります。
💡 さらに発展させるアイデア
- 迷路サイズ（WIDTH・HEIGHT）をユーザー入力で変更できるようにする
- 探索速度（interval）を調整してアニメーション速度を制御する
- DFSやA*など別のアルゴリズムと比較して、探索経路の違いを可視化する
🧩 動作確認環境
- Python 3.11
- matplotlib 3.9.2
- numpy 1.26+
- pillow 10.3.0
📚 参考資料
📝 まとめ
- Pythonとmatplotlibを使えば、迷路の自動生成と探索アニメーションが簡単に実装できる
- BFSアルゴリズムを使えば、最短ルートを確実に求められる
- カラーマップ指定や通路判定を意識すると、正しく動作するアニメが作れる
- 教育・ゲーム・ロボット制御・アルゴリズム学習など応用範囲が広い
Python初心者でも取り組みやすく、アルゴリズムの理解にも役立つこの迷路探索アニメーション。
ぜひ自分なりに改造して、オリジナルの迷路アプリを作ってみてください！
