在六边形网格上：在选定点的给定半径内选择瓷砖。

Question

(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++)来“选择”相邻的瓷砖；对于（y-range；y+range；y++)；，因为它选择了不需要的平铺（在我给出的示例中，选择（1,1）平铺并给出1的范围也会给出（3,0）平铺（我实际上需要的平铺是（0,1)(0,2)(1,0)(1,2)(2,1)(2,2))，它有点靠近平铺（因为数组的结构方式），但这并不是我真正想要选择的东西。

有人能在这里给我指个正确的方向吗？

Answer 1

上面你可以看到的是两个网格。这一切都取决于你给瓷砖编号的方式，以及你理解什么是六边形网格的方式。在我看来，六边形网格只不过是一个变形的正交网格。

我用紫色圈出的两个十六进制块理论上仍然与0,0相邻。然而，由于我们从正交网格中获得十六进制网格的变形，这两个网格在视觉上不再相邻。

我们需要理解的是在某个方向上发生的变形，在我的例子中沿着[(-1,1)(1,-1)]假想线。更准确地说，这就好像网格沿着那条线被拉长了，而沿着垂直于那条线被压扁了。因此，这条线上的两块瓷砖自然地展开了，在视觉上不再相邻。相反，与(0,0)对角线的tiles(1,1)和(-1,-1)现在异常地靠近(0,0)，实际上它们现在在视觉上与(0,0)相邻。然而，在数学上，它们仍然是对角线，在代码中这样处理它们是有帮助的。

我所展示的图像说明了半径为1。对于半径为2时，您会注意到(2,-2)和(-2,2)是不应该包含在选定内容中的块。诸如此类。因此，对于半径r的任何选择，都不应选择(r,-r)和(-r,r)点。除此之外，您的选择算法应该与平铺网格相同。

只要确保你的轴正确地设置在六边形网格上，并相应地为你的瓷砖编号。

让我们进一步讨论一下这个问题。我们现在知道沿着网格中的任何方向移动花费我们1。沿着伸展的方向移动要花费我们2。例如，请参见(0,0)到(-1,1)。

Normal distance = (1, 1) - (-2, 5) = (3, -4)

(3, -4) = (3, -3) + (0, -1)

所以重述一下。(1,1)和(-2,5)之间的距离是(3,-3)的长度加上(0,-1)的长度。也就是说距离=3*2+1=7。

下面是我上面解释的算法在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;
}

(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)