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!

  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



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;

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


- 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: