Bresenham and Line of Sight in Panzer

So you say you want to calculate line of site on a hex based digital map...

Lines are made up of individual pixels. But which pixels?

We need to know how lines are represented on a computer. Horizontal lines are obviously constructed using pixels in a single row from point A to point B. The same can be said for any vertical line... all pixels from point A to point B from a particular column are used. Diagonal lines at 45 degrees are somewhat more complicated, but if we just travel one to the right and one up, we can cobble a fairly straight-forward algorithm together to manage these 3 simple cases.

However, it's when we start to draw lines of different slopes/orientations that we need to come up with something clever to determine every pixel that a line contains. Fortunately, my detective work paid off and the case was solved. The magic bullet... the Bresenham line algorithm. I know... very exciting.

Let's back up for a second. At this point, you might be somewhat confused. Why do we need to know what pixels constitute a line on a computer?

Let's start with how I have represented the GMT Panzer map in my project. The basic game comes with a paper map. The map is divided into hexes...

Hex id 1006. Clear terrain.

I took a single hex from a digital version of the map and brought it into GIMP, which is like Adobe Photoshop. From there I used the "Line Tool" and drew lines over top of the hex borders...

Tracing the border of a hex.

Now if I remove the hex image, it will leave us with just the red line I traced...

A single side of a hex border. We can use each pixel in this line to our advantage.

It turns out that GIMP (and other programs like "Paint") uses the infamous Bresenham Line Algorithm  (or versions of it) to draw the line I just painted. Cool. Now I can trace the entire border of a single hex...

Now we can identify each pixel that is used to define the hex border.

... and manually record each pixel coordinate. This will define the border of my hex. Here's how I'm storing the hex pixel border data...

Each hex border pixel is stored as a "Point".

Let's take a closer look at the first line...

There are two points specified in this line. The first point (43, 0) is the upper left corner of our hex border. The second point (130, 0) defines the upper right corner of our hex border.

The second line is as follows...

Here we have another two points (42, 1) and (131, 1), which define the left and right border pixels one row down from the top row.

We continue to do this for each set of points in our hex borders, row by row, until we reach the bottom of our hex.

When a line is drawn on the Panzer map for line of sight purposes, we use the Bresenham Line Algorithm to determine all of the points on that line, then compare each of its pixels to see if it falls between our pixel boundaries for each row of pixels in the hex. If one of the pixels does fall within these boundaries, the hex is in our line of sight.

Pixel points of line falling inside hex border points.

Now that we have our starting hex with all of its border points established, we extrapolate out the border points for all other map hexes based on their map hex number. If we are determining the border points for hex 0210, we simply shift the left and right border points the 2 widths of a hex and shift the rows down "10" heights of a hex using multiplication. With a little trial and error, the system works!

Of course, there are some minor details that I haven't communicated, but I don't want to bore you!

Although, if I haven't already...