六角砖并找到其相邻的邻居 [英] 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屋！