Did they have to treat pixels like rocks on the beach, pick each one up, paint it, put it down, then move to the next one?
I'm talking about the days before vector extensions.
Honeywell machines had cool hardware that would increment a loop index in the same cycle it executed an instruction, but the 8088 didn't even have that.
The basic way to do flood fill worked something like this:
On the CGA, this is simple, because all of a pixel is in a single byte, and you may have several pixels in a byte.
On the EGA and VGA, it's a bit more complicated, because of the separate colour planes. It might be worth reading a whole scan line into RAM at once so that you can work on it quickly. Writing is easier, because you can write to several colour planes with one CPU write.
I've never implemented flood-fill on a PC, although I did it on the BBC Micro. That had some OS primitives for implementing flood-fill, and I was able to make it quite fast in a BBC BASIC program. In contrast, the Computer Concepts Advanced Graphics ROM for the same machine was almost slow enough to see individual pixels being processed. I still don't know how they made it so slow.
(Possibly off-topic, since this is not specifically about an 8088 implementation, but perhaps of interest.)
A piece of software called The Graphics Magician, by Penguin Software, was used to create the graphics on a number of old adventure games. It used lines, pre-defined brushes, and flood-fill to paint the screens in games like Transylvania. The games were ported to multiple platforms.
The manual described the algorithm they used for the flood fill:
The interesting bit is in step 3. Shifting the center allowed the flood fill to handle some concave shapes in a single operation. For example, imagine a crescent moon shaped like a parenthesis. If you start at the top, the center point would swerve around the inside as the algorithm moved downward.
(You can find a disassembly of the Apple II hi-res graphics version here, but the memory layout for that graphics mode is... unique.)
The adventure-game algorithms prized speed over thoroughness. If you want something that flows around corners, you'll need something that uses more memory and time. For example, this video of Micro-Painter demonstrates what someone once referred to as a "screen etcher". The code does essentially what is described in @tofro's answer here, probing each pixel and adding neighbors to a work list.
More or less like that:
void fill (x, y, col) {
setPixel (x, y, col)
if (getPixel (x + 1, y) != col then fill (x + 1, y, col);
if (getPixel (x, y + 1) != col then fill (x, y + 1, col);
if (getPixel (x - 1, y) != col then fill (x - 1, y, col);
if (getPixel (x, y - 1) != col then fill (x, y - 1, col);
}
Flood fill is an inherently recursive activity. (Too) simple implementations can easily run into a stack overflow (the real thing, not the web site ;)) More sophisticated implementations wouldn't use the CPU stack, but a separately allocated one to be able to observe memory usage and avoid that. With some more code invested, you can improve the algorithm to make sure every pixel is only visited once.
Note the getPixel() and putPixel() complexity stands and falls with the hardware implementation of the frame buffer. Implementations that use separate bit planes/color can make the code pretty expensive, while hardware implementations that use one byte (or one word) per pixel make for a much faster implementation.
pcmpgtborpcmpeqbandpmovmskb eax, xmm0/test eax,eax/jnz any_matches, and maybe bit-scan the integer bitmap of element matches. Horizontally within a line, you want to search for a start point (probably starting near the start column of the previous line, so maybe only a couple vectors). And find an end point, either as you go reading + filling, or find then start+end with scalar then basically SIMD memset vs.rep stosd.