Qix was a quite unique Taito arcade video game that saw ports to nearly any home computing platform of its time. At first glance, the game mechanics seem to be targeted at low-performance hardware - no need for fast pixel graphics, as the game objects consist mainly of lines, no need for many colors, as the playfield actually seems to be using 4 colours only. Using such simple graphics also doesn't ask for hardware sprite support, and the music is fairly limited.
When you look a bit deeper, however, the game algorithm that reacts on the user closing up an area with a line, seems to become a bit more tricky: What needs to happen is the game to decide whether the newly closed-up area is "left" or "right" of the line that was just drawn - this decision is apparently based on the position of the "Qix" (the conglomerate of lines that erratically moves about the screen in the non-player-occupated black areas) - the newly drawn line has divided the black area of the screen in two parts, one that does contain the Qix, and one that doesn't. The game apparently choses the part that doesn't contain the Qix as the newly-claimed screen area. (Apparently, in later stages of the game there can be more than one Qix, and "splitting the Qix", that is, there's one Qix on either side of the line, makes you automatically win the level).
There are trivial cases (like a new line dividing the screen horizontally in half) where it's dead-easy to find the area that doesn't contain he Qix. But more complicated cases apparently need a "simulated flood-fill" (probably in an off-screen buffer) to find the half of the screen where the Qix is - in order to be able to do a real flood-fill of the other area. Flood-fill is a pretty expensive operation for an 8-bit CPU.
Question: Did Qix (and its home-computer descendants) really use a flood-fill algorithm to decide the newly-claimed areas? Or did the programmers find a "better" or "simpler" method?