在〈Theta 迷宮（二）〉中談到，可以依圓周長決定選擇將細胞一切為二的時機，只不過就目前 Maze 的細胞資料結構設計而言，實作這個需求會有些麻煩，如果細胞可以知道自身的細胞鄰居，特別是往內及外往的鄰居有哪些，實作時會簡單許多。

鄰居與牆面設計

可以使用鏈結的概念來實作細胞與細胞鄰居間的關係，對於以下的紅色細胞，它會有的鄰居定義為 inward（往內）、outwards（往外）、cw（順時針）、ccw（逆時針），outwards 是複數，因為往外的鄰居可能是一個，或者在切分處會有兩個：

因為現在就是要針對 Theta 迷宮設計，因此就直接採 inward、outwards 之類的名詞了，當然如果你願意，將這邊的迷宮設計畫為像在〈Theta 迷宮（二）〉中的方形迷宮，也是可以的。

在牆面設計上，每個細胞預設的牆面有內牆與逆時針牆，座標 (row, column) 等的關係如下：

注意！你不能為細胞設計外牆，因為在切分點時，往外會有兩個鄰居，若這時選擇其中一個往外的鄰居，往外走時拆掉了目前細胞的外牆，就等於往外的那兩個鄰居門戶都開了，這就不正確了。

（〈Theta 迷宮（一）〉中的牆面就算設計了外牆，也不會有這個問題，是因為沒有切分細胞。）

根據圓周切分細胞

接下來就直接用程式實作來進行說明，首先還是要先定義細胞的資料結構：

function cell(row, column, wallType) {
    // inward、outwards、cw、ccw 預設都是 undefined
    return {row, column, wallType, notVisited: true};
}

因為 JavaScript 中，物件的特性沒有定義時，試圖存取該特性會得到 undefined，cell 函式中不用特別定義 inward、outwards、cw、ccw 特性後指定為 undefined，因為就執行效果來說會得到相同的結果（雖然技術上有些差別，這邊不是在討論 JavaScript，就不多談了）。

來看一下迷宮細胞的初始建構：

class ThetaMaze {
    constructor(totalRows, beginingColumns, dividedRatio=1.5) { 
        constructRows(this, totalRows, beginingColumns, dividedRatio);
        configNeighbors(this);
    }
}

ThetaMaze.NO_WALL='no_wall';
ThetaMaze.INWARD_WALL='inward_wall';
ThetaMaze.CCW_WALL='ccw_wall';
ThetaMaze.INWARD_CCW_WALL='inward_ccw_wall';

// 處理每個細胞的便捷函式
function forEachCell(maze, cellAction) {
    maze.rows.forEach(row => {
        row.forEach(cellAction);
    });
}

constructRows 為迷宮建構每一列的細胞，細胞的劃分會根據圓周決定，在這邊並不會考慮繪圖時的處理，不會有細胞寬度資訊，因此計算圓周的方式是基於單位圓，也就是半徑為 1 的圓：

function constructRows(maze, totalRows, beginingColumns, dividedRatio) {
    maze.rows=[];

    // 建構索引 0 列
    const cells=[];
    for(let column=0; column < beginingColumns; column++) {
        cells.push(cell(0, column, ThetaMaze.INWARD_CCW_WALL));
    }
    maze.rows.push(cells);

    // 建構其餘的列
    const cellWidth=1 / totalRows;      // 基於單元圓計算細胞寬度
    for(let row=1; row < totalRows; row++) {
        const r=row * cellWidth;       
        const circumference=TWO_PI * r; // 該列外圓周長

        // 若依舊使用前一列的細胞數，細胞外牆的長度
        const previousColumns=maze.rows[row - 1].length;
        const estimatedOutWallWidth=circumference / previousColumns;

        // 細胞外牆的長度與細胞寬度相比，超過 dividedRatio 時切分為 2
        const ratio=estimatedOutWallWidth / cellWidth >= dividedRatio ? 2 : 1;
        const cols=previousColumns * ratio;
        const cells=[];
        for(let column=0; column < cols; column++) {
            cells.push(cell(row, column, ThetaMaze.INWARD_CCW_WALL));
        }
        maze.rows.push(cells);
    }
}

程式碼中的註解說明了切分的方式，這邊可注意的是 dividedRatio，預設為 1.5，也就是細胞外牆的長度與細胞寬度相比，大於等於 1.5 時就切分，這個比例可以應付約 30 環左右的切分：

