18

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.

enter image description here

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?

6
  • 1
    I would suspect, if the code keeps an array of endpoints for the lines forming the Qix (the X,Y for each endpoint) then you could write a fairly simple loop to test if the Qix intersects any given rectangle.
    – Geo...
    Nov 14, 2020 at 15:42
  • 1
    Re, "The game apparently choses the part that doesn't contain the Qix." Not sure why you said, "apparently." That's kind of like saying that in Tennis, the players "apparently" try to hit the ball over the net. Capturing the area that does not contain the Qix pretty much is the heart of the game. Nov 14, 2020 at 16:46
  • 1
    @SolomonSlow That's actually not completely true. In later stages of the game, there can be more than one Quix that can be separated.
    – tofro
    Nov 14, 2020 at 18:07
  • 2
    I've always wondered how the enemy moves. Literally always. From when I first saw it in the early '80s to when MAME came out, to today. Jun 3, 2021 at 2:13
  • 1
    @hippietrail In fact, I was searching for the AI in the Qix, thinking that somebody would explain it, but what I found instead is many forum questions about the flood fill algorithm. Kinda shocked, as the fill and the side of the Qix is straightforward to code with raster algorithms. Found no questions on the Qix moves... and it's challenging, it seems to be a balance between random and deliberate attack. I guess people start writing their Qix remake with the fill code, and then they didn't finish it (or made a poor AI), because otherwise the web would have tons of questions related to the AI
    – cesss
    Dec 30, 2022 at 10:58

4 Answers 4

7

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.

3
  • 1
    Flood-filling is a relatively expensive operation on an 8-bit machine. I originally suspected it's done as you say - But flood-filling the whole screen (which it effectively turns out to) would probably take in the vicinity of several seconds on most 8-bit machines. That's the main doubt behind my question. I guess there must be a "clever trick" hidden somewhere to find the side with the Quix faster.
    – tofro
    Nov 14, 2020 at 12:44
  • 3
    The "clever trick" might have been the 3 CPUs that were on the board -- scratch that - it had dual 6809s - and the 6809 is a pretty powerful 8-bit CPU.
    – LawrenceC
    Nov 14, 2020 at 17:24
  • as qix was even working on much simpler 8 bit machines the flood fill approach was not working on them. One example is the Atari VCS 5200 which houses a 6502 with 1.79 Mhz. May 26, 2021 at 15:26
3

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.

2

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.

5
  • The amount of time the game pauses seems largely independent of the amount of area being filled, which suggests to me an algorithm based upon scanning the entire screen to count how many vertical lines would get crossed by the scanning process.
    – supercat
    Nov 14, 2020 at 17:50
  • @supercat Well, to be able to fill the area that doesn't contain the Quix, You probably always need to traverse (nearly) every pixel of the screen - First, to find the area that indeed does contain the Quix, then, really filling the other one.
    – tofro
    Nov 14, 2020 at 18:11
  • @tofro: It's not necessary to traverse all of the pixels of the area containing the Qix; it would suffice to scan left from any arbitrary spot on the Qix to find the border of the enclosing area, and then use a wall-hugging algorithm to traverse that.
    – supercat
    Nov 14, 2020 at 18:16
  • 1
    "The only limit is player patience." And that limit is greatly extended by the sense of accomplishment, having just successfully claimed a large area. So the time it takes to fill it in actually enhances that reward in my experience playing it.
    – AaronD
    Nov 14, 2020 at 22:26
  • You don't have to scan for the QIX. You know where the QIX is. Any pixel checking is done during the line drawing part. Once it's complete, it's trivial to know where the QIX is and is not to decide which area to fill. Nov 14, 2020 at 22:36
2

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)

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .