#undef MODULE_TEST
#ifndef max
#define max(a,b) ((a) > (b) ? (a) : (b))
#endif
#ifndef min
#define min(a,b) ((a) < (b) ? (a) : (b))
#endif
int hexrange(int x1, int y1, int x2, int y2)
{
/* hexrange() computes the minimum number of hexes that must be
* traversed to get from hex (x1, y1) to hex (x2, y2). The
* coordinates relate to an odd-high orthogonally-numbered hex grid,
* like that shown below:
*
* /~~\ /~~\ /
* /1,1 \__/3,1 \__/
* \ /~~\ /~~\
* \__/2,1 \__/4,1 \
* /~~\ /~~\ /
* /1,2 \__/3,2 \__/
* \ /~~\ /~~\
* \__/2,2 \__/4,2 \
* /~~\ /~~\ /
* / \__/ \__/
*/
int decision;
int coldiff;
int rowdiff;
int cols, rows;
int dist;
coldiff = x2 - x1;
rowdiff = y2 - y1;
/* There is a correction to be computed, arising from the fact that
* *both* (2,0) and (2,1) are adjacent to (1,1). To determine which
* way the correction should point, we check the oddness of the
* x-coordinates, then use a switch on the resulting value (oddness
* of x1 in bit 1, oddness of x2 in bit 2. */
decision = ((x1 & 1) << 1) | (x2 & 1);
switch (decision)
{
case 0:
/* both x coordinates are even - no offsets are
* required. */
break;
case 1:
/* x2 is odd, x1 even. Therefore, x101 is below x201.
* Therefore, x100 is in an adjacent row to x201.
* So, if (y2 > y1) (i.e., hex 2 is "below" hex 1,
* we need to adjust the row difference towards
* zero. */
if (rowdiff > 0)
{
rowdiff--;
}
break;
case 2:
/* x1 is odd, x2 even. Therefore, x201 is below x101.
* Therefore, x200 is in an adjacent row to x101.
* So, if (y2 < y1) (i.e., hex 2 is "above" hex 1,
* we need to adjust the row difference towards
* zero. */
if (rowdiff < 0)
{
rowdiff++;
}
break;
case 3:
/* both odd */
break;
}
/* The range is now:
* (hdist) + max(vdist - (hdist / 2), 0)
* using the corrected vertical distance we just computed.
* cols is (hdist), rows is (vdist).
*/
cols = abs(coldiff);
rows = abs(rowdiff);
dist = cols + max((rows - (cols/2)), 0);
return dist;
}
#ifdef MODULE_TEST
int main()
{
printf("hex range (1,1)->(2,2): %d\n", hexrange(1,1,2,2));
printf("hex range (1,1)->(7,3): %d\n", hexrange(1,1,7,3));
return 0;
}
#endif