|Flood Filling - Language inspecific
Date: 07 October, 2011, 05:14:30
|Summary: This is a simple, but effective way to flood fill
If you don't like the methods over at wikipedia on flood filling, that's ok, because I didn't either. So here is my way to flood fill something. In comparison to the other methods, I believe I thrown away memory for speed and simplicity, but since the calculator screen isn't that big, it's not a huge deal.
This method should work for really any language. You could even do it in BASIC if you wanted to.
1. Create a buffer that is the same size (in pixels) as the screen you are about to flood fill.
2. Clear out the whole buffer with 00's.
3. Mark any spaces that are elgible to be filled (i.e. empty) with a 01 in this new buffer.
4. Mark the point where the flood fill was issued with a 02.
This part is a loop:
5. Search your buffer for a 02.
6. When you find one, take a look at the 4 spaces around it (or less if you're on an edge.) If the space contains a 01, change it to a 02. If it contains anything else, ignore it.
7. Mark this pixel with a 03
8. Restart this loop
The loop will stop when you run out of 02's
9. Take all of the 03's in your buffer and translate them over to filled in pixels on your screen.
The one obvious drawback with this technique is that if you are rendering a full screen image (on a calculator), that is 6,144 pixels, which means 6,144 bytes. While you could certainly achieve this with an appVar, you can actually use 1/4 of this. That's because since the only numbers involved are 0-3, you can store 4 pixels to a byte. This means you only need 1,536 bytes, which you can certainly scrap if need be.
On the other end of the spectrum, for those who want to sacrifice even more space for speed and ease of coding, there is an option. The idea to making this routine easier is to eliminate edge checking, which can seriously slow down your routine. The fix for this is to add padding to all 4 sides of your buffer so that even when you do reach the edge, you can evaluate all 4 pixels without worrying about corrupting anything. The way to pull this off is to make your buffer 1 pixel wider and 2 pixels taller. The 1 pixel wider actually catches run-off from both sides. The most important part to using this method though is to ignore those extra rows, if you evaluate them, they aren't run-off buffers anymore.
Lastly, this routine can be used for things besides flood filling. Let's say you have a puzzle game with bombs: When you set off a bomb, you can essentially say that you are going to flood fill the screen with explosions. So you do that, and then when you are done, just clear out all of the spaces that have been destroyed by the explosions. In this case, it would probably make sense to check the 8 surrounding squares rather than the 4 surrounding squares, but with this setup, that makes close to no difference code-wise.
With that, you can flood fill. It might not be the most optimized or the fastest, but it's pretty easy to under stand, and it always works.