Update: Also see Amit’s guide to hex grids[1] (2013), where I expand on the ideas Clark Verbrugge posted in this article.
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. The original version of the document[2] can be found on Clark’s site[3].
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:
- array -> hexspace given by:
array2hex(x,y) = (x - floor(y/2),x+ceil(y/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);
}
// See comment thread below from Ullaspool before using hexesintersectingline()
// 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 calculate h’s hex coords as follows:
- 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). - 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:
- Initialize 4 cones
- Expand the arcs of the cones out one radius unit, respecting the arms.
- 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.
- 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[4]. 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}
}
Notes from others
Frantisek Fuka writes:
I read the algorithm for calculating the distance in hexagonal
coordinates system, which is as follows:
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);
}
I think the simpler (=faster) method is:
dx = B.x - A.x;
dy = B.y - A.y;
dist = (abs (dx) + abs (dy) + abs (dx-dy)) / 2
Of course, the division by 2 can be done faster as right bitshift...
Thanks Frantisek! --Amit
Kjkazinski finds that the formulas that Clark uses for converting between array coordinates and hex coordinates will need modification if your array coordinates aren’t exactly the same as what Clark uses.
Ullaspool writes that there is likely a bug in the implementation of hexesintersectingline(); see the comment thread below.