Simple FOV on a hexagonal grid

[AgingMinotaur]

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)

Code: [Select]


 /\  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:

Code: [Select]

. . . . . . . .
 . . 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

[owen]

Just bumping this to say that using the approximation that each hexagon in a ring subtends an equal arc of the circle seems to work out reasonably well.  Here's an example of what my FOV effect looks like.  Note that I'm using a flat-topped hexagonal grid instead of pointy tops like you are.





My algorithm works in basically the same way:

1.  Start with one large view arc that is defined by a minangle and maxangle.

2.  For each ring of hexagons (expanding outward from the origin tile), For each view arc remaining:

2a.  Add all the hexagons in the arc to the viewable list

2b. If an opaque hexagon(s) subtends the angle of one arm of the viewing arc, then shrink the view arc from that side.  If the view arc is shrunk so that either both arms hit the same opaque hex, or the view arc is sufficiently narrow, then cull the view arc.

2c.  If an opaque hexagon(s) falls in the middle of the view arc, then split the view arc into two smaller arcs around the opaque hexagon(s).

3.  Keep doing this until you hit the maximum view-radius or you run out of view arcs.  Return the list of viewable tiles.

[abraksil]

Cool! Thx for sharing!

[owen]

Another approach.  Described here: https://www.reddit.com/r/roguelikedev/comments/4ezjq3/sharing_saturday_98/d273ir1

https://vid.me/Cdn9

[Tilded]

Here's my approach described on reddit. And here's the corresponding code:

Code: [Select]

const xDir = [0, 1, 1, 0,-1,-1];
const yDir = [1, 0,-1,-1, 0, 1];

// displacement vector for moving tangent to a circle counterclockwise in a certain sector
const tangent = [
    [ 0,-1],//  \
    [-1, 0],//  -
    [-1, 1],//  /
    [ 0, 1],//  \
    [ 1, 0],//  -
    [ 1,-1],//  /
    [ 0,-1],//  \
];

// displacement vector for moving normal to a circle outward in a certain sector
const normal = [
    [ 1, 0],// -
    [ 1,-1],// /
    [ 0,-1],// \
    [-1, 0],// -
    [-1, 1],// /
    [ 0, 1],// \
    [ 1, 0],// -
];

// round a number, but round down if it ends in .5
const roundTieDown = n => Math.ceil(n - 0.5);

const fov = (ox, oy, transparent, reveal) => {
    reveal(ox, oy);

    const revealWall = (x, y) => {
        if (!transparent(x, y)) {
            reveal(x, y);
        }
    };

    for (let i = 0; i < 6; i++) {
        revealWall(ox + normal[i][0], oy + normal[i][1]);
    }

    const polar2rect = (radius, angle) => {
        const sector = Math.floor(angle);
        const arc = roundTieDown((angle - sector) * (radius - 0.5));
        return [
            ox + radius * normal[sector][0] + arc * tangent[sector][0],
            oy + radius * normal[sector][1] + arc * tangent[sector][1],
            radius * sector + arc,
        ];
    };

    // angles are measured from 0 to 6
    // radius - radius of arc
    // start & end - angles for start and end of arc
    const scan = (radius, start, end) => {
        let someRevealed = false;
        let [x, y, arc] = polar2rect(radius, start);
        let current = start;
        while (current < end) {
            if (transparent(x, y)) {
                current = arc / radius;
                if (current >= start && current <= end) {
                    reveal(x, y);
                    someRevealed = true;
                    if (current >= 0 && current <= 2) { revealWall(x + 1, y - 1); }
                    if (current >= 1 && current <= 3) { revealWall(x    , y - 1); }
                    if (current >= 2 && current <= 4) { revealWall(x - 1, y    ); }
                    if (current >= 3 && current <= 5) { revealWall(x - 1, y + 1); }
                    if (current >= 4 && current <= 6) { revealWall(x    , y + 1); }
                    if (current <= 1 || current >= 5) { revealWall(x + 1, y    ); }
                }
            } else {
                current = (arc + 0.5) / radius;
                if (someRevealed) {
                    scan(radius + 1, start, (arc - 0.5) / radius);
                }
                start = current;
            }
            // increment everything
            const displacement = tangent[Math.floor(arc / radius)];
            x += displacement[0];
            y += displacement[1];
            arc++;
        }
        if (someRevealed) {
            scan(radius + 1, start, end);
        }
    }
    scan(1, 0, 6);
};