是否可以使用 requestanimationframe 对递归进行建模？

Question

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

Answer 1

这是在单个 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 对要绘制的单元格的渲染进行排队 frame-by-frame。

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>

是否可以使用 requestanimationframe 对递归进行建模？

Is it possible to model recursion with requestanimationframe?

javascript

recursion

maze

例子

动画！