Python 影像迷宮求解器：BFS、A* 與並查集視覺化實作

本專案展示三種演算法解決「迷宮圖片」路徑搜尋問題，並將搜尋過程輸出為動態 GIF 視覺化。程式碼已開源於 GitHub，歡迎參考與改進。

演算法比較

BFS（廣度優先搜尋）：層層擴展，保證找到最短路徑，但搜尋節點數較多。

A* 算法：引入啟發式函數（曼哈頓距離），大幅減少探索節點，但優先隊列操作帶來額外開銷，在本測試圖上實際耗時反而略高於 BFS。

並查集：非尋路用途，而是將迷宮中的連通白色區域標記為不同顏色，展示圖像分割應用。

核心程式架構

# -*- coding:utf-8 -*-
from PIL import Image
import Queue
import time

# 參數設定
imageName = 'p.png'
saveName = '{0:05d}.png'
startPoint = [400, 984]
endPoint   = [398, 25]

# 1. 圖片二值化
def changeImage():
    ...

# 2. BFS 實作
def bfs(start, end):
    ...

# 3. A* 實作
def aStar(start, end):
    ...

# 4. 並查集連通區域標記
def connectivity():
    ...

# 執行與計時
t1 = time.time()
changeImage()
# bfs(startPoint, endPoint)
# aStar(startPoint, endPoint)
connectivity()
t2 = time.time()
print t2 - t1

關鍵技術細節

• 使用 PIL.Image 載入像素並轉為 RGB 模式，以閾值 128 二值化為黑白。
• BFS 採用佇列儲存完整路徑，每擴展一步即將像素標記為填充色，每 200 步輸出一幀。
• A* 使用 Queue.PriorityQueue，優先級 = 路徑長度 + 啟發式估值。
• 並查集採用路徑壓縮優化 find，掃描圖像時依左、上鄰像素決定合併策略。
• 動態圖生成利用 ImageMagick convert 指令：convert -delay 10 *.png maze.gif。

效能觀察與心得

A* 理論上搜尋節點較少，但 Python 的 PriorityQueue 開銷在小型迷宮中抵銷優勢。實務上若迷宮極大或需即時回應，建議改用 C/C++ 或引入 heapq 優化。並查集展示了圖像處理中連通區域分析的經典應用，可延伸至 OCR 前處理、缺陷檢測等領域。