# Flood-Fill & Backtracking

This topic is 4581 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I've been reading about backtracking algorithms and how I could implement it in a flood-fill scenario. I came across a pseudo-code which was something like:
Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. Set the color of node to replacement-color.
3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
4. Return.


Say I used a for loop to loop through each of the 4 directions (N,E,S,W), would this approach fit into the category of a backtracking algorithm? Also, does anyone know the Big-O notation of a flood fill algorithm (say the most used implementation), since I've been unable to find it in google? Thanks.

##### Share on other sites
If you're just trying to implement flood-fill on some two-dimensional surface (e.g., the Bucket tool in Paint), a backtracking algorithm is not the right approach. The accepted way is to divide the region into a certain number of subrectangles and then flood-fill each rectangle.

##### Share on other sites
Quote:
 Original post by steegHi, I've been reading about backtracking algorithms and how I could implement it in a flood-fill scenario. I came across a pseudo-code which was something like:*** Source Snippet Removed ***Say I used a for loop to loop through each of the 4 directions (N,E,S,W), would this approach fit into the category of a backtracking algorithm? Also, does anyone know the Big-O notation of a flood fill algorithm (say the most used implementation), since I've been unable to find it in google? Thanks.

That pseudo-code is recursive..

Out of curiosity, k, when would a backtracking algorithm be the right approach?

##### Share on other sites
I know there are better alternatives to backtracking, it's just that I'm doing a paper on this type of algorithms and I wanted to find other possible scenarios for it instead of the ones that appear all over the internet, such as the knight's tour or maze solution.

Also, do you know the Big O notation for a typical flood fill algorihtm, be it implemented as backtracking or other?...Thanks.

##### Share on other sites
The pseudocode you have above comes directly from wikipedia (http://en.wikipedia.org/wiki/Flood_fill). Have a look at the rest of the page, as it shows pseudocode for more practical applications that don't put your stack at risk.

##### Share on other sites
in the wikipedia page, there ir an animated gif of this algorithm...doesn't it work like an implicit backtracking, since once it cannot move to any other directions (all of the color have already been changed), it returns recursively to previous positions?

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
634134
• Total Posts
3015749
×