javascript - 是否可以使用 requestanimationframe 来建模递归？

标签 javascript recursion maze

我正在创建一个迷宫生成函数，它需要使用递归回溯，并且显然需要递归。该函数必须运行 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中重写这个函数，这样就不会超过最大递归深度。是否可以？有没有什么方法可以将递归转换为其他形式？谢谢!

最佳答案

这是一个重构代码以在单个 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();
  }
}

使用 requestAnimationFrame 或 setTimeout 来逃避堆栈从来都不是一个好主意。它会使代码运行缓慢。

示例

这是可运行代码片段中的内容。我添加了迷宫的可视化，以便于检查输出。

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>

关于javascript - 是否可以使用 requestanimationframe 来建模递归？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/72348501/

上一篇：apache-flink - Flink AggregateFunction 与带有 ValueState 的 KeyedProcessFunction

下一篇：regex - 无法将两个正则表达式合并为一个以生成在 VSCode 中使用的代码片段

相关文章：

javascript - 填充下拉列表选择

javascript - jQuery动画批量图像

javascript - React.js 中游戏币的结账按钮

algorithm - 在 n+1 次调用中返回 3^k 的函数

java - 这是什么最短路径迷宫算法？

c++ - 迷宫表示帮助

javascript - p :menuitem onclick update not working

c# - 尝试用递归更优雅地解决电话词

python - 使用 python 删除 JSON 中的键时如何正确保持结构？

java - 尝试放大迷宫 GUI 时矩形重叠

©2024 IT工具网  联系我们