Interfaces and Flood Fill

I create a lot of throwaway mini-libraries while researching various ideas or experimenting with different designs.

Yesterday I mentioned code that could treat bitmaps and game map layers as the structurally equivalent entities they were, and so allow algorithms such as flood fill to be reused when dealing with either. To help proof this concept, and others, I've created a little helper library named Mu.

If you have the Java SDK installed (1.5 or greater-- I do my tinkering with 1.6) and Eclipse (I use 3.1,) you can open up Mu and this Flood Filler Example as projects and be ready to rock. These files and others will be available through SVN once my host and I learn to communicate better.

The above example is the first half of the proof, and works with a bitmap. It loads a ridiculously large image with a complex outline and then fills that outline. I will put up the second half of the proof tomorrow, which will use the same code to perform the same operation on a VERGE 3 map.

You'll notice the mu.* package is chalk full of nothing but interfaces. Head First Design Patterns stresses "programming to interfaces" instead of concrete classes, and I'm basically running with that idea.

The book mentions how programmers new to design patterns will often go to extremes, looking for any excuse to implement patterns, rather than relying on experience to indicate why a given pattern may fit well within a given context. I am certainly one of these newbies, and so my use of interfaces here is indicative of my general approach to learning-- the brute force method. I'll use them until I discover reasons not to.

I'll cover the reasoning behind the MuSet and MuMap interfaces in another post under a more suitable category, but a MuSet is a list, and a MuMap is a grid. A MuBitmap is a "grid of colors," as is indicated by its extension of MuMap<MuColor>.

The flood filling algorithm operates on a MuMap object:

void fill(MuMap<E> map, E next, int x, int y);

Because of this, any class which implements MuMap is fair game!

For those of you interested in tweaking algorithms for speed, and also partly to help illustrate how interfaces can provide a highly extensible framework, I have created two implementations of the flood fill algorithm: MuFloodFillerImpl and MuFloodFillerScanlineImpl. They both implement the MuFloodFiller interface, and you can easily examine the difference in speed by changing the following line:

MuFloodFiller<MuColor> ff = ...
new MuFloodFillerImpl<MuColor>();

to this:

MuFloodFiller<MuColor> ff = ...
new MuFloodFillerScanlineImpl<MuColor>();

They are both iterative incarnations.The simplicity of recursive varieties is appealing to me for clarity's sake, but runtime stack exhaustion would be imminent for all of my intended purposes. That is, filling regions in potentially large maps, as well as some other image-based uses I have in mind.

The scanline version is more savvy about filling columns as it goes, and is some 3x faster than the basic filler.

Both algorithms were adapted from code in Lode's Computer Graphics Tutorial on flood fill-- very "clean" and easy to understand algorithms. Plus he's from the old school! There are tutorials on demoscene effects and other nifty stuff there. You should check the site out if you're a former demoscene wannabe like I am.