六角砖，并找到他们的邻近邻居 [英] Hexagonal Tiles and finding their adjacent neighbourghs
问题描述
这是我的地图系统的工作原理：
< （0,0）（0,1）（0,2）（0,3）（0,4）
（1,0）（1,1）pre>
（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 ...
我正在努力的事实是，我不能通过使用来选择相邻的图块的x范围; X +范围; X ++）; for（y-range; y + range; y ++）; 因为它选择不想要的图块（在我给出的例子中，选择（1,1）图块并给出1的范围也会给我（3,0）瓦（我实际需要的是（0,1）（0,2）（1,0）（1,2）（2,1）（2,2）），这是有点相邻（因为数组的结构方式），但并不是我想要选择的那样，我只能强力强制，但这并不美观，可能不会涵盖选择半径事物的各个方面，
有人可以在这里指向正确的方向吗？
什么是六边形网格？
你可以看到上面的两个网格，这一切都是你编号的方式，你了解六边形网格的方式，我的方式看到它，一个六边形的网格只不过是一个变形的正交一个。
我以紫色圈出的两个六角瓷砖在理论上仍然与 0,0 相邻。然而，由于我们已经经历的变形，从正交的角度获得六角瓦格，两个不再是视觉上相邻的。
变形
我们需要了解的是，变形发生在某个方向，沿着<$ c在我的例子中，$ c> [（ - 1,1）（1，-1）] 虚线。更准确地说，就像网格沿着这条线已经伸长，并且沿着垂直于该线的线挤压。那么自然地，这条线上的两块瓷砖已经展开，不再是视觉上相邻的。相反，与<$ c对角线的瓷砖（1，1）和（ - 1，-1） $ c>（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）之间的距离我们有一个正常的网格：
正常距离=（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）
{
//像正常网格一样计算距离
点距离;
distance.x = A.x - B.x;
distance.y = A.y - B.y;
//补偿网格变形
//网格沿（-n，n）线延伸，所以沿着这条线的点有
//它们之间的距离为2的1
//计算最短路径，我们将其分解为一个对角线运动（快捷方式）
//和沿轴的一个直线运动
点对角线运动;
int lowerCoord = abs（distance.x）< abs（distance.y）？ abs（distance.x）：abs（distance.y）;
diagonalMovement.x =（distance.x <0）？无缘//保持符号
diagonalMovement.y =（distance.y< 0）？无缘//保持标志
点直线运动;
//其中一个x或y应始终为0，因为我们正在计算一条直线
//沿着一条轴
straightMovement.x = distance.x - diagonalMovement 。X;
straightMovement.y = distance.y - diagonalMovement.y;
//计算距离
size_t straightDistance = abs（straightMovement.x）+ abs（straightMovement.y）;
size_t diagonalDistance = abs（diagonalMovement.x）;
//如果我们沿着拉伸变形斜向走，我们双倍
//对角线距离
if（（diagonalMovement.x<&&&&&& > 0）||
（diagonalMovement.x> 0&&"对角线运动< 0））
{
diagonalDistance * = 2;
}
return straightDistance + diagonalDistance;
}
现在，给出上述实现的 ComputeDistanceHexGrid 函数，您现在可以对选择算法进行天真，未优化的实现，忽略比指定选择范围更大的任何图块。
code> int _tmain（int argc，_TCHAR * argv []）
{
//你的半径选择现在变成你惯用的正交算法
//除了你消除十六进制瓦远离你的选择中心
// for（x-range; x + range; x ++）;为（Y-范围; Y +范围; Y ++）;
Point selectionCenter = {1，1};
int range = 1; （int x = selectionCenter.x - range;
x< = selectionCenter.x + range;
++ x）
（int y = selectionCenter.y - range;
y< = selectionCenter.y + range;
++ y）
{
点p = {x，y};
if（ComputeDistanceHexGrid（selectionCenter，p）< = range）
cout<< （< x，，< - ）< ENDL;
else
{
//不做任何事情，跳过此图块，因为它不在选区范围内
}
}
}
return 0;
}
对于选择点（1，1）和一系列 1 ，上述代码将显示预期结果：
<$ p $ （0，0）
（0，1）
（1，0）
（1，1）
（1，2）
（2，1）
（2，2）
可能的优化< h2>
为了优化这一点，您可以包括了解从选择点到多远的逻辑（逻辑在 ComputeDistanceHexGrid ）直接进入你的选择循环，所以你可以以避免超出范围瓦片的方式迭代网格。
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)
etc...
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 is a hexagonal grid?
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.
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.
Deformation
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.
Selection
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.
Implementation
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.
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)
As you can see, we've decomposed the vector into one diagonal one (3, -3) and one straight along an axis (0, -1).
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.
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.
Implementation in 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;
}
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;
}
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)
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屋！
