Sunday, May 13, 2012

Computing Line of Sight

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.

No comments: