在〈二元樹迷宮〉中談到，就二元樹演算來說，連通至父節點的方式，只能是往上或往右，這會令迷宮產生偏差（Bias），想改進這個偏差的話，可以加入更多隨機性或變化。
遞迴回溯演算
例如，從目前格子隨機地選擇一個未造訪的鄰接格子，打通中間的牆後造訪該格，然後重複以上過程；若遇到鄰接格子都造訪過了，退回上一格，試著找出該格未造訪的鄰接格子…以上流程重複進行至全部格子都造訪完畢為止。
就程式而言，這看來適合使用遞迴來實現，因此這樣的演算就稱為遞迴回溯（recursive backtracker），與二元樹演算不同的是，二元樹演算每次丟硬幣決定拆哪面牆，是在決定連接至哪個父節點，然而遞迴回溯演算。每次選擇鄰接哪個鄰居，是在選擇連接至哪個子節點。
為什麼會這樣呢？在二元樹演算時，在每個格子丟硬幣選擇要打掉的牆時，根本不在乎牆另一面的格子有沒有走訪過，而且每個格子只能打掉一面牆，才會形同是在選擇父節點。
在遞迴回溯演算時，因為你會事先調查鄰接格子是否走訪過，若牆的另一面格子若走訪過，你是不能打掉該面牆，而且在回溯至上一格時，若該格還有可造訪的鄰接格子，你就可以打掉鄰接的牆，也就是說，回溯後可以在該格再次打牆。
你可以想像一下有棵樹在迷宮中生長，例如，在一個 5 x 5 的迷宮中，樹若從左上角開始生長，每次的前進就是生成個子節點，若無法前進了就退至某個可往另一方面生成的節點，分支繼續生成下去，例如：
上圖的紅色虛線表示左上角開始一路生長的方向，最後無法繼續前進了，回溯至綠色虛線起點處的節點，然後分支生長出去，綠色虛線生長至無法生長了，回溯至棕色虛線起點處的節點，然後分支生長出去，因而樹最後是生成了藍色實線的路徑，在格子都長滿後，最後會一口氣回溯至起點，如下圖所示：
最後形成的還是樹狀結構，樹根節點就是最先選擇的節點，因為是樹，任兩個節點之間，必然只有一條路徑連通，因而可構成完美迷宮。
實作遞迴回溯迷宮
如方才談到的，你必須記得哪些細胞已經產生，也就是記得迷宮中哪些格子已經走過，別急著為細胞的資料結構加上是否造訪過的旗標，記得嗎？先前文件是使用陣列來記錄產生的細胞，某個格子未造訪過，陣列中是不會有該細胞的資料：
function notVisited(maze, x, y) {
// cells 中沒有就表示沒造訪過
return maze.cells.find(cell => cell.x === x && cell.y === y) === undefined;
}
除了知道該細胞未曾造訪過，可以造訪的格子必須在邊宮邊界內：
function isVisitable(maze, x, y) {
return y >= 0 && y < maze.rows && // y 不超出邊界
x >= 0 && x < maze.columns && // x 不超出邊界
notVisited(maze, x, y); // 未造訪過
}
為了便於取得下個細胞的位置，實作 nextX、nextY，其中 dir 可接受 R、T、L、B：
const R = 0; // 右
const T = 1; // 上
const L = 2; // 左
const B = 3; // 下
// 下個細胞 x 座標
function nextX(x, dir) {
return x + [1, 0, -1, 0][dir];
}
// 下個細胞 y 座標
function nextY(y, dir) {
return y + [0, -1, 0, 1][dir];
}
往下個細胞前進時，必須將牆打掉，因為細胞會有上右牆、上牆、右牆與無牆四種可能性，就必須做四次判斷，決定怎麼打牆，對嗎？
有些迷宮演算在實作時，確實是這麼做，往往地，那類實作中的細胞資料結構中也會帶有四面牆的資料，通常用布林值表示某方向有無牆面，然後在穿越該方向時，拿掉目前細胞的牆，也拿掉下個細胞的牆，這麼實作也沒錯，思考上也比較簡單。
然而那類實作最後繪圖時，因為每個細胞各定義自己的四面牆，單個細胞雖然牆面完整，然而一群細胞排列後，牆面會重複繪製，也就是最後迷宮完成後，若兩細胞間不互通，同一牆面會畫兩次。
從〈手動迷宮〉的介紹開始，我們的細胞資料結構中，就決定每個細胞只有上牆與右牆，原因就在於考量到，最後細胞會是排列在一起的；另外，打掉牆之前，並不用做四次判斷，因為在遞迴回溯演算中，造訪過的細胞是不能再造訪的。
例如，若能往右走，表示右邊細胞沒造訪過，也就是右牆一定沒被拆過，這就只有目前細胞具有上右牆，或僅具備右牆的情況，只要判斷兩種就可以了，因為往右造訪新細胞，新細胞一定有上右牆：
// 往右走，打掉右牆，加入一個有右牆與上牆的細胞
function visitRight(maze, currentCell) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.TOP_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(currentCell.x + 1, currentCell.y, Maze.TOP_RIGHT_WALL));
}
類似地，若能往上走，表示上邊細胞沒造訪過，也就是上牆一定沒被拆過，這就只有目前細胞具有上右牆，或僅具備上牆的情況，因為往上造訪新細胞，新細胞一定有上右牆：
// 往上走，打掉上牆，加入一個有右牆與上牆的細胞
function visitTop(maze, currentCell) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.RIGHT_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(currentCell.x, currentCell.y - 1, Maze.TOP_RIGHT_WALL));
}
因為細胞的資料結構中，牆面只有上牆與右牆，可以往左走時，目前細胞牆面是不會變動的，只要加入一個新細胞，因為是由右往左走，新細胞不會有右牆，只會有上牆：
// 往左走，左邊細胞不會有右牆，也就是加入一個只有上牆的細胞
function visitLeft(maze, currentCell) {
maze.cells.push(cell(currentCell.x - 1, currentCell.y, Maze.TOP_WALL));
}
類似地，若能往下走，目前細胞牆面是不會變動的，只要加入一個新細胞，因為是由上往下走，新細胞不會有上牆，只會有右牆：
// 往下走，下邊細胞不會有上牆，也就是加入一個只有右牆的細胞
function visitBottom(maze, currentCell) {
maze.cells.push(cell(currentCell.x, currentCell.y + 1, Maze.RIGHT_WALL));
}
來寫個 visit 函式，可以指定方向，決定呼叫哪個 visitXXX 函式：
function visit(maze, currentCell, dir) {
switch(dir) {
case R:
visitRight(maze, currentCell); break;
case T:
visitTop(maze, currentCell); break;
case L:
visitLeft(maze, currentCell); break;
case B:
visitBottom(maze, currentCell); break;
}
}
有了這些基礎函式後，就可以寫個 backtracker 來進行遞迴回溯了：
function backtracker(maze) {
// cells 中最後一個細胞就是最後造訪的細胞
const currentCell = maze.cells[maze.cells.length - 1];
// 隨機的四個方向
const rdirs = shuffle([R, T, L, B]);
// 找出可造訪的方向清單
const vdirs = rdirs.filter(dir => {
const nx = nextX(currentCell.x, dir);
const ny = nextY(currentCell.y, dir);
return isVisitable(maze, nx, ny);
});
// 完全沒有可造訪的方向就回溯
if(vdirs.length === 0) {
return;
}
// 逐一造訪可行方向
vdirs.forEach(dir => {
const nx = nextX(currentCell.x, dir);
const ny = nextY(currentCell.y, dir);
// 原先可造訪的方向，可能因為深度優先的關係被造訪過了
// 因此必須再次確認一次是否仍然可以造訪
if(isVisitable(maze, nx, ny)) {
// 造訪下個細胞
visit(maze, currentCell, dir);
// 就目前迷宮狀態進行遞迴回溯演算
backtracker(maze);
}
});
}
最後在 Maze 上加個 backtracker 方法就完成了：
class Maze {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
}
...
backtracker(x = 0, y = 0) {
this.cells = [];
// 加入起點細胞
this.cells.push(cell(x, y, Maze.TOP_RIGHT_WALL));
// 就目前迷宮狀態進行遞迴回溯演算
backtracker(this);
}
}
為了能隨機選擇四個方向，這邊使用了 p5.js 的 shuffle，它會依指定的清單來傳回打亂後的清單；來看看完整的執行範例：
若想看看整個建立牆面的過程，可以直接使用〈二元樹迷宮〉中的 drawMazeCells 函式，不過，這邊對它加點料，讓它可以進一步地顯示樹根至目前生長點的路徑，為此，必須能找出這個路徑。
因為我們記錄了細胞的產生順序，要找出這個路徑的話，只要從最後一個加入的細胞開始，往前找出它的鄰居細胞，再找出該鄰居細胞的鄰居細胞…一直到起點細胞為止，這樣找出來的路徑就是樹根至目前生長點的路徑，因為它就像根管子在迷宮中捅啊捅的，就命名為 findTube 吧！
// 是否為鄰居細胞
function isNeighbor(cell1, cell2) {
const xd = cell1.x - cell2.x;
const yd = cell1.y - cell2.y;
return abs(xd) + abs(yd) === 1;
}
function findTube(maze, n) {
if(n === maze.rows * maze.columns) {
return [];
}
let cell = maze.cells[n - 1];
const tube = [cell];
for(let i = n - 2; i >= 0; i--) {
const pre = maze.cells[i];
if(isNeighbor(cell, pre)) {
tube.push(pre);
cell = pre;
}
}
return tube;
}
接著就可以改寫一下 drawMazeCells，將 findTube 找到的路徑也畫出來：
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();
}
findTube(maze, n).forEach(cell => {
push();
noStroke();
fill(255, 0, 0);
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();
}
來看看完整的範例，你可以藉由調整 frameRate 來控制速度以便觀察：