Articles

It’s been a long programming day, so I’m in a bit of a technical mood. I’ve gotten several questions regarding the line of sight article, so I wanted to take a moment to elaborate a bit more on the math. Hopefully this will clear things up.

As I had discussed on the article, I’m using a hex grid that is rotated 90 degrees from the usual wargamer style. Its coordinate system looks like this:

When we lay hexes out in this manner, their position is not like if we were to lay a square grid – there is a displacement that is not the same as the hex side.

We can calculate this displacement based on the hex center (the almost invisible center dots in this image):

We can do this because each hexagon can be segmented into six equilateral triangles. Assuming a hex’s side length measures d units, then the hex’s center point will also be d units from any of its corners.

Knowing that, we can calculate how many units we need to move vertically for the next hex on the grid. Does this look familiar?

We know that vertical line towards the center of the hex intersects the diagonal from the vertex, which measures d. We also know that since it’s right at the center, the measure c at the bottom equals d / 2. We can therefore calculate that height trivially by using the Pythagorean theorem:

h^2 + dˆ2 / 4 = dˆ2

h^2 = d^2 – d^2/4

h^2 = d^2 * (1 – 1/4)

h = d * sqrt (0.75)

So each hex’s center is (d * sqrt (0.75) * 2) units above the previous one.

Now, suppose we were to subdivide these hexagons once into triangles. We would end up with a segmentation that looks like this:

We can number these triangles using a coordinate system as well. This is what I described on my original article as

“If we renumber these triangles according to a left-right, bottom-top sequence”

They would end up looking like this:

Notice that the coordinates would include triangles that are not contained in any of the hexagons. This is something we need to account for later on.

Suppose that we place an imaginary dot at the center of the vertical line bisecting each triangle. The collection of these imaginary dots would form a perfect grid, which is the one that we would traverse using Bresenham’s.

Once you have the list of points covered by a line, you only need to keep in mind that these are not triangle but hex coordinates. You would then apply calculation to find out which hexagon each point belongs to (accounting for empty triangles), which is trivial as the number of both vertical and horizontal triangles per hex is known, and that will give you the hexagons in your line of sight.

Notice that the hexagon and triangle distance calculations are relevant mostly if we care about finding out a line of sight from a particular world space, and not only from a specific hexagon to another.  If that’s all you care about, your calculations are reduced to the hexagon subdivision.

You say Bresenham’s line algorithm is easy to apply to triangles but I’m not so sure. Triangles are not square and these are 60 degrees so cant be converted into squares.