二元樹迷宮


在〈手動迷宮〉中們制定了細胞的資料結構，以線段作為牆來繪製迷宮，接下來只要能自動產生細胞資料，就能生成迷宮，這邊要來說明最簡單的二元樹演算（Binary Tree Algorithm）。

二元樹演算

二元樹演算概念很簡單，用它來理解自動生成迷宮的原理是個不錯的出發點，而且可以生成完美迷宮 （Perfect maze），也就是任兩個細胞間只有一條路徑可以互通的迷宮。

以 4 乘 4 迷宮為例，首先，每個牆都還沒打穿，任選一個起點：

二元樹迷宮

現在來丟硬幣吧！如果是正面，就打掉右邊的牆，反面就打掉上面的牆，然後移到下一格，例如，若硬幣丟出了反面，往右一格移動，狀態會變成：

二元樹迷宮

對二元樹演算來說，從哪一格開始，或者下一格是哪格都無所謂，為了便於說明，下一格就都往右吧！假設現在又依序丟出了 正、反，狀態就會變成：

二元樹迷宮

到達最右邊的區塊了，現在該怎麼辦呢？不能打掉右邊的牆了，因為那是迷宮的邊界，只能打掉上面的牆，既然這樣，就表示最右邊一排都不用丟硬幣了，直接打掉上面的牆，那麼就一次處理吧！

二元樹迷宮

類似地，如果是最上一排，不能打掉上面的牆，因此也不用丟硬幣，一律打掉右邊的牆：

二元樹迷宮

還剩底下算來第二排與第三排還沒處理，那就先來到左下二排：

二元樹迷宮

假設硬幣丟出了正、反，並持續往右移動，接著又丟出了反面：

二元樹迷宮

現在只剩一排還沒處理了了，從該排最左邊開始，並丟出正、正、正：

二元樹迷宮

YA！迷宮完成了，入口、出口可以任選，因為任兩個細胞間只有一個路徑連通。

為什麼是二元樹？

來為每個細胞設個中心點，然後將互通的點連接起來：

二元樹迷宮

接著不看牆，只看連接中心點的線段，然後稍微轉個角度：

二元樹迷宮

這不就成了二元樹了嗎？每次選擇打掉一個牆，其實就是在選擇父節點，只能打掉一個牆，表示各節點只能有一個父節點，也就是從某個子節點開始，要往特定一個父裔節點移動，只會有一條路徑。

任兩個節點間要能互通，表示它們會有一個共通的父裔節點，既然從某個子節點開始，要往特定一個父裔節點移動，只會有一條路徑，那就表示任兩節點間只會有一條路徑連通。

二元樹迷宮

無論是哪種迷宮演算，若要生成完美迷宮，就是形成某種樹狀結構，從某個子節點開始，要往特定一個父裔節點移動，只會有一條路徑，從而保證路徑不會形成迴圈。

就二元樹演算來說，每個細胞基本上就只是丟硬幣決定要打掉上牆或右牆，然而這就表示，連通至父節點的方式，只能是往上或往右，這會令迷宮產生偏差（Bias），不管你怎麼改變生成細胞的順序，最後生成的迷宮，根節點一定是在右上角。

二元樹迷宮

想改進這個偏差的話，可以加入更多隨機性或變化，例如，後續文件會示範上下左右隨機行進，而不只是往右或往上。

實作二元樹迷宮

二元樹迷宮是丟硬幣決定打右牆或上牆，相對地，就是丟硬幣決定保留上牆或右牆，基於〈手動迷宮〉的程式基礎，可以如下實作：

function binaryTreeRandomCell(x, y, rows, columns) {
    // 最右排
    if(x === columns - 1) {  
        return cell(x, y, Maze.RIGHT_WALL);
    }

    // 最上排
    if(y === 0) {            
        return cell(x, y, Maze.TOP_WALL);    
    }

    // 隨機選擇保留上牆或右牆
    return cell(x, y, random([Maze.TOP_WALL, Maze.RIGHT_WALL]));
}

p5.js 的 random 可以指定清單，每次隨機從清單中挑選一個，用來隨機選擇保留上牆或右牆就很方便。

就二元樹演算來說，每個細胞基本上就只是丟硬幣決定要打掉上牆或右牆，這表示生成細胞的順序不重要，就實作而言，最簡單的方式就是迴圈依序走訪每一個細胞，來調整一下〈手動迷宮〉中的 Maze 實作，加入一個 binaryTree 方法：

class Maze {
    constructor(rows, columns) {
        this.rows = rows;
        this.columns = columns;
    }

    binaryTree() {
        this.cells = [];
        for(let y = 0; y < this.rows; y++) {
            for(let x = 0; x < this.columns; x++) {
                this.cells.push(binaryTreeRandomCell(x, y, this.rows, this.columns));
            }
        }
    }
}

現在可以來自動生成迷宮了，可以調整底下範例的 rows、columns，指定生成不同大小的迷宮：

單純地生成迷宮很有趣，若能進一步地將生成的過程以動畫方式展現，就會更有趣了，因為細胞產生的順序，就是加入至 cells 陣列的順序，只要指定 cells 中的細胞要畫出幾個，就可以階段性地展現生成過程，為此，可以實作一個 drawMazeCells 函式：

function drawMazeCells(n, maze, cellWidth, sx = 0, sy = 0, ex = maze.columns - 1, ey = maze.rows - 1) {
    // 白色背景
    for(let i = 0; i < n; i++) {
        const cell = maze.cells[i];
        push();
        noStroke();
        translate(cell.x * cellWidth, cell.y * cellWidth);
        square(0, 0, cellWidth);
        pop();    
    }

    // 細胞牆面
    for(let i = 0; i < n; i++) {
        const cell = maze.cells[i];
        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(halfWidth);
        textAlign(CENTER, CENTER);
        text('S', sx * cellWidth + halfWidth, sy * cellWidth + halfWidth);
        text('E', ex * cellWidth + halfWidth, ey * cellWidth + halfWidth);
    pop();
}

來看看動畫展示生成迷宮的過程：

不過，因為是單純地以列、行順序生成細胞，過程略顯單調了些，後續文件會談到隨機上、下、左、右生成細胞的話，屆時過程就會有更多的變化性。

一個有趣的問題是，就細胞來說，它可能會有幾種狀態呢？嗯！因為牆面有上牆、上右牆、右牆、無牆，有四種狀態？不！只有兩種，別忘了，我們是在每個細胞丟硬幣決定的，只會有正與反兩種狀態，對應至牆面，細胞最後只可能會有上牆或右牆，不會有另外兩種牆面狀態，或者說，二元樹演算法只會用到其中兩種。