C語言迷宮探路實現：左手貼牆算法與隨機迷宮生成

專案簡介

本程式實現經典「左手貼牆」迷宮探路算法：機器人始終沿迷宮左側牆壁移動，最終必能找到出口（若迷宮為單連通）。迷宮地圖隨機生成，支援人工控制（WASD）與自動演示兩種模式，基於 Turbo C 圖形庫（graphics.h）繪製。

核心算法：左手貼牆法

規則：嘗試向左轉 → 若左側無牆則左轉前進 → 否則嘗試直行 → 再嘗試右轉 → 最後後退。這保證在單連通迷宮中最終遍歷所有可達路徑並到達終點。

代碼結構解析

常數與全域變數

#define N 22
#define M 22
int bg[M][N];  // 迷宮地圖：0=牆 1=路

int step = 20, len = 10, size = 20;  // 繪圖參數
int x = 0, y = 0;                    // 人物螢幕座標
int i = 0, j = 0;                    // 人物地圖邏輯座標
int direc;                           // 方向：0西 1北 2東 3南

迷宮生成 makebg()（代碼截斷，邏輯推測）

典型隨機迷宮生成算法：

1. 初始化所有牆（bg[][]=0）。
2. 從起點開始，隨機鑿除牆壁（深度優先搜尋 + 回溯 / Prim 算法）。
3. 確保起點 (0,0)、終點 (M-1,N-1) 連通。

繪圖函數

• drawbg()：遍歷 bg[][]，用 rect() 繪製牆壁方塊。
• drawman(x,y,len)：在 (x,y) 繪製人物（XOR 模式便於移動刪除）。
• rect()：繪製矩形塊。

主流程 main()

void main() {
    // 初始化圖形模式
    int gdriver = DETECT, gmode;
    initgraph(&gdriver, &gmode, "c:\\tc20\\bgi");
    cleardevice();
    setwritemode(XOR_PUT);  // XOR 寫入：再畫一次即刪除
    // 繪製迷宮與人物
    makebg(M, N);
    drawbg(bg, M, N, size, 0, 0);
    x = len; y = len;
    drawman(x, y, len);
    // 模式選擇
    outtextxy(60, 120, "PRESS KEY <1> : YOU");
    outtextxy(70, 150, "OTHER KEY : AUTOMATIC");
    if (getch() == '1') {
        // ===== 人工控制模式 =====
        while (getch() != 'q') {
            drawman(x, y, len);  // 擦除舊位置
            switch (getch()) {
                case 'a': if (j>0 && bg[i][j-1]==0 && x>step) { x-=step; j--; } break;  // 左
                case 's': if (i0 && bg[i-1][j]==0 && y>step) { y-=step; i--; } break; // 上
            }
            drawman(x, y, len);  // 繪製新位置
            delay(800);
            if (i>=M-1 && j>=N-1) { outtextxy(150,260,"YOU WIN!"); }
        }
    } else {
        // ===== 自動模式（左手貼牆）=====
        direc = 2;  // 初始向東
        i = j = 0;
        while (i < M-1 || j < N-1) {
            delay(80000);  // 速度控制
            drawman(x, y, len);
            switch (direc) {
                case 0: /* 西 */ break;
                case 1: /* 北 */ break;
                case 2: /* 東 */ break;
                case 3: /* 南 */ break;
            }
            // 核心邏輯：按優先級嘗試左、直、右、後
            // 更新 direc, i, j, x, y
            drawman(x, y, len);
        }
    }
    closegraph();
}

自動模式核心邏輯補完

代碼截斷處為自動導航核心，完整邏輯如下：

// 方向編碼：0西 1北 2東 3南
// 左轉：(direc + 3) % 4  直行：direc  右轉：(direc + 1) % 4  後退：(direc + 2) % 4
int try_dir[4] = { (direc+3)%4, direc, (direc+1)%4, (direc+2)%4 };
int dx[4] = {-1, 0, 1, 0};  // 西北東南
int dy[4] = {0, -1, 0, 1};

for (int k = 0; k < 4; k++) {
    int nd = try_dir[k];
    int ni = i + dy[nd], nj = j + dx[nd];
    if (ni>=0 && ni=0 && nj