Information on Hex Grid Algorithms
Copyright (c) Clark Verbrugge, 1996. [clump@cs.mcgill.ca]
This article may be freely distributed as long as this attribution is
included.
Here's a hexagonal grid with a coordinate system mapped to square grids.
Note that this is just one possible orientation of the hexagonsif
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 orthogonalthat
is, the ycoord increases to the upperleft, and the xcoord increases
to the upperright. 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.
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;
How do you compute lineofsight? 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);
Incidentally, the distance metric and matrix representation
described above is (well?) known in the literature; if you want
the reference email me (address is at top).
