遊戲尋路演算法入門：回溯法遞歸實作與全路徑枚舉

編輯：關於C語言

問題定義

在二維網格地圖中，從起點 (1,0) 找到終點 (值為 2)。地圖編碼：`1`=可通行路徑，`0`=牆壁/障礙，`2`=目標點。

地圖與狀態資料結構

#define MAX_N 6

// 地圖靜態資料
static int gPath[MAX_N][MAX_N] = {
    {0, 0, 0, 0, 1, 1},
    {1, 1, 0, 0, 1, 0},
    {0, 1, 1, 1, 1, 0},
    {0, 0, 1, 0, 1, 2},
    {0, 0, 1, 0, 1, 0},
    {0, 0, 1, 1, 1, 0}
};

// 走訪標記陣列：0=未走，'#'=已走/路徑上
static int gValue[MAX_N][MAX_N] = {0};

核心輔助函式：合法性檢查

int check_pos_valid(int x, int y) {
    // 1. 邊界檢查
    if (x < 0 || x >= MAX_N || y < 0 || y >= MAX_N) return 0;
    // 2. 是否為路
    if (0 == gPath[x][y]) return 0;
    // 3. 是否已走過（避免循環）
    if ('#' == gValue[x][y]) return 0;
    return 1;
}

演算法一：尋找單一路徑（DFS + 回溯）

策略：嘗試四個方向（上、左、下、右），任一方向成功即返回。失敗則回溯（清除標記）。

int find_path(int x, int y) {
    if (!check_pos_valid(x, y)) return 0;

    // 到達終點
    if (2 == gPath[x][y]) {
        gValue[x][y] = '#';
        return 1;
    }

    // 標記當前點為路徑一部分
    gValue[x][y] = '#';

    // 依序嘗試四個方向（順序影響找到的路徑形狀）
    if (find_path(x, y - 1)) return 1; // 上
    if (find_path(x - 1, y)) return 1; // 左
    if (find_path(x, y + 1)) return 1; // 下
    if (find_path(x + 1, y)) return 1; // 右

    // 四個方向皆失敗 → 回溯
    gValue[x][y] = 0;
    return 0;
}

演算法二：列印所有可能路徑

修改遞歸函式：到達終點時列印當前路徑，並不返回，繼續回溯尋找下一條路徑。

void print_path() {
    for (int i = 0; i < MAX_N; ++i) {
        for (int j = 0; j < MAX_N; ++j)
            printf("%c ", gValue[i][j] ? '#' : '.');
        printf("\n");
    }
    printf("----------\n");
}

void find_all_paths(int x, int y) {
    if (!check_pos_valid(x, y)) return;

    if (2 == gPath[x][y]) {
        gValue[x][y] = '#';
        print_path();
        gValue[x][y] = 0; // 回溯繼續找
        return;
    }

    gValue[x][y] = '#';
    find_all_paths(x, y - 1);
    find_all_paths(x - 1, y);
    find_all_paths(x, y + 1);
    find_all_paths(x + 1, y);
    gValue[x][y] = 0; // 回溯
}

主程式呼叫

int main() {
    // 尋找單一路徑
    if (find_path(1, 0)) {
        printf("找到路徑:\n");
        print_path();
    } else {
        printf("無路可走。\n");
    }

    // 列印所有路徑
    printf("\n--- 所有可能路徑 ---\n");
    find_all_paths(1, 0);
    return 0;
}