I just implemented field of vision (FOV) in Land of Strangers, and figured I'd share my method, as it took me a bit of brain wracking to come up with a pretty simple solution. It is also reasonably quick – badly implemented in Python and crunching on my low-end netbook, my function scans a map of 469 hexes in about 0.1 seconds. To see the actual code I came up with, download the

source code of Land of Strangers and check out the module named fov.py.

At first, I revisited my high school trigonometry. Keeping in mind that the ratio between a hexagon's height H and width W equals H/W = 2/√3, and that you can quite easily divide a hexagon in pretty chunks (see attempt at illustration below), it's not very difficult to calculate the distance and angle between two points on a hexagonal grid, using the inverse tangent. Here's some crappy ascii art to show the inner dimensions of a hexagon (or

click here for a much better image)

/\ h H = 4h

| | h W = 2w

| | h H/W=2/√3

\/ h

ww

After pondering the problem for a bit, though, I'm glad to say I didn't need to apply that knowledge. Instead, I found a pretty easy way to implement shadowcasting on a hexagonal grid. Basically, you start at the center and spiral outwards, covering one ring of hexes for each iteration of the shadowcasting routine. The innermost ring (first iteration) consists of the 6 hexagons directly adjacent to the center, the second ring/iteration touches 12 hexagons, the next ring 18 hexes, then 24, 30, 36, etc. for as long as you want to go. Tracing the spiral is pretty trivial, so I'll leave that up to you. Here's to illustrate the kind of spiral I'm talking about:

`. . . . . . . .`

. . J 8 9 . .

. . I 7 2 A . .

. H 6 1 3 B . .

. . G 5 4 C . .

. . F E D . . .

. . . . . . . .

It may be obvious to brighter minds than my own, but it took me days to consider that since a perfect circle always maps 360°, it's trivial to know that in the first iteration (hexes 2-7), consisting of 6 hexes, each hex spans 360°/6=60°; in the second iteration that is narrowed down to 360°/12=30°, in the third iteration 360°/18=20°, and so forth. The minimum and maximum angles of hex number H of iteration number N thus equals:

min_angle=(H-1)*(360 / (6*N))

max_angle=min_angle+(360 / (6*N))

For odd numbered iterations, we need to subtract (360 / (3*N)) from these numbers.

At this point, implementing shadowcasting on the grid is really easy. Here are the basic steps I took:

In preparation, make two empty lists: One to add hexes that are seen, and one to keep track of shadows that have been cast. The entries we put in this shadow list should be pairs of digits, where the first digit signifies the minimum angle of a cast shadow, and the second digit the maximum angle. Eg. if the very first hex (right NE from the viewer) casts a shadow, that shadow would be signified as a (0,60) entry in the list.

Now, loop through every hex of every iteration, doing the following:

1. Test the hex' min/max angles against existing shadows: If it falls within any shadow (the hex' min_angle is higher than the min_angle of the shadow AND the hex' max_angle is lower than the max_angle of the shadow), that hex is out of view.

2. If the hex is not shaded, add it to the list of visible hexes.

3. If the hex blocks view, add a new shadow with that hex' (min_angle,max_angle) in the list of shadows cast.

3b. If the new shadow overlaps an existing shadow, it's pertinent to merge the two into one, spanning from the lowest min_angle of the two shadows, to the highest max_angle.

Whenever you come to a hex where the min_angle is less than 0 or the max_angle is higher than 360, you need to make the program understand what's going on. For my part, I simply split such angles in two. For instance, to test the first hex of the second iteration, spanning (-15°,15°), I'd test to see if (345,360) is shaded AND (0,15) is shaded. If both are true, it follows that the hex is shaded. Likewise, to cast a shadow from that hex, I'd split it in two entries – (345,360) and (0,15) – to put in the list of shadows cast.

To optimize further, you can automatically skip over hexes that are necessarily shaded. If the algorithm just stated that the hex spanning (0,20) is out of view because of a shadow spanning (0,180), you can really just autoshade the next 5 hexes and test again for the hex spanning (180,200).

Depending on how you do your calculations, some shades may not merge properly, for instance if you're ending up with digits like 79.999. An ugly, effective way to deal with this is to enlarge every shadow by half a degree on both sides, to make sure everything overlaps nicely. A more elegant solution would be to use fractions, but at least in Python, that makes calculations ten times as slow. Sometimes the ugly kludges are better

As always,

Minotauros