迷宮探路實戰（三）：基於 Dijkstra 思想的最短路徑尋找與可視化

專案背景

本程式實現了一個迷宮自動尋路系統，核心演算法借鑑 Dijkstra 單源最短路徑 思想，採用廣度優先搜尋 (BFS) 分層擴展，保證找到從入口到出口的最短路徑。程式整合了 graphics.h 圖形庫（Borland Turbo C 風格），可動態顯示迷宮生成、探索過程與最終路徑回放動畫。

核心資料結構

#define N 22  // 迷宮寬
#define M 22  // 迷宮高

int bg[M][N];     // 原始迷宮地圖 (0=路, -1=牆)
int aa[M][N];     // 搜索標記陣列 (0=未訪問, >0=步數/層級)

struct pace {     // 路徑節點
    int pre;      // 前驅節點索引 (回溯用)
    int x, y;     // 螢幕座標
    int ri, rj;   // 迷宮網格座標
} road[M*N], bestroad[M*N];

road 陣列作為 BFS 隊列（靜態環狀隊列模擬），記錄每一步的擴展節點；bestroad 用於存儲最終回溯出的最短路徑。

演算法流程：分層 BFS (Dijkstra 簡化版)

因迷宮邊權重均為 1，Dijkstra 退化為 BFS。程式採用雙指標分層技巧避免額外隊列結構：

1. 初始化：入口 (0,0) 標記 aa[0][0]=1，加入 road[0]，begin=0, end=0, le=1。
2. 主循環 (while(!suc))：
   • le++：下一層級標記值。
   • 遍歷當前層所有節點 k = begin ... end。
   • 對每節點嘗試四方向擴展 (dx, dy)。
   • 若新座標 (i,j) 合法且 aa[i][j]==0 (未訪問路)：
     • 標記 aa[i][j] = le。
     • 記錄前驅 road[end+cnt].pre = k，座標入隊。
     • 若到達終點 (N-1, M-1) → suc=1，跳出。
3. 層級切換：begin = end+1; end = end+cnt;（下一層成為當前層）。

此過程構建了一棵以入口為根的最短路徑樹，pre 指針指向父節點。

路徑回溯與動畫回放

// 1. 逆序回溯填充 bestroad
i = end; j = 0;
while (i != -1) {
    bestroad[j] = road[i]; // 複製座標
    i = road[i].pre;       // 往父節點回溯
    j++;
}

// 2. 反轉 bestroad 使其從入口到出口
for (i = 0; i < j/2; i++) swap(bestroad[i], bestroad[j-1-i]);

// 3. 動畫回放
drawman(x0, y0, len); // 繪製起點小人
for (i = 0; i < j; i++) {
    drawman(bestroad[i].x, bestroad[i].y, len); // 移動到下一步
    delay(80000);       // 延時
    drawman(bestroad[i].x, bestroad[i].y, len); // 擦除 (XOR 模式)
}

利用 setwritemode(XOR_PUT)，同座標繪製兩次即可實現「移動不留痕」效果。

迷宮生成策略

makebg() 採用兩階段隨機生成：

1. 主幹路徑：從 (0,0) 到 (M-1,N-1) 隨機游走（避免立即回頭），保證至少存在一條通路。
2. 隨機填充：其餘牆壁以 50% 概率打通，增加複雜度與多解性。

圖形繪製模組

• drawbg()：遍歷 aa[][]，-1 畫實心矩形（牆），0 留白（路），外圍畫邊框。
• drawman()：用線段繪製簡易火柴人（頭、身、手、腳）。
• rect()：逐行掃描線填充實心矩形。

編譯與運行環境說明

代碼針對 Borland Turbo C 2.0 / TC++ 環境，依賴 graphics.h、initgraph()、BGI 驅動。現代環境下可考慮：

• DOSBox 運行原版 TC。
• 移植至 SDL2 / SFML / EasyX 等現代圖形庫（替換繪圖函數即可，邏輯不變）。
• Web 端用 Canvas/JavaScript 重寫。

總結與啟發

• 靜態陣列模擬隊列：road[M*N] + begin/end 指針，無需動態分配，嵌入式系統常用技巧。
• 分層 BFS 即 Dijkstra (單位權)：le 變量巧妙標記層級/距離，pre 構建前驅樹。
• XOR 繪圖模式：無需雙緩衝即可實現簡易動畫，經典 DOS 遊戲技巧。
• 關注點分離：地圖生成、搜索邏輯、圖形渲染模組化，便於移植與測試。

這個小專案雖代碼古老，但蘊含的圖搜索核心邏輯、靜態資料結構技巧、即時可視化思想，至今仍具備極高的教學與工程參考價值。