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

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 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);