Home arrow Practices arrow Page 4 - Solving Problems with Recursion

The Flood Fill Algorithm - Practices

Recursion is a way to solve a problem by...reducing it to the same problem. What? It may be counterintuitive, but many turn-based games (including chess) use exactly this technique to make a computer player "think." Mohamed Saad explains the concept, along with when (and when not) to use recursion in your programming. Check out the Connect4 example!

TABLE OF CONTENTS:
  1. Solving Problems with Recursion
  2. The Plot Thickens
  3. First Programming Example
  4. The Flood Fill Algorithm
  5. How it Works
  6. Connect 4 AI program
  7. The Minimax Method
  8. Placing Pieces
  9. Trying it Out
  10. Two More Tips
By: Mohamed Saad
Rating: starstarstarstarstar / 54
November 17, 2004

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

Now, let's turn our attention to a totally different problem. We are working on a 2D drawing package, and we want to make a bucket fill tool similar to that found in Microsoft Paint. The user selects a color, clicks on a point, and the color spreads to fill the area with this color. Have a look at this figure.

Solving Problems with Recursion

Fig 2. We need to write a program to flood fill a shape

We want to write a function to implement this feature. We are given a 2 dimensional array of colors, a point to start painting from, and a color. We should fill the fill area with the color as mentioned above.

There is no easy non-recursive solution to this problem, but we can solve this recursively in just 8 lines of code. How? The idea is simply to make a flood fill from a point do the following:

  • If the point we want to color is already filled, don't do anything and stop, else color it.
  • If the point above it is not colored, call flood fill from that point (recursive step).
  • If the point to the right is not colored, call flood fill from that point (recursive step).
  • If the point to the left is not colored, call flood fill from that point (recursive step).
  • If the point below it is not colored, call flood fill from that point (recursive step).

Now, you see, the whole solution is just 5 steps, and 4 of them are recursive calls. It is important to understand how this actually works.

class Canvas
{
 byte board[][]=new byte[100][100];
 public void Fill(int x,int y,byte c)
 {
  if(board[x][y]==c) return;
  board[x][y]=c;
  if(x<99&&board[x+1][y]!=c)
   Fill(x+1,y,c);
  if(x>0&&board[x-1][y]!=c)
   Fill(x-1,y,c);
  if(y<99&&board[x][y+1]!=c)
   Fill(x,y+1,c);
  if(y>0&&board[x][y-1]!=c)
   Fill(x,y-1,c);
 }
}

I have tried to make the code simpler by fixing width and height. But, of course, it is easy to generalize the code to different sizes and color formats.



 
 
>>> More Practices Articles          >>> More By Mohamed Saad
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PRACTICES ARTICLES

- Calculating Development Project Costs
- More Techniques for Finding Things
- Finding Things
- Finishing the System`s Outlines
- The System in So Many Words
- Basic Data Types and Calculations
- What`s the Address? Pointers
- Design with ArgoUML
- Pragmatic Guidelines: Diagrams That Work
- Five-Step UML: OOAD for Short Attention Span...
- Five-Step UML: OOAD for Short Attention Span...
- Introducing UML: Object-Oriented Analysis an...
- Class and Object Diagrams
- Class Relationships
- Classes

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: