Talk:Flood fill

From Wikipedia, the free encyclopedia

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

[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)

[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.

[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...