經典 C 語言圖形程式設計：迷宮探路算法實現（避免重複路徑）

編輯：關於C語言

簡介

本文展示一個基於 Turbo C 圖形庫（graphics.h）的迷宮探路程式範例。此版本改進了基本的迷宮走法，核心邏在於「不走回頭路」，即記錄已走過的路徑點，避免重複經過同一座標，從而實現更高效的自動尋路。

程式架構說明

開發環境：Turbo C 2.0 / Borland C++（需 BGI 圖形驅動）。
核心資料結構：使用結構體陣列 struct square p[200] 記錄每一步的座標 (x, y) 與移動方向 direc。
迷宮生成：makebg() 函數隨機生成 22x22 的迷宮地圖（bg[M][N]），0 代表可通行，1 代表牆壁。
繪圖邏輯：drawbg() 繪製迷宮牆壁，drawman() 以 XOR 模式繪製/清除小人圖案，實現無閃爍移動動畫。

雙模式操作

1. 人工控制模式

按鍵 1 進入。使用 W（上）、S（下）、A（左）、D（右）控制移動。程式檢查目標格子是否為通路（bg[i][j]==0）及邊界條件。到達右下角終點 (M-1, N-1) 顯示「YOU WIN!」。按 Q 退出。

2. 電腦自動尋路模式

按下非 1 鍵啟動。採用「右手規則」或優先順序嘗試法（依當前方向決定嘗試順序：右、直、左、後）。

防重複邏輯（核心改進）：

// 記錄當前位置與方向
p[k].x = x; p[k].y = y; p[k].direc = direc;

// 檢查是否重複到達同一座標
if (k > 0) {
    count = k - 1;
    while (count >= 0 && (p[count].x != p[k].x || p[count].y != p[k].y))
        count--;
    // 若找到相同座標，回溯至該步驟，避免陷入死循環
    if (count >= 0) {
        k = count;
        p[k].direc = direc;
        // 根據記錄座標還原迷宮索引 i, j
        i = (p[k].y - len) / step;
        j = (p[k].x - len) / step;
    }
}
k++;

此機制確保自動尋路時，一旦發現走回頭路，立即回溯至上一次訪問該點的狀態，並嘗試新方向，有效解決簡單遞迴或貪婪算法易陷入無限循環的問題。

完整原始碼（關鍵片段）

/* crazymaze.c - 迷宮探路 II */
/* 2003-8-26 */
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <graphics.h>

#define N 22
#define M 22
#define MAXLEN 200

int bg[M][N];
struct square { int x, y, direc; } p[MAXLEN];

void makebg(int, int);
void drawbg(int[][N], int, int, int, int, int);
void drawman(int, int, int);
void rect(int, int, int, int);

void main() {
    int step = 20, len = 10, size = 20;
    int x = 0, y = 0, x0 = 0, y0 = 0;
    int i = 0, j = 0, k = 0, count = 0;
    int gdriver = DETECT, gmode;
    char ch; int direc;

    makebg(M, N);
    initgraph(&gdriver, &gmode, "c:\\tc20\\bgi");
    cleardevice();
    setwritemode(XOR_PUT);
    // ... 繪製介面與迷宮 ...

    // 自動尋路主迴圈片段
    direc = 2; // 初始向東
    i = j = 0; k = 0;
    while (i < M-1 || j < N-1) { // 修正原代碼邏輯判斷條件
        switch(direc) {
            case 0: /* 西 */ /* ... 嘗試順序：南、西、北、東 ... */ break;
            case 1: /* 北 */ /* ... 嘗試順序：西、北、東、南 ... */ break;
            case 2: /* 東 */ /* ... 嘗試順序：北、東、南、西 ... */ break;
            case 3: /* 南 */ /* ... 嘗試順序：東、南、西、北 ... */ break;
        }
        // 執行移動、記錄、防重複檢查 (如上邏輯)
        drawman(x, y, len);
        delay(200);
    }
    closegraph();
}