Lines of Sight (LOS)

To make all this work, I needed to trace clean lines of sight. This, it turns out, was no simple matter. Be warned: The next few pages are tediously technical. If you want to avoid the gory technical details, skip ahead to the line that says, “If you're a non-technical reader, you can resume reading now.”

Still with me? Good for you! Now, those simple 8-bit processors had no hardware multiply/divide capabilities. All calculations were carried out with 8-bit addition and subtraction. How can a program trace a straight line from point (x1, y1) to point (x2, y2) without any concept of slope (ΔY divided by ΔX)?

I couldn't just cram a software multiply/divide library into the game: There wasn't enough ROM. I needed a fast algorithm that required little ROM or RAM. It was precisely this difficulty that forced all shooting games on the VCS to use simple angles for shots: horizontal, vertical, or 45-degree diagonals. A few of the snazzier games also handled 30-degree and 60-degree shots because they had slopes that were simple 2:1 ratios. But a general-purpose line calculator? That seemed impossible.

Such an algorithm had already been invented, but I was too unschooled to know of it; I had to re-invent this wheel. As it happens, the route I followed to do so provides an interesting tale. After many long walks in the parking lot, trying to figure out a solution, it one day dawned on me that the Maya Indians had faced the same problem in designing their calendar. The critical task facing any calendar maker is the determination of the exact length of the year, which is approximately 365.24220 days. Unfortunately, the Maya did not have the concept of decimals in their mathematics, nor did they have fractions, so they had no way to express this number. They knew that the length of the year was a bit more than 365 days and decidedly less than 366 days, but that was as far as their mathematics could take them. Until one day when some Maya genius came up with a way to express it: There are 1461 days in four years (1461 divided by 4 is 365.25). With further refinement, they were able to figure out that there are 14,975 days in 41 years, and so on. This system allows you to express ratios with as much resolution as you require, and permits running calculations of slope using just integers.

Here's how my algorithm worked: Let's say that we want to trace the LOS (which is exactly the same as the path of a bullet) from the player at (20,30) to the monster at (30,57). ΔX is 10 and ΔY is 27. Now we carry out a brute force division of 27 by 10; to do this, we subtract 10 from 27 until the remainder is less than 10. This happens just twice, so we conclude that the slope is at least 2; the next higher integer is 3, so the true value of the slope is between 2 and 3. Our basic algorithm, then, will be to sometimes take a jump of 3 steps in Y for every one step in X, and other times take a jump of 2 steps in Y for every one step in X. The problem is to figure out when to take which jump. (See Figure 15.3).

We have to start somewhere, so we'll pick one of the two jumps. Since the remainder of the previous division was more than half of the divisor (27 mod 10 gives 7, which is more than 5), we'll start with the bigger 3:1 jump rather than the smaller 2:1 jump.

So we take three steps in Y followed by one step in X. Our bullet moves along the path (20,30); (20,31); (20,32); (20,33); (21,33). Our cumulative path so far has taken us 3 steps in Y and 1 step in X; these cumulative values will become important soon.

Now we must decide whether to make a 3:1 jump or a 2:1 jump. If it were 2:1, then we would have a cumulative motion in Y of 5 and a cumulative motion in X of 2; if instead we take a 3:1 jump, then the cumulative ΔY will be 6 and the cumulative ΔX will be 2. Now, the temptation here is to calculate slopes of the two possible lines, but we can't do that because we don't have fractional division. Instead of dividing down to small values that will be fractions, we will multiply up to large values that will be integers. So let's extrapolate our values upward. How far must we go? We will simply ask, how many cumulative ΔX's are there in the final ΔX; that's how far we must extrapolate our ΔY. So, with each jump, the cumulative ΔX will be 2. There are five 2's (the cumulative ΔX) in 10 (the final ΔX), so we want to see how five cumulative ΔY's compare with the final ΔY. The big jump would yield a cumulative ΔY of 6, while the shorter jump would yield a cumulative ΔY of 5. Multiplying these two values by 5 yields 30 and 25, respectively. Which is closer to 27? The value coming from the shorter jump, so that's the jump we want to take this time.

Now we repeat the process. Unfortunately, we encounter a problem here: We can't extrapolate our Δ values with integers. Our ΔX values will each be 3, and 3 does not divide integrally into 10. Put in mathematical terms, 10 modulo 3 is nonzero. What now?

The solution relies on the fact that, of the two possible jumps (3:1 or 2:1), the 3:1 jump is the “majority” jump—we know from the final ΔY:ΔX that the 3:1 jump will be taken more often. Therefore, a close approximation is to use that jump to fill in remainders. Here's how it works: We go ahead and divide 10 by 3 to get 3, but we make a note of the remainder of 1. Then we extrapolate each of our cumulative ΔY's by three, and then we add one more majority jump to each ratio, to account for the remainder. Here's the calculation:

• 3:1 cumulative ΔY:ΔY is 8:3.

• 2:1 cumulative ΔY:ΔX is 7:3.

• Multiply 3:1 cumulative ΔY:ΔX to get 24:9.

• Multiply 2:1 cumulative ΔY:ΔX to get 21:9.

• Add one 3:1 jump to 3:1 cumulative ΔY:ΔX to get 27:10.

• Add one 3:1 jump to 2:1 cumulative ΔY:ΔX to get 24:10.

Aha! The 3:1 jump gets us closer to the correct 27:10 value; that's our choice. We then continue this process all the way along the line,

Here's a table showing the calculations for each jump. I used an alternating choice when the two choices were equally close to the ideal value of 27.

(The algorithm I actually used was a bit more complicated and efficient than this one, but I figured that this example was befuddling enough, so I kept it simple.)

In this way I was able to calculate either the trajectories of bullets or the LOS. Of course, to calculate the LOS, you must determine whether it intersects any solid objects, in which case it is blocked. Here I pulled a simple trick: The TIA chip also provided collision detection between moving objects and playfield (collision detection tells you when one graphical object is superposed over another), so I simply ran a bullet from the monster to the player and checked collision detection to see if the LOS was blocked. In other words, the LOS was checked by shooting invisible, harmless bullets from the monster to the player; if there was no collision detection, then the LOS was good and the next bullet was for real.

If you're a non-technical reader, you can resume reading now. For the player graphics, I used a simple stick man whose legs wiggled about as he moved. For the monster, I used a rotating spiral; along with the thump-dump, thump-dump of its heart, it was robustly creepy.

Somewhere along the way, I decided to add a topic to the game. All along, I had simply followed the logic of game. From the starting point of hidden players, everything else flowed naturally. But having concocted this screwball situation, I needed some plausible context. What the hell, I decided, it might as well be a wizard fighting a monster; after all, wizards can do anything. The wizard's bullet became a fireball; the maze became a dungeon, and poof, that was all there was to it.