Is it possible to model recursion with requestanimationframe?

user_16943727 0
Viewed 53

I am creating a maze generation function, which requires uses recursive backtracking and obviously requires recursion. The function has to be run length * breath times, which sometimes exceeds the maximum recursion depth. The following is the code for the maze:

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

Given the definition of recursion, I believe that this function can be rewritten in requestAnimationFrame, so that the maximum recursion depth will not be exceeded. Is it possible? Are there any methods to convert recursion to something else? Thank you!

maze recursion javascript
1 Answers

Here's an example of your code refactored to run in a single while loop. I'm not sure if there's a specific approach to it, but just showing you the code might help...

This is the main part:

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

Using a requestAnimationFrame or setTimeout to kind of escape the stack is never a good idea. It will make the code run slow.

Example

Here's the thing in a runnable snippet. I added visualization of the maze to make it easy to check the output.

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>

Animations!

Just for fun, here's an example of what requestAnimationFrame is useful for: animating stuff! This snippet generates the maze in a single loop, but uses requestAnimationFrame to queue the rendering of a cell to be drawn 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>

user_32972910
Related