Home Projects Resources About Articles Resume


The Scanline Flood Fill Algorithm (under construction)

Flood fill is an algorithm most commonly seen in the paint bucket tool in Microsoft Paint. It can also be used to create a 'fuzzy selection'/'magic wand' kind of tool. In the first case, we are overwriting data. In the second case, we are collecting the data. There are several ways to implement a flood fill. We will be covering the scanline flood fill algorithm. The scanline algorithm is the fastest, though a little more difficult to implement compared to more intuitive techniques. The Wikipedia article explains a lot about flood fill algorithms, and is worth a read. This article follows on by explaining how to get the algorithm working in your game.

...

The above image is an example of the ubiquitous paint bucket tool. The inner shape has been filled with purple. We can see that this particular algorithm does not fill through diagonal pixels.

FUZZY SELECT

The paint bucket tool isn't the only such use of the algorithm. One other use for the flood fill algorithm is determining areas. For example, in a map which is divided into water and land, you can use flood fill to find the seperate landmasses. This can be used for several things... You can use the result to quickly determine if a unit may travel to a particular tile. This can simplify pathfinding, by telling us quickly if a path may be calculated between two points.

The basic principle behind the flood fill is to start at the chosen pixel, and go left until an obstacle is reached, filling each pixel, and simultaneously checking the above and below pixels to see if they should be checked in the next pass. Once an obstacle is reached, then the algorithm goes right along the horizontal line until it hits another obstacle. At this point it moves onto the next line, starting at the next tile to be checked. It is critical to understand the special criteria required for a tile to be checked in the next pass.

The flood fill can be further broken down into 2 types:

The most common type is to write the fill values directly into the array you are checking. This is the traditional 'paint bucket fill'.

The second use for this algorithm is to select a particular area. In this case, the fill algorithm can be used as a kind of 'fuzzy select' tool.