Theta 迷宮(二)


在〈Theta 迷宮(一)〉中看到,直接將〈遞迴回溯迷宮〉的 Maze 作為 Theta 迷宮繪製的基礎,顯然會有問題,因為圓周越來越大,在細胞每環切分的格數不變下,越外環的細胞佔的面積會越來越大。

雖然可以試著繪製較小的開口、增加最內環的半徑等方式來彌補,構成另一種風格的迷宮,不過,心中總會想,有沒有辦法直接面對越外環的細胞佔的面積會越來越大這個問題呢?

切分細胞

基本上是可以的,例如,每兩環就對細胞的張角進行切分:

Theta 迷宮(二)

每兩環就對細胞的張角進行切分是最簡單的作法,不過外環會有細胞迅速變小的問題,這個稍後再來看。

每兩環就對細胞的張角進行切分,這意謂著〈遞迴回溯迷宮〉不能用了嗎?畢竟會一分二、二分四…不會是個 m x n 迷宮了!

確實地,這不會是個 m x n 的迷宮,然而,並不表示不能基於〈遞迴回溯迷宮〉的成果來修改,一分二、二分四…代表著未打通的迷宮會是如下圖:

Theta 迷宮(二)

若以上圖為例,y 為 0 該列,第一個細胞的左上角座標是 (0, 0),第二個細胞會是 (4, 0),第三個是 (8, 0),第四個是 (12, 0),y 為 2 該列,第一個細胞的左上角座標是 (0, 0),第二個細胞會是 (2, 0),第三個是 (4, 0) … 依此類推。

最後一列的細胞數(行數),取決於第一列的細胞數(行數)與總列數,若起始列、行數為 rowscolumns,就可以使用 columns * pow(2, floor(rows / 2)) 算出來。

若是如此劃分,接下來就是要想辦法產生以下的迷宮:

Theta 迷宮(二)

怎麼走訪呢?x 的步進值不再是單純的 1,不過無論是在哪列,同一列的 x 步進值會相同,也就是只要有 x 的步進值 step,往左或往右就只是 -stepstep

往下呢?在 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); 
} 

從上往下探訪細胞時,可能會有左下、右下兩種選擇,因此增加 BLBR 兩種選擇,nextXnextY 因應 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 等來判斷選擇哪個步進值,這方才已經討論過了,這邊只是使用程式碼實作出來罷了。

visitRightvisitLeft 等,現在不是單純地對 x 加或減 1,改呼叫 nextXnextY

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

為了方便,增加了 visitBottomLeftvisitBottomRight

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 增加 BLBR 兩個 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 為奇數時,往下可能會有 BLBR 兩種,而不單只是 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);
        }
    });
}

其實不用增加 BLBR不判斷,直接給 [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);
    }
}

調整切分方式

以上的範例執行結果會如下,乍看是還可以:

Theta 迷宮(二)

這篇文件一開始有談到,每兩環就對細胞的張角進行切分是最簡單的作法,不過外環會有細胞迅速變小的問題,例如,將以上範例的 rowscolumns 修改為 15、10,繪製出來的圖會變成:

Theta 迷宮(二)

每兩環就切一次,就等於是 2 的次方在切分,會有以上的圖是必然的結果,每兩環就切一次只是計算方便,也能應付較少環數的 Theta 迷宮,如果想要環數多一些,就必須改用較複雜一些的切分方式。

例如,兩環後切一次,接著三環後切一次,再來四環後切一次,就可以讓切分的速度緩下來,同樣是 rowscolumns 為 15、10,畫出來就不會那麼快變得稠密:

Theta 迷宮(二)

然而相對來說,這在計算上就麻煩許多了,有興趣的話,可以試著修改以上範例,我就不再說明了,你可以試著當成挑戰,底下直接提供我修改後的成果作為參考:

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

這個切分法可以應付更多環數,不過,指定到某個環數之後,還是會有過於稠密的問題,例如 rowscolumns 為 24、8 時會如下:

Theta 迷宮(二)

可以看到已經開始變得稠密,只是沒有一開始每兩環就切分那麼快,以上的切分法只是對 Theta 迷宮的實作,在理解上比較容易,不用對〈遞迴回溯迷宮〉做太多修改罷了,如果你應付的環數不多,這會是比較簡單的方式。

想要更進一步解決這個問題,可以依圓周長決定選擇將細胞一切為二的時機,只不過以目前的 Maze 實作來做這件事,會有許多計算上的困難。

遞迴回溯演算本身還是可以使用,不過更改一下細胞的資料結構,程式實作依圓周長切分細胞時,就會有較簡單的做法,這就留待之後的文件再探討了。