Talk:Flood fill

From Wikipedia, the free encyclopedia

This article falls within the scope of WikiProject Visual arts, an attempt to build a comprehensive and detailed guide to visual arts on Wikipedia. If you would like to participate, visit the project page, where you can join the project and/or contribute to the discussion.
??? Class: This article has not been assigned a class according to the assessment scale.

Contents

[edit] 4-connected vs. 8-connected and the animated GIFs

Just looking at the article the animated GIFs don't really make any sense, in fact they seem to contract each other. One might ask, "Why does the first one fill just the region but the second fills all the white spaces?" But what I think these images are trying to illustrate is the difference between 4-connected and 8-connected flood fill. 4-connected means there are four directions (N,S,E,W) to fill where as 8-connected has the diagonals as well (NE,SE,NW,SW). With that in mind the animated GIFs make perfect sense. In any case, the GIFs need to be labeled in some way and I think the difference between them needs to be explained. Bdean42 03:53, 15 December 2006 (UTC)

[edit] Random Comments

The article uses the word "array" in a non-standard way. I would assume most readers think of "indexed list of elements" when they read "array", but this is not at all what we are talking about here. I can't think of the right word right now. --AxelBoldt

Would "multidimensional array" be better? --Damian Yerrick

Yes, that would be better. --AxelBoldt

Could you provide sample implementation please ? --Taw

What problems does flood filling have??

Flood fill/C example --Damian Yerrick


The section of vector algorithms appears to be an advertisement. This be converted to something that actually talks about a vector implementation of the flood fill algorithm. -- Engineeringsimon

[edit] Flood-fill in Tetris

The opening paragraph of this article currently reads,

It is used in the "bucket" fill tool of paint programs to determine which part of a bitmap to fill with color, in Tetris implementations for determining what falls and what doesn't, and in implementations of Puyo Puyo, Magical Drop, and Lumines for determining what pieces are cleared in at least some cases.

Now, I've played Tetris before, and it doesn't use flood-fill for anything I can see. There are two conditions under which Tetris pieces fall: (1) one piece at a time falls from the top of the screen under the player's control, no flood-fill involved; and (2) when a line is cleared, every tile above the cleared line falls one step downward, no flood-fill involved. I'm removing the clause; if anyone knows a (reasonably encyclopedic) Tetris variant in which flood-fill is used, feel free to reinstate something like "... in some Tetris variants for determining what falls and what doesn't, ...". --Quuxplusone 21:59, 22 July 2005 (UTC)

Okay, User:Damian Yerrick has semi-reverted to "... and in puzzle games such as Puyo Puyo, Lumines, Magical Drop, and some implementations of Tetris (but not Columns) for determining which pieces are cleared." This makes no sense to me. First of all, Tetris doesn't use floodfill. Second of all, Columns does use floodfill, according to its Wikipedia entry ("If, after a column has fallen, there are three or more of the same symbols touching, those symbols disappear"). Third of all, one major reason for that revision was to get rid of the long and unnecessary list of Columns-variant games. I'm actually surprised that (1) there are so many Wikipedia articles on video-game clones, and (2) there's no category for them. (I don't know if Columns is the "original" in that genre, but it's the oldest of the four mentioned.)
Puyo Puyo uses the criterion of 4 like pieces touching. On the other hand, Columns, like Klax, Dr. Mario, and Tetris Attack, use n in a row. I went in and corrected the Columns article to match observed behavior on every implementation of Columns that I have played and to match the screenshot, which clearly shows three blue pieces "touching" but not in a row. Some Tetris variants (and no, not just homebrew) do use floodfill; examples include Blastris (Super NES, published by Nintendo), Bombliss (Super Famicom and Game Boy, published by BPS) aka Tetris Blast (Game Boy, developed by BPS and published by Nintendo), and Tetanus On Drugs (Game Boy Advance, homebrew). And as for "older", I'm not sure which is older between Columns and Klax. --Damian Yerrick 17:59, 26 July 2005 (UTC)
Anyway, I'll leave it alone for now, to give Damian a chance to explain his edits. --Quuxplusone 01:06, 26 July 2005 (UTC)
Magitriss, a tetris variant, uses flood fill, I believe. It's in Super Tetris 3 for the SNES. BomBliss does too when the bombs explode (sort of).

Has this issue been resolved? I don't see how Tetris would use flood filling. If it exists in a variant, I don't think that is important enough to mention here and will only serve to confuse the majority of people who are familiar only with vanilla Tetris.

