六边形瓷砖并找到他们相邻的邻居

Question

我正在使用六角形瓷砖地图开发一个简单的2D棋盘游戏，我已经阅读了几篇文章（包括Gamedev One，每次在六角形瓷砖上都有链接），如何在屏幕上绘制Hexes以及如何管理运动（尽管我以前已经做过很多）。我的主要问题是根据给定半径找到相邻的瓷砖。

这就是我的地图系统的工作方式：

(0,0) (0,1) (0,2) (0,3) (0,4)
   (1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
   (3,0) (3,1) (3,2) (3,3) (3,4)

ETC...

我正在努力的事实是，我不能通过使用来“选择”相邻的瓷砖 for(x-range;x+range;x++); for(y-range;y+range;y++); 因为它选择了不需要的瓷砖（在我给出的示例中，选择（1,1）瓷砖并给出1的范围也会给我（3,0）瓷砖（我实际上需要的是（0,1）（0,1）（ 0,2）（1,0）（1,2）（2,1）（2,2）），有点与瓷砖相邻（由于数组结构化的方式），但这并不是我真正想要的选择。我只能强迫它，但这不会很漂亮，可能不会涵盖“选择半径”的各个方面。

有人可以在这里指向正确的方向吗？

Answer 1

什么是六角形网格？

您可以在上面看到的是两个网格。这一切都是您编号瓷砖的方式以及您了解六角形网格的方式。我的看法，六角形网格不过是一个变形的正交网格。

从理论上讲，我用紫色圆圈的两个十六进制瓷砖仍与 0,0. 。但是，由于变形，我们已经经历了从正交的六角磁力网格，这两个不再是 视觉上 邻近的。

形变

我们需要了解的是变形沿着某个方向发生 [(-1,1) (1,-1)] 在我的示例中，虚线。更确切地说，好像网格沿着该线伸长了，并且 挤压 沿着垂直于此的线。因此，自然而然地，该线上的两个瓷砖散布了，并且不再在视觉上相邻。相反，瓷砖 (1, 1) 和 (-1, -1) 对角线 (0, 0) 现在异常接近 (0, 0), ，实际上是如此亲密，以至于他们现在是 视觉上相邻 至 (0, 0). 。但是，从数学上讲，它们仍然是对角线的，它有助于以您的代码方式对待它们。

选择

我显示的图像说明了半径为1。对于两个半径，您会注意到 (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) 确实确实满足了该条件，因此该对角线矢量沿变形。这意味着该向量的长度（或成本）而不是 3, ，这将是两倍，即 6.

因此回顾。之间的距离 (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）直接进入选择循环，因此您可以以完全避免范围瓷砖的方式迭代网格。

Answer 2

我能想到的最简单方法...

minX = x-range; maxX = x+range
select (minX,y) to (maxX, y), excluding (x,y) if that's what you want to do
for each i from 1 to range:
    if y+i is odd then maxX -= 1, otherwise minX += 1
    select (minX, y+i) to (maxX, y+i)
    select (minX, y-i) to (maxX, y-i)

可能有点不合时宜。我只是在脑海中努力工作。但至少，这是您需要做的事情的想法。

在c'ish中：

void select(int x, int y) { /* todo: implement this */ }

void selectRange(int x, int y, int range)
{
    int minX = x - range, maxX = x + range;
    for (int i = minX; i <= maxX; ++i)
        if (i != x) select(i, y);
    for (int yOff = 1; yOff <= range; ++yOff)
    {
        if (y+yOff % 2 == 1) --maxX; else ++minX;
        for (int i=minX; i<=maxX; ++i)
        {
            select(i, y+yOff);  select(i, y-yOff);
        }
    }  
}