# 實作遞迴回溯迷宮

``````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);        // 未造訪過
}
``````

``````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));
}
``````

``````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;
}
}
``````

``````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);
}
});
}
``````

``````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);
}
}
``````

``````// 是否為鄰居細胞
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;
}
``````

``````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();
}
``````