JavaScript 扫雷 - 立即打开整个无雷区域无法正常工作（洪水填充）

问题描述 投票：0回答：1

我正在尝试用 JavaScript 构建一个简单的扫雷游戏。除了单击无地雷图块时打开整个无地雷区域的功能外，它还可以正常工作。它开始检查相邻的瓷砖，但当第一个相邻的瓷砖有地雷时停止。

正如您在下面的屏幕截图中看到的（单击图块 1/5 后），仅打开第一个“1”之前的图块。它实际上应该打开一个更大的区域：

看来我已经很接近了。这是我的代码：

const gridSize = 10

// generate grid
const board = document.querySelector("#minesweeper");
// loop over num for rows
let header = 0;
for(let i = 0; i < gridSize+1; i++) {
  const row = document.createElement("tr");
  // loop over num for cols
  for (let j = 0; j < gridSize+1; j++) {
  // add col to row
    if ( i === 0 ) {
      row.insertAdjacentHTML("beforeend", `<th>${header}</th>`);
      header += 1;
    } else if (j === 0) {
      row.insertAdjacentHTML("beforeend", `<th>${header-10}</th>`);
      header += 1;
    } else {
      row.insertAdjacentHTML("beforeend", `<td class='unopened' dataset-column=${j}></td>`);
    };
  };
  // add row to board
  board.append(row);
};

// functions -------------------

function getNeighbour(tile, i, j) {
  const column = tile.cellIndex; // so the columns get the cellIndex
  const row = tile.parentElement.rowIndex; // row gets the rowIndex(tr) 
  const offsetY = row + i;
  const offsetX = column + j;
  return document.querySelector(`[data-row="${offsetY}"][data-column="${offsetX}"]`);
}
// count mines of neighbours

function countMines(tile) {
  let mines = 0;

  for(i = -1; i <= 1; i++) {
    for(j = -1; j <= 1; j++ ) {
      // check if neighbour has mine
      // get cell values from neighbour in DOM
      nb = getNeighbour(tile, i, j);
      if (nb && nb.classList.contains('has-mine') || (nb && nb.classList.contains('mine'))) mines += 1; // if nb exists and has a mine increase mines
    }
  }

  // write into DOM
  if (mines === 0) {
    tile.classList.add(`opened`);
  } else {
    tile.classList.add(`neighbour-${mines}`);
  }
  tile.classList.remove(`unopened`);

  // if mines are 0, go to neigbours and count mines there
  // console.log(tile.classList);
  if (mines === 0) {
    // alert("mines are zero");
    for (i = -1; i <= 1; i+=1) {
      for (j = -1; j <= 1; j+=1) {
        nb = getNeighbour(tile, i, j);
        if (nb && nb.classList.contains("unopened")) {
          countMines(nb);
        }
      }   
    }
  }
  return mines;
}

// function open tile on click
function openTile(event) {
  const tile = event.currentTarget;

    // if there is a mine you lose
    if (tile.classList.contains("has-mine")) {
      document.querySelectorAll(".has-mine").forEach((cell) => {
        cell.classList.remove("has-mine", "unopened");
        cell.classList.add("mine", "opened");
      });
      alert("booooooooom!");
    } else {
      countMines(tile);
    }
  }
  

const tiles = document.querySelectorAll("td");

tiles.forEach((td) => {
  td.dataset.column = td.cellIndex; // so the columns get the cellIndex
  td.dataset.row = td.parentElement.rowIndex; // row gets the rowIndex(tr) 

  // add mines randomly
  const freq = 0.1;
  if (Math.random() < freq) {
    td.classList.add("has-mine");
  } 


  // eventlisteners per tile
  td.addEventListener("click", openTile);
});

我已经思考了几个小时，但找不到使用此代码的方法。不确定我是否已经接近或是否需要修改整个方法？

javascript flood-fill minesweeper
1个回答
3
投票

原理很简单，对于每个空单元格，必须添加所有相邻的空单元格。
还需要收集每个单元格的相邻地雷数量

a) 列出 8 个相邻单元格，除了位于边缘的单元格 这是我代码中的 

prxElm()
函数
b) 计算单元周围存在的地雷 -> 
prxMne()

从第一个单元格开始
1-我们计算 (a) 附近的地雷
2-它成为要映射的单元格堆栈的第一个元素
3-如果附近的地雷数量为零，则对所有相邻单元格重复此操作

该算法的特殊性在于仅使用一个堆栈来累加待映射的坐标。 它将具有相邻地雷的元素放在堆栈的顶部，而那些没有相邻地雷的元素则放在堆栈的末尾。

由于可能有多个单元格没有相邻的地雷，因此我们保留最后处理的空单元格的索引

iExp
。 当然，当您在堆栈开头附近添加一个带有地雷的单元格时，该索引会发生移动。

该算法还注意不要通过检查该单元格是否不在堆栈中来添加重复的相同单元格。 见

.filter(x=>!explor.some(e=>e.p===x.p))

当探索索引 

