程式自動生成迷宮：深度優先遞迴與優化演算法對比

本文分享兩種自動生成迷宮的演算法：原創遞迴探索法與經典「格點打通法」，並提供完整 C++ 參考實現。

演算法一：隨機遞迴探索（原創思路）

1. 初始化全牆壁地圖。
2. 從中心隨機點出發，隨機選擇方向嘗試移動。
3. 若目標為牆壁且不與現有路徑相通，則打通為路徑。
4. 深度優先遞迴至新點；四周無路則回溯上一節點換方向。
5. 直到所有點探索完畢。

缺點：易產生細碎封閉區塊，視覺效果較雜亂；邊界檢查繁瑣。

演算法二：格點打通法（經典優化）

核心思想：預設地圖為間隔分佈的「格點」，僅在格點間打通牆壁形成通道。格點間隔為 2，邊界外圍保留牆壁。

• 地圖大小：(2*x+3) x (2*y+3)，格點座標為偶數索引。
• 隨機選擇起始格點，隨機順序嘗試四方向。
• 若目標格點未被訪問（仍為牆壁），則打通中間牆壁與目標格點，遞迴進入。
• 天然保證迷宮為「完美迷宮」（任兩點唯一路徑），無孤島、無迴路，結構清晰。

參考實現（Tanky Woo 版本）

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

#define MAZE_MAX 50
char map[MAZE_MAX+2][MAZE_MAX+2];
const int x = 11, y = 11;
int z1, z2;

void printMaze();
void makeMaze();
int searchPath(int, int);

int main() {
    // 初始化全牆壁 (1)
    for (int i=0; i<=x*2+2; ++i)
        for (int j=0; j<=y*2+2; ++j)
            map[i][j] = 1;
    makeMaze();
    cout << "Tanky Woo" << endl;
    printMaze();
}

void printMaze() {
    for (z2=1; z2<=y*2+1; z2++) {
        for (z1=1; z1<=x*2+1; z1++)
            fputs(map[z2][z1]==0 ? "  " : "█", stdout);
        putchar('\n');
    }
    cout << endl;
}

void makeMaze() {
    // 邊界開口
    for (z1=0, z2=2*y+2; z1<=2*x+2; ++z1) {
        map[z1][0] = map[z1][z2] = 0;
    }
    for (z1=0, z2=2*x+2; z1<=2*y+2; ++z1) {
        map[0][z1] = map[z2][z1] = 0;
    }
    map[2][1] = 0;              // 入口
    map[2*x][2*y+1] = 0;        // 出口
    
    srand((unsigned)time(NULL));
    searchPath(rand()%x+1, rand()%y+1);
}

int searchPath(int x, int y) {
    static int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; // 右下左上
    int zx = x*2, zy = y*2;
    map[zx][zy] = 0;            // 打通當前格點
    
    int turn = rand()%2 ? 1 : 3; // 隨機決定順/逆時針
    for (int i=0, next=rand()%4; i<4; ++i, next=(next+turn)%4) {
        int nx = zx + 2*dir[next][0];
        int ny = zy + 2*dir[next][1];
        if (map[nx][ny] == 1) { // 目標格點未訪問
            map[zx+dir[next][0]][zy+dir[next][1]] = 0; // 打通中間牆
            searchPath(x+dir[next][0], y+dir[next][1]);
        }
    }
    return 0;
}

原始碼下載

完整專案：https://up.2cto.com/2011/1118/20111118024909417.rar

總結

格點打通法代碼更精簡、生成迷宮結構更優美，是實務首選。理解遞迴回溯與隨機化方向選擇是掌握迷宮生成的關鍵。