Flood Fill algorithm: A graphical step-by-step explanation of the paint bucket
Tags: computerscience, algorithms, tutorial, javascript
Published: 2020-10-25 16:34:26

Finally (🎉🎆) I was able to put the idea of illustrating bits of my knowledge and create Youtube videos from it into practice and therefore [🖍️crayon code🖍️ was born](https://www.youtube.com/channel/UCqGvJhEVdtqwDk6ixVl5uOQ). 
Today I'd like to share this episode on the `Flood Fill` algorithm with all the friendly people on dev.to. I'm grateful for any kind of feedback - especially on the video itself and of course on anything else you like or think could use improvement. 

Below you can watch the video as well as read the transcript with selected frames from the illustration.

{% youtube 5Bochyn8MMI %}

Flood Fill is a simple implementation of what makes the paint bucket work in graphics software. It can be implemented in basically two ways: Recursively and iteratively. In this episode we're going to cover the iterative version, which will also make use of the queue data structure.

![Schema of recursive and iterative implementation](https://dev-to-uploads.s3.amazonaws.com/i/0pjf5ai4cy2dh7fvpum1.png)

All flood fill needs, is
- an `image` to work on
- a so called `seed` which is simply the `x` and `y` coordinates for instance where paint bucket was clicked
- and a `fillColor` which we'll pour over the image.

![Flood fill signature](https://dev-to-uploads.s3.amazonaws.com/i/s5b53dabl3klg75qp6yi.png)

So, imagine having a nice little image with different color patches. The marked pixel of the white patch is the seed, because that's where the user clicked. 
Now, the goal of the Flood Fill algorithm is to find all pixels which have the same color as the seed pixel and which are also connected to it.

![Seed and seed color](https://dev-to-uploads.s3.amazonaws.com/i/b1uv5e7kb8sp6ivn5ehr.png)

Right at the beginning, the seed pixel is a quite important one as it defines the so called `seedColor`. Only neighboring pixels that have the same color as the seed color are seen as part of the area to be filled. Non-adjacent pixels of different colors are therefore ignored.

With a `queue` we'll keep track of the neighboring pixels that need to be looked at next. So the first pixel that needs to be looked at is the seed pixel itself. Which is why it's the first one to be added to the `queue`.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/bilu8pkt8hxmy8yczodj.png)

Now, by using a `while` loop we'll work our way through the image, which means that as long as there are pixels in the `queue`, we'll keep processing them.

The pixel currently being looked at is stored in the variable called `current`. So we change the color of the current pixel to the new fill color and start expanding to the neighboring pixels. This simply means that we add the four adjacent pixels east, south, west and north to the queue.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/4e9gdgg00pzs4pbiitw0.png)

And from there on it's literally just repeating that over and over, which means that all pixels in the queue are colored one after another and expanded to their respective neighbors.

However, one piece of logic is still missing. In case the current pixel is pointing at a pixel that does not match the seed color, this pixel is neither colored nor expanded to its neighbors, which is the reason why the loop is simply continued without further action. That way it's ensured that the algorithm does not cross over to areas that do not match the seed color.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/6e89i662geixvwebnou3.png)

Now, you may have wondered, why the diagonal neighbors like south-east and north-west are not taken into acount. This final situation shows perfectly well, why. If the _south-eastern_ neighbor would be taken into account, flood fill would be able to cross through the diagonal border, causing it to flood more image areas than actually desired.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/y2myzf0m6dgs4fv2oh40.png)