However, I'm surprised Minesweeper isn't mentioned in the list-- clearly that uses a flood fill algo whenever you click on a "blank square" (one without a mine or number).

I'm going to remove Tetris and the unnecessary Columns reference and add Minesweeper. --209.6.22.35 22:47, 23 July 2006 (UTC)

Flood fill is used in some variants as part of code that prevents chunks of blocks from "floating"

i.e. given the board

        YY
N       YY
NCCCCCCCCC
NXXXX XX
NXX XXX

where "NNNN" was just dropped and "CCCC" is the line that gets cleared, some games will go to

X       
XXXXX XXYY
XXX XXX YY

instead of

        YY
X       YY
XXXXX XX
XXX XXX

and they use flood fill to detect that the YYYY blocks aren't attached to the XXXX blocks once CCCC is removed. What may be throwing people off is that the algorithm isn't used for anything _visible_ as it does in a paint program, minesweeper etc, but rather just to tag tiles as "touching the ground" vs "not touching the ground" --Random832 (contribs) 20:47, 18 April 2008 (UTC)

[edit] Bugs

I might be worth noting that the last (supposedly best) algoithm described on this page doesn't actually work. I tried implementing it and found that it runs out of heap space quite quickly. The reason is that you need to keep track of which nodes you've already visited so that you don't hit them again. After adding that it works well.

This shouldn't be a problem if the program is properly checking that the node it's visiting has the target color. A list of visited nodes isn't needed, because they can be identified: they are fill-colored instead of target-colored 152.23.68.158 (talk) 14:41, 29 March 2008 (UTC)

[edit] Other algorithms

It seems there is no wikipedia article about the odd/even scanline fill algorithm described e.g. here: scanline fill 1 and here: scanline fill 2. Does anyone have the time and skill to write one? --FaetterH 12:48, 4 October 2006 (UTC)

I added some information about the scanline algorithm, and a link to a more complete description. It would be nice if someone could provide an animated image, as it's much easier to understand it animated. DanielKO 03:24, 23 October 2006 (UTC)
I suspect this is used by gdi32.dll on Windows whenever you create a poly/ellipse region and get a load of rectangular blocks back from a call to GetRegionData. Except the intersection between polygon edges and scanlines are calculated as opposed to an every-pixel colour test as per the link algorithms.
and of course to perform FillRgn, PaintRgn etc...

[edit] Bugs and optimizations

Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to the end of Q.
 4. For each element n of Q:
 5.  Set the color of n to replacement-color.
 6.  If the color of the node to the west of n is target-color, add that node to the end of Q.
     If the color of the node to the east of n is target-color, add that node to the end of Q.
     If the color of the node to the north of n is target-color, add that node to the end of Q.
     If the color of the node to the south of n is target-color, add that node to the end of Q.
 7. Continue looping until Q is exhausted.
 8. Return.

This will not work well. I have played a bit with filling algorithms on my Casio calculator which has very limited memory and CPU speed, and i can promise that under such conditions it would simply run out of stack space quickly. The reason is that it would go on visiting each node a large number of times, and add a number of nodes to the stack each time.

Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to the end of Q.
 4. For each element n of Q:
 5.  If the color of node n is target-color,
 6.   Set the color of n to replacement-color.
 7.   If the color of the node to the west of n is target-color, add that node to the end of Q.
      If the color of the node to the east of n is target-color, add that node to the end of Q.
      If the color of the node to the north of n is target-color, add that node to the end of Q.
      If the color of the node to the south of n is target-color, add that node to the end of Q.
 8. Continue looping until Q is exhausted.
 9. Return.

That one is working. But it can be more optimized. I found the following one to be much faster. It doesn't wait to color a pixel until it has been popped from the stack, but does it directly when the pixel is found. That causes the pixel to be added only ONCE to the stack, and that way it can reduce the stack space needed by "orders of magnitude". Of course, this makes the code larger.

Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to the end of Q.
 4. For each element n of Q:
 5.  If the color of the node to the west of n is target-color, set the color of that node to replacement-color and add that node to the end of Q.
     If the color of the node to the east of n is target-color, set the color of that node to replacement-color and add that node to the end of Q.
     If the color of the node to the north of n is target-color, set the color of that node to replacement-color and add that node to the end of Q.
     If the color of the node to the south of n is target-color, set the color of that node to replacement-color and add that node to the end of Q.
 6. Continue looping until Q is exhausted.
 7. Return.

-- Olle Bergkvist 81.232.34.203 (talk) 13:35, 24 February 2008 (UTC)