Ответ 1
Что такое шестиугольная сетка?
То, что вы видите выше, - это две сетки. Все это в том, как вы числиваете свои плитки и как вы понимаете, что такое гексагональная сетка. Как я вижу, гексагональная сетка - это не что иное, как деформированная ортогональная.
Две шестигранные плитки, которые я совершил в фиолетовом цвете, теоретически по-прежнему находятся рядом с 0,0. Однако из-за деформации, которую мы прошли, чтобы получить решетку с шестигранной решеткой из ортогональной, они уже не визуально смежны.
Деформация
Нам нужно понять, что деформация произошла в определенном направлении вдоль воображаемой линии [(-1,1) (1,-1)] в моем примере. Чтобы быть более точным, это как если бы сетка была вытянута вдоль этой линии и раздавлена вдоль линии, перпендикулярной этому. Так что, естественно, две плитки на этой линии разбросаны и уже не визуально смежны. Наоборот, плитки (1, 1) и (-1, -1), которые были диагональны к (0, 0), теперь необычно близки к (0, 0), поэтому на самом деле они близки к (0, 0). Математически, однако, они все еще являются диагоналями, и это помогает рассматривать их таким образом в вашем коде.
Выбор
Изображение, которое я показываю, иллюстрирует радиус 1. Для радиуса два вы заметите, что (2, -2) и (-2, 2) - это плитки, которые не должны включаться в выборку. И так далее. Таким образом, для любого выбора радиуса r точки (r, -r) и (-r, r) не должны выбираться. Помимо этого, ваш алгоритм выбора должен быть таким же, как квадратная сетка.
Просто убедитесь, что ваша ось настроена правильно на гексагональной сетке и что вы соответствующим образом набираете свои плитки.
Реализация
Пусть это немного расширится. Теперь мы знаем, что движение по любому направлению в сетке стоит нам 1. И движение вдоль протяженного направления стоит нам 2. Например, (0, 0) to (-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.
Реализация в С++
Ниже приведена реализация в С++ описанного выше алгоритма:
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;
}
Для точки выбора (1, 1) и диапазона 1 приведенный выше код отобразит ожидаемый результат:
(0, 0)
(0, 1)
(1, 0)
(1, 1)
(1, 2)
(2, 1)
(2, 2)
Возможная оптимизация
Чтобы оптимизировать это, вы можете включить логику определения того, насколько далеко фрагмент из точки выбора (логика, найденный в ComputeDistanceHexGrid), непосредственно в ваш цикл выделения, поэтому вы можете перебирать сетку таким образом, чтобы избежать в целом.