如何修复扫雷程序中超出的最大调用堆栈大小

Question

我今天用纯js和css做了一个扫雷器。单击一个块时，将使用递归打开其他块。首先，我将它用于 10x10 板。它工作得很好。但是现在当我做了一个 50x50 板子的时候。它给出了错误

Uncaught RangeError: Maximum call stack size exceeded.

这是我的完整代码。它很多，但你必须只专注于递归调用的 openBlock 函数。 50x50 棋盘上只有 10 个地雷。所以在几乎所有情况下，除了地雷之外，所有的区块都应该打开。但是部分block因为报错没有打开

// -1 => mine
// 0 => a block without touching any mine
// 1 => block touching 1 mine
// etc

//Helper Methods
//Short for querySelector and querySelectorAll
const qs = str => document.querySelector(str);
const qsa = str => document.querySelectorAll(str);

//To create an element
const ce = ({ tag, style, ...rest }) => {
   const element = document.createElement(tag);
   if (rest) {
      for (let k in rest) {
         element[k] = rest[k];
      }
   }
   return element;
};

const main = qs("#main");
//Main variables
let len, wid, mines, blocks;
let isPlaying = true;

//Helping Data
let touchingBlockArr = [
   [1, 0],
   [0, 1],
   [1, 1],
   [1, -1]
];
touchingBlockArr = touchingBlockArr.concat(
   touchingBlockArr.map(x => x.map(a => -a))
);

//Object to assign colors for different numbers.
const colorObj = {
   "-1": "red",
   0: "gray",
   1: "blue",
   2: "orange",
   3: "green",
   4: "purple",
   5: "maroon"
};

//Function to create new game.
function newGame(l, w, m = 10) {
   len = l;
   wid = w;
   mines = m;
   main.innerHTML = "";
   game = [];
   blocks = [];
   createBoard();
}

//Create board
function createBoard() {
   for (let i = 0; i < len; i++) {
      let tr = ce({ tag: "tr" });
      blocks.push([]);
      for (let j = 0; j < len; j++) {
         let td = ce({
            className: "block",
            tag: "td",
            onclick: onBlockClick,
            id: `${i},${j}`
         });
         tr.appendChild(td);
         td.id = `${i},${j}`;
         blocks[blocks.length - 1].push(td);
      }
      main.appendChild(tr);
   }
   addMines();
   setValues();
}

//Adding Mines
function addMines() {
   let addedMines = [];
   for (let i = 0; i < mines; i++) {
      let str, randX, randY;
      //To avoid repition of mines on same block.
      do {
         randX = Math.floor(Math.random() * wid);
         randY = Math.floor(Math.random() * len);
         str = `${randX},${randY}`;
      } while (addedMines.includes(str));
      addedMines.push(str);

      blocks[randX][randY].classList.add("mine");
      blocks[randX][randY].setAttribute("data-value", -1);
   }
}

//Set Numbers for each block
function setValues() {
   for (let i = 0; i < len; i++) {
      for (let j = 0; j < len; j++) {
         let val;
         let tile = +blocks[i][j].dataset.value;
         if (tile !== -1) {
            val = touchingBlockArr.filter(([y, x]) => {
               if (blocks[i + y] && blocks[i + y][j + x]) {
                  return +blocks[i + y][j + x].dataset.value === -1;
               }
            }).length;
         }
         val = val === undefined ? -1 : val;
         blocks[i][j].setAttribute("data-value", val);
         blocks[i][j].style.color = colorObj[val];
      }
   }
}


function openSingleBlock(td) {
   let val = +td.dataset.value;
   if (val === -1) {
   } else {
      td.innerHTML = val || "";
   }
   td.classList.add("opened");
}


//When a left mouse button is clicked
function onBlockClick() {
   if (this.classList.contains("flagged")) return false;
   let val = +this.dataset.value;
   //If mine is clicked.
   if (val === -1) {
      openSingleBlock(this);
   }

   //Empty block
   else if (val === 0) {
      openBlock(this);
      openSingleBlock(this);
   }

   //For blocks touching mines.
   else {
      openSingleBlock(this);
   }
}

//A function which open the blocks recursively
function openBlock(td) {
   const [x, y] = td.id.split(",").map(Number);

   //If the block is not empty then don't proceed further.
   if (+td.dataset.value !== 0) return false;
   let touchingBlocks = touchingBlockArr.map(([dx, dy]) => [x + dx, dy + y]);
   openSingleBlock(td);
   touchingBlocks.forEach(([x, y]) => {
      //To checks if blocks are not out of range
      if (blocks[x] === undefined) return false;
      if (blocks[x][y] === undefined) return false;

      let val = +blocks[x][y].dataset.value;
      let td = blocks[x][y];
      //Not a mine
      if (val !== -1) {
         //Not touching mine and not opened and not flagged.
         if (
            val === 0 &&
            !td.classList.contains("opened")
         ) {
            openBlock(td);
         }

         //Touching a mine
         else {
            openSingleBlock(td);
         }
      }
   });
}


newGame(50, 50);

body {
   font-family: cursive;
}

.block {
   height: 10px;
   width: 10px;
   text-align: center;
   border: 1px solid black;
   background-color: lightgray;
   filter: brightness(0.8);
   cursor: pointer;
   font-size: 0.25rem;
   box-shadow: 1px 1px c10px black;
   background-size: contain;
}
.block:hover {
   filter: brightness(1);
}

.opened {
   background-color: rgb(255, 255, 255);
   filter: brightness(1);
}

#main {
   border-collapse: collapse;
}
.opened.mine {
   background-image: url(mine.jpg);
   background-size: contain;
}

.flagged {
   background-image: url(flag.png);
   background-size: contain;
}

<table id="main"></table>

如果您有任何提高代码性能的技巧，请将其添加到您的答案中。

Answer 1

通常，解决由于递归导致的堆栈溢出的最简单方法是不使用递归。

在这种情况下，您可以使用以下算法：

当用户点击一个空方块时（这里，"empty block"表示一个方块没有地雷，也没有相邻的地雷）：

将块推入空堆栈
当堆栈非空时：
1. 从堆栈中弹出顶部项目
2. 如果该项目尚未打开：
  1. 将项目标记为打开
  2. 检查项目的邻居 - 将任何空的、未打开的邻居推入堆栈并将具有相邻地雷的任何非地雷邻居标记为打开

这是该算法的核心部分：

function openBlocks(startingBlock) {
    let blocksToOpen = [startingBlock];

    while (blocksToOpen.length) {
        let nextBlock = blocksToOpen.pop();

        if (!nextBlock.classList.contains("opened")) {
            // openBlock returns an array of empty neighbors that are not
            // yet open
            let additionalBlocksToOpen = openBlock(nextBlock);

            if (additionalBlocksToOpen.length) {
                blocksToOpen = [...blocksToOpen, ...additionalBlocksToOpen];
            }
        }
    }
}

请参阅下面的完整解决方案。

仅供参考，我认为如果您使用普通对象来表示游戏数据并且只在需要更改其中一部分时才触摸 DOM（显示一个块， ETC。）。由于各种原因，DOM 是出了名的慢。

// -1 => mine
// 0 => a block without touching any mine
// 1 => block touching 1 mine
// etc

//Helper Methods
//Short for querySelector and querySelectorAll
const qs = str => document.querySelector(str);
const qsa = str => document.querySelectorAll(str);

//To create an element
const ce = ({ tag, style, ...rest }) => {
   const element = document.createElement(tag);
   if (rest) {
      for (let k in rest) {
         element[k] = rest[k];
      }
   }
   return element;
};

const main = qs("#main");
//Main variables
let len, wid, mines, blocks;
let isPlaying = true;

//Helping Data
let touchingBlockArr = [
   [1, 0],
   [0, 1],
   [1, 1],
   [1, -1]
];
touchingBlockArr = touchingBlockArr.concat(
   touchingBlockArr.map(x => x.map(a => -a))
);

//Object to assign colors for different numbers.
const colorObj = {
   "-1": "red",
   0: "gray",
   1: "blue",
   2: "orange",
   3: "green",
   4: "purple",
   5: "maroon"
};

//Function to create new game.
function newGame(l, w, m = 10) {
   len = l;
   wid = w;
   mines = m;
   main.innerHTML = "";
   game = [];
   blocks = [];
   createBoard();
}

//Create board
function createBoard() {
   for (let i = 0; i < len; i++) {
      let tr = ce({ tag: "tr" });
      blocks.push([]);
      for (let j = 0; j < len; j++) {
         let td = ce({
            className: "block",
            tag: "td",
            onclick: onBlockClick,
            id: `${i},${j}`
         });
         tr.appendChild(td);
         td.id = `${i},${j}`;
         blocks[blocks.length - 1].push(td);
      }
      main.appendChild(tr);
   }
   addMines();
   setValues();
}

