# Flood Fill Visualization (#201)

**URL:** <https://www.ruby-forum.com/t/flood-fill-visualization-201/165796>\
**Category:** Ruby\
**Created:** [April 17, 2009, 5:20pm UTC](https://www.ruby-forum.com/t/flood-fill-visualization-201/165796 "2009-04-17T17:20:21Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [April 17, 2009, 5:20pm UTC](https://www.ruby-forum.com/t/flood-fill-visualization-201/165796/1 "2009-04-17T17:20:21Z")

</div>

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this  
quiz until 48 hours have elapsed from the time this message was  
sent.

2. Support Ruby Q. by submitting ideas and responses  
as often as you can!  
Visit: [http://rubyquiz.strd6.com/suggestions](http://rubyquiz.strd6.com/suggestions)

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem  
helps everyone on Ruby T. follow the discussion. Please reply to  
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Flood Fill Visualization (#201)

Bonjour Rubyists,

This week’s quiz comes from [Martin DeMello](http://zem.novylen.net)

[Flood fill](http://en.wikipedia.org/wiki/Flood_fill) is a simple algorithm that colours in a connected  
region of a bitmap. The algorithm looks for all nodes which are  
connected to the start node by a path of the target color, and changes  
them to the replacement color. (Check out the Wikipedia page for more  
information.)

While simple, the algorithm is pretty satisfying to watch in action,  
which brings us to the quiz: have a program accept a bitmap and a  
starting point, and animate the algorithm as it floodfills the region  
containing that point.

Have Fun!

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [April 20, 2009, 6:49am UTC](https://www.ruby-forum.com/t/flood-fill-visualization-201/165796/2 "2009-04-20T06:49:02Z")

</div>

My solution attached.

Thanks!  
martin

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [April 23, 2009, 6:41am UTC](https://www.ruby-forum.com/t/flood-fill-visualization-201/165796/3 "2009-04-23T06:41:34Z")

</div>

Here’s my solution - a bit quick-and-dirty, but I had fun writing it 🙂

martin

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [April 25, 2009, 10:37pm UTC](https://www.ruby-forum.com/t/flood-fill-visualization-201/165796/4 "2009-04-25T22:37:48Z")

</div>

This quiz was submitted by Martin DeMello [1](http://zem.novylen.net) using the submission  
form: [http://rubyquiz.strd6.com/suggestions](http://rubyquiz.strd6.com/suggestions). Please do submit quiz  
ideas, Ruby Q. thrives with support from the community!

Martin B. provided a solution that animates the filling process by  
printing the output to the console.

The core of Martin B.'s solution is this recursive fill method.

```
def fill(x, y, target_color, replacement_color)
    return unless self[y][x] # valid point?

    return if self[y][x] != target_color
    return if self[y][x] == replacement_color

    (dump; sleep(0.2)) if @options[:animation]

    self[y][x] = replacement_color
    fill(x+1, y, target_color, replacement_color)
    fill(x-1, y, target_color, replacement_color)
    fill(x, y+1, target_color, replacement_color)
    fill(x, y-1, target_color, replacement_color)
end

```

The method begins with a few checks to determine if it should return.  
The first check exits the method if the point is outside of the  
canvas. The next check exits if the current point’s color does not  
match the target color, we don’t want to fill just anything. The third  
check exits if the current point’s color is equal to the replacement  
color, if we didn’t then we would fill forever!

This part: `(dump; sleep(0.2))` is responsible for printing the state  
of the operation to the console and waiting a little bit.

Partially Complete [2](http://rubyquiz.strd6.com/quizzes/201/floodfill_1.png)

Completed [3](http://rubyquiz.strd6.com/quizzes/201/floodfill_2.png)

The final section sets the color of the current point and recursively  
calls `fill` on all adjacent points.

Martin DeMello submitted a Shoes App solution. Although Martin D.'s  
solution didn’t work for me exactly as submitted, with a little  
tweaking I was able to get it to run. The neat part about Martin D.'s  
solution is that, aside from being colorful Shoes App, it allows you  
to view the animation when the cells are placed in a stack or a queue.

Here are two images showing the difference in how the fills proceed  
when using a stack or a queue:

Stack [4](http://rubyquiz.strd6.com/quizzes/201/stack.png)

Queue [5](http://rubyquiz.strd6.com/quizzes/201/queue.png)

In both solution the starting canvas data was represented as characters  
like so:

```
data = <<END
##############
# # #
# # #
# # # #
### # #
# # #
##############
END

```

Together these two solutions cover the major possible implementations  
of the Flood Fill algorithm: recursively with an implicit stack (the  
call stack) and iteratively with an explicit stack or queue.

I hope you find these solutions interesting and that they help you out  
when you are making your next graphics application (maybe a future  
quiz!)

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [April 26, 2009, 8:49am UTC](https://www.ruby-forum.com/t/flood-fill-visualization-201/165796/5 "2009-04-26T08:49:56Z")

</div>

On Sun, Apr 26, 2009 at 2:07 AM, Daniel M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Martin DeMello submitted a Shoes App solution. Although Martin D.'s  
> solution didn’t work for me exactly as submitted, with a little  
> tweaking I was able to get it to run.

Yes, my bad. I built this against the latest shoes-git and ruby 1.9;  
the scoping turned out to be slightly different for shoes built  
against ruby 1.8

martin