Workshop › Puzzle Bobble-style Bubble Shooter › Step 17 of 31

Flood fill

What we are doing

connected finds every cell reachable from a start through neighbours that pass a test, like paint spreading: a queue of cells to visit and a set of cells already seen.

```js
// Flood fill: every cell connected to (r, c) through neighbours that pass the test.
function connected(starts, test) {
  const seen = new Set(starts.map(([r, c]) => r * COLS + c))
  const queue = [...starts]
  while (queue.length) {
    const [r, c] = queue.shift()
    for (const [nr, nc] of neighbors(r, c)) {
      if (seen.has(nr * COLS + nc) || !test(nr, nc)) continue
      seen.add(nr * COLS + nc)
      queue.push([nr, nc])
    }
  }
  return [...seen].map((k) => [Math.floor(k / COLS), k % COLS])
}
```

What it means

seen holds cells as single numbers (r * COLS + c); the starts count as seen.
While the queue is not empty, take the first cell and look at its neighbours.
A neighbour that is new and passes test is marked seen and joins the queue.
At the end every seen number is turned back into [r, c].

Your turn

Under snap, write the comment and connected.

Skills: Loops, Arrays and objects

← Six neighbours Three in a row pop →

All steps