11

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?

3
  • 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 '20 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. – Solomon Slow Nov 14 '20 at 16:46
  • @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 '20 at 18:07
5

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.

2
  • 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 '20 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 '20 at 17:24
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.

1

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 '20 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 '20 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 '20 at 18:16
  • "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 '20 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. – Will Hartung Nov 14 '20 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.