//Adding Mines
function addMines() {
   let addedMines = [];
   for (let i = 0; i < mines; i++) {
      let str, randX, randY;
      //To avoid repition of mines on same block.
      do {
         randX = Math.floor(Math.random() * wid);
         randY = Math.floor(Math.random() * len);
         str = `${randX},${randY}`;
      } while (addedMines.includes(str));
      addedMines.push(str);

      blocks[randX][randY].classList.add("mine");
      blocks[randX][randY].setAttribute("data-value", -1);
   }
}

//Set Numbers for each block
function setValues() {
   for (let i = 0; i < len; i++) {
      for (let j = 0; j < len; j++) {
         let val;
         let tile = +blocks[i][j].dataset.value;
         if (tile !== -1) {
            val = touchingBlockArr.filter(([y, x]) => {
               if (blocks[i + y] && blocks[i + y][j + x]) {
                  return +blocks[i + y][j + x].dataset.value === -1;
               }
            }).length;
         }
         val = val === undefined ? -1 : val;
         blocks[i][j].setAttribute("data-value", val);
         blocks[i][j].style.color = colorObj[val];
      }
   }
}


function openSingleBlock(td) {
   let val = +td.dataset.value;
   if (val === -1) {
   } else {
      td.innerHTML = val || "";
   }
   td.classList.add("opened");
}

function openBlocks(startingBlock) {
    let blocksToOpen = [startingBlock];
    
    while (blocksToOpen.length) {
        let nextBlock = blocksToOpen.pop();

        if (!nextBlock.classList.contains("opened")) {
            // openBlock returns an array of empty neighbors that are not
            // yet open
            let additionalBlocksToOpen = openBlock(nextBlock);

            if (additionalBlocksToOpen.length) {
                blocksToOpen = [...blocksToOpen, ...additionalBlocksToOpen];
            }
        }
    }
}

//When a left mouse button is clicked
function onBlockClick() {
   if (this.classList.contains("flagged")) return false;
   let val = +this.dataset.value;
   //If mine is clicked.
   if (val === -1) {
      openSingleBlock(this);
   }

   //Empty block
   else if (val === 0) {
      openBlocks(this);
   }

   //For blocks touching mines.
   else {
      openSingleBlock(this);
   }
}

function alreadyOpened(td) {
    return td.classList.contains('opened');
} 

//A function which open the blocks recursively
function openBlock(td) {
   let blocksToOpen = [];       

   const [x, y] = td.id.split(",").map(Number);

   //If the block is not empty then don't proceed further.
   if (+td.dataset.value !== 0) return false;
   let touchingBlocks = touchingBlockArr.map(([dx, dy]) => [x + dx, dy + y]);
   openSingleBlock(td);
   touchingBlocks.forEach(([x, y]) => {
      //To checks if blocks are not out of range
      if (blocks[x] === undefined) return false;
      if (blocks[x][y] === undefined) return false;

      let val = +blocks[x][y].dataset.value;
      let td = blocks[x][y];
      //Not a mine
      if (val !== -1) {
         //Not touching mine and not opened and not flagged.
         if (
            val === 0 &&
            !alreadyOpened(td)
         ) {
            blocksToOpen.push(td);
         }

         //Touching a mine
         else {
            openSingleBlock(td);
         }
      }
   });
   
   return blocksToOpen;
}


newGame(50, 50, 20);

body {
   font-family: cursive;
}

.block {
   height: 10px;
   width: 10px;
   text-align: center;
   border: 1px solid black;
   background-color: lightgray;
   filter: brightness(0.8);
   cursor: pointer;
   font-size: 0.25rem;
   box-shadow: 1px 1px c10px black;
   background-size: contain;
}
.block:hover {
   filter: brightness(1);
}

.opened {
   background-color: rgb(255, 255, 255);
   filter: brightness(1);
}

#main {
   border-collapse: collapse;
}
.opened.mine {
   background-image: url(mine.jpg);
   background-size: contain;
}

.flagged {
   background-image: url(flag.png);
   background-size: contain;
}

<table id="main"></table>

如何修复扫雷程序中超出的最大调用堆栈大小

How to fix Maximum call stack size exceeded in minesweeper

html

javascript

css

minesweeper