我正在創建一個迷宮生成函式，它需要使用遞回回溯，并且顯然需要遞回。該函式必須是運行length * breath時間，有時超過最大遞回深度。以下是迷宮的代碼：
function maze(width, height){
var grid = [];
for (var y = 0; y < height; y ){
grid.push([]);
for (var x = 0; x < width; x ) grid[y].push(0);
}
function shuffle(){
var result = ["N", "S", "E", "W"];
for (var count = result.length; count > 0; count--){
rand = Math.floor(Math.random() * count);
[result[count - 1], result[rand]] = [result[rand], result[count - 1]];
}
return result;
}
function carve(curr_x, curr_y){
for (var dir of shuffle()){
var new_x = curr_x {N: 0, S: 0, E: 1, W: -1}[dir], new_y = curr_y {N: -1, S: 1, E: 0, W: 0}[dir];
if (new_y >= 0 && new_y <= height - 1 && new_x >= 0 && new_x <= width - 1 && grid[new_y][new_x] == 0){
grid[curr_y][curr_x] = {N: 1, S: 2, E: 4, W: 8}[dir];
grid[new_y][new_x] = {N: 2, S: 1, E: 8, W: 4}[dir];
carve(new_x, new_y);
}
}
}
carve(Math.floor(width / 3) Math.floor(Math.random() * Math.floor(2 / 3 * width)), Math.floor(height / 3) Math.floor(Math.random() * Math.floor(2 / 3 * height)));
return grid;
}
給定遞回的定義，我相信這個函式可以改寫成requestAnimationFrame，這樣就不會超出最大遞回深度。可能嗎？有什么方法可以將遞回轉換為其他東西嗎？謝謝！
uj5u.com熱心網友回復：
這是一個重構代碼以在單個 while 回圈中運行的示例。我不確定是否有特定的方法，但只是向您展示代碼可能會有所幫助......
這是主要部分：
let pos = start;
let revisit = [];
while (pos) {
const next = randomEmptyAdjacent(pos);
if (next) {
carve(pos, next);
revisit.push(pos); // Mark this cell for revisiting
pos = next; // Go depth-first
} else {
pos = revisit.pop();
}
}
使用requestAnimationFrameorsetTimeout來逃避堆疊從來都不是一個好主意。它會使代碼運行緩慢。
例子
這是可運行片段中的內容。我添加了迷宮的可視化，以便于檢查輸出。
顯示代碼片段
function maze(width, height) {
const grid = [];
const start = [
Math.floor(width / 3) Math.floor(Math.random() * Math.floor(2 / 3 * width)),
Math.floor(height / 3) Math.floor(Math.random() * Math.floor(2 / 3 * height))
];
for (var y = 0; y < height; y ) {
grid.push([]);
for (var x = 0; x < width; x ) grid[y].push(0);
}
const randomEmptyAdjacent = ([y, x]) => {
const available = [
[y - 1, x], // top
[y, x 1], // right
[y 1, x], // bottom
[y, x - 1] // left
].filter(
([y, x]) => (
y >= 0 && y <= height - 1 &&
x >= 0 && x <= width - 1 &&
grid[y][x] === 0
)
);
return available[Math.floor(Math.random() * available.length)];
}
const carve = (from, to) => {
const [y1, x1] = from;
const [y2, x2] = to;
const dy = y2 - y1;
const dx = x2 - x1;
if (dy === 1) {
grid[y1][x1] = 2;
grid[y2][x2] = 1;
} else if (dy === -1) {
grid[y1][x1] = 1;
grid[y2][x2] = 2;
}
if (dx === 1) {
grid[y1][x1] = 4;
grid[y2][x2] = 8;
} else if (dx === -1) {
grid[y1][x1] = 8;
grid[y2][x2] = 4;
}
}
let pos = start;
let revisit = [];
while (pos) {
const next = randomEmptyAdjacent(pos);
if (next) {
carve(pos, next);
revisit.push(pos);
pos = next;
} else {
pos = revisit.pop();
}
}
return grid;
}
const renderMaze = maze => {
const h = maze.length;
const w = maze[0].length;
const S = 10;
const mazeEl = document.querySelector(".maze");
mazeEl.innerHTML = "";
mazeEl.style.width = `${w * S}px`;
mazeEl.style.height = `${h * S}px`;
for (const row of maze) {
for (const cell of row) {
const cellEl = document.createElement("div");
cellEl.classList.add("cell");
if (cell & 8) {
cellEl.style.borderLeftColor = "transparent";
}
if (cell & 4) {
cellEl.style.borderRightColor = "transparent";
}
if (cell & 2) {
cellEl.style.borderBottomColor = "transparent";
}
if (cell & 1) {
cellEl.style.borderTopColor = "transparent";
}
cellEl.style.width = `${S - 2}px`;
cellEl.style.height = `${S - 2}px`;
mazeEl.appendChild(cellEl);
}
}
}
const m = maze(50, 50);
renderMaze(m);.maze {
border: 1px solid black;
display: flex;
flex-wrap: wrap;
}
.cell {
flex: none;
border-width: 1px;
border-style: solid;
border-color: black;
font-size: 12px;
}<div class="maze"></div>影片！
只是為了好玩，這里有一個有用的例子requestAnimationFrame：影片！此片段在單個回圈中生成迷宮，但用于requestAnimationFrame將要逐幀繪制的單元格的渲染排隊。
顯示代碼片段
function maze(width, height) {
const start = [
Math.floor(width / 3) Math.floor(Math.random() * Math.floor(2 / 3 * width)),
Math.floor(height / 3) Math.floor(Math.random() * Math.floor(2 / 3 * height))
];
const grid = [];
const S = 6;
const mazeEl = document.querySelector(".maze");
mazeEl.innerHTML = "";
mazeEl.style.width = `${width * S}px`;
mazeEl.style.height = `${height * S}px`;
for (var y = 0; y < height; y ) {
grid.push([]);
for (var x = 0; x < width; x ) {
grid[y].push(0);
const cellEl = document.createElement("div");
cellEl.style.width = `${S - 2}px`;
cellEl.style.height = `${S - 2}px`;
cellEl.classList.add("cell");
mazeEl.appendChild(cellEl);
}
}
const randomEmptyAdjacent = ([y, x]) => {
const available = [
[y - 1, x], // top
[y, x 1], // right
[y 1, x], // bottom
[y, x - 1] // left
].filter(
([y, x]) => (
y >= 0 && y <= height - 1 &&
x >= 0 && x <= width - 1 &&
grid[y][x] === 0
)
);
return available[Math.floor(Math.random() * available.length)];
}
const carve = (from, to) => {
const [y1, x1] = from;
const [y2, x2] = to;
const dy = y2 - y1;
const dx = x2 - x1;
if (dy === 1) {
grid[y1][x1] = 2;
grid[y2][x2] = 1;
} else if (dy === -1) {
grid[y1][x1] = 1;
grid[y2][x2] = 2;
}
if (dx === 1) {
grid[y1][x1] = 4;
grid[y2][x2] = 8;
} else if (dx === -1) {
grid[y1][x1] = 8;
grid[y2][x2] = 4;
}
queue(
mazeEl.children[y1 * width x1], grid[y1][x1],
mazeEl.children[y2 * width x2], grid[y2][x2],
)
}
let pos = start;
let revisit = [];
while (pos) {
const next = randomEmptyAdjacent(pos);
if (next) {
carve(pos, next);
revisit.push(pos);
pos = next;
} else {
pos = revisit.pop();
}
}
return grid;
}
const renderQueue = [];
const queue = (c1, v1, c2, v2) => {
renderQueue.push(() => {
renderCell(c1, v1);
renderCell(c2, v2);
const next = renderQueue.shift();
if (next) requestAnimationFrame(next);
});
}
const renderCell = (cellEl, cell) => {
if (cell & 8) {
cellEl.style.borderLeftColor = "transparent";
}
if (cell & 4) {
cellEl.style.borderRightColor = "transparent";
}
if (cell & 2) {
cellEl.style.borderBottomColor = "transparent";
}
if (cell & 1) {
cellEl.style.borderTopColor = "transparent";
}
}
const m = maze(40, 40);
renderQueue.shift()();.maze {
border: 1px solid black;
display: flex;
flex-wrap: wrap;
}
.cell {
flex: none;
border-width: 1px;
border-style: solid;
border-color: black;
font-size: 12px;
}<div class="maze"></div>轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/487136.html
標籤：javascript 递归 迷宫
下一篇：使用戶輸入等于變數的值