六边形瓷砖并找到它们的相邻邻居 [英] Hexagonal tiles and finding their adjacent neighbours

问题描述

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

I'm developing a simple 2D board game using hexagonal tile maps, I've read several articles (including the gamedev one's, which are linked every time there's a question on hexagonal tiles) on how to draw hexes on the screen and how to manage the movement (though much of it I had already done before). My main problem is finding the adjacent tiles based on a given radius.

这就是我的地图系统的工作原理:

This is how my map system works:

(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)

等等……

我正在努力解决的问题是，我不能只使用 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) )，它与瓦片有点相邻(因为数组的结构方式)但它并不是我真正想要选择的.我可以暴力破解它，但这不会很漂亮，并且可能不会涵盖选择半径事物"的各个方面.

What I'm struggling with is the fact that I cant just 'select' the adjacent tiles by using for(x-range;x+range;x++); for(y-range;y+range;y++); because it selects unwanted tiles (in the example I gave, selecting the (1,1) tile and giving a range of 1 would also give me the (3,0) tile (the ones I actually need being (0,1)(0,2)(1,0)(1,2)(2,1)(2,2) ), which is kinda adjacent to the tile (because of the way the array is structured) but it's not really what I want to select. I could just brute force it, but that wouldn't be beautiful and would probably not cover every aspect of 'selecting radius thing'.

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

Can someone point me in the right direction here?

推荐答案

您在上面看到的是两个网格.这完全取决于您为瓷砖编号的方式以及您理解六边形网格的方式.在我看来，六边形网格只不过是一个变形的正交网格.

What you can see above are the two grids. It's all in the way you number your tiles and the way you understand what a hexagonal grid is. The way I see it, a hexagonal grid is nothing more than a deformed orthogonal one.

我用紫色圈出的两个十六进制图块理论上仍然与 0,0 相邻.然而，由于我们从正交网格获得六边形网格所经历的变形，两者不再视觉上相邻.

The two hex tiles I've circled in purple are theoretically still adjacent to 0,0. However, due to the deformation we've gone through to obtain the hex-tile grid from the orthogonal one, the two are no longer visually adjacent.

我们需要了解的是变形发生在某个方向，在我的示例中，沿着 [(-1,1) (1,-1)] 假想线.更准确地说，就好像网格沿着那条线被拉长了，并且沿着垂直于那条线的线压扁.所以很自然地，那条线上的两块瓷砖分散开来，在视觉上不再相邻.相反，与 (0, 0) 对角线的图块 (1, 1) 和 (-1, -1) 现在异常接近 (0, 0)，事实上它们是如此接近，以至于它们现在 视觉上相邻 到 (0, 0).然而，从数学上讲，它们仍然是对角线，在您的代码中以这种方式处理它们会有所帮助.

What we need to understand is the deformation happened in a certain direction, along a [(-1,1) (1,-1)] imaginary line in my example. To be more precise, it is as if the grid has been elongated along that line, and squashed along a line perpendicular to that. So naturally, the two tiles on that line got spread out and are no longer visually adjacent. Conversely, the tiles (1, 1) and (-1, -1) which were diagonal to (0, 0) are now unusually close to (0, 0), so close in fact that they are now visually adjacent to (0, 0). Mathematically however, they are still diagonals and it helps to treat them that way in your code.

我展示的图像说明了半径为 1.对于半径为 2，您会注意到 (2, -2) 和 (-2, 2)是不应包含在选择中的图块.等等.因此，对于半径 r 的任何选择，不应选择点 (r, -r) 和 (-r, r).除此之外，您的选择算法应该与方形网格相同.

The image I show illustrates a radius of 1. For a radius of two, you'll notice (2, -2) and (-2, 2) are the tiles that should not be included in the selection. And so on. So, for any selection of radius r, the points (r, -r) and (-r, r) should not be selected. Other than that, your selection algorithm should be the same as a square-tiled grid.

只需确保在六边形网格上正确设置轴，并相应地对图块进行编号.

Just make sure you have your axis set up properly on the hexagonal grid, and that you are numbering your tiles accordingly.

让我们稍微扩展一下.我们现在知道沿网格中任何方向的移动都会花费我们 1.沿拉伸方向移动会花费我们 2.参见 (0, 0) 到 (-1, 1) 例如.

Let's expand on this for a bit. We now know that movement along any direction in the grid costs us 1. And movement along the stretched direction costs us 2. See (0, 0) to (-1, 1) for example.

知道了这一点，我们可以通过将距离分解为两个分量来计算此类网格上任意两个图块之间的最短距离:对角线移动和沿其中一个轴的直线移动.例如，对于普通网格上 (1, 1) 和 (-2, 5) 之间的距离，我们有:

Knowing this, we can compute the shortest distance between any two tiles on such a grid, by decomposing the distance into two components: a diagonal movement and a straight movement along one of the axis. For example, for the distance between (1, 1) and (-2, 5) on a normal grid we have:

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

如果它们在方形网格上，那将是两个图块之间的距离矢量.但是我们需要补偿网格变形，所以我们分解如下:

That would be the distance vector between the two tiles were they on a square grid. However we need to compensate for the grid deformation so we decompose like this:

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

如您所见，我们已将向量分解为一个对角线一个 (3, -3) 和一个沿轴的直线 (0, -1).

As you can see, we've decomposed the vector into one diagonal one (3, -3) and one straight along an axis (0, -1).

我们现在检查对角线是否沿着变形轴，它是任意点 (n, -n) 其中 n 是一个整数，可以是正面或负面.(3, -3) 确实满足那个条件，所以这个对角向量是沿着变形的.这意味着这个向量的长度(或成本)不是3，而是双倍，即6.

We now check to see if the diagonal one is along the deformation axis which is any point (n, -n) where n is an integer that can be either positive or negative. (3, -3) does indeed satisfy that condition, so this diagonal vector is along the deformation. This means that the length (or cost) of this vector instead of being 3, it will be double, that is 6.

所以回顾一下.(1, 1) 和 (-2, 5) 的距离是 (3, -3) 的长度加上<代码>(0, -1).即 distance = 3 * 2 + 1 = 7.

So to recap. The distance between (1, 1) and (-2, 5) is the length of (3, -3) plus the length of (0, -1). That is distance = 3 * 2 + 1 = 7.

下面是我上面解释过的算法在 C++ 中的实现:

Below is the implementation in C++ of the algorithm I have explained above:

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 函数，您现在可以拥有一个简单的、未优化的选择算法实现，该算法将忽略超出指定选择范围的任何图块:

Now, given the above implemented ComputeDistanceHexGrid function, you can now have a naive, unoptimized implementation of a selection algorithm that will ignore any tiles further than the specified selection range:

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的范围，上面的代码会显示预期的结果:

For a selection point (1, 1) and a range of 1, the above code will display the expected result:

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

可能的优化

为了优化这一点，您可以将了解图块距离选择点多远的逻辑(在 ComputeDistanceHexGrid 中找到的逻辑)直接包含在选择循环中，这样您就可以在完全避免超出范围的图块的方式.

Possible optimization

For optimizing this, you can include the logic of knowing how far a tile is from the selection point (logic found in ComputeDistanceHexGrid) directly into your selection loop, so you can iterate the grid in a way that avoids out of range tiles altogether.

这篇关于六边形瓷砖并找到它们的相邻邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！