什么是六边形网格？
你可以在上面看到的是两个网格。这完全取决于您为瓷砖编号的方式以及您理解六边形网格的方式。在我看来，六边形网格只不过是一个变形的正交网格。
我用紫色圈出的两个六角图块理论上仍然相邻0,0。然而，由于我们为了从正交网格获得六边形网格而经历了变形，这两者在视觉上不再是相邻的。
形变
我们需要了解的是变形发生在某个方向上，[(-1,1) (1,-1)]在我的例子中是沿着一条假想的线。更准确地说，就好像网格沿着那条线被拉长了，然后沿着垂直于那条线的线被压扁了。所以很自然地，那条线上的两块瓷砖分散开来，在视觉上不再相邻。相反，与 对角线的图块(1, 1)现在(-1, -1)异常(0, 0)接近(0, 0)，实际上如此接近，以至于它们现在在视觉上与相邻(0, 0)。然而，在数学上，它们仍然是对角线，有助于在代码中以这种方式处理它们。
选择
我展示的图像说明了半径为 1。对于半径为 2，您会注意到(2, -2)并且(-2, 2)是不应包含在选择中的图块。等等。因此，对于半径r的任何选择，不应选择点(r, -r)和。(-r, r)除此之外，您的选择算法应该与方形网格相同。
只需确保在六边形网格上正确设置了轴，并相应地对图块进行编号。
执行
让我们稍微扩展一下。我们现在知道沿网格中的任何方向移动都会花费我们 1。沿拉伸方向移动会花费我们 2。例如(0, 0)，请参阅(-1, 1)。
知道了这一点，我们可以通过将距离分解为两个分量来计算这种网格上任意两个图块之间的最短距离：对角线运动和沿其中一个轴的直线运动。例如，对于普通网格之间(1, 1)和上的距离，我们有：(-2, 5)
Normal distance = (1, 1) - (-2, 5) = (3, -4)
如果它们在方形网格上，那将是两个图块之间的距离矢量。但是我们需要补偿网格变形，所以我们分解如下：
(3, -4) = (3, -3) + (0, -1)
如您所见，我们已将向量分解为一个对角线(3, -3)和一个沿轴的直线(0, -1)。
我们现在检查对角线是否沿着变形轴，变形轴是可以是正数或负数的整数
(n, -n)的任何点。确实满足那个条件，所以这个对角向量是沿着变形的。这意味着这个向量的长度（或成本）不是，而是两倍，即。n(3, -3)36
所以回顾一下。(1, 1)和之间的距离(-2, 5)是 的长度(3, -3)加上 的长度(0, -1)。那就是distance = 3 * 2 + 1 = 7。
用 C++ 实现
下面是我上面解释的算法的 C++ 实现：
int ComputeDistanceHexGrid(const Point & A, const Point & B)
{
// compute distance as we would on a normal grid
Point distance;
distance.x = A.x - B.x;
distance.y = A.y - B.y;
// compensate for grid deformation
// grid is stretched along (-n, n) line so points along that line have
// a distance of 2 between them instead of 1
// to calculate the shortest path, we decompose it into one diagonal movement(shortcut)
// and one straight movement along an axis
Point diagonalMovement;
int lesserCoord = abs(distance.x) < abs(distance.y) ? abs(distance.x) : abs(distance.y);
diagonalMovement.x = (distance.x < 0) ? -lesserCoord : lesserCoord; // keep the sign
diagonalMovement.y = (distance.y < 0) ? -lesserCoord : lesserCoord; // keep the sign
Point straightMovement;
// one of x or y should always be 0 because we are calculating a straight
// line along one of the axis
straightMovement.x = distance.x - diagonalMovement.x;
straightMovement.y = distance.y - diagonalMovement.y;
// calculate distance
size_t straightDistance = abs(straightMovement.x) + abs(straightMovement.y);
size_t diagonalDistance = abs(diagonalMovement.x);
// if we are traveling diagonally along the stretch deformation we double
// the diagonal distance
if ( (diagonalMovement.x < 0 && diagonalMovement.y > 0) ||
(diagonalMovement.x > 0 && diagonalMovement.y < 0) )
{
diagonalDistance *= 2;
}
return straightDistance + diagonalDistance;
}
现在，给定上述实现的ComputeDistanceHexGrid功能，您现在可以拥有一个简单的、未优化的选择算法实现，它将忽略超出指定选择范围的任何图块：
int _tmain(int argc, _TCHAR* argv[])
{
// your radius selection now becomes your usual orthogonal algorithm
// except you eliminate hex tiles too far away from your selection center
// for(x-range;x+range;x++); for(y-range;y+range;y++);
Point selectionCenter = {1, 1};
int range = 1;
for ( int x = selectionCenter.x - range;
x <= selectionCenter.x + range;
++x )
{
for ( int y = selectionCenter.y - range;
y <= selectionCenter.y + range;
++y )
{
Point p = {x, y};
if ( ComputeDistanceHexGrid(selectionCenter, p) <= range )
cout << "(" << x << ", " << y << ")" << endl;
else
{
// do nothing, skip this tile since it is out of selection range
}
}
}
return 0;
}
对于一个选择点(1, 1)和一个范围1，上面的代码将显示预期的结果：
(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)
可能的优化
为了优化这一点，您可以将了解图块距离选择点多远的逻辑（在 中找到的逻辑ComputeDistanceHexGrid）直接包含到您的选择循环中，这样您就可以以完全避免超出范围图块的方式迭代网格。