In some hex-based boardgames it is necessary to determine if a clear line of sight exists between a firing unit and the target unit. This can be done easily enough in a tabletop game by a simple rule to examine the hexes along an imaginary line from the center of one hex to the center of another. This is not so easily done in a computer boardgame. This post outlines a method for determining line of sight in a hex-based computer game.
Consider a map image. It consists of pixels that form an x/y Cartesian coordinate system. Overlaid on the map image is a hexagon grid.
Assume that we know the pixel coordinates of the center of each hexagon. Assume further that we have a firing unit at hex 1 with pixel x/y center at x1,y1 and a target hex 2 with center at x2,y2.
We want to "draw" a line from x1,y1 to x2,y2 and determine of a hex center x0,y0 is within d pixels of the line. If it is, then we can say that the hex at x0,y0 is in the line of sight between the firing and target hexes.
Given a point and a slope, a line is given by the equation
(1) y-y1=m*(x-x1), where m is the slope of the line.
Given two points, the slope, m, of the line that goes through each point is
(2) m = y2-y1/x2-x1.
Subsituting (2) into (1), we have
(3) y - y1 = (y2-y1/x2-x1) * (x-x1) or
(4) (x2-x1)*y + (y1-y2)*x + (y2*x1-y1*x2) = 0.
A line is expressed by ax + by + c = 0. From (4), we have
a = y1 - y2
b = x2 - x1
c = y2*x1 - y1*x2.
Now the distance, D, from a point x0,y0 to a line ax + by + c = 0 is given by the equation
D = ABS(a*x0 + b*y0 + c) / SQRT(a*a + b*b).
For each hex center point x0,y0 on our map image, compute a value of D. If D < d the hex center is within d pixels of the line between x1,y2 and x2,y2 and can be said to be in the line of sight between hex 1 and hex 2.