Recursive fill function on a grid of pixels?

Question

I'm looking for a way to create a function that fills a grid of pixels w/ a given colour.

If the user clicks on one pixel, my idea is to check if each of the pixel's neighbours (up, down, left, and right) is the same colour as the pixel that was clicked. For each neighbour, if it's the same colour, change it to black. If the neighbour pixel isn't the same colour as the original pixel clicked, it would be a stop condition.

Each of my pixels lives inside an array, and structure of each pixel object is as follows:

{
  colour: 0xFFFFFF, // Or some other color
  neighbours: {
    l: PixelObj,
    r: PixelObj,
    u: PixelObj,
    d: PixelObj
  }
}

If the pixel is on the edge of the grid (40x40), one of it's neighbour objects will be null instead of a reference to another pixel.

Is there a way to create a function that fills a colour recursively, given each pixel in a grid that knows it's neighbours properties?

Sounds like you want a [flood](https://stackoverflow.com/questions/36408961/flood-fill-algorithm-in-javascript-too-much-recursion) [fill](https://stackoverflow.com/questions/19839947/flood-fill-in-python?rq=1) [algorithm](https://stackoverflow.com/questions/21358513/flood-fill-recursive-algorithm?rq=1). It even has it's [own tag](https://stackoverflow.com/questions/tagged/flood-fill). — Nick is tired, Mar 27 '18 at 03:45
Awesome, yes this is exactly what I was looking for. If you want to post this as an answer I'll accept it :) — saricden, Mar 27 '18 at 03:52

score 1 · Answer 1 · answered Mar 27 '18 at 03:41

Seems simple enough, use a Set to check to see if each pixel you're iterating over has been checked yet:

function recursiveFill(origPixel) {
  const checkedPixels = new Set();
  function fillPixelRec(pixel, clickedColor) {
    // nulls:
    if (!pixel) return;
    // pixels already checked:
    if (checkedPixels.has(pixel)) return;
    // make sure this pixel doesn't get checked again:
    checkedPixels.add(pixel);

    if (pixel.color === clickedColor) return;
    pixel.color = 0xffffff;
    fillPixelRec(pixel.l, clickedColor);
    fillPixelRec(pixel.r, clickedColor);
    fillPixelRec(pixel.u, clickedColor);
    fillPixelRec(pixel.d, clickedColor);
  }
  const origColor = origPixel.color;
  fillPixelRec(origPixel.l, origColor);
  fillPixelRec(origPixel.r, origColor);
  fillPixelRec(origPixel.u, origColor);
  fillPixelRec(origPixel.d, origColor);
}

score 1 · Accepted Answer · answered Mar 27 '18 at 03:59

The name of the algorithm that you've described is called a flood fill algorithm.

There are plenty of examples available to you on SO such as:

It even has it's own tag: flood-fill.

If you try to implement one of these algorithms and run into more specific problems then you can come back and ask another question.

Recursive fill function on a grid of pixels?

2 Answers2