不過你可以看出三個明顯的環狀區段，更多的環數會有更多的環狀區段，例如 50 環：

這種狀況是正常的，因為你是圓周到一定程度才切分，在切分處細胞一定較小，然後往外較大，留個 dividedRatio 作為參數，可以微調環狀區段，例如同為 50 環，然後 dividedRatio 變成 2：

選擇 dividedRatio 預設值為 1.5，是因為我覺得就算到了 30 環，畫出來的迷宮也蠻好看的，30 幾環差不多也是執行環境在遞迴回溯演算時，會遇到堆疊數量的限制了，如果你想要更多的環，可以試著將 dividedRatio 設更高，並看看繪圖後的效果。

另一個考量是，ratio 也可以是根據 r 的不同而變動，例如：

const ratio=estimatedOutWallWidth / cellWidth >= (dividedRatio + r * r) ? 2 : 1;

這會讓超過百環的切分時，細胞趨向一個穩定大小，程式中我沒這麼做的原因是，在不調整執行環境堆疊數量的限制下，這種考量沒有意義，畢竟你也算不出迷宮。

接著來看看建立細胞間關係的 configNeighbors：

function configNeighbors(maze) {
    forEachCell(maze, cell => {
        // 除了最外環之外，每個細胞都有向外的一或兩個鄰居，這邊先準備好陣列
        if(cell.row < maze.rows.length - 1) {
           cell.outwards=[];
        }
    });

    forEachCell(maze, cell => {
        const row=maze.rows[cell.row];
        // 逆時針與順時針的鄰居
        cell.ccw=row[(cell.column + 1) % row.length];
        cell.cw=row[cell.column > 0 ? cell.column - 1 : cell.column - 1 + row.length];

        if(cell.row > 0) {
            // 往內與往外的鄰居
            const ratio=row.length / maze.rows[cell.row - 1].length;
            cell.inward=maze.rows[cell.row - 1][floor(cell.column / ratio)];
            cell.inward.outwards.push(cell);
        }
    });
}

因為資料結構上的改變，我們可以知道每列的細胞數，用來計算往內與往外的鄰居就方便多了，畢竟 ratio 只會是 1 或 2，在 1 的時候，表示兩列的細胞數相同，為 2 的時候，表示目前這列比前一列的細胞數多一倍，內牆細胞的 column 座標自然就是除以 2 後的整數部份。

接下來呢？資料結構改變了，遞迴回溯演算還能用嗎？當然！只是實作面上調整了一下罷了，遞迴回溯演算本身的流程還是不變的：

function notVisited(maze, row, column) {
    return maze.rows[row][column].notVisited;
}

function isVisitable(cell) {
    return cell.notVisited;
} 

const IN =0;  // 內
const OUT=1;  // 外
const CW =2;  // 順
const CCW=3;  // 逆

// 一律傳回陣列，這便於呼叫者使用一致的方式處理
function nextCells(cell, dir) {
    return [
        cell.inward ? [cell.inward] : [], 
        cell.outwards ? cell.outwards : [],
        cell.cw ? [cell.cw] : [], 
        cell.ccw ? [cell.ccw] : []
    ][dir];
}

// 往內走，打掉目前細胞內牆
function visitIN(maze, next, currentCell) {
    if(currentCell.wallType === ThetaMaze.INWARD_CCW_WALL) {
        currentCell.wallType=ThetaMaze.CCW_WALL;
    }
    else {
        currentCell.wallType=ThetaMaze.NO_WALL;
    }
    next.notVisited=false;
}

// 往外走，打掉下個細胞的內牆
function visitOUT(maze, next, currentCell) {
    next.wallType=ThetaMaze.CCW_WALL;
    next.notVisited=false;
}

// 順時針，打掉下個細胞的逆時牆
function visitCW(maze, next, currentCell) {
    next.wallType=ThetaMaze.INWARD_WALL;
    next.notVisited=false;
}

// 逆時針，打掉目前細胞的逆時針牆
function visitCCW(maze, next, currentCell) {
    if(currentCell.wallType === ThetaMaze.INWARD_CCW_WALL) {
        currentCell.wallType=ThetaMaze.INWARD_WALL;
    }
    else {
        currentCell.wallType=ThetaMaze.NO_WALL;
    }
    next.notVisited=false;
}

