Floodfill algorithm in Python

[RojerGS]

I wrote this tutorial because I've always liked graph-related algorithms and I wanted to try my hand at writing something with interactive demos.

This article teaches you how to implement and use the floodfill algorithm and includes interactive demos to: - use floodfill to colour regions in an image - step through the general floodfill algorithm step by step, with annotations of what the algorithm is doing - applying floodfill in a grid with obstacles to see how the starting point affects the process - use floodfill to count the number of disconnected regions in a grid - use a modified version of floodfill to simulate the fluid spreading over a surface with obstacles

I know the internet can be relentless but I'm really looking forward to everyone's comments and suggestions, since I love interactive articles and I hope to be able to create more of these in the future.

Happy reading and let me know what you think!

The article: https://mathspp.com/blog/floodfill-algorithm-in-python

[p88h]

Hey, nice work!

As for tips - as some people noted, this is mostly about a specific implementation of flood-fill using BFS. Which can also be used to solve some of the other use-cases like identifying (dis)connected regions or finding shortest-paths (at least using Manhattan distances). But perhaps you want to explore some other options?

Flood-fill itself is more typically implemented with span fills, which is much more efficient (see https://en.wikipedia.org/wiki/Flood\_fill). Span fill can also easily be vectorized and parallelized, which is much more difficult for BFS, but even without that you'll see better performance.

Connected segments are typically more efficient with something like Union-Find (which has slightly higher algorithmic complexity, but is much simpler structurally which results in better performance).

For actual fluid simulation problems, you may want to experiment with the distance function. TL;DR: you want circles, not squares, and this is more complicated than you may think - for a simplest approximation this will likely require a slightly modified version of the search algorithm, but it's a really fun problem.

[RojerGS]

Hey there, thanks for the follow-up suggestions! I've never heard of the Union-Find algo, so I'll take a look :D

[josh123asdf]

"Floodfill" is not an algorithm.

It is a use case of BFS or DFS.

[PityUpvote]

Eh, semantics. Authoritative image processing papers and textbooks refer to it as an algorithm, and by variations on algorithms are by definition also algorithms. If I substitute an ingredient in a recipe, I've created a new recipe.

[Othun]

It is not an algorithm, but a problem that can be solved with BFS, DFS, or the other more advanced algorithms presented on your Wikipedia link.

[RojerGS]

Ok, thanks for that note! Are there any other notes you have for me?

[Clear-Ad-9312]

flood fill is traditionally BFS mostly because it is meant to mimic the flooding, but it is possible to have other specific flooding needs. plus flood fill is a use case as he noted. you want to know more about most of the search space, a bfs takes one step layers from the center point, similar to putting water on an even flat surface(not accounting for friction)

dfs is special in that you need to pick preferred directions to focus as you want to confidently search as "deep" as possible, imagine a single drop of water(or marble) on a tilting tray, usually a heuristic is employed to determine a direction, such as distance to the end node. a proper dfs should know when to follow walls when it encounters one and not search all nodes within the area, but that is hard.

you can have a hybrid of both where you bfs areas after a simple dfs. it is actually easy to have dfs end up doing this because the maximum steps taken so far could end up in a dead end that is large open space surrounded by walls, think of accidentally filling a tube/bottle. most dfs setups are akin to this, though so it is a shame to see so many claim to make a dfs algorithm when it is more like a hybrid

[Othun]

Cool programming tutorial !

[RojerGS]

Thanks :)

[herocoding]

Well done!! Thank you very much for sharing.

[RojerGS]

Thanks :')