在〈Theta 迷宮(一)〉中看到,直接將〈遞迴回溯迷宮〉的 Maze
作為 Theta 迷宮繪製的基礎,顯然會有問題,因為圓周越來越大,在細胞每環切分的格數不變下,越外環的細胞佔的面積會越來越大。
雖然可以試著繪製較小的開口、增加最內環的半徑等方式來彌補,構成另一種風格的迷宮,不過,心中總會想,有沒有辦法直接面對越外環的細胞佔的面積會越來越大這個問題呢?
切分細胞
基本上是可以的,例如,每兩環就對細胞的張角進行切分:
每兩環就對細胞的張角進行切分是最簡單的作法,不過外環會有細胞迅速變小的問題,這個稍後再來看。
每兩環就對細胞的張角進行切分,這意謂著〈遞迴回溯迷宮〉不能用了嗎?畢竟會一分二、二分四…不會是個 m x n 迷宮了!
確實地,這不會是個 m x n 的迷宮,然而,並不表示不能基於〈遞迴回溯迷宮〉的成果來修改,一分二、二分四…代表著未打通的迷宮會是如下圖:
若以上圖為例,y 為 0 該列,第一個細胞的左上角座標是 (0, 0),第二個細胞會是 (4, 0),第三個是 (8, 0),第四個是 (12, 0),y 為 2 該列,第一個細胞的左上角座標是 (0, 0),第二個細胞會是 (2, 0),第三個是 (4, 0) … 依此類推。
最後一列的細胞數(行數),取決於第一列的細胞數(行數)與總列數,若起始列、行數為 rows
、columns
,就可以使用 columns * pow(2, floor(rows / 2))
算出來。
若是如此劃分,接下來就是要想辦法產生以下的迷宮:
怎麼走訪呢?x 的步進值不再是單純的 1,不過無論是在哪列,同一列的 x
步進值會相同,也就是只要有 x 的步進值 step
,往左或往右就只是 -step
或 step
。
往下呢?在 y 為偶數時沒問題,因為只能選正下方的細胞,也就是 x 是不變的,然而 y 為奇數時,下方會有兩個細胞可以選擇,就稱為左下與右下好了,選擇左下時,x 不變,選擇右下時,x 的步進會是 step / 2
。
往上呢?在 y 為奇數時沒問題,因為只能選正上方的細胞,也就是 x 是不變的,然而 y 為偶數時,就要看自己是上方細胞的左下或右下,若是前者,x 不變,若是後者,x 的步進會是 -step
。
只是,如何得知自己是上方細胞的左下或右下呢?這似乎牽涉到總行數與 x 的奇偶判斷?你要從這個角度去算也是可以,只不過會複雜一些,仔細觀察方才未打通的迷宮,自己是上方細胞的左下時,自身一定是該列的偶數細胞,右下時,自身一定是該列的奇數細胞,也就是說,自身的 x 除以 step
,若為偶數就是左下,若為奇數就是右下。
綜合以上,剩下的就是 x 步進值如何計算的問題,這很簡單,只要有第一列的 x 步進值,這會是總行數除以初始行數,接著每兩列後就切一次。
修改迷宮演算
以上的說明感覺是要對〈遞迴回溯迷宮〉做很大的修改?其實不用,來一個一個看,首先是計算最後總行數與第一列的 x 步進值:
class Maze {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
// 最後總行數
this.outMostcolumns = columns * pow(2, floor(rows / 2));
// 第一列的 x 步進值
this.initialXStep = this.outMostcolumns / columns;
}
backtracker(x = 0, y = 0) {
this.cells = [];
this.cells.push(cell(x, y, Maze.TOP_RIGHT_WALL));
backtracker(this);
}
}
基於 y 可能得到不同的步進值,如方才說明的,這會是依第一列的 x 步進值,每兩列後就切一次的結果:
function xStep(maze, y) {
return maze.initialXStep / pow(2, floor(y / 2));
}
因為 columns
現在是指初始行數,在計算迷宮邊界時,不再是依 columns
,而是總行數,因此 isVisitable
的改一下:
function isVisitable(maze, x, y) {
return y >= 0 && y < maze.rows &&
x >= 0 && x < maze.outMostcolumns && // 這邊改用 outMostcolumns
notVisited(maze, x, y);
}
從上往下探訪細胞時,可能會有左下、右下兩種選擇,因此增加 BL
與 BR
兩種選擇,nextX
與 nextY
因應 dir
會有六個可能,也做了修改:
const R = 0;
const T = 1;
const L = 2;
const B = 3;
const BL = 4; // 左下
const BR = 5; // 右下
function nextX(cell, dir, step) {
const isYEven = cell.y % 2 == 0;
const isStepOdd = (cell.x / step) % 2 == 1;
return cell.x + [
step,
isYEven && isStepOdd ? -step : 0,
-step,
0,
0,
step / 2
][dir];
}
function nextY(y, dir) {
return y + [0, -1, 0, 1, 1, 1][dir];
}
因為對 y 來說,正下方、左下、右下,都是增加 1 罷了,nextY
只是增加了兩個元素 1 罷了,nextX
則必須根據目前的 x 步進值、y 等來判斷選擇哪個步進值,這方才已經討論過了,這邊只是使用程式碼實作出來罷了。
visitRight
、visitLeft
等,現在不是單純地對 x 加或減 1,改呼叫 nextX
、nextY
:
function visitRight(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.TOP_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(currentCell, R, step), nextY(currentCell.y, R), Maze.TOP_RIGHT_WALL));
}
function visitTop(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.RIGHT_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(currentCell, T, step), nextY(currentCell.y, T), Maze.TOP_RIGHT_WALL));
}
function visitLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, L, step), nextY(currentCell.y, L), Maze.TOP_WALL));
}
function visitBottom(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, B, step), nextY(currentCell.y, B), Maze.RIGHT_WALL));
}
為了方便,增加了 visitBottomLeft
、visitBottomRight
:
function visitBottomLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, BL, step), nextY(currentCell.y, BL), Maze.RIGHT_WALL));
}
function visitBottomRight(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, BR, step), nextY(currentCell.y, BR), Maze.RIGHT_WALL));
}
visit
增加 BL
、BR
兩個 case
:
function visit(maze, currentCell, dir, step) {
switch(dir) {
case R:
visitRight(maze, currentCell, step); break;
case T:
visitTop(maze, currentCell, step); break;
case L:
visitLeft(maze, currentCell, step); break;
case B:
visitBottom(maze, currentCell, step); break;
case BL:
visitBottomLeft(maze, currentCell, step); break;
case BR:
visitBottomRight(maze, currentCell, step); break;
}
}
接著就是遞迴回溯走訪了,重點在於 x 步進值的計算,以及 rdirs
,在 y 為奇數時,往下可能會有 BL
、BR
兩種,而不單只是 B
:
function backtracker(maze) {
const currentCell = maze.cells[maze.cells.length - 1];
// 計算 x 步進值
const step = xStep(maze, currentCell.y);
// 隨機選擇時要看 y 為偶數或奇數
const rdirs = shuffle(currentCell.y % 2 == 0 ? [R, T, L, B] : [R, T, L, BL, BR]);
const vdirs = rdirs.filter(dir => {
const nx = nextX(currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
return isVisitable(maze, nx, ny);
});
if(vdirs.length === 0) {
return;
}
vdirs.forEach(dir => {
const nx = nextX(currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
if(isVisitable(maze, nx, ny)) {
visit(maze, currentCell, dir, step);
backtracker(maze);
}
});
}
其實不用增加 BL
、BR
不判斷,直接給 [R, T, L, B]
來打亂也是可以,也就是有左下、右下可選時,每次都選左下也行的,這會產生某種程度的偏差,不過繪製為 Theta 迷宮的話就看不太出來。
〈遞迴回溯迷宮〉的實作,沒有很大的修改,說穿了只是在修改界線方面的判斷,遞迴回溯演算的主流程是沒有什麼變動的。
最後就是繪圖了,因為迷宮細胞大小不會相同,顯然地是依照 x 步進值決定細胞大小:
function drawCell(wallType, cellWidth, step) {
if(wallType === Maze.TOP_WALL || wallType === Maze.TOP_RIGHT_WALL) {
line(0, 0, cellWidth * step, 0);
}
if(wallType === Maze.RIGHT_WALL || wallType === Maze.TOP_RIGHT_WALL) {
line(cellWidth * step, 0, cellWidth * step, cellWidth);
}
}
function drawMaze(maze, cellWidth) {
maze.cells.forEach(cell => {
push();
// 依 x 步進決定細胞大小
const step = xStep(maze, cell.y);
translate(cell.x * cellWidth, cell.y * cellWidth);
drawCell(cell.wallType, cellWidth, step);
pop();
});
const totalWidth = cellWidth * maze.outMostcolumns;
const totalHeight = cellWidth * maze.rows;
line(0, 0, 0, totalHeight);
line(0, totalHeight, totalWidth, totalHeight);
}
底下是修改後的完整範例(因為 p5.js-widget 不能放太長的程式碼,就直接列出來了):
function setup() {
createCanvas(300, 300);
noLoop();
}
function draw() {
background(220);
const rows = 5;
const columns = 4;
const cellWidth = (width - 60) / (rows * 3);
const maze = new Maze(rows, columns);
maze.backtracker();
strokeWeight(5);
translate(cellWidth, height / 2 - cellWidth * rows / 2);
drawMaze(maze, cellWidth);
}
function cell(x, y, wallType) {
return {x, y, wallType};
}
class Maze {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
this.outMostcolumns = columns * pow(2, floor(rows / 2));
this.initialXStep = this.outMostcolumns / columns;
}
backtracker(x = 0, y = 0) {
this.cells = [];
this.cells.push(cell(x, y, Maze.TOP_RIGHT_WALL));
backtracker(this);
}
}
function xStep(maze, y) {
return maze.initialXStep / pow(2, floor(y / 2));
}
Maze.NO_WALL = 'no_wall';
Maze.TOP_WALL = 'top_wall';
Maze.RIGHT_WALL = 'right_wall';
Maze.TOP_RIGHT_WALL = 'top_right_wall';
function notVisited(maze, x, y) {
return maze.cells.find(cell => cell.x === x && cell.y === y) === undefined;
}
function isVisitable(maze, x, y) {
return y >= 0 && y < maze.rows &&
x >= 0 && x < maze.outMostcolumns &&
notVisited(maze, x, y);
}
const R = 0;
const T = 1;
const L = 2;
const B = 3;
const BL = 4;
const BR = 5;
function nextX(cell, dir, step) {
const isYEven = cell.y % 2 == 0;
const isStepOdd = (cell.x / step) % 2 == 1;
return cell.x + [
step,
isYEven && isStepOdd ? -step : 0,
-step,
0,
0,
step / 2
][dir];
}
function nextY(y, dir) {
return y + [0, -1, 0, 1, 1, 1][dir];
}
function visitRight(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.TOP_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(currentCell, R, step), nextY(currentCell.y, R), Maze.TOP_RIGHT_WALL));
}
function visitTop(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.RIGHT_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(currentCell, T, step), nextY(currentCell.y, T), Maze.TOP_RIGHT_WALL));
}
function visitLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, L, step), nextY(currentCell.y, L), Maze.TOP_WALL));
}
function visitBottom(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, B, step), nextY(currentCell.y, B), Maze.RIGHT_WALL));
}
function visitBottomLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, BL, step), nextY(currentCell.y, BL), Maze.RIGHT_WALL));
}
function visitBottomRight(maze, currentCell, step) {
maze.cells.push(cell(nextX(currentCell, BR, step), nextY(currentCell.y, BR), Maze.RIGHT_WALL));
}
function visit(maze, currentCell, dir, step) {
switch(dir) {
case R:
visitRight(maze, currentCell, step); break;
case T:
visitTop(maze, currentCell, step); break;
case L:
visitLeft(maze, currentCell, step); break;
case B:
visitBottom(maze, currentCell, step); break;
case BL:
visitBottomLeft(maze, currentCell, step); break;
case BR:
visitBottomRight(maze, currentCell, step); break;
}
}
function backtracker(maze) {
const currentCell = maze.cells[maze.cells.length - 1];
const step = xStep(maze, currentCell.y);
const rdirs = shuffle(currentCell.y % 2 == 0 ? [R, T, L, B] : [R, T, L, BL, BR]);
const vdirs = rdirs.filter(dir => {
const nx = nextX(currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
return isVisitable(maze, nx, ny);
});
if(vdirs.length === 0) {
return;
}
vdirs.forEach(dir => {
const nx = nextX(currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
if(isVisitable(maze, nx, ny)) {
visit(maze, currentCell, dir, step);
backtracker(maze);
}
});
}
function drawCell(wallType, cellWidth, step) {
if(wallType === Maze.TOP_WALL || wallType === Maze.TOP_RIGHT_WALL) {
line(0, 0, cellWidth * step, 0);
}
if(wallType === Maze.RIGHT_WALL || wallType === Maze.TOP_RIGHT_WALL) {
line(cellWidth * step, 0, cellWidth * step, cellWidth);
}
}
function drawMaze(maze, cellWidth) {
maze.cells.forEach(cell => {
push();
const step = xStep(maze, cell.y);
translate(cell.x * cellWidth, cell.y * cellWidth);
drawCell(cell.wallType, cellWidth, step);
pop();
});
const totalWidth = cellWidth * maze.outMostcolumns;
const totalHeight = cellWidth * maze.rows;
line(0, 0, 0, totalHeight);
line(0, totalHeight, totalWidth, totalHeight);
}
繪製為 Theta 迷宮
能夠繪製出以上的迷宮後,接著就是將之繪製與 Theta 迷宮了,主要的繪製方式在〈Theta 迷宮(一)〉都說明過了,最重要的是,在〈Theta 迷宮(一)〉最後的範例裡,x 的步進值固定是 1,然而在這邊,x 的步進值是必須根據 y 來計算:
function drawMaze(maze, cellWidth) {
const thetaStep = TWO_PI / maze.outMostcolumns;
maze.cells.forEach(cell => {
if(cell.x === 0 && cell.y === 0) {
return;
}
// 最內環的半徑是 1
const innerR = (cell.y + 1) * cellWidth;
const outerR = (cell.y + 2) * cellWidth;
const theta1 = -thetaStep * cell.x;
// 根據 y 計算步進值
const theta2 = -thetaStep * (cell.x + xStep(maze, cell.y));
const innerVt1 = p5.Vector.fromAngle(theta1, innerR);
const innerVt2 = p5.Vector.fromAngle(theta2, innerR);
const outerVt2 = p5.Vector.fromAngle(theta2, outerR);
if(cell.wallType === Maze.TOP_WALL || cell.wallType === Maze.TOP_RIGHT_WALL) {
line(innerVt1.x, innerVt1.y, innerVt2.x, innerVt2.y);
}
if(cell.wallType === Maze.RIGHT_WALL || cell.wallType === Maze.TOP_RIGHT_WALL) {
line(innerVt2.x, innerVt2.y, outerVt2.x, outerVt2.y);
}
});
const r = cellWidth * (maze.rows + 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);
}
}
然而為了順時針、逆時針都能打通迷宮,nextX
修改了一下:
function nextX(maze, cell, dir, step) {
const isYEven = cell.y % 2 == 0;
const isStepOdd = (cell.x / step) % 2 == 1;
const nx = (cell.x + [
step,
isYEven && isStepOdd ? -step : 0,
-step,
0,
0,
step / 2
][dir]);
// 順時針、逆時針都要能打通迷宮
return nx >= 0 ? (nx % maze.outMostcolumns) : (nx + maze.outMostcolumns);
}
底下是完整的範例實作:
function setup() {
createCanvas(300, 300);
noLoop();
}
function draw() {
background(220);
const rows = 8;
const columns = 8;
const cellWidth = (width - 60) / (rows * 2);
const maze = new Maze(rows, columns);
maze.backtracker();
strokeWeight(2);
translate(width / 2 , height / 2);
drawMaze(maze, cellWidth);
}
function cell(x, y, wallType) {
return {x, y, wallType};
}
class Maze {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
this.outMostcolumns = columns * pow(2, floor(rows / 2));
this.initialXStep = this.outMostcolumns / columns;
}
backtracker(x = 0, y = 0) {
this.cells = [];
this.cells.push(cell(x, y, Maze.TOP_RIGHT_WALL));
backtracker(this);
}
}
function xStep(maze, y) {
return maze.initialXStep / pow(2, floor(y / 2));
}
Maze.NO_WALL = 'no_wall';
Maze.TOP_WALL = 'top_wall';
Maze.RIGHT_WALL = 'right_wall';
Maze.TOP_RIGHT_WALL = 'top_right_wall';
function notVisited(maze, x, y) {
return maze.cells.find(cell => cell.x === x && cell.y === y) === undefined;
}
function isVisitable(maze, x, y) {
return y >= 0 && y < maze.rows &&
x >= 0 && x < maze.outMostcolumns &&
notVisited(maze, x, y);
}
const R = 0;
const T = 1;
const L = 2;
const B = 3;
const BL = 4;
const BR = 5;
function nextX(maze, cell, dir, step) {
const isYEven = cell.y % 2 == 0;
const isStepOdd = (cell.x / step) % 2 == 1;
const nx = (cell.x + [
step,
isYEven && isStepOdd ? -step : 0,
-step,
0,
0,
step / 2
][dir]);
return nx >= 0 ? (nx % maze.outMostcolumns) : (nx + maze.outMostcolumns);
}
function nextY(y, dir) {
return y + [0, -1, 0, 1, 1, 1][dir];
}
function visitRight(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.TOP_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(maze, currentCell, R, step), nextY(currentCell.y, R), Maze.TOP_RIGHT_WALL));
}
function visitTop(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.RIGHT_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(maze, currentCell, T, step), nextY(currentCell.y, T), Maze.TOP_RIGHT_WALL));
}
function visitLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, L, step), nextY(currentCell.y, L), Maze.TOP_WALL));
}
function visitBottom(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, B, step), nextY(currentCell.y, B), Maze.RIGHT_WALL));
}
function visitBottomLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, BL, step), nextY(currentCell.y, BL), Maze.RIGHT_WALL));
}
function visitBottomRight(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, BR, step), nextY(currentCell.y, BR), Maze.RIGHT_WALL));
}
function visit(maze, currentCell, dir, step) {
switch(dir) {
case R:
visitRight(maze, currentCell, step); break;
case T:
visitTop(maze, currentCell, step); break;
case L:
visitLeft(maze, currentCell, step); break;
case B:
visitBottom(maze, currentCell, step); break;
case BL:
visitBottomLeft(maze, currentCell, step); break;
case BR:
visitBottomRight(maze, currentCell, step); break;
}
}
function backtracker(maze) {
const currentCell = maze.cells[maze.cells.length - 1];
const step = xStep(maze, currentCell.y);
const rdirs = shuffle(currentCell.y % 2 == 0 ? [R, T, L, B] : [R, T, L, BL, BR]);
const vdirs = rdirs.filter(dir => {
const nx = nextX(maze, currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
return isVisitable(maze, nx, ny);
});
if(vdirs.length === 0) {
return;
}
vdirs.forEach(dir => {
const nx = nextX(maze, currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
if(isVisitable(maze, nx, ny)) {
visit(maze, currentCell, dir, step);
backtracker(maze);
}
});
}
function drawMaze(maze, cellWidth) {
const thetaStep = TWO_PI / maze.outMostcolumns;
maze.cells.forEach(cell => {
if(cell.x === 0 && cell.y === 0) {
return;
}
const innerR = (cell.y + 1) * cellWidth;
const outerR = (cell.y + 2) * cellWidth;
const theta1 = -thetaStep * cell.x;
const theta2 = -thetaStep * (cell.x + xStep(maze, cell.y));
const innerVt1 = p5.Vector.fromAngle(theta1, innerR);
const innerVt2 = p5.Vector.fromAngle(theta2, innerR);
const outerVt2 = p5.Vector.fromAngle(theta2, outerR);
if(cell.wallType === Maze.TOP_WALL || cell.wallType === Maze.TOP_RIGHT_WALL) {
line(innerVt1.x, innerVt1.y, innerVt2.x, innerVt2.y);
}
if(cell.wallType === Maze.RIGHT_WALL || cell.wallType === Maze.TOP_RIGHT_WALL) {
line(innerVt2.x, innerVt2.y, outerVt2.x, outerVt2.y);
}
});
const r = cellWidth * (maze.rows + 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);
}
}
調整切分方式
以上的範例執行結果會如下,乍看是還可以:
這篇文件一開始有談到,每兩環就對細胞的張角進行切分是最簡單的作法,不過外環會有細胞迅速變小的問題,例如,將以上範例的 rows
、columns
修改為 15、10,繪製出來的圖會變成:
每兩環就切一次,就等於是 2 的次方在切分,會有以上的圖是必然的結果,每兩環就切一次只是計算方便,也能應付較少環數的 Theta 迷宮,如果想要環數多一些,就必須改用較複雜一些的切分方式。
例如,兩環後切一次,接著三環後切一次,再來四環後切一次,就可以讓切分的速度緩下來,同樣是 rows
、columns
為 15、10,畫出來就不會那麼快變得稠密:
然而相對來說,這在計算上就麻煩許多了,有興趣的話,可以試著修改以上範例,我就不再說明了,你可以試著當成挑戰,底下直接提供我修改後的成果作為參考:
function setup() {
createCanvas(300, 300);
noLoop();
}
function draw() {
background(220);
const rows = 15;
const columns = 10;
const cellWidth = (width - 60) / (rows * 2);
const maze = new Maze(rows, columns);
maze.backtracker();
strokeWeight(2);
translate(width / 2 , height / 2);
drawMaze(maze, cellWidth);
}
function cell(x, y, wallType) {
return {x, y, wallType};
}
class Maze {
constructor(rows, columns) {
this.rows = rows;
this.columns = columns;
this.outMostcolumns = outMostColumns(this);
this.initialXStep = this.outMostcolumns / columns;
}
backtracker(x = 0, y = 0) {
this.cells = [];
this.cells.push(cell(x, y, Maze.TOP_RIGHT_WALL));
backtracker(this);
}
}
function outMostColumns(maze) {
let rowCount = maze.rows;
let diff = 2;
while((rowCount = rowCount - diff) > 0) {
diff++;
}
return pow(2, diff - 2) * maze.columns;
}
function nthSection(y) {
let yi = 1, i = 0, diff = 3;
while(y > yi) {
yi += diff;
diff++;
i++;
}
return i;
}
function sectionLine(y) {
let yi = 0, diff = 2;
while(y > yi) {
yi += diff;
diff++;
}
return yi === y;
}
function xStep(maze, y) {
return maze.initialXStep / pow(2, nthSection(y));
}
Maze.NO_WALL = 'no_wall';
Maze.TOP_WALL = 'top_wall';
Maze.RIGHT_WALL = 'right_wall';
Maze.TOP_RIGHT_WALL = 'top_right_wall';
function notVisited(maze, x, y) {
return maze.cells.find(cell => cell.x === x && cell.y === y) === undefined;
}
function isVisitable(maze, x, y) {
return y >= 0 && y < maze.rows &&
x >= 0 && x < maze.outMostcolumns &&
notVisited(maze, x, y);
}
const R = 0;
const T = 1;
const L = 2;
const B = 3;
const BL = 4;
const BR = 5;
function nextX(maze, cell, dir, step) {
const isYOdd = cell.y % 2 == 1;
const isStepOdd = (cell.x / step) % 2 == 1;
const nx = cell.x + [
step,
sectionLine(cell.y) && isStepOdd ? -step : 0,
-step,
0,
0,
step / 2
][dir];
return nx >= 0 ? (nx % maze.outMostcolumns) : (nx + maze.outMostcolumns);
}
function nextY(y, dir) {
return y + [0, -1, 0, 1][dir];
}
function visitRight(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.TOP_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(maze, currentCell, R, step), nextY(currentCell.y, R), Maze.TOP_RIGHT_WALL));
}
function visitTop(maze, currentCell, step) {
if(currentCell.wallType === Maze.TOP_RIGHT_WALL) {
currentCell.wallType = Maze.RIGHT_WALL;
}
else {
currentCell.wallType = Maze.NO_WALL;
}
maze.cells.push(cell(nextX(maze, currentCell, T, step), nextY(currentCell.y, T), Maze.TOP_RIGHT_WALL));
}
function visitLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, L, step), nextY(currentCell.y, L), Maze.TOP_WALL));
}
function visitBottom(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, B, step), nextY(currentCell.y, B), Maze.RIGHT_WALL));
}
function visitBottomLeft(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, BL, step), nextY(currentCell.y, BL), Maze.RIGHT_WALL));
}
function visitBottomRight(maze, currentCell, step) {
maze.cells.push(cell(nextX(maze, currentCell, BR, step), nextY(currentCell.y, BR), Maze.RIGHT_WALL));
}
function visit(maze, currentCell, dir, step) {
switch(dir) {
case R:
visitRight(maze, currentCell, step); break;
case T:
visitTop(maze, currentCell, step); break;
case L:
visitLeft(maze, currentCell, step); break;
case B:
visitBottom(maze, currentCell, step); break;
case BL:
visitBottomLeft(maze, currentCell, step); break;
case BR:
visitBottomRight(maze, currentCell, step); break;
}
}
function backtracker(maze) {
const currentCell = maze.cells[maze.cells.length - 1];
const step = xStep(maze, currentCell.y);
const rdirs = shuffle(sectionLine(cell.y) ? [R, T, L, B, BL, BR] : [R, T, L, B]);
const vdirs = rdirs.filter(dir => {
const nx = nextX(maze, currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
return isVisitable(maze, nx, ny);
});
if(vdirs.length === 0) {
return;
}
vdirs.forEach(dir => {
const nx = nextX(maze, currentCell, dir, step);
const ny = nextY(currentCell.y, dir);
if(isVisitable(maze, nx, ny)) {
visit(maze, currentCell, dir, step);
backtracker(maze);
}
});
}
function drawMaze(maze, cellWidth) {
const thetaStep = TWO_PI / maze.outMostcolumns;
maze.cells.forEach(cell => {
if(cell.x === 0 && cell.y === 0) {
return;
}
const innerR = (cell.y + 1) * cellWidth;
const outerR = (cell.y + 2) * cellWidth;
const theta1 = -thetaStep * cell.x;
const theta2 = -thetaStep * (cell.x + xStep(maze, cell.y));
const innerVt1 = p5.Vector.fromAngle(theta1, innerR);
const innerVt2 = p5.Vector.fromAngle(theta2, innerR);
const outerVt2 = p5.Vector.fromAngle(theta2, outerR);
if(cell.wallType === Maze.TOP_WALL || cell.wallType === Maze.TOP_RIGHT_WALL) {
line(innerVt1.x, innerVt1.y, innerVt2.x, innerVt2.y);
}
if(cell.wallType === Maze.RIGHT_WALL || cell.wallType === Maze.TOP_RIGHT_WALL) {
line(innerVt2.x, innerVt2.y, outerVt2.x, outerVt2.y);
}
});
const r = cellWidth * (maze.rows + 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);
}
}
這個切分法可以應付更多環數,不過,指定到某個環數之後,還是會有過於稠密的問題,例如 rows
、columns
為 24、8 時會如下:
可以看到已經開始變得稠密,只是沒有一開始每兩環就切分那麼快,以上的切分法只是對 Theta 迷宮的實作,在理解上比較容易,不用對〈遞迴回溯迷宮〉做太多修改罷了,如果你應付的環數不多,這會是比較簡單的方式。
想要更進一步解決這個問題,可以依圓周長決定選擇將細胞一切為二的時機,只不過以目前的 Maze
實作來做這件事,會有許多計算上的困難。
遞迴回溯演算本身還是可以使用,不過更改一下細胞的資料結構,程式實作依圓周長切分細胞時,就會有較簡單的做法,這就留待之後的文件再探討了。