function visitNext(maze, next, currentCell, dir) {
    switch(dir) {
        case IN:  
            visitIN(maze, next, currentCell); break;
        case OUT:
            visitOUT(maze, next, currentCell); break;
        case CW:
            visitCW(maze, next, currentCell); break;
        case CCW:
            visitCCW(maze, next, currentCell); break;
    }
}

function backtracker(maze, currentCell) {
    // 隨機的四個方向
    const rdirs=shuffle([IN, OUT, CW, CCW]);

    // 找出可造訪的方向清單
    const vdirs=rdirs.filter(dir => {
        return nextCells(currentCell, dir).some(isVisitable);
    });

    // 完全沒有可造訪的方向就回溯
    if(vdirs.length === 0) {
        return;
    }

    // 逐一造訪可行方向
    vdirs.forEach(dir => {
        const cells=nextCells(currentCell, dir);
        // 原先可造訪的方向，可能因為深度優先的關係被造訪過了
        // 因此必須再次確認一次是否仍然可以造訪
        cells.forEach(cell => {
            if(isVisitable(cell)) {
                visitNext(maze, cell, currentCell, dir);
                // 就目前迷宮狀態進行遞迴回溯演算
                backtracker(maze, cell);
            }
        });
    });
}

其實，你要在方形迷宮中，就設計細胞間的關係以鏈結來串起，也是可以的，只不過這是需求與設計間平衡的問題！

如果只是面對方形迷宮，〈遞迴回溯迷宮〉的實作方式比較簡單，畢竟上、下、左、右就只是座標索引加減 1 的問題，當時若透過鏈結來設計，或許你還會覺得多此一舉。

然而，如果你一開始就是想使用遞迴回溯演算，並用同一個程式作為通用實作，可處理完方形迷宮與 Theta 迷宮，那麼一開始就設計使用鏈結來串起細胞間的關係，這樣的實作就會有價值。

一開始該設計到什麼程度呢？看需求！需求會變化啊！不能一開始就考量多一些嗎？這又會引發過度設計的問題…因此才說，這是需求與設計間平衡的問題…這已經不是 p5.js 這系列的重點了…XD

話題拉回來，ThetaMaze 要加個 backtracker：

class ThetaMaze {
    constructor(totalRows, beginingColumns, dividedRatio=1.5) { /
        constructRows(this, totalRows, beginingColumns, dividedRatio);
        configNeighbors(this);
    }

    backtracker() {
        const currentCell=this.rows[0][0];
        currentCell.notVisited=false;
        backtracker(this, currentCell);
    }   
}

最後就是繪製迷宮了，這沒什麼困難的了吧！

function drawMaze(maze, cellWidth) {
    forEachCell(maze, cell => {
        const thetaStep=TWO_PI / maze.rows[cell.row].length;

        const innerR=(cell.row + 1) * cellWidth;
        const outerR=(cell.row + 2) * cellWidth; 
        const theta1=-thetaStep * cell.column;
        const theta2=-thetaStep * (cell.column + 1);

        const innerVt1=p5.Vector.fromAngle(theta1, innerR);
        const innerVt2=p5.Vector.fromAngle(theta2, innerR);
        const outerVt2=p5.Vector.fromAngle(theta2, outerR);

        if(cell.wallType === ThetaMaze.INWARD_WALL || cell.wallType === ThetaMaze.INWARD_CCW_WALL) {
            line(innerVt1.x, innerVt1.y, innerVt2.x, innerVt2.y);
        }

        if(cell.wallType === ThetaMaze.CCW_WALL || cell.wallType === ThetaMaze.INWARD_CCW_WALL) {
            line(innerVt2.x, innerVt2.y, outerVt2.x, outerVt2.y);
        }
    });

    const thetaStep=TWO_PI / maze.rows[maze.rows.length - 1].length;
    const r=cellWidth * (maze.rows.length + 1);
    for(let theta=0; theta < TWO_PI; theta=theta + thetaStep) {
        const vt1=p5.Vector.fromAngle(theta, r);
        const vt2=p5.Vector.fromAngle(theta + thetaStep, r);
        line(vt1.x, vt1.y, vt2.x, vt2.y);
    }  
}

來看看〈Theta 迷宮（二）〉中會開始過密的 24 x 8 迷宮，改為以上實作後的表現：

以下是完整的程式實作：