Что такое гексагональная сетка?
То, что вы видите выше, это две сетки.Все дело в том, как вы нумеруете свои плитки и как вы понимаете, что такое шестиугольная сетка.На мой взгляд, гексагональная сетка - это не что иное, как деформированная ортогональная.
Две шестигранные плитки, которые я обвел фиолетовым, теоретически все еще примыкают к 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) до (-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 функция, теперь вы можете иметь наивную, неоптимизированную реализацию алгоритма выбора, которая будет игнорировать любые плитки дальше указанного диапазона выбора:
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) непосредственно в вашем цикле выбора, так что вы можете перебирать сетку таким образом, чтобы полностью исключить плитки вне диапазона.