How was the main mechanic of the game Qix implemented?

Question

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?

Answer 1

I believe many versions of Qix did a flood-fill on both sides of the line, then observed which one hit the Qix itself and "activated" the other one. There are flood-fill algorithms that are quite efficient for the relatively large, open, geometric areas that usually result from gameplay.

A modern approach would probably use a path-based scanline-fill algorithm, using the boundary of the open playfield and the newly drawn line. The origin and termination of the new line would become split points on the boundary path, dividing that into left and right halves, and then forward and reverse copies of the new line would be inserted into these to form closed polygons. Scanline fill only requires looking for vertical segments of these polygons; after crossing an odd number you are inside the polygon, and after crossing an even number you are outside it.

Answer 2

I don't know how the algorithm works, but I can describe an algorithm which is consistent with the behavior I've observed.

The marker moves multiple pixels at a time. This means that rows and columns can be divided into those that the marker can occupy and those which it cannot. Software need only concern itself with pixels that are on columns the marker can occupy but rows that it cannot, or rows the marker can occupy but columns it cannot (each group of consecutive rows or columns the marker can't occupy can be treated as a single row or column). Each such "pixel" would need two bits to distinguish whether it is:

1. On the path the player drew
2. On the portion of the boundary of the area occupied by the Qix
3. On a portion of the boundary that is confirmed to surround the Qix
4. None of the above.

Once the player completes a path, the system should scan leftward from the Qix until it hits either the player's path or the boundary. It should then proceed upward around the new boundary while hugging the left wall, marking as "confirmed" any portions of the boundary which it traverses, until it encounters a pixel that is on the portion of the path which has been confirmed to surround the Qix (which would only happen after it has made a complete circuit).

Once scanning has made a complete circuit, software should proceed through all of the rows where the marker can't move. Scan each row left to right and toggle the "painting" state every time one encounters a pixel which the player drew, or that was on the boundary but does not surround the Qix.

The scenario where the player splits the two Qix could be detected by running the above scanning algorithm for the first Qix, and then starting it for the second but stopping as soon as code encounters a pixel on the old boundary. If that pixel is on the path surrounding the first Qix, both are surrounded by that path. Otherwise, the Qix were split.

Answer 3

I can't say, I didn't write it, and I haven't seen the game in some time.

But the fill is pretty simple as I recall.

Remember, that the boundary that is drawn does not have to be square, or a straight line, or anything. You press the button and leave the border, and then you can draw a shape of arbitrary complexity (you just can't cross over yourself, and, of course, there's no curves, just straight lines).

Once that's done, you have a well defined polygon, and you can quickly iterate from top to bottom, creating a list of line segments to fill.

You can do a simple ray casting technique, for example. The play field is broken up in to horizontal chunks by the lines of the pattern. Those "in" the polygon, and those "out" of the polygon. Once you've determined "in" vs "out", you can easily skip to each point. Just run down the list, toggling "in" and "out" as you encounter each line.

Once that's done, you have your list of lines to paint to fill the zone, and that can be done howere you like.

The trivial flood fill algorithm is a recursive algorithm, and certainly does not look like what QIX does when rendered. You start at a point, "fill the point", then fill its neighbors by calling flood fill again with each point.

It's expensive because of all the recursion and call over head, and it does not look at all like QIX, which paints from the top down.

And you'll notice during the game (if I recall), that the game halts (even the QIX stops) during the fill. So big fills cause a big pause to the game while it resets the play field. In that sense the fill only has to be "fast enough" without any hard real time limits to keep up with the game play. The only limit is player patience.

Answer 4

I think it is done purely geometrically(the polygon representation is only used for the filling, not for other parts of the game and will be constructed in the delay before the fill starts):

1. When player closes a path the old playfield is split into 2 Polygons consisting of horizontal and vertical lines
2. With a very easy point-in-polygon check you are able to see in what polygon the qix resides
3. you fill the other polygon

A small python snippet to illustrate:

# 1st: split playfield
poly1, poly2 = split_polygon(playfield, players_path)
# 2nd: check which poly is new playfield(the one with the qix inside)
if is_inside(poly1, qix_coords):
    playfield = poly1
    split_poly = poly2
else:
    playfield = poly2
    split_poly = poly1

The easy point-in-polygon check:

1. cast a vertical line from a point outside of the polygon to the position of the qix (for example line from (qx,0) to (qx,qy) with qx/qy coordinate of the qix)
2. count the intersections with the horizontal lines. This is a simple smaller/greater comparison for each horizontal line segment.
3. If the number of intersections is even, the qix is outside the polygon, if it is odd, the qix is inside (you could even use a single bit which you toggle on each intersection)