JavaScript Minesweeper - Opening whole mine-free area at once not working properly (flood-fill)

Question

I am trying to build a simple minesweeper game in Javascript. It works propererly apart from the function to open the entire mine-free area when clicking on a mine-free tile. It starts checking the neighbouring tiles, but stops when the first neighbouring tile has a mine.

As you can see on the screenshot below (after clicking on tile 1/5) only the tiles until the first "1" are opened. It should actually open a much larger area:

It seems I am pretty close. THis is my code:

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

I have been thinking hours about it but could not find a way to work on with this code. Not sure if I am close or if I would need to modify the whole approach?

Answer 1

the principle is simple, for each empty cell, you must add all the adjacent empty cells.
it is also necessary to collect the number of adjacent mines of each cell

a) list the 8 adjacent cells, except for the cells placed at the edge this is the prxElm() function in my code
b) count the mines present around a cell -> prxMne()

starting from the first cell
1- we count (a) nearby mines
2- it becomes the first element of a stack of cells to be mapped
3- if its number of nearby mines is zero, repeat this operation for all adjacent cells

the particularity of this algorithm is to use only one stack to accumulate the coordinates to be mapped. it places the elements with adjacent mines at the top of the stack, and those with none at the end of the stack.

as there can be several cells without adjacent mines, we keep an indexiExp of the last empty cell processed. of course when you add a cell with mines nearby at the start of the stack, this index is shifted.

the algorithm also take care not to add duplicate the same cell by checking before if this cell is not in the stack. see .filter(x=>!explor.some(e=>e.p===x.p))

this ends when the exploration index iExp reaches the end of the stack.

here is the whole code, it is not completely finalized, but the essentials are there.

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>

I don't think a recursive method is suitable for this kind of problem. It requires having a complex strategy for exploring empty spaces. For example, spiraling around the starting point.
But this strategy comes up against the problem of the island hindering this progress, and which requires, once crossed, to carry out a new spiral advance to recover the points hidden during the previous spiral, but having to avoid the points already explored during the previous spiral.

You can also move forward by sectors from an initial point, but you will still encounter the same problem of the islet and its backtracking, which also multiply here with each roughness on the explored shores.

This requires complex calculations that are difficult to master and debug, not to mention the fact that recursive methods intensively use call stacks which it adds up for each new branch.

(Without neglecting the risk of going crazy, by striving to develop its recursive algorithms.)

The larger the grid and the more its recursive lists will conflict with each other, and more the computationnal time will be affected.

Of course there are already winning heuristics on this type of strategy, they are of a very high level, and we are here just on a minesweeper game where hundreds of lines of code have nothing to do.

My method only uses a single stack, its algorithm is easy to understand and requires a few lines of code.
What more ?