HEX GRIDS
---------
Copyright (c) Clark Verbrugge, 1997. [clump@cs.mcgill.ca]
Copyright (c) Clark Verbrugge, 1996.
This article may be freely distributed as long as this attribution is
included.
This is version 3 of this document.
Contents:
(0) Version History
(1) The Hexagonal Coordinate System
(2) Distance in Hexspace
(3) Line of Sight (LOS) in Hexspace
(4) How to Use Rectangular Arrays of Hexagons
(5) Distance and LOS in a Rectangular Array of Hexagons
(6) LOS by Intersection of Hexagons with a Straight Line
(7) Euclidean Field of View (FOV) on a Hexagonal Grid
(8) References
(0) Version History
-------------------
3 : Added this section, and sections on FOV and LOS by intersection
2.1: Fixed bug in Floor2 and Ceil2, which gave wrong values
for negative inputs.
2 : Addition of material dealing with rectangular patches of hexagons.
(1) The Hexagonal Coordinate System
-----------------------------------
Here's a hexagonal grid with a coordinate system mapped to square grids.
Note that this is just one possible orientation of the hexagons---if
you change it so hexes are adjacent horizontally instead of vertically,
you get a symmetric situation (the details of which i'm sure you can
work out; essentially, in (1) and (2) below, the "==" changes to a "!=").
__ 5
__/D \__ 4
__/ \__/ \__ 3 "Y" coord
__/ \__/ \__/ \__ 2
__/A \__/ \__/ \__/ \__ 1
__/ \__/ \__/E \__/B \__/ \__ 0
/ \__/G \__/ \__/ \__/F \__/C \
\__/ \__/ \__/ \__/ \__/ \__/
\__/ \__/ \__/ \__/ \__/ 5
\__/ \__/ \__/ \__/ 4
\__/ \__/ \__/ 3
\__/ \__/ 2 "X" coord
\__/ 1
0
Unlike the obvious route, these coordinates are not orthogonal---that
is, the y-coord increases to the upper-left, and the x-coord increases
to the upper-right. This means "A" has coords (2,5), B is (4,2),
C = (5,0), D = (5,5), E = (3,3), F = (4,1) and G = (1,4).
This also means that a "square" in this coordinate system is more of
a diamond shape (as you can tell from the 6x6 "square" shown above).
Circles, however, are reasonably circular.
(2) Distance in Hexspace
------------------------
Distance between points A and B is given by:
dx = B.x - A.x;
dy = B.y - A.y;
if (sign(dx) == sign(dy)) { // this is (1); see first paragraph
dist = max(abs(dx),abs(dy));
} else {
dist = abs(dx) + abs(dy);
}
This is a distance metric in the technical sense.
So, for instance, the distance between A and B is given by:
dx = 4 - 2 = 2;
dy = 2 - 5 = -3;
since sign(dx) != sign(dy),
dist = abs(2) + abs(-3) = 5;
(3) Line of Sight (LOS) in Hexspace
-----------------------------------
How do you compute line-of-sight? You use a simple modification of
Bresenham's line algorithm. Here's a schematic version which calls
the function "process()" for each coord in the line from A to B.
Note that there's a choice in the horizontal move of whether to
increment x, process, then y, or to increment y, process, then x.
// assume abs(dx) >= abs(dy), it's symmetric otherwise
int sig,dx,dy,factor,x,y,xone,yone;
// this is (2); the next line changes from "==" to "!=" if
// hexagons are not stacked vertically (see first paragraph)
sig = (sign(dx) == sign(dy));
if(dx<0) xone = -1; else xone = 1; // unit increments
if(dy<0) yone = -1; else yone = 1; // unit increments
if (dx % 2) { // so dx is divisible by two
dx *= 2;
dy *= 2;
}
dx = abs(dx); dy = abs(dy); // don't need the signs anymore
factor = dx/2; // should start at 0.5, which is just (dx/2)/dx
x = A.x; y = A.y;
process(x,y);
while (x != B.x || y != B.y) {
factor += dy;
if (factor >= dx) {
// Make a "diagonal move" in grid (ie vertical or horizontal)
factor -= dx;
if(sig) { // vertical move: 2 moves in 1
x += xone; // add 1 in the appropriate sign
y += yone;
} else { // horizontal move: 2 moves in 2
x += xone; // doesn't matter which increases first
process(x,y);
y += yone;
}
} else {
x += xone;
}
process(x,y);
}
For example to get from G to D in our grid described above, we get
the following sequence of steps:
dx = 4, dy = 1, factor = 2, sig = true
process(1,4);
factor = 3, process(2,4);
factor = 0, process(3,5);
factor = 1, process(4,5);
factor = 2, process(5,5);
(4) How to Use Rectangular Arrays of Hexagons
---------------------------------------------
A "square" or "rectangle" in the above hexagon coordinates
unfortunately looks like a diamond-shape. This is fine when
the boundary of your domain is irrelevant. However, it does not
work out so well if you want your hexagons to fit neatly on a
rectangular screen, while still keeping the information in an
array. Fortunately, this is a rather simple transformation.
Consider the following rectangular "patch" of hexspace, with
the origin (0,0) at the upper left, and suppose you want to
embed this into a 9x8 array so the upper row is at y=0, with
x increasing to the right, the next row down is y=1, etc.
Here is the patch with the corresponding hex coordinate system
shown:
Hex X coord
\ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \
0 1 2 3 4 5 6 7 8
/ \ / \ / \ / \ / \ / \ / \ / \ / \
| O | W | | A | | | | | |
H \ / \ / \ / \ / \ / \ / \ / \ / \ / \
e 0 | V | | Z | | | | | | |
x / / \ / \ / \ / \ / \ / \ / \ / \ / \ /
/ | U | | | | | | | | |
Y \ / \ / \ / \ / \ / \ / \ / \ / \ / \
1 | B | | | | | | | | |
c / / \ / \ / \ / \ / \ / \ / \ / \ / \ /
o / | | | | | | | | | |
o \ / \ / \ / \ / \ / \ / \ / \ / \ / \
r 2 | | | | | | | | | |
d / / \ / \ / \ / \ / \ / \ / \ / \ / \ /
/ | | | | | | | | | |
\ / \ / \ / \ / \ / \ / \ / \ / \ / \
3 | | | | | | | | | |
/ \ / \ / \ / \ / \ / \ / \ / \ / \ /
/
O = upper-left origin = (0,0)
Your hex x-coord increases to the right and up.
Your hex y-coord increases to the right and down.
So in hex space,
U=(-1,1), V=(0,1), W=(1,1), Z=(2,3), A=(3,3), B=(-1,2)
and in array space,
U=(0,2), V=(0,1), W=(1,0), Z=(2,1), A=(3,0), B=(0,3)
The idea is then to store this patch of hexspace into
a 9x8 array, and be able to address hexes by their
array coordinates.
We need two transformations: 1) array -> hexspace given by:
array2hex(x,y) = (x - floor(y/2),x+ceil(y/2))
and 2) hexspace -> array given by:
hex2array(x,y) = (floor((x+y)/2),y-x)
Note that floor & ceiling here will need to deal with negative
as well as positive inputs. Also note that this is for a
rectangular patch as depicted above---if the topmost line is
to be offset to the right (instead of to the left as is shown),
then floor & ceil change places.
(5) Distance and LOS in a Rectangular Array of Hexagons
-------------------------------------------------------
Given these transformations, computing distance and LOS is easy.
Let A and B be a hexagons, with array coordinates given by A.ax, A.ay
and B.ax, B.ay. Then distance between them is:
// a macro to compute integer floor/ceiling when divide by two
#define Floor2 (X) (((X) >= 0) ? ((X>>1) : (((X)-1)/2))
#define Ceil2 (X) (((X) >= 0) ? (((X)+1)>>1) : ((X)/2))
// calculate hexspace coordinates of A and B
A.x = A.ax - Floor2(A.ay);
A.y = A.ax + Ceil2(A.ay);
B.x = B.ax - Floor2(B.ay);
B.y = B.ax + Ceil2(B.ay);
// calculate distance using hexcoords as per previous algorithm
dx = B.x - A.x;
dy = B.y - A.y;
if (sign(dx) == sign(dy)) {
dist = max(abs(dx),abs(dy));
} else {
dist = abs(dx) + abs(dy);
}
You might have expected the "==" to change to a "!=" given my comments
about the original hexspace algorithm for computing distance. However,
in this case the hex grid is not just rotated, but the axes have changed
too, fortuitously resulting in an identical situation.
So, the distance between the hexes mapped to array coords (3,4)
and (3,0) is just:
A.x = 3 - Floor2(4) = 1; A.y = 3 + Ceil2(4) = 5
B.x = 3 - Floor2(0) = 3; B.y = 3 + Ceil2(0) = 3
dx = 3 - 1 = 2;
dy = 3 - 5 = -2;
and thus, dist = 4;
and the distance between the hexes mapped to array coords (3,4)
and (1,4) is just:
A.x = 3 - Floor2(4) = 1; A.y = 3 + Ceil2(4) = 5
B.x = 1 - Floor2(4) = -1; B.y = 1 + Ceil2(4) = 3
dx = -1 - 1 = -2;
dy = 3 - 5 = -2;
and thus, dist = 2;
As you might expect, line-of-sight is computed exactly in the same way
as before, except we first convert our array coordinates to hex coords,
and convert back before we call process. The complete algorithm would
be:
// Assume A.x, A.y, B.x and B.y have been calculated, as has dx and dy
// assume abs(dx) >= abs(dy), it's symmetric otherwise
int sig,dx,dy,factor,x,y,xone,yone;
sig = (sign(dx) == sign(dy));
if(dx<0) xone = -1; else xone = 1; // unit increments
if(dy<0) yone = -1; else yone = 1; // unit increments
if (dx % 2) { // so dx is divisible by two
dx *= 2;
dy *= 2;
}
dx = abs(dx); dy = abs(dy); // don't need the signs anymore
factor = dx/2; // should start at 0.5, which is just (dx/2)/dx
x = A.x; y = A.y;
process(A.ax,A.ay); // note process being called with array coords
while (x != B.x || y != B.y) {
factor += dy;
if (factor >= dx) {
// Make a "diagonal move" in grid (ie vertical or horizontal)
factor -= dx;
if(sig) { // vertical move: 2 moves in 1
x += xone; // add 1 in the appropriate sign
y += yone;
} else { // horizontal move: 2 moves in 2
x += xone; // doesn't matter which increases first
process(Floor2(x+y),y-x); // note: passing array coords
y += yone;
}
} else {
x += xone;
}
process(Floor2(x+y),y-x); // note: passing array coords
}
So, the sequence of array coords to get from the hex at array coords
(3,0) to the one at (0,3) is:
(A.hex = (3,3), B.hex = (-1,2), sig = 1, dx = -4, dy = -1)
process(3,0)
process(2,1)
process(1,1)
process(1,2)
process(0,3)
(6) LOS by Intersection of Hexagons with a Straight Line
--------------------------------------------------------
The algorithm given above computes LOS by finding a shortest, "straightest"
path between two hexagons. Sometimes, though, it is desireable to compute
LOS not just by trying to draw as straight a line as can be formed formed
from hexagons, but by finding all the hexagons that intersect a Euclidean
line drawn on the hexagonal grid. If our "line" is a infinite half-ray (ie
an arrow which starts at a given hexagon but continues on forever), then
this corresponds to the set of hexagons which would be "visible" by someone
standing at a particular hexagon and looking in a given direction; it is
the Euclidean LOS mapped to the hexagonal grid. The algorithm given above
is not ideal for this purpose---it draws a "straight" line which does not
deviate too much from a Euclidean line, but it does not *always* find *all*
the hexagons which would intersect this line.
The brute force approach to this problem is just to go through every
hexagon and calculate if a given straight line intersects the hexagon
(intersection of a line and convex object like a hexagon is a simple
problem, and an algorithm is given below; finding the actual intersection
point is computationally more expensive), and then decide if it lies on the
half-ray. This is quite wasteful, though, and it is a simple matter to
restrict our intersection tests to a more realistic set, and in a way that
does not actually require calculating any intersection points. We will
still need functions to tell if a hexagon intersects a line, though. You
could do this in many ways; here's an easy and efficient way.
The following turns() function is quite standard in graphics/geometry; it
tells whether a given point is "left of" or "right of" a given directed
line.
#define LEFT 1
#define STRAIGHT 0
#define RIGHT -1
// returns LEFT if (x0,y0)-->(x1,y1)-->(x2,y2) turns to the left,
// RIGHT if (x0,y0)-->(x1,y1)-->(x2,y2) turns to the right
// STRAIGHT if (x2,y2) is colinear with (x0,y0)-->(x1,y1)
int turns(double x0,double y0,double x1,double y1,double x2,double y2) {
double cross;
cross = (x1-x0)*(y2-y0) - (x2-x0)*(y1-y0);
return((cross>0.0) ? LEFT : ((cross==0.0) ? STRAIGHT : RIGHT));
}
// A convex object (like a hexagon) intersects an infinite line if and
// only if some (at least one) of its coordinates lie on one side of the
// line, and some (at least one) lie on the other. Note that any two
// distinct points on our infinite line will work for (x0,y0) and (x1,y1).
// Also note that this function will consider a hexagon to intersect even
// if it just touches the line. Returns 1 if it does intersect, 0 if not.
int hexintersectsline(hexagon *h,double x0,double y0,double x1,double y1) {
// first see if it intersects the infinite line
int side1,i,j;
side1 = turns(x0,y0,x1,y1,h->x[0],h->y[0]);
if (side1==STRAIGHT) return 1;
for (i=1;i<6;i++) {
j = turns(x0,y0,x1,y1,h->x[i],h->y[i]);
if (j==STRAIGHT || j!=side1) return 1;
}
return 0;
}
So, suppose we're standing at hexagon h0, which has centre (x0,y0), and
you're looking toward hexagon h1, which has center (x1,y1). To find all
the hexagons intersecting this LOS, you have to find all hexagons
intersecting the infinite half-ray starting at (x0,y0) and extending
towards (and past maybe) (x1,y1). The following algorithm works by
"following" the line as it intersects hexagons; we begin at hexagon h0 and
we check to see which side of the hexagon the line exits from---the hexagon
adjacent in that direction is the next one on the list. We continue in
this manner until reaching h1 (which we are certain to do). For this we
need a standardized way of referring to the sides and vertices of our
hexagons.
// This set of routines finds all hexagons intersecting a Euclidean line
// between h0 and h1. For this we need to make some assumptions about how
// hexagon corners are designated. Assuming a coordinate system as shown
// in the section on how to use rectangular arrays of hexagons, we assume
// that hexagon vertices are stored in an array accessible by the hexagon
// structure and that vertices are numbered in the following way:
// 2
// 3 / \ 1
// | A |
// 4 \ / 0
// 5
// Given the coordinate system, we also know how coordinates change as we
// move to any particular adjacent hexagon:
//
// / \ / \
// | A | B | if Z = (x,y) in hex coords, then:
// / \ / \ / \ A = (x,y-1) F = (x,y+1)
// | C | Z | D | C = (x-1,y-1) D = (x+1,y+1)
// \ / \ / \ / E = (x-1,y) B = (x+1,y)
// | E | F |
// \ / \ /
//
// And that hexagons are maintained such that we can call the function
// "hexAt(x,y)" for hexagon-coordinates (x,y) and get the hexagon structure
// at that location. Symmetrically, we have to be able to tell what are
// the hexagonal coordinates of a given hexagon, so we assume each hexagon
// structure also contains its coordinates in its "hx" and "hy" fields.
//
// A line can intersect at most 3 hexagons at any point. If we are
// building our list of intersecting hexagons incrementally by following
// the line, then each time we leave a hexagon we will have to consider
// the possibility that we may be next intersecting either one or two
// hexagons, but no more. Thus, this routine calls "process" each time
// with either one or two hexagons (in the latter case the 2nd argument
// will be NULL). Note that hexagons are assumed to intersect even if
// it's just an edge or vertex that intersects the line.
//
// But first, a routine that finds the next hex or 2 after cur, making
// sure it's/they're not cur2 (or cur) or last1 or last2. Returns the
// total number of next hexes found (should always be 1 or 2)
int nexthexes(hexagon *cur,hexagon *cur2,hexagon **next1,hexagon **next2,
hexagon *last1,hexagon *last2,
double x0,double y0,double x1,double y1) {
hexagon *h;
int i,j,turn1,turn2;
static int hexneighbours[6][2] = { {1,1}, {1,0}, {0,-1},
{-1,-1}, {-1,0}, {0,1} };
*next1 = NULL; *next2 = NULL;
for (i=0;i<6;i++) {
turn1 = turn(x0,y0,x1,y1,cur->x[i],cur->y[i]);
turn2 = turn(x0,y0,x1,y1,cur->x[(i+1)%6],cur->y[(i+1)%6]);
if (turn1==STRAIGHT || turn2==STRAIGHT || turn1!=turn2) {
// in each of these cases we'll have to consider the hexagon
// adjacent to edge (i,i+1)
h = hexAt(cur->hx+hexneighbours[i][0],
cur->hy+hexneighbours[i][1]);
if (h!=cur && h!=cur2 && h!=*next1 && h!=*next2 &&
h!=last1 && h!=last2) {
if (*next1==null) *next1 = h;
else if (*next2==null) *next2 = h;
}
if (turn1==STRAIGHT) { // current vertex (i) lies on the line
// hex next to edge (i-1,i)
h = hexAt(cur->hx+hexneighbours[(i+5)%6][0],
cur->hy+hexneighbours[(i+5)%6][1]);
if (h!=cur && h!=cur2 && h!=*next1 && h!=*next2 &&
h!=last1 && h!=last2) {
if (*next1==null) *next1 = h;
else if (*next2==null) *next2 = h;
}
}
if (turn2==STRAIGHT) { // next vertex (i+1) lies on the line
// hex next to edge (i+1,i+2)
h = hexAt(cur->hx+hexneighbours[(i+1)%6][0],
cur->hy+hexneighbours[(i+1)%6][1]);
if (h!=cur && h!=cur2 && h!=*next1 && h!=*next2 &&
h!=last1 && h!=last2) {
if (*next1==null) *next1 = h;
else if (*next2==null) *next2 = h;
}
}
}
}
return (next2==NULL) ? 1 : 2);
}
// Calls process with hexagons at each step. This version of the
// algorithm stops when it reaches h1---this is not a requirement,
// and it should be obvious how to extend it to keep going to
// infinity. The center coordinates of hexagons are presumed to be
// accessible by their cx,cy fields.
// Note that 2 calls to nexthexes are made. This is because each time
// we go through the loop we follow the line out of one or two hexes
// and into one or two new hexes, so we need two calls to make sure
// we have all possible new hexes starting from either of our two hexes.
void hexesintersectingline(hexagon *h0,hexagon *h1) {
hexagon *next1,*next2,*cur1,*cur2,*last1,*last2;
cur1 = h0;
cur2 = NULL;
last1 = last2 = NULL;
do {
process(cur1,cur2);
if (cur1==h1) break;
next1 = next2 = NULL;
nexthexes(cur1,cur2,&next1,&next2,last1,last2,
h0->cx,h0->cy,h1->cx,h1->cy);
nexthexes(cur2,cur1,&next1,&next2,last1,last2,
h0->cx,h0->cy,h1->cx,h1->cy);
last1 = cur1; last2 = cur2;
cur1 = next1; cur2 = next2;
} while (1);
}
(7) Euclidean Field of View (FOV) on a Hexagonal Grid
-----------------------------------------------------
If you're calculating LOS on a hexagonal grid in order to find all hexes
visible from someone standing at a particular hexagon, you're actually
looking for the "Field of View."
You can calculate the FOV from hexagon h in a rectangular patch of a
hexagonal grid by drawing Euclidean lines from h to every hexagon.
Obviously, this is not the most efficient method---lines overlap, and so
many hexagons will be examined repeatedly. Fortunately, a more efficent
way exists.
Consider a circle or "bubble" expanding outwards from h. If there are no
obstacles in sight, everything within the bubble (up to some maximum radius
if desired) is visible from h. An obstacle, a hexagon one cannot see
through, though casts a shadow, which should block view of all hexagons
"behind" the obstacle hexagon. In the diagram below, for instance, if we
are standing at the centre of h and hexagon X contains the only obstacle
(which completely fills X), we should be able to see all unmarked hexagons,
but any marked S are fully obscured, and ones marked P are partially
visible (depending on your goals, you can consider partially-blocked hexes
as visible or not):
/ \ / \ / \ / \ / \ / \ / \
| | | | | P | S | S |
/ \ / \ / \ / \ / \ / \ / \ / \
| | | | | P | S | S | S |
\ / \ / \ / \ / \ / \ / \ / \ /
| | | | X | P | P3| P |
/ \ / \ / \ / \ / \ / \ / \ / \
| | | h | | P1| P2| | |
\ / \ / \ / \ / \ / \ / \ / \ /
| | | | | | | |
/ \ / \ / \ / \ / \ / \ / \ / \
| | | | A | | | | |
\ / \ / \ / \ / \ / \ / \ / \ /
In other words, we look from a point (center of h), and obstacles are
presumed to fill their entire hexagon. This means obstacles cast a shadow
"cone"---the center is the center of h, and the "arms" of the cone are as
close to hexagon X as possible without crossing the interior of X (sorry,
ascii is just not up to depicting this). This means our circular field of
view from h can be divided into a sequence of shadow cones separated by
visible cones. Of course, whether we consider shadow cones or visible
cones is not real critical here (from one representation we can clearly
derive the other), and in fact it turns out to be slightly more efficient
to represent the field of view as composed of a sequence of visible cones,
rather than a sequence of shadow cones. This is what we shall do.
Suppose we start off with some visible cones, with their union forming the
entire 360-degree FOV. Determining visibility is then a matter of
repeatedly expanding these cones outward one radius unit, possibly
shrinking them or splitting them as they encounter obstacles.
Each cone is thus represented by its two (x,y)-coordinates for its two
arms, and a list of the hexagons forming its "outer arc". Actually, we
don't need to keep a literal list of hexagons---we can number each hexagon
in our expanding bubble by it's "polar" coordinates, formed from radius and
counter-clockwise distance along the circle from the hex at 3 o'clock.
Thus in our above diagram, P1 has polar coords (2,0), P2 is (3,0), P3 is
(4,1), X is (2,1) and A is (2,10). It is easy to convert between hex
coords, array coords, and these new hex polar coords; if a hex h has
polar coordinates (r,t), and the center of the circle has hex coords
(x,y), then we can calcalate h's hex coords as follows:
1) Each circle at a given radius looks like a big hexagon. We first
find out which "side" h is on, which we can do be noting that
each of the sides of the circle at radius r consist of r hexagons. Thus,
h is on side s = (int)(t/r).
2) It is easy to figure out where the 6 corners of the circle are. Each
corner is r hexes along a line of adjacent hexagons, so we can use
the way coordinates change (described in Section (7), the A-F directions
from Z). We can then tell where h is if we know how far along the
given side h is, which can be calculated by e = t%r. First we determine
the hex coords of the appropriate corner (cx,cy) = ((x,y) + (r * one of A-F)),
then we use the same set of direction vectors to calculate the coords
of h as (cx,cy) + e * (a different one of A-F) by following along the
appropriate line. Sample code is shown in the HexGrid.hexOnCircle() method
of the HGAT code, described below.
Thus, we need only store the coords of the two hexes forming the end-points
of our arc for each cone. Using these polar coords and being able to
conveniently convert from polar to hex/array means that we can iterate
through the list of hexagons forming the arc, say (r,t1) and (r,t2), by
just running through all hexes in (r,i) for i=t1 to t2.
It should be noted that our cones make use of two kinds of information for
designating their limits: the arms and the outer arc of hexagons. It is
the arms which designate the limits of visibility for each particular cone.
However, the end-points of the arms are *not* updated each iteration
outward unless we encounter a new obstacle. There's really no need to
stretch the arms out if the cone hasn't changed; the whole point of the
cones is to be able to determine which hexagons lie inside (wholly or
partially) the cone, and which do not. This sort of information is
calculated by looking at cross products to determine whether hexagon
vertices are "left of" (CC-wise) or "right of" (C-wise) of a given arm;
such an approach works for any two points on our cone arm, so if the arm
does not move there's no reason to update the arm endpoint.
So, why do we need to maintain the arc-list of hexagons? Each time we
expand outward we may encounter new obstacles in the path of our cone. The
arc-list makes finding these obstacles somewhat easier than checking every
hexagon on the circle perimeter for intersection with a given cone. Given
a list of hexagons comprising the outer arc of a cone it is also a simple
matter to expand it outward one radius unit; one looks at all neighbours of
the two arc endpoints which are one radius unit further out, and checks to
see which hex intersects the cone's actual arm, or which is the first to
lie entirely to one side of the arm (ie, it's inside the cone, but one has
to be careful not to exclude the possibility of the cone being too narrow
to contain a whole hexagon). The hex which does so is the endpoint of the
next arc outward. It should be noted that these endpoints are not unique
between cones---adjacent cones might indeed share an endpoint hex; effectively,
the arms designate the cone limits, but the arcs give the list of hexagons
which fully *or partially* intersect the given cone.
When we encounter obstacles, we shrink or split the cone to exclude them.
If the obstacle blocks an endpoint of the arc, we simply move our cone arm
toward the other cone arm, effectively shrinking the cone. Thus, the
process of expanding outwards includes not only finding the next arc, but
also possibly shrinking the cone by moving the arm endpoints. Of course if
we move both arm endpoints to the degree where the clockwise and
counter-clockwise arms of our cone meet or cross over, then the cone is
empty and can be discarded.
As well as shrinking the cones to account for obstacles near the endpoints
of our arcs, we may also have to split our cones if we encounter an obstacle
somewhere within the interior of an arc. In such a case we divide our cone
into two cones, and recursively repeat the process of adjusting our cones.
There are some non-trivial implementation issues here. First, in order to
avoid dealing with degenerate cones---obtuse ones, and in particular ones
with an interior angle of 180-degrees or more---it is best not to start off
with one 360-degree cone representing the entire space; rather, space
should be already divided into several cones. The HGAT code starts off
with 4 cones, one for each quadrant; since cones never widen, this ensures
we do not have to ever worry about clockwise and counter-clockwise arms
getting confused. The second issue results from dealing with finite hex
grids---what does one do when the arcs are only partially on the
rectangular patch of hex grid in which we are interested? After all, our
expanding circles are certain to only refer to valid hexagons when they're
entirely contained inside the section of grid we are representing, but the
FOV calculation should not stop until it has expanded the circle so the
entire circle is outside the grid (if we want FOV over the entire grid).
We could hack in special code to avoid this situation; the approach in HGAT
is to generate "fake" hexagon structures for the hexagons outside our
grid---these structures are only created as requested by the FOV algorithm,
and are discarded as soon as they are no longer needed. This isn't the
most efficient way of dealing with this problem---special code would be
better---but it is perhaps the easiest way of avoiding the issue.
One final implementation point is how to deal with numerical error.
Depending on how we calculate the coordinates of hexagon corners, we may
find that cones which should be eliminated are instead just becoming
extremely-thin. This can result in hexagons which should be obscured being
considered visible. In the implementation mentioned below this is handled
by checking the interior angle of all cones created---any which are too
narrow are considered empty. Note that we don't have to actually calculate
the angle; we use instead an upper bound on the cosine of the angle, which
avoids actually evaluating trigonometric functions.
The entire algorithm is just too long to include the code here. The
overall process is simple enough, though:
1) Initialize 4 cones
2) Expand the arcs of the cones out one radius unit, respecting the arms.
3) If the arms intersect any obstacle hexes, contract the arms (and
hex-lists) to exclude the obstacle hex. Do this for both sides;
if this causes the arms to coincide or cross, the cone is empty
and can be discarded. Otherwise run through each hex on the
arc list and look for obstacle hexes. Such obstacles cause
the cone to be split into two (non-empty, because we know the
arc endpoints are not obstacles) cones, which may be recursively
shrunk and/or split.
4) Repeat from step 2)
A Java implementation illustrating the FOV algorithm can be seen at:
http://www-acaps.cs.mcgill.ca/~clump/Hex/HGAT.html
The program is available as an applet on the above page; complete source
code is available (HGAT.zip) in the same directory.
In this program you see a hex grid with some obstacle hexes darkened (and
FOV is to be calculated from the center). Each time you press the "Expand"
button the cones move out one radius unit ("New" randomizes the locations
of the obstacles, "Restart" does the same grid again). The cone arms are
also shown; note how the endpoints are not updated unless the arm must be
moved. Visible hexes at each step are indicated by writing their polar
coords inside the hex.
(8) References
--------------
Incidentally, the distance metric and matrix representation described above
are (well?) known in the literature. You can read more about them in:
@Article{LuczakRos76,
author = {Ed Luczak and Azriel Rosenfeld},
title = {Distance on a Hexagonal Grid},
journal = {{IEEE} Transactions on Computers},
year = 1976,
volume = 25,
number = 5,
month = {may},
pages = {532--533}
}