iExp
到达堆栈末尾时，此过程结束。

这是全部代码，尚未完全确定，但要点已经有了。

const 
  MinesCount = 17  // adjusted values to fit this snippet display area
, gridSz = { r:7, c:20 } // grid  rows x cols
, gridMx = gridSz.r * gridSz.c
, proxim = [ {v:-1,h:-1},  {v:-1,h:0}, {v:-1,h:+1}, {v:0,h:-1}, {v:0,h:+1}, {v:+1,h:-1}, {v:+1,h:0}, {v:+1,h:+1} ]
, prxElm = (r,c) => proxim.reduce((a,{v,h})=>
    { 
    let rv = r+v, ch = c+h;
    if (rv>=0 && ch>=0 && rv<gridSz.r && ch<gridSz.c) a.push({p:((rv * gridSz.c) + ch), r:rv, c:ch} )
    return a
    },[])
, GenNbX = (nb,vMax) => [null].reduce(arr=>
    {
    while (arr.length < nb)
      {
      let numGen = Math.floor(Math.random() * vMax)
      if (!arr.includes(numGen)) arr.push(numGen);
      }
    return arr //.sort((a,b)=>a-b)
    },[])
, minesP = GenNbX( MinesCount, gridMx )
, prxMne = (r,c) => prxElm(r,c).reduce((a,{p})=>minesP.includes(p)?++a:a,0)  // count mines arroub=nd
, td2rcp = td => 
    {
    let r = td.closest('tr').rowIndex -1  // -1 for thead count of rows
      , c = td.cellIndex
      , p = (r * gridSz.c) +c
    return {r,c,p}
    }
, p2rc  = p =>({r: Math.floor(p / gridSz.c), c: (p % gridSz.c)})
, { timE, cFlags, minesArea } = drawTable('mines-area', gridSz, MinesCount )
;
const chrono = (function( timeElm )
  {
  const
    one_Sec = 1000
  , one_Min = one_Sec * 60
  , twoDgts = t => (t<10) ? `0${t}` : t.toString(10)
  , chronos =
    { timZero : null
    , timDisp : timeElm
    , timIntv : null
    , running : false
    }
  , obj =
    { start()
      {
      if (chronos.running) return
      chronos.timDisp.textContent = '00:00'
      chronos.running = true
      chronos.timZero = new Date().getTime()
      chronos.timIntv = setInterval(() =>
        {
        let tim = (new Date().getTime()) - chronos.timZero
        chronos.timDisp.textContent = `${Math.floor(tim/one_Min)}:${twoDgts(Math.floor((tim % one_Min)/one_Sec))}`   
        }
        , 250);
      }
    , stop()
      {
      if (!chronos.running) return
      chronos.running = false
      clearInterval( chronos.timIntv )
      }
    }
  return obj
  }(timE))

function drawTable(tName, gSz, mines )
  {
  let table = document.getElementById(tName)
  //  table.innerHTML = ''  // eraze table

  let tHead  = table.createTHead()
    , tBody  = table.createTBody()
    , xRow   = tHead.insertRow()
    , timE   = xRow.insertCell()
    , cFlags = xRow.insertCell()
    ;
  timE.setAttribute('colspan', gSz.c -4)
  timE.className   = 'time'
  timE.textContent = '0:00'

  cFlags.setAttribute('colspan', 4)
  cFlags.className   = 'flag'
  cFlags.textContent = ' 0/' + mines
  
  for (let r=gSz.r;r--;)
    {
    xRow = tBody.insertRow()
    for(let c = gSz.c;c--;) xRow.insertCell()
    }
  return { timE, cFlags, minesArea: tBody } 
  }
minesArea.onclick = ({target}) =>
  {
  if (!target.matches('td'))        return
  if (target.hasAttribute('class')) return // already done

  chrono.start()

  let {r,c,p} = td2rcp(target)
  
  if (minesP.includes(p))  // you are dead!
    {
    chrono.stop()
    minesArea.className = 'Boom'
    minesP.forEach(p=>  // show mines
      {
      let {r,c} = p2rc(p) 
      let td = minesArea.rows[r].cells[c]
      if (!td.hasAttribute('class')) td.className = 'mineOff'
      })
    minesArea.rows[r].cells[c].className = 'mineBoom'  // this one is for you
    minesArea.querySelectorAll('td:not([class]), td.flag') // jusr disable click 
      .forEach(td=>td.classList.add('off'))               // and cursor
    }
  else
    {
    let explor = [ {p, r, c, m:prxMne(r,c) } ]
      , iExp   = 0
      ;
    while (iExp < explor.length && explor[iExp].m === 0) // Open mine-free area 
      {
      prxElm(explor[iExp].r,explor[iExp].c)  // look around
      .filter(x=>!explor.some(e=>e.p===x.p)) // if not already in
      .forEach(x=>
        {
        M = prxMne(x.r,x.c) 
        if (M>0 ) { explor.unshift( { p:x.p, r:x.r, c:x.c, m:M} ); iExp++ }
        else        explor.push( { p:x.p, r:x.r, c:x.c, m:M} )  // mine-free space
        }) 
      iExp++
      }
    explor.forEach(({r,c,m})=>minesArea.rows[r].cells[c].className = 'm'+m )
    }
  if (checkEnd()) // some kind of victory!?
    {
    chrono.stop()
    minesArea.querySelectorAll('td.flag').forEach(td=>td.classList.add('off'))
    minesArea.className = 'win'
    }
  }
