Jump to content
  • Advertisement
Sign in to follow this  
steeg

Flood-Fill & Backtracking

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by steeg
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:
*** 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!