在六边形网格上:选择选定点的给定半径内的切片.

Question

我正在使用六边形瓷砖地图开发一个简单的2D棋盘游戏,我已经阅读了几篇文章(包括gamedev one,每次有关于六边形瓷砖的问题时都会链接)关于如何在屏幕上绘制六边形以及如何管理运动(虽然我以前做过很多).我的主要问题是根据给定的半径找到相邻的瓷砖.

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

(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,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, 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函数,您现在可以使用一个简单的,未经优化的选择算法实现,该算法将忽略指定选择范围以外的任何tile:

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)直接进入选择循环的距离,因此您可以以避免超出范围切片的方式迭代网格.