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