Calculating Line of Sight

The next problem was figuring the line of sight through a hexgrid. Imagine the situation: Tank #1 is at coordinates C4 and Tank #2 is at F9. Can Tank #1 see Tank #2? To put it in more computationally rigorous terms, can Tank #1 trace an unblocked line of sight to Tank #2? See Figure 13.2.

13.2. Determining line of sight (LOS).

The solution to this problem turns out to be rather complicated and mathematical, so I will not delve into its gory details. The problem was exacerbated by the requirement to operate in an 8-bit CPU with no hardware multiplication or division; everything had to be done with logical operations and simple addition and subtraction of 8-bit integers. It happens that computer scientists had solved a similar problem years before, but I, having no training in computer science, simply had to re-invent this wheel for myself. Sad to say, the solution was not discovered by game programmers for quite a few years after me. Roger Keating in Australia discovered it not long after I did, but there were plenty of wargames as late as 1982 whose designers still hadn't cracked the problem. Nowadays, with floating-point hardware multiply-divide capabilities, this kind of problem is so simple that it's silly to discuss, but back in the 1970s, this was a serious challenge.