- PVSM.RU - https://www.pvsm.ru -
Сетки из шестиугольников (гексагональные сетки) используются в некоторых играх, но они не так просты и распространены, как сетки прямоугольников. Я коллекционирую ресурсы о сетках шестиугольников [1] уже почти 20 лет, и написал это руководство по самым элегантным подходам, реализуемым в простейшем коде. В статье часто используются руководства Чарльза Фу (Charles Fu [2]) и Кларка Вербрюгге (Clark Verbrugge [3]). Я опишу различные способы создания сеток шестиугольников, их взаимосвязь, а также самые общие алгоритмы. Многие части этой статьи интерактивны: выбор типа сетки изменяет соответствующие схемы, код и тексты. (Прим. пер.: это относится только к оригиналу, советую его изучить. В переводе вся информация оригинала сохранена, но без интерактивности.).
Примеры кода в статье написаны псевдокодом, так их легче читать и понимать, чтобы написать свою реализацию.
Шестиугольники — это шестигранные многоугольники. У правильных шестиугольников все стороны (грани) имеют одинаковую длину. Мы будем работать только с правильными шестиугольниками. Обычно в сетках шестиугольников используются горизонтальная (с острым верхом) и вертикальная (с плоским верхом) ориентации.
Шестиугольники с плоским (слева) и острым (справа) верхом
У шестиугольников по 6 граней. Каждая грань общая для двух шестиугольников. У шестиугольников по 6 угловых точек. Каждая угловая точка общая для трёх шестиугольников. Подробнее о центрах, гранях и угловых точках можно прочитать в моей статье о частях сеток [4] (квадратах, шестиугольниках и треугольниках).
В правильном шестиугольнике внутренние углы равны 120°. Есть шесть «клиньев», каждый из которых является равносторонним треугольником с внутренними углами 60°. Угловая точка i находится на расстоянии (60° * i) + 30°
, на size
единиц от центра center
. В коде:
function hex_corner(center, size, i):
var angle_deg = 60 * i + 30
var angle_rad = PI / 180 * angle_deg
return Point(center.x + size * cos(angle_rad), center.y + size * sin(angle_rad))
Для заполнения шестиугольника нужно получить вершины многоугольника с hex_corner(…, 0)
по hex_corner(…, 5)
. Для отрисовки контура шестиугольника нужно использовать эти вершины, а затем нарисовать линию снова в hex_corner(…, 0)
.
Разница между двумя ориентациями в том, что x и y меняются местами, что приводит к изменению углов: углы шестиугольников с плоским верхом равны 0°, 60°, 120°, 180°, 240°, 300°, а с острым верхом — 30°, 90°, 150°, 210°, 270°, 330°.
Углы шестиугольников с плоским и острым верхом
Теперь мы хотим расположить несколько шестиугольников вместе. В горизонтальной ориентации высота шестиугольника height = size * 2
. Вертикальное расстояние между соседними шестиугольниками vert = height * 3/4
.
Ширина шестиугольника width = sqrt(3)/2 * height
. Горизонтальное расстояние между соседними шестиугольниками horiz = width
.
В некоторых играх для шестиугольников используется пиксель-арт, который не точно соответствует правильным шестиугольникам. Формулы углов и расположений, описанные в этом разделе, не будут совпадать с размерами таких шестиугольников. Остальная часть статьи, описывающая алгоритмы сеток шестиугольников, применима даже если шестиугольники немного растянуты или сжаты.
Давайте приступим к сборке шестиугольников в сетку. В случае сеток квадратов существует только один очевидный способ сборки. Для шестиугольников же есть множество подходов. Я рекомендую использовать в качестве первичного представления кубические координаты. Осевые координаты или координаты смещений следует использовать для хранения карт и отображения координат для пользователя.
Наиболее частый подход — смещение каждого последующего столбца или строки. Столбцы обозначаются col
или q
. Строки обозначаются row
или r
. Можно смещать нечётные или чётные столбцы/строки, поэтому у горизонтальных и вертикальных шестиугольников есть по два варианта.
Горизонтальное расположение «нечет-r»
Горизонтальное расположение «чёт-r»
Вертикальное расположение «нечет-q»
Вертикальное расположение «чёт-q»
Ещё один способ рассмотрения сеток шестиугольников — видеть в них три основные оси, а не две, как в сетках квадратов. В них проявляется элегантная симметрия.
Возьмём сетку кубов и вырежем диагональную плоскость в x + y + z = 0
. Это странная мысль, но она поможет нам упростить алгоритмы сеток шестиугольников. В частности, мы сможем воспользоваться стандартными операциями из декартовых координат: суммированием и вычитанием координат, умножением и делением на скалярную величину, а также расстояниями.
Заметьте три основные оси на сетке кубов и их соотношение с шестью диагональными направлениями сетки шестиугольников. Диагональные оси сетки соответствуют основному направлению сетки шестиугольников.
Шестиугольники
Кубы
Поскольку у нас уже есть алгоритмы для сеток квадратов и кубов, использование кубических координат позволяет нам адаптировать эти алгоритмы под сетки шестиугольников. я буду использовать эту систему для большинства алгоритмов статьи. Для использования алгоритмов с другой системой координат я преобразую кубические координаты, выполню алгоритм, а затем преобразую их обратно.
Изучите, как кубические координаты работают для сетки шестиугольников. При выборе шестиугольников выделяются кубические координаты, соответствующие трём осям.
z
, равным 0, 1, 2, 3, чтобы увидеть связь. Строка отмечена синим. Попробуйте то же самое для x
(зелёный) и y
(сиреневый).+y
и -z
, поэтому каждый шаг на «север» увеличивает y
на 1 и уменьшает z
на 1.
Кубические координаты — разумный выбор для системы координат сетки шестиугольников. Условием является x + y + z = 0
, поэтому в алгоритмах оно должно сохраняться. Условие также гарантирует, что для каждого шестиугольника всегда будет каноническая координата.
Существует множество различных систем координат для кубов и шестиугольников. В некоторых из них условие отличается от x + y + z = 0
. Я показал только одну из множества систем. Можно также создать кубические координаты с x-y
, y-z
, z-x
, у которых будет свой набор интересных свойств, но я не буду их здесь рассматривать.
Но вы можете возразить, что не хотите хранить 3 числа для координат, потому что не знаете, как хранить карту в таком виде.
Осевая система координат, иногда называемая «трапецеидальной», строится на основе двух или трёх координат из кубической системы координат. Поскольку у нас есть условие x + y + z = 0
, третья координата не нужна. Осевые координаты полезны для хранения карт и отображения координат пользователю. Как и в случае с кубическими координатами, с ними можно использовать стандартные операции суммирования, вычитания, умножения и деления декартовых координат.
Существует множество кубических систем координат и множество осевых. В этом руководстве я не буду рассматривать все сочетания. Я выберу две переменные, q
(столбец) и r
(строка). В схемах этой статьи q
соответствует x
, а r
соответствует z
, но такое соответствие произвольно, потому что можно вращать и поворачивать схемы, получая различные соответствия.
Преимущество этой системы перед сетками смещений в большей понятности алгоритмов. Недостатком системы является то, что хранение прямоугольной карты выполняется немного странно; см. раздел о сохранении карт. Некоторые алгоритмы ещё понятнее в кубических координатах, но поскольку у нас есть условие x + y + z = 0
, мы можем вычислить третью подразумеваемую координату и использовать её в этих алгоритмах. В своих проектах я называю оси q
, r
, s
, поэтому условие выглядит как q + r + s = 0
, и я, когда нужно, могу вычислить s = -q - r
.
Координаты смещения — это первое, о чём думает большинство людей, потому что они совпадают со стандартными декартовыми координатами, используемыми для сеток квадратов. К сожалению, одна из двух осей должна проходить «против шерсти», и это в результате всё усложняет. Кубическая и осевая система идут «по шерсти» и у них более простые алгоритмы, но хранение карт немного более сложное. Существует ещё одна система, называемая «чередуемой» или «двойной», но здесь мы не будем её рассматривать; некоторые считают, что с ней проще работать, чем с кубической или осевой.
Координаты смещения, кубические и осевые
Ось — это направление, в котором соответствующая координата увеличивается. Перпендикуляр к оси — это линия, на которой координата остаётся постоянной. На схемах сеток выше показаны линии перпендикуляров.
Вероятно, что вы будете использовать в своём проекте осевые координаты или координаты смещения, но многие алгоритмы проще выражаются в кубических координатах. Поэтому нам нужно уметь преобразовывать координаты между системами.
Осевые координаты близко связаны с кубическими, поэтому преобразование делается просто:
# преобразование кубических в осевые координаты
q = x
r = z
# преобразование осевых в кубические координаты
x = q
z = r
y = -x-z
В коде эти две функции могут быть записаны следующим образом:
function cube_to_hex(h): # осевая
var q = h.x
var r = h.z
return Hex(q, r)
function hex_to_cube(h): # кубическая
var x = h.q
var z = h.r
var y = -x-z
return Cube(x, y, z)
Координаты смещения совсем немного сложнее:
# преобразование кубических в смещение чёт-q
col = x
row = z + (x + (x&1)) / 2
# преобразование смещения чёт-q в кубические
x = col
z = row - (col + (col&1)) / 2
y = -x-z
# преобразование кубических в смещение нечет-q
col = x
row = z + (x - (x&1)) / 2
# преобразование смещения нечет-q в кубические
x = col
z = row - (col - (col&1)) / 2
y = -x-z
# преобразование кубических в смещение чёт-r
col = x + (z + (z&1)) / 2
row = z
# преобразование чёт-r в кубические
x = col - (row + (row&1)) / 2
z = row
y = -x-z
# преобразование кубических в нечет-r
col = x + (z - (z&1)) / 2
row = z
# преобразование нечет-r в кубические
x = col - (row - (row&1)) / 2
z = row
y = -x-z
Примечание о реализации: я использую a&1 (побитовое «И» [5]) вместо a%2 (деления с остатком [6]) для определения, является ли число чётным (0) или нечётным (1). Подробное описание см. на странице примечаний к моей реализации [7].
Дан один шестиугольник, с какими шестью шестиугольниками он находится рядом? Как и можно ожидать, легче всего дать ответ в кубических координатах, довольно просто в осевых координатах, и немного сложнее в координатах смещения. Также может потребоваться рассчитать шесть «диагональных» шестиугольников.
Перемещение на одно пространство в координатах шестиугольников приводит к изменению одной из трёх кубических координат на +1 и другой на -1 (сумма должна оставаться равной 0). На +1 могут изменяться три возможных координаты, а на -1 — оставшиеся две. Это даёт нам шесть возможных изменений. Каждое соответствует одному из направлений шестиугольника. Простейший и быстрейший способ — предварительно вычислить изменения и поместить их в таблицу кубических координат Cube(dx, dy, dz)
во время компиляции:
var directions = [
Cube(+1, -1, 0), Cube(+1, 0, -1), Cube( 0, +1, -1),
Cube(-1, +1, 0), Cube(-1, 0, +1), Cube( 0, -1, +1)
]
function cube_direction(direction):
return directions[direction]
function cube_neighbor(hex, direction):
return cube_add(hex, cube_direction(direction))
Как и раньше, мы используем для начала кубическую систему. Возьмём таблицу Cube(dx, dy, dz)
и преобразуем в таблицу Hex(dq, dr)
:
var directions = [
Hex(+1, 0), Hex(+1, -1), Hex( 0, -1),
Hex(-1, 0), Hex(-1, +1), Hex( 0, +1)
]
function hex_direction(direction):
return directions[direction]
function hex_neighbor(hex, direction):
var dir = hex_direction(direction)
return Hex(hex.q + dir.q, hex.r + dir.r)
В осевых координатах мы вносим изменения в зависимости от того, в каком месте сетки находимся. Если мы в столбце/строке смещения, то правило отличается от случая столбца/строки без смещения.
Как и раньше, мы создаём таблицу чисел, которые нужно прибавить к col
and row
. Однако на этот раз у нас будет два массива, один для нечётных столбцов/строк, а другой — для чётных. Посмотрите на (1,1)
на рисунке карты сетки выше и заметьте, как меняются col
и row
меняются при перемещении в каждом из шести направлений. Теперь повторим процесс для (2,2)
. Таблицы и код будут разными для каждого из четырёх типов сеток смещений, приводим соответствующий код для каждого типа сетки.
Нечет-r
var directions = [
[ Hex(+1, 0), Hex( 0, -1), Hex(-1, -1),
Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ],
[ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1),
Hex(-1, 0), Hex( 0, +1), Hex(+1, +1) ]
]
function offset_neighbor(hex, direction):
var parity = hex.row & 1
var dir = directions[parity][direction]
return Hex(hex.col + dir.col, hex.row + dir.row)
Сетка для чётной (EVEN) и нечётной (ODD) строк
Чёт-r
var directions = [
[ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1),
Hex(-1, 0), Hex( 0, +1), Hex(+1, +1) ],
[ Hex(+1, 0), Hex( 0, -1), Hex(-1, -1),
Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ]
]
function offset_neighbor(hex, direction):
var parity = hex.row & 1
var dir = directions[parity][direction]
return Hex(hex.col + dir.col, hex.row + dir.row)
Сетка для чётной (EVEN) и нечётной (ODD) строк
Нечет-q
var directions = [
[ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1),
Hex(-1, -1), Hex(-1, 0), Hex( 0, +1) ],
[ Hex(+1, +1), Hex(+1, 0), Hex( 0, -1),
Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ]
]
function offset_neighbor(hex, direction):
var parity = hex.col & 1
var dir = directions[parity][direction]
return Hex(hex.col + dir.col, hex.row + dir.row)
Сетка для чётного (EVEN) и нечётного (ODD) столбцов
Чёт-q
var directions = [
[ Hex(+1, +1), Hex(+1, 0), Hex( 0, -1),
Hex(-1, 0), Hex(-1, +1), Hex( 0, +1) ],
[ Hex(+1, 0), Hex(+1, -1), Hex( 0, -1),
Hex(-1, -1), Hex(-1, 0), Hex( 0, +1) ]
]
function offset_neighbor(hex, direction):
var parity = hex.col & 1
var dir = directions[parity][direction]
return Hex(hex.col + dir.col, hex.row + dir.row)
Сетка для чётного (EVEN) и нечётного (ODD) столбцов
Использование вышеуказанных таблиц подстановки — это простейший способ вычисления соседей. Если вам интересно, можно также почитать об извлечении этих чисел [8].
Перемещение в «диагональном» пространстве в координатах шестиугольников изменяет одну из трёх кубических координат на ±2 и две другие на ∓1 (сумма должна оставаться равной 0).
var diagonals = [
Cube(+2, -1, -1), Cube(+1, +1, -2), Cube(-1, +2, -1),
Cube(-2, +1, +1), Cube(-1, -1, +2), Cube(+1, -2, +1)
]
function cube_diagonal_neighbor(hex, direction):
return cube_add(hex, diagonals[direction])
Как и раньше, мы можем преобразовать эти координаты в осевые, откинув одну из трёх координат, или преобразовать в координаты смещения, предварительно вычислив результаты.
В кубической системе координат каждый шестиугольник является кубом в трёхмерном пространстве. Соседние шестиугольники находятся в сетке шестиугольников на расстоянии 1 друг от друга, но на расстоянии 2 в сетке кубов. Это делает расчёт расстояний простым. В сетке квадратов манхэттенские расстояния [9] равны abs(dx) + abs(dy)
. В сетке кубов манхэттенские расстояния равны abs(dx) + abs(dy) + abs(dz)
. Расстояние в сетке шестиугольников равно их половине:
function cube_distance(a, b):
return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2
Эквивалентом этой записи будет выражение того, что одна из трёх координат должна быть суммой двух других, а затем получение её в качестве расстояния. Можно выбрать форму деления пополам или форму максимального значения, приведённую ниже, но они дают одинаковый результат:
function cube_distance(a, b):
return max(abs(a.x - b.x), abs(a.y - b.y), abs(a.z - b.z))
На рисунке максимальные значения выделены цветом. Заметьте также, что каждый цвет обозначает одно из шести «диагональных» направлений.
В осевой системе третья координата выражена неявно. Давайте преобразуем [10] из осевой в кубическую систему для расчёта расстояния:
function hex_distance(a, b):
var ac = hex_to_cube(a)
var bc = hex_to_cube(b)
return cube_distance(ac, bc)
Если компилятор в вашем случае встраивает (inline) hex_to_cube
и cube_distance
, то он сгенерирует такой код:
function hex_distance(a, b):
return (abs(a.q - b.q)
+ abs(a.q + a.r - b.q - b.r)
+ abs(a.r - b.r)) / 2
Существует множество различных способов записи расстояний между шестиугольниками в осевых координатах, но вне зависимости от способа записи расстояние между шестиугольниками в осевой системе извлекается из манхэттенского расстояния в кубической системе. Например, описанная здесь [11] «разность разностей» получается из записи a.q + a.r - b.q - b.r
как a.q - b.q + a.r - b.r
и с использованием формы максимального значения вместо формы деления пополам cube_distance
. Все они аналогичны, если увидеть связь с кубическими координатами.
Как и в случае с осевыми координатами, мы преобразуем [10] координаты смещения в кубические координаты, а затем используем расстояние кубической системы.
function offset_distance(a, b):
var ac = offset_to_cube(a)
var bc = offset_to_cube(b)
return cube_distance(ac, bc)
Мы будем использовать тот же шаблон для многих алгоритмов: преобразуем из шестиугольников в кубы, выполняем кубическую версию алгоритма и преобразуем кубические результаты в координаты шестиугольников (осевые или координаты смещения).
Как нарисовать линию от одного шестиугольника до другого? Я использую линейную интерполяцию для рисования линий [12]. Линия равномерно сэмплируется в N+1
точках и вычисляется, в каких шестиугольниках находятся эти сэмплы.
N
, которое будет расстоянием в шестиугольниках между конечными точками.N+1
точек между точками A и B. С помощью линейной интерполяции определяем, что для значений i
от 0
до N
, включая их, каждая точка будет A + (B - A) * 1.0/N * i
. На рисунке эти контрольные точки показаны синим. В результате получаются координаты с плавающей запятой.cube_round
(см. ниже).Соединяем всё вместе для отрисовки линии от A до B:
function lerp(a, b, t): // для float
return a + (b - a) * t
function cube_lerp(a, b, t): // для шестиугольников
return Cube(lerp(a.x, b.x, t),
lerp(a.y, b.y, t),
lerp(a.z, b.z, t))
function cube_linedraw(a, b):
var N = cube_distance(a, b)
var results = []
for each 0 ≤ i ≤ N:
results.append(cube_round(cube_lerp(a, b, 1.0/N * i)))
return results
Примечания:
cube_lerp
возвращает точку, находящуюся точно на грани между двумя шестиугольниками. Затем cube_round
сдвигает её в ту или иную сторону. Линии выглядят лучше, если их сдвигают в одном направлении. Это можно сделать, добавив «эпсилон»-шестиугольный Cube(1e-6, 1e-6, -2e-6)
к одной или обеим конечным точкам перед началом цикла. Это «подтолкнёт» линию в одном направлении, чтобы она не попадала на границы граней.N
к максимуму расстояния по каждой из осей. Мы делаем то же самое в кубическом пространстве, что аналогично расстоянию в сетке шестиугольников.cube_lerp
должна возвращать куб с координатами в float. Если вы программируете на языке со статической типизацией, то не сможете использовать тип Cube
. Вместо него можно определить тип FloatCube
или встроить (inline) функцию в код отрисовки линий, если вы не хотите определять ещё один тип.cube_lerp
, а затем рассчитав B.x-A.x
, B.x-A.y
и 1.0/N
за пределами цикла. Умножение можно преобразовать в повторяющееся суммирование. В результате получится что-то вроде алгоритма DDA-линии.
Для заданного центра шестиугольника и диапазона N
какие шестиугольники находятся в пределах N
шагов от него?
Мы можем произвести обратную работу из формулы расстояния между шестиугольниками distance = max(abs(dx), abs(dy), abs(dz))
. Чтобы найти все шестиугольники в пределах N
, нам нужны max(abs(dx), abs(dy), abs(dz)) ≤ N
. Это значит, что нужны все три значения: abs(dx) ≤ N
и abs(dy) ≤ N
и abs(dz) ≤ N
. Убрав абсолютное значение, мы получим -N ≤ dx ≤ N
и -N ≤ dy ≤ N
и -N ≤ dz ≤ N
. В коде это будет вложенный цикл:
var results = []
for each -N ≤ dx ≤ N:
for each -N ≤ dy ≤ N:
for each -N ≤ dz ≤ N:
if dx + dy + dz = 0:
results.append(cube_add(center, Cube(dx, dy, dz)))
Этот цикл сработает, но будет довольно неэффективным. Из всех значений dz
, которые мы перебираем в цикле, только одно действительно удовлетворяет условию кубов dx + dy + dz = 0
. Вместо этого мы напрямую вычислим значение dz
, удовлетворяющее условию:
var results = []
for each -N ≤ dx ≤ N:
for each max(-N, -dx-N) ≤ dy ≤ min(N, -dx+N):
var dz = -dx-dy
results.append(cube_add(center, Cube(dx, dy, dz)))
Этот цикл проходит только по нужным координатам. На рисунке каждый диапазон является парой линий. Каждая линия — это неравенство. Мы берём все шестиугольники, удовлетворяющие шести неравенствам.
Если нужно найти шестиугольники, находящиеся в нескольких диапазонах, то перед генерированием списка шестиугольников можно пересечь диапазоны.
Можно подойти к этой проблеме с точки зрения алгебры или геометрии. Алгебраически каждая область выражается как условия неравенств в форме -N ≤ dx ≤ N
, и нам нужно найти пересечение этих условий. Геометрически каждая область является кубом в трёхмерном пространстве, и мы пересечём два куба в трёхмерном пространстве для получения прямоугольного параллелепипеда в трёхмерном пространстве. Затем мы проецируем его обратно на плоскость x + y + z = 0
, чтобы получить шестиугольники. Я буду решать эту задачу алгебраически.
Во-первых, мы перепишем условие -N ≤ dx ≤ N
в более общей форме xmin ≤ x ≤ xmax
, и примем xmin = center.x - N
и xmax = center.x + N
. Сделаем то же самое для y
и z
, в результате получив общий вид кода из предыдущего раздела:
var results = []
for each xmin ≤ x ≤ xmax:
for each max(ymin, -x-zmax) ≤ y ≤ min(ymax, -x-zmin):
var z = -x-y
results.append(Cube(x, y, z))
Пересечением двух диапазонов a ≤ x ≤ b
и c ≤ x ≤ d
является max(a, c) ≤ x ≤ min(b, d)
. Поскольку область шестиугольников выражена как диапазоны над x
, y
, z
, мы можем отдельно пересечь каждый из диапазонов x
, y
, z
, а затем использовать вложенный цикл для генерирования списка шестиугольников в пересечении. Для одной области шестиугольников мы принимаем xmin = H.x - N
and xmax = H.x + N
, аналогично для y
и z
. Для пересечения двух областей шестиугольников мы принимаем xmin = max(H1.x - N, H2.x - N)
и x
max = min(H1.x + N, H2.x + N), аналогично для y
и z
. Тот же шаблон работает для пересечения трёх или более областей.
При наличии препятствий проще всего выполнить заливку с ограничением по расстоянию (поиск в ширину). На рисунке ниже мы ограничиваемся четырьмя ходами. В коде fringes[k]
— это массив всех шестиугольников, которых можно достичь за k
шагов. При каждом проходе по основному циклу мы расширяем уровень k-1
на уровень k
.
function cube_reachable(start, movement):
var visited = set()
add start to visited
var fringes = []
fringes.append([start])
for each 1 < k ≤ movement:
fringes.append([])
for each cube in fringes[k-1]:
for each 0 ≤ dir < 6:
var neighbor = cube_neighbor(cube, dir)
if neighbor not in visited, not blocked:
add neighbor to visited
fringes[k].append(neighbor)
return visited
Для заданного вектора шестиугольника (разницу между двумя шестиугольниками) нам может понадобиться повернуть его, чтобы он указывал на другой шестиугольник. Это просто сделать, имея кубические координаты, если придерживаться поворота на 1/6 окружности.
Поворот на 60° вправо сдвигает каждую координату на одну позицию вправо:
[ x, y, z]
to [-z, -x, -y]
Поворот на 60° влево сдвигает каждую координату на одну позицию влево:
[ x, y, z]
to [-y, -z, -x]
«Поиграв» [в оригинале статьи] со схемой, можно заметить, что каждый поворот на 60° меняет знаки и физически «поворачивает» координаты. После поворота на 120° знаки снова становятся теми же. Поворот на 180° меняет знаки, но координаты поворачиваются в своё изначальное положение.
Вот полная последовательность поворота положения P вокруг центрального положения C, приводящего к новому положению R:
P_from_C = P - C = Cube(P.x - C.x, P.y - C.y, P.z - C.z)
.P_from_C
как описано выше и присваивание итоговому вектору обозначения R_from_C
.R = R_from_C + C = Cube(R_from_C.x + C.x, R_from_C.y + C.y, R_from_C.z + C.z)
.Здесь несколько этапов преобразований, но каждый из них довольно прост. Можно сократить некоторые из этих этапов, определив поворот непосредственно в осевых координатах, но векторы шестиугольников не работают с координатами смещения, и я не знаю, как сократить этапы для координат смещения. См. также обсуждение [16] других способов вычисления поворота на stackexchange.
Чтобы выяснить, принадлежит ли заданный шестиугольник к кольцу заданного радиуса radius
, нужно вычислить расстояние от этого шестиугольника до центра, и узнать, равно ли оно radius
. Для получения списка всех таких шестиугольников нужно сделать radius
шагов от центра, а затем следовать за поворачиваемыми векторами по пути вдоль кольца.
function cube_ring(center, radius):
var results = []
# этот код не работает для radius == 0; вы понимаете, почему?
var cube = cube_add(center,
cube_scale(cube_direction(4), radius))
for each 0 ≤ i < 6:
for each 0 ≤ j < radius:
results.append(cube)
cube = cube_neighbor(cube, i)
return results
В этом коде cube
начинается на кольце, показанном большой стрелкой от центра к углу схемы. Я выбрал для начала угол 4, потому что он соответствует пути, в котором двигаются мои числа направлений. Вам может понадобиться другой начальный угол. На каждом этапе внутреннего цикла cube
двигается на один шестиугольник по кольцу. Через 6 * radius
шагов он завершает там, где начал.
Проходя по кольцам по спиральному паттерну, мы можем заполнить внутренние части колец:
function cube_spiral(center, radius):
var results = [center]
for each 1 ≤ k ≤ radius:
results = results + cube_ring(center, k)
return results
Площадь большого шестиугольника равна сумме всех окружностей плюс 1 для центра. Для вычисления площади используйте эту формулу [17].
Обход шестиугольников таким способом можно также использовать для вычисления диапазона перемещения (см. выше).
Что видимо из заданного положения с заданным расстоянием, и не перекрывается препятствиями? Простейший способ определить это — нарисовать линию к каждому шестиугольнику в заданном диапазоне. Если линия не встречается со стенами, то вы видите шестиугольник. Перемещайте мышь по шестиугольникам [на схеме в оригинале статьи], чтобы увидеть отрисовку линий к этим шестиугольникам и стены, с которыми линии встречаются.
Этот алгоритм может быть медленным на больших площадях, но его легко реализовать, поэтому рекомендую начать с него.
Существует много разных определений видимости. Хотите ли вы видеть центр другого шестиугольника из центра начального? Хотите ли вы видеть любую часть другого шестиугольника из центра начального? Может быть, любую часть другого шестиугольника из любой точки начального? Мешающие взгляду препятствия меньше полного шестиугольника? Область видимости — это более хитрое и разнообразное понятие, чем кажется на первый взгляд. Начнём с простейшего алгоритма, но ждите, что он обязательно правильно вычислит ответ в вашем проекте. Бывают даже случаи, когда простой алгоритм даёт нелогичные результаты.
В руководстве Кларка Вербрюгге [3] описывается алгоритм для вычисления области видимости «начинаем с центра и двигаемся наружу». См. также проект Duelo [18], у которого есть на Github онлайн-демо области видимости с направлениями [19]. Также можете прочитать мою статью об расчёте 2d-видимости [20], в ней есть алгоритм, работающий с многоугольниками, в том числе и с шестиугольниками. У сообщества любителей roguelike есть хороший набор алгоритмов для сеток квадратов (см. здесь [21], здесь [22] и здесь). Некоторые из них можно адаптировать под сетки шестиугольников.
Для перевода из шестиугольников в пиксели полезно изучить схему размеров и расположения, представленную в разделе «Геометрия». В случае осевых координат к преобразованию из шестиугольников в пиксели надо подходить, рассматривая базисные векторы. На схеме стрелка A→Q — это базисный вектор q, а A→R — базисный вектор r. Координата пикселя равна q_basis * q + r_basis * r
. Например, B в (1, 1) является суммой базисных векторов q и r.
При наличии библиотеки матриц операция является простым умножением матриц. Однако здесь я запишу код без матриц. Для осевой сетки x = q
, z = r
, которую я использую в этом руководстве, преобразование будет иметь следующий вид:
Для шестиугольников с плоскими верхами
function hex_to_pixel(hex):
x = size * 3/2 * hex.q
y = size * sqrt(3) * (hex.r + hex.q/2)
return Point(x, y)
Для шестиугольников с острыми верхами
function hex_to_pixel(hex):
x = size * sqrt(3) * (hex.q + hex.r/2)
y = size * 3/2 * hex.r
return Point(x, y)
Матричный подход будет удобен позже, когда нам нужно будет преобразовать координаты пикселей обратно в координаты шестиугольников. Всё, что нам понадобится — обратить матрицу. Для кубических координат можно либо использовать кубические базисные векторы (x, y, z), или сначала преобразовать их в осевые, а затем использовать осевые базисные векторы (q, r).
Для координат смещения нам нужно будет сместить номер столбца или строки (он больше не будет целым). После этого можно использовать базисные векторы q и r, связанные с осями x и y:
Нечет-r
function offset_to_pixel(hex):
x = size * sqrt(3) * (hex.col + 0.5 * (hex.row&1))
y = size * 3/2 * hex.row
return Point(x, y)
Чёт-r
function offset_to_pixel(hex):
x = size * sqrt(3) * (hex.col - 0.5 * (hex.row&1))
y = size * 3/2 * hex.row
return Point(x, y)
Нечет-q
function offset_to_pixel(hex):
x = size * 3/2 * hex.col
y = size * sqrt(3) * (hex.row + 0.5 * (hex.col&1))
return Point(x, y)
Чёт-q
function offset_to_pixel(hex):
x = size * 3/2 * hex.col
y = size * sqrt(3) * (hex.row - 0.5 * (hex.col&1))
return Point(x, y)
К сожалению, координаты смещения не имеют базисных векторов, которые можно использовать вместе с матрицей. Это одна из причин того, почему преобразования из пикселей в шестиугольники сложнее в координатах смещения.
Другой подход: преобразовывать координаты смещения в кубические/осевые координаты, затем использовать преобразование кубических/осевых координат в пиксели. Благодаря встраиванию кода преобразования при оптимизации он в результате будет таким же, как выше.
Один из самых частых вопросов заключается в том, как взять положение пикселя (например, щелчка мыши) и преобразовать его в координату сетки шестиугольников? Я покажу, как это делается для осевых или кубических координат. Для координат смещения проще всего будет преобразовать в конце кубические координаты в координаты смещения.
Для преобразования координат шестиугольников в координаты пикселей мы умножили q
, r
на базисные векторы для получения x
, y
. Можно считать это умножением матриц. Вот матрица для шестиугольников с острыми верхами:
Преобразование координат пикселей обратно в координаты шестиугольников достаточно прямолинейно. Мы можем обратить матрицу:
Эти вычисления дадут нам дробные осевые координаты (float) для q
и r
. Функция hex_round()
преобразует дробные осевые координаты в целые осевые координаты шестиугольников.
Вот код для осевых шестиугольников с острыми верхами:
function pixel_to_hex(x, y):
q = (x * sqrt(3)/3 - y / 3) / size
r = y * 2/3 / size
return hex_round(Hex(q, r))
А вот код для осевых шестиугольников с плоскими верхами:
function pixel_to_hex(x, y):
q = x * 2/3 / size
r = (-x / 3 + sqrt(3)/3 * y) / size
return hex_round(Hex(q, r))
Эти три строчки кода преобразуют положение пикселя в осевую координату шестиугольника. Если вы используете координаты смещения, то воспользуйтесь return cube_to_hex(cube_round(Cube(q, -q-r, r)))
.
Существует множество других способов преобразования пикселей в шестиугольники. На этой странице [23] перечислены известные мне.
Иногда у нас получается кубическая координата (x, y, z) с плавающей запятой, и нам нужно узнать, в каком шестиугольнике она должна находиться. Это выясняется отрисовкой линии и преобразованием из пикселей в шестиугольники. Преобразование значения с плавающей запятой в целое значение называется округлением (rounding), поэтому я назвал этот алгоритм cube_round
.
В кубических координатах x + y + z = 0
даже при кубических координатах с плавающей точкой. Поэтому давайте округлим каждую компоненту до ближайшего целого (rx, ry, rz)
. Однако, хотя x + y + z = 0
, после округления у нас нет гарантий того, что rx + ry + rz = 0
. Поэтому мы изменяем компоненту с самым большим изменением так, чтобы условие rx + ry + rz = 0
было верным. Например, если изменение y
abs(ry-y)
больше abs(rx-x)
и abs(rz-z)
, то мы изменяем его на ry = -rx-rz
. Это гарантирует нам, что rx + ry + rz = 0
. Вот алгоритм:
function cube_round(h):
var rx = round(h.x)
var ry = round(h.y)
var rz = round(h.z)
var x_diff = abs(rx - h.x)
var y_diff = abs(ry - h.y)
var z_diff = abs(rz - h.z)
if x_diff > y_diff and x_diff > z_diff:
rx = -ry-rz
else if y_diff > z_diff:
ry = -rx-rz
else:
rz = -rx-ry
return Cube(rx, ry, rz)
Для некубических координат проще всего будет преобразовать их в кубические координаты, воспользоваться алгоритмом округления, а затем преобразовать обратно:
function hex_round(h):
return cube_to_hex(cube_round(hex_to_cube(h)))
Примечание о реализации: cube_round
и hex_round
получают координаты в float, а не в int. Если вы написали классы Cube
и Hex
, они будут отлично работать в языках с динамической типизацией, в которых можно передавать числа с плавающей запятой вместо целых, и в языках со статической типизацией с унифицированным типом чисел. Однако в большинстве языков со статической типизацией нужен будет отдельный тип class/struct для координат float и cube_round
будет иметь тип FloatCube → Cube
. Если вам также нужна hex_round
, она будет FloatHex → Hex
, использующей вспомогательную функцию floatcube_to_floathex
вместо cube_to_hex
. В языках с параметризированными типами (C++, Haskell и т.д.) можно определить Cube, где T является int или float. Или же можно написать cube_round
для получения трёх чисел с плавающей точкой в качестве входных данных вместо определения нового типа только для этой функции.
Чаще всего осевая система координат вызывает жалобы потому, что приводит к ненужному расходованию пространства при использовании прямоугольных карт. Это одна из причин в пользу системы координат смещения. Однако все системы координат шестиугольников приводят к расходу пространства при использовании треугольных или шестиугольных карт. Мы можем использовать одну стратегию для хранения всех этих типов карт.
Прямоугольная карта
Треугольная карта
Шестиугольная карта
Ромбовидная карта
Заметьте на схеме, что неиспользуемое пространство находится справа и слева от каждой строки (за исключением ромбовидных карт). Это даёт нам три варианта стратегий хранения карты:
q,r
мы вместо этого получаем доступ к hash_table(hash(q,r))
. Инкапсулируем её в геттер/сеттер в классе сетки, чтобы остальная часть игры не должна была знать о ней.Чтобы применить эту стратегию в произвольных выпуклых картах, необходимо хранить дополнительный массив «первых столбцов». Когда нужно получить доступ к шестиугольнику в q,r
, мы вместо этого получаем доступ к array[r][q - first_column[r]]
. Инкапсулируем его в геттер/сеттер в классе сетки, чтобы остальная часть игры не должна была знать о нём. На съеме first_column
показан в левой части каждой строки.
Если карты имеют фиксированные формы, то «первые столбцы» можно вычислять «на лету», а не хранить их в массиве.
first_column[r] == -floor(r/2)
. В результате мы получаем доступ к array[r][q + r/2]
, что оказывается аналогом преобразования координат в координаты смещения сетки.first_column[r] == 0
, поэтому мы получаем доступ к access array[r][q]
— очень удобно! Для треугольных карт, ориентированных по-другому (не показаны на схеме), это будет array[r][q+r]
.N
, где N = max(abs(x), abs(y), abs(z)
, у нас получается first_column[r] == -N - min(0, r)
. Мы получаем доступ к array[r][q + N + min(0, r)]
. Однако так как мы начинаем с каких-то значений r < 0
, нам также нужно сместить строку и использовать array[r + N][q + N + min(0, r)]
.array[r][q]
.
В некоторых играх требуется, чтобы карта «склеивалась» по краям. Квадратную карту можно обернуть только по оси x (что примерно соответствует сфере) или по обеим осям x и y (что примерно соответствует тору). Сворачивание зависит от формы карты, а не от формы её элементов. Сворачивание квадратной карты проще выполняется в координатах смещения. Я покажу, как выполняется сворачивание шестиугольной карты в кубических координатах.
Относительно центра карты существует шесть «зеркальных» центров. При выходе с карты мы вычитаем ближайший к нам зеркальный центр, пока снова не вернёмся на основную карту. На схеме [в оригинале статьи] попробуйте покинуть центральную карту, и понаблюдайте, как один из зеркальных центров входит в карту с противоположной стороны.
Простейшей реализацией будет предварительное вычисление ответов. Создаём таблицу подстановок, хранящую для каждого шестиугольника, выходящего с карты, соответствующий куб с другой стороны. Для каждого из шести зеркальных центров M
и для каждого из положений на карте L
храним mirror_table[cube_add(M, L)] = L
. Каждый раз при вычислении шестиугольника, находящегося в таблице зеркал заменяем его неотзеркаленной версией.
На шестиугольной карте с радиусом N
зеркальные центры будут Cube(2*N+1, -N, -N-1)
и шестью его поворотами.
При использовании поиска пути на графах, например алгоритма поиска A*, алгоритма Дейкстры или Флойда-Уоршелла поиск пути на сетках шестиугольников не отличается от поиска пути на сетках квадратов. Пояснения и код из моего руководства по поиску пути [24] применимы и для сеток шестиугольников.
[В оригинале статьи пример интерактивен, нажатиями мыши можно добавлять и удалять стены]
graph.neighbors
. Используйте для этого функцию в разделе «Соседние шестиугольники». Отфильтровывайте непроходимые соседние шестиугольники.heuristic
, получающая расстояние между двумя положениями. Используйте формулу расстояний, умноженную на затраты на передвижение. Например, если перемещение стоит 5 единиц на шестиугольник, то умножайте расстояние на 5.
У меня есть руководство по реализации собственной библиотеки сеток шестиугольников [25] с примерами кода на C++, Java, C#, Javascript, Haxe и Python.
Код [оригинала] этой статьи написан на смеси Haxe [47] и Javascript: Cube.hx [48], Hex.hx [49], Grid.hx [50], ScreenCoordinate.hx [51], ui.js [52] и cubegrid.js [53] (для анимации кубов/шестиугольников). Однако если вы хотите написать свою библиотеку сеток шестиугольников, то рекомендую вместо этого кода изучить моё руководство по реализации [25].
Я хочу в дальнейшем расширять это руководство. У меня есть список на Trello [54].
Автор: PatientZero
Источник [55]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/news/236400
Ссылки в тексте:
[1] коллекционирую ресурсы о сетках шестиугольников: http://www-cs-students.stanford.edu/~amitp/gameprog.html#hex
[2] Charles Fu: http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon2.html
[3] Clark Verbrugge: http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html
[4] моей статье о частях сеток: http://www-cs-students.stanford.edu/~amitp/game-programming/grids/
[5] побитовое «И»: https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%B2%D1%8B%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8#.D0.9F.D0.BE.D0.B1.D0.B8.D1.82.D0.BE.D0.B2.D0.BE.D0.B5_.C2.AB.D0.98.C2.BB_.28AND.29
[6] деления с остатком: https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%BE%D0%BC
[7] на странице примечаний к моей реализации: http://www.redblobgames.com/grids/hexagons/implementation.html#offset
[8] извлечении этих чисел: http://www.redblobgames.com/grids/hexagons/derive-hex-neighbor-formula.html
[9] манхэттенские расстояния: https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%B3%D0%BE%D1%80%D0%BE%D0%B4%D1%81%D0%BA%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D1%80%D1%82%D0%B0%D0%BB%D0%BE%D0%B2
[10] преобразуем: http://www.redblobgames.com/grids/hexagons/#conversions
[11] здесь: http://3dmdesign.com/development/hexmap-coordinates-the-easy-way
[12] линейную интерполяцию для рисования линий: http://www.redblobgames.com/grids/line-drawing.html
[13] Алгоритм DDA-линии: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_DDA-%D0%BB%D0%B8%D0%BD%D0%B8%D0%B8
[14] эту статью: http://zvold.blogspot.com/2010/02/line-of-sight-on-hexagonal-grid.html
[15] «сверхпокрытие»: http://stackoverflow.com/questions/3233522/elegant-clean-special-case-straight-line-grid-traversal-algorithm
[16] обсуждение: http://gamedev.stackexchange.com/questions/15237/how-do-i-rotate-a-structure-of-hexagonal-tiles-on-a-hexagonal-grid/
[17] эту формулу: https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%80%D1%8F%D0%B4
[18] Duelo: https://github.com/jbochi/duelo
[19] онлайн-демо области видимости с направлениями: https://s3.amazonaws.com/jbochi/layout.html
[20] мою статью об расчёте 2d-видимости: http://www.redblobgames.com/articles/visibility/
[21] здесь: http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html
[22] здесь: http://www.roguebasin.com/index.php?title=Pre-Computed_Visibility_Tries
[23] этой странице: http://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html
[24] руководства по поиску пути: http://www.redblobgames.com/pathfinding/a-star/introduction.html
[25] руководство по реализации собственной библиотеки сеток шестиугольников: http://www.redblobgames.com/grids/hexagons/implementation.html
[26] В DevMag есть хороший визуальный обзор математики шестиугольников: http://devmag.org.za/2013/08/31/geometry-with-hex-coordinates/
[27] версия в PDF: http://www.gamelogic.co.za/downloads/HexMath2.pdf
[28] GameLogic Grids: http://gamelogic.co.za/grids/documentation-contents/quick-start-tutorial/gamelogics-hex-grids-for-unity-and-amit-patels-guide-for-hex-grids/
[29] У Джеймса Макнейла есть хорошее визуальное объяснение преобразований сеток: http://playtechs.blogspot.com/2007/04/hex-grids.html
[30] Обзор типов координат шестиугольников: http://web.archive.org/web/20090205120106/http://sc.tri-bit.com/Hex_Grids
[31] Библиотека Rot.js: http://ondras.github.io/rot.js/manual/#hex/indexing
[32] Диапазон в кубических координатах: http://stackoverflow.com/questions/2049196/generating-triangular-hexagonal-coordinates-xyz
[33] Определение расстояний в сетках шестиугольников: http://keekerdc.com/2011/03/hexagon-grids-coordinate-systems-and-distance-calculations/
[34] этом руководстве: http://www.br-gs.com/tutorial/hexagon-grid.html
[35] Преобразование кубических координат шестиугольников в координаты пикселей: http://stackoverflow.com/questions/2459402/hexagonal-grid-coordinates-to-pixel-coordinates
[36] этом посте: http://gamedev.stackexchange.com/questions/51264/get-ring-of-tiles-in-hexagon-grid
[37] HexPart: http://www.webwargaming.org/hexagoncoordinates.shtml
[38] плюсы и минусы у шестиугольников с плоским и острым верхом: http://gamedev.stackexchange.com/questions/49718/vertical-vs-horizontal-hex-grids-pros-and-cons
[39] Линия видимости в сетке шестиугольников: http://arges-systems.com/blog/2011/01/10/hex-grid-line-of-sight-revisited/
[40] соотношение между шестиугольниками и кубами: http://hexnet.org/content/permutohedron
[41] этой страницы: http://incompetech.com/graphpaper/hexagonal/
[42] Обобщённая сбалансированная троичная система счисления: http://www.reddit.com/r/gamedev/comments/19wmvn/a_data_structure_for_a_game_board_with_hexagonal/c8s9qbe
[43] Hex-Grid Utilities: http://hexgridutilities.codeplex.com/documentation
[44] Reddit: http://www.reddit.com/r/gamedev/comments/1dz1tr/
[45] Hacker News: https://news.ycombinator.com/item?id=5809724
[46] MetaFilter: http://www.metafilter.com/128649/Hexagonal-Grids
[47] Haxe: http://haxe.org/
[48] Cube.hx: http://www.redblobgames.com/grids/hexagons/Cube.hx
[49] Hex.hx: http://www.redblobgames.com/grids/hexagons/Hex.hx
[50] Grid.hx: http://www.redblobgames.com/grids/hexagons/Grid.hx
[51] ScreenCoordinate.hx: http://www.redblobgames.com/grids/hexagons/ScreenCoordinate.hx
[52] ui.js: http://www.redblobgames.com/grids/hexagons/ui.js
[53] cubegrid.js: http://www.redblobgames.com/grids/hexagons/cubegrid.js
[54] список на Trello: https://trello.com/card/hexagonal-grids-2-0/4f1dbfdc0fc2508c1b238d7d/52
[55] Источник: https://habrahabr.ru/post/319644/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.