minesArea.oncontextmenu = e =>  // Yes, there is a right click for flag mines
  {
  if (!e.target.matches('td')) return
  e.preventDefault()

  let {r,c,p} = td2rcp( e.target)
    , cell_rc = minesArea.rows[r].cells[c]
    ;
  if (!cell_rc.hasAttribute('class'))    cell_rc.className = 'flag'
  else if (cell_rc.className === 'flag') cell_rc.removeAttribute('class')

  let nbFlags = minesArea.querySelectorAll('td.flag').length

  cFlags.textContent = ` ${nbFlags} / ${MinesCount}`
  }
function checkEnd()
  {             // what about us ?
  let count     = 0
    , reject    = 0 
    , tdNotSeen = minesArea.querySelectorAll('td:not([class])')
    , flagPos   = minesArea.querySelectorAll('td.flag')
    ;
  cFlags.textContent = ` ${flagPos.length} / ${MinesCount}`
    
  if (tdNotSeen.length > MinesCount ) return false

  flagPos.forEach(td=>
    {
    let {r,c,p} = td2rcp(td)
    if (minesP.includes(p)) count++    // correct place
    else                    reject++
    })
  tdNotSeen.forEach(td=>
    {
    let {r,c,p} = td2rcp(td)
    if (minesP.includes(p)) count++
    else                    reject++ // no mines there
    })
  if (count != MinesCount || reject != 0 ) return false

  tdNotSeen.forEach(td=>
    {
    let {r,c,p} = td2rcp(td)
    minesArea.rows[r].cells[c].className = 'mineOff'
    })
  cFlags.textContent = ` ${MinesCount} / ${MinesCount}`
  return true
  }
body { background-color: #383947; }  /* dark mode ? ;-) */
table {
  border-collapse : collapse;
  margin          : 1em auto;
  --szRC          : 18px;
  font-family     : Arial, Helvetica, sans-serif;
  }
table td {
  border     : 1px solid #1a1a1a80;
  text-align : center;
  }
table thead {
  font-size        : .8em;
  background-color : #c3c5db; 
  }
table tbody {
  background-color : #a39999;
  cursor           : cell;
  }
table tbody td {
  width     : var(--szRC);
  height    : var(--szRC);
  overflow  : hidden;
  }
.m0, .m1, .m2, .m3, .m4, .m5, .m6, .m7, .m8  { background-color: whitesmoke; font-size: 12px; font-weight: bold; cursor: default; }
.m1::after { content: '1'; color: #0000ff; }
.m2::after { content: '2'; color: #008000; }
.m3::after { content: '3'; color: #ff0000; }
.m4::after { content: '4'; color: #000080; }
.m5::after { content: '5'; color: #800000; }
.m6::after { content: '6'; color: #008080; }
.m7::after { content: '7'; color: #000000; }
.m8::after { content: '8'; color: #808080; }
.off { cursor: default; }
.Boom            { background-color: yellow; cursor: default; }
.mineOff         { cursor: default;               padding: 0;  }
.flag            { background-color: lightgray; padding: 0; }
.mineBoom        { color: crimson;              padding: 0; }
.mineOff::after,
.mineBoom::after { content: '\2738';  }     
.flag::before    { content: '\2691'; color: crimson; }
.time::before    { content: 'Time elapsed : '; color: darkblue; }
.win td          { border-color: gold;}
<table id="mines-area"></table>

我认为递归方法不适合解决这类问题。 它需要制定复杂的策略来探索空白空间。 例如，围绕起点盘旋。
但这种策略遇到了岛屿阻碍前进的问题，一旦穿越，就需要进行新的螺旋前进，恢复上一次螺旋中隐藏的点，但又要避开上一次螺旋中已经探索过的点。螺旋。

你也可以从初始点按扇区前进，但你仍然会遇到同样的小岛及其回溯问题，这些问题也会随着探索海岸的每一个粗糙度而倍增。

这需要复杂的计算，难以掌握和调试，更不用说递归方法大量使用调用堆栈，而调用堆栈会为每个新分支累加。

（在不忽视发疯的风险的情况下，努力开发其递归算法。）

网格越大，其递归列表之间的冲突就越多，计算时间受到的影响也越大。

当然，这种类型的策略已经有了获胜的启发式方法，它们的水平非常高，而我们现在只是在进行扫雷游戏，数百行代码毫无作用。

我的方法只使用单栈，其算法很容易理解，只需要几行代码。
还有什么？

最新问题
© www.soinside.com 2019 - 2025. All rights reserved.