自動生成迷宮是個迷人的主題，在起點與終點間充滿各種路徑，起點與終點又必須能連通，乍看之下很神秘；然而嚴格來說，迷宮演算法不難理解，網路上也找得到各種迷宮演算法，實作時更多時候需要的只是細心。

單元的連通

迷宮設計的起點是，雖然起點與終點間充滿各種路徑，不過迷宮說穿了，並不是路徑的問題，而是迷宮中某單元與鄰居單元間如何連通的問題，具體而言，就是哪個鄰接單元可以連到我這個單元，而我這個單元可以連到哪一個鄰接單元，也就是從來哪，往哪去。

以方形迷宮為例，每個單元就是一個細胞（cell），一開始彼此都是不通的：

你可能會想，每個單元應該都是長這樣：

這樣確實也是彼此不通，不過，可以更簡單些，每一格如下也是彼此不通：

當然，真的排列出來會像是：

這樣左邊與下面不就沒有牆了嗎？那是繪圖時的問題，繪圖時補上兩條線就可以了，就資料上的關係來說，一個細胞只要有上牆與右牆，彼此排列後就是互不相通了。

在這樣的資料結構下，如果要能通往右邊的細胞，表示沒有右牆，如果可以通往上面的細胞，表示沒有上牆，如果可以往左走，表示左邊的細胞沒有右牆，如果可以往下走，表示下面的細胞沒有上牆。

因此，如果迷宮的每個細胞牆面狀況如下：

上牆,   上牆,   上牆, 上右牆 
右牆, 上右牆,   上牆,   右牆 
無牆,   右牆,   右牆,   右牆 
上牆,   上牆,   右牆,   右牆

你就可以畫出底下的圖案：

如果左上角為入口，右下角為出口，補上兩條線，就是迷宮了：

不同的迷宮演算法，就是自動產生細胞時採用的方式不同，不過在探討這些演算法之前，會先來手動設置這些細胞，並根據這些細胞畫出迷宮，這是為了先實作一些基礎程式碼。

迷宮的資料結構

每個單元在這邊稱為一個細胞，包含了它的位置以及牆面類型：

function cell(x, y, wallType) {
    return {x, y, wallType};
}

接著是迷宮，因為將實作方形迷宮，要指定它有幾列（row）幾行（column）：

class Maze {
    constructor(rows, columns) {
        this.rows = rows;
        this.columns = columns;
        // 先手動設置
        this.cells = [
            cell(0, 0, Maze.TOP_WALL),   cell(1, 0, Maze.TOP_WALL),       cell(2, 0, Maze.TOP_WALL),   cell(3, 0, Maze.TOP_RIGHT_WALL), 
            cell(0, 1, Maze.RIGHT_WALL), cell(1, 1, Maze.TOP_RIGHT_WALL), cell(2, 1, Maze.TOP_WALL),   cell(3, 1, Maze.RIGHT_WALL), 
            cell(0, 2, Maze.NO_WALL),    cell(1, 2, Maze.RIGHT_WALL),     cell(2, 2, Maze.RIGHT_WALL), cell(3, 2, Maze.RIGHT_WALL), 
            cell(0, 3, Maze.TOP_WALL),   cell(1, 3, Maze.TOP_WALL),       cell(2, 3, Maze.RIGHT_WALL), cell(3, 3, Maze.RIGHT_WALL)
        ];
    }
}

Maze.NO_WALL = 'no_wall';
Maze.TOP_WALL = 'top_wall';
Maze.RIGHT_WALL = 'right_wall';
Maze.TOP_RIGHT_WALL = 'top_right_wall';

可以看到這邊定義了一些常數，可用來設置細胞的牆面類型，這邊先手動設置了每個細胞，後續的文件會自動產生這些細胞。

你可能會想，為什麼這邊使用一維陣列呢？以二維陣列來實作，這樣可以使用列、行指定陣列索引不是比較方便嗎？也是可以！只不過我想要更有彈性一些，這種寫法其實可以不受限於只能用來實作方形迷宮，另一方面，後續在實作自動產生細胞時，產生的順序就是加入一維陣列的順序，不必額外增加程式碼來記錄順序，就可以拿來實作出動畫顯示迷宮生成的過程。

繪製迷宮

迷宮既然是由細胞組成，要能繪製迷宮，總要先能繪製細胞吧！

function drawCell(wallType, cellWidth) {
    if(wallType === Maze.TOP_WALL || wallType === Maze.TOP_RIGHT_WALL) {
        line(0, 0, cellWidth, 0);
    }

    if(wallType === Maze.RIGHT_WALL || wallType === Maze.TOP_RIGHT_WALL) {
        line(cellWidth, 0, cellWidth, cellWidth);
    }    
}

這邊單純就是用線段來代表牆面，繪製出平面迷宮，這邊也可以看到，我將迷宮的資料結構與繪製分開的好處，如果你要繪製更漂亮的牆，或是斜角地圖迷宮，甚至是 3D 迷宮，都是可以的！

接著來繪製整個迷宮：

function drawMaze(maze, cellWidth, sx = 0, sy = 0, ex = maze.columns - 1, ey = maze.rows - 1) {
    // 根據細胞繪製
    maze.cells.forEach(cell => {
        push();

        translate(cell.x * cellWidth, cell.y * cellWidth);
        drawCell(cell.wallType, cellWidth);

        pop();
    });

    // 迷宮外牆
    const totalWidth = cellWidth * maze.columns;
    const totalHeight = cellWidth * maze.rows;

    line(0, 0, 0, totalHeight);  
    line(0, totalHeight, totalWidth, totalHeight);
    line(totalWidth, totalHeight, totalWidth, 0);  
    line(totalWidth, 0, 0, 0);  

    // 起點、終點
    const halfWidth = cellWidth / 2;
    push();
        textSize(cellWidth / 2);
        textAlign(CENTER, CENTER);
        text('S', sx * cellWidth + halfWidth, sy * cellWidth + halfWidth);
        text('E', ex * cellWidth + halfWidth, ey * cellWidth + halfWidth);
    pop();
}

接下來就只要在 p5.js 中設置一下就可以了：

後續不會更動繪圖的部份了，因為要來專注如何自動產生細胞，也如何自動產生 Maze 中的 cells 陣列元素了。