c# - Flood Fill Algorithms

Question

Its the weekend again, and that means I get to play with my hobby project.

I've gotten tired of creating test levels by hand, so I thought I'd take a break from engine development and work on a level editor:

Level Editor http://gfilter.net/junk/Editor.JPG

I'd like to implement a flood fill algorithm in the editor, which would work just like in a paint program. Does anyone have any pointers on what technique would work good for me here?

The level is just a 2d array, so it could be considered the same as a bitmap really.

Thanks!

Answer 1

The Wikipedia article is pretty good. As long as your grids are small, just about anything will work.

Earlier this fall I did some flood filling on 10 megapixel scanned images. (The problem was to remove black edges from book pages that had been scanned on a photocopier.) In that case there are only two colors so I essentially treated the problem like a search in an undirected graph, with each pixel connected to its neighbors along the four compass directions. I maintained a separate bitmap to keep track of which pixels had been visited.

The main findings were

• Don't try recursive depth-first search. You really want an explicit data structure.

• An auxiliary queue uses much less space than a stack. About forty times less space. In other words, prefer breadth-first search to depth-first search.

Again, these findings apply only to grids with multiple megapixels. On a nice small grid like the one shown in your question, any simple algorithm should work.