Создание сеток шестиугольников

Сетки из шестиугольников (гексагональные сетки) используются в некоторых играх, но они не так просты и распространены, как сетки прямоугольников. Я коллекционирую ресурсы о сетках шестиугольников уже почти 20 лет, и написал это руководство по самым элегантным подходам, реализуемым в простейшем коде. В статье часто используются руководства Чарльза Фу (Charles Fu) и Кларка Вербрюгге (Clark Verbrugge). Я опишу различные способы создания сеток шестиугольников, их взаимосвязь, а также самые общие алгоритмы. Многие части этой статьи интерактивны: выбор типа сетки изменяет соответствующие схемы, код и тексты. (Прим. пер.: это относится только к оригиналу, советую его изучить. В переводе вся информация оригинала сохранена, но без интерактивности.).

Примеры кода в статье написаны псевдокодом, так их легче читать и понимать, чтобы написать свою реализацию.

Геометрия

Шестиугольники — это шестигранные многоугольники. У правильных шестиугольников все стороны (грани) имеют одинаковую длину. Мы будем работать только с правильными шестиугольниками. Обычно в сетках шестиугольников используются горизонтальная (с острым верхом) и вертикальная (с плоским верхом) ориентации.

Шестиугольники с плоским (слева) и острым (справа) верхом

У шестиугольников по 6 граней. Каждая грань общая для двух шестиугольников. У шестиугольников по 6 угловых точек. Каждая угловая точка общая для трёх шестиугольников. Подробнее о центрах, гранях и угловых точках можно прочитать в моей статье о частях сеток (квадратах, шестиугольниках и треугольниках).

Углы

В правильном шестиугольнике внутренние углы равны 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. Это странная мысль, но она поможет нам упростить алгоритмы сеток шестиугольников. В частности, мы сможем воспользоваться стандартными операциями из декартовых координат: суммированием и вычитанием координат, умножением и делением на скалярную величину, а также расстояниями.

Заметьте три основные оси на сетке кубов и их соотношение с шестью диагональными направлениями сетки шестиугольников. Диагональные оси сетки соответствуют основному направлению сетки шестиугольников.

Шестиугольники

Кубы

Поскольку у нас уже есть алгоритмы для сеток квадратов и кубов, использование кубических координат позволяет нам адаптировать эти алгоритмы под сетки шестиугольников. я буду использовать эту систему для большинства алгоритмов статьи. Для использования алгоритмов с другой системой координат я преобразую кубические координаты, выполню алгоритм, а затем преобразую их обратно.

Изучите, как кубические координаты работают для сетки шестиугольников. При выборе шестиугольников выделяются кубические координаты, соответствующие трём осям.

1. Каждое направление сетки кубов соответствует линии на сетке шестиугольников. Попробуйте выделить шестиугольник с z, равным 0, 1, 2, 3, чтобы увидеть связь. Строка отмечена синим. Попробуйте то же самое для x (зелёный) и y (сиреневый).
2. Каждое направление сетки шестиугольника — это сочетание двух направлений сетки кубов. Например, «север» сетки шестиугольников лежит между +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 (побитовое «И») вместо a%2 (деления с остатком) для определения, является ли число чётным (0) или нечётным (1). Подробное описание см. на странице примечаний к моей реализации.

Соседние шестиугольники

Дан один шестиугольник, с какими шестью шестиугольниками он находится рядом? Как и можно ожидать, легче всего дать ответ в кубических координатах, довольно просто в осевых координатах, и немного сложнее в координатах смещения. Также может потребоваться рассчитать шесть «диагональных» шестиугольников.

Кубические координаты

Перемещение на одно пространство в координатах шестиугольников приводит к изменению одной из трёх кубических координат на +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) столбцов

Использование вышеуказанных таблиц подстановки — это простейший способ вычисления соседей. Если вам интересно, можно также почитать об извлечении этих чисел.

Диагонали

Перемещение в «диагональном» пространстве в координатах шестиугольников изменяет одну из трёх кубических координат на ±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 в сетке кубов. Это делает расчёт расстояний простым. В сетке квадратов манхэттенские расстояния равны 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))

На рисунке максимальные значения выделены цветом. Заметьте также, что каждый цвет обозначает одно из шести «диагональных» направлений.

Осевые координаты

В осевой системе третья координата выражена неявно. Давайте преобразуем из осевой в кубическую систему для расчёта расстояния:

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

Существует множество различных способов записи расстояний между шестиугольниками в осевых координатах, но вне зависимости от способа записи расстояние между шестиугольниками в осевой системе извлекается из манхэттенского расстояния в кубической системе. Например, описанная здесь «разность разностей» получается из записи a.q + a.r - b.q - b.r как a.q - b.q + a.r - b.r и с использованием формы максимального значения вместо формы деления пополам cube_distance. Все они аналогичны, если увидеть связь с кубическими координатами.

Координаты смещения

Как и в случае с осевыми координатами, мы преобразуем координаты смещения в кубические координаты, а затем используем расстояние кубической системы.

function offset_distance(a, b):
    var ac = offset_to_cube(a)
    var bc = offset_to_cube(b)
    return cube_distance(ac, bc)

Мы будем использовать тот же шаблон для многих алгоритмов: преобразуем из шестиугольников в кубы, выполняем кубическую версию алгоритма и преобразуем кубические результаты в координаты шестиугольников (осевые или координаты смещения).

Отрисовка линий

Как нарисовать линию от одного шестиугольника до другого? Я использую линейную интерполяцию для рисования линий. Линия равномерно сэмплируется в N+1 точках и вычисляется, в каких шестиугольниках находятся эти сэмплы.

1. Сначала мы вычисляем N, которое будет расстоянием в шестиугольниках между конечными точками.
2. Затем равномерно сэмплируем N+1 точек между точками A и B. С помощью линейной интерполяции определяем, что для значений i от 0 до N, включая их, каждая точка будет A + (B - A) * 1.0/N * i. На рисунке эти контрольные точки показаны синим. В результате получаются координаты с плавающей запятой.
3. Преобразуем каждую контрольную точку (float) обратно в шестиугольники (int). Алгоритм называется 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) к одной или обеим конечным точкам перед началом цикла. Это «подтолкнёт» линию в одном направлении, чтобы она не попадала на границы граней.
• Алгоритм DDA-линии в сетках квадратов приравнивает N к максимуму расстояния по каждой из осей. Мы делаем то же самое в кубическом пространстве, что аналогично расстоянию в сетке шестиугольников.
• Функция cube_lerp должна возвращать куб с координатами в float. Если вы программируете на языке со статической типизацией, то не сможете использовать тип Cube. Вместо него можно определить тип FloatCube или встроить (inline) функцию в код отрисовки линий, если вы не хотите определять ещё один тип.
• Можно оптимизировать код, встроив (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) и xmax = 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:

1. Преобразование положений P и C в кубические координаты.
2. Вычисление вектора вычитанием центра: P_from_C = P - C = Cube(P.x - C.x, P.y - C.y, P.z - C.z).
3. Поворот вектора P_from_C как описано выше и присваивание итоговому вектору обозначения R_from_C.
4. Преобразование вектора обратно в положение прибавлением центра: R = R_from_C + C = Cube(R_from_C.x + C.x, R_from_C.y + C.y, R_from_C.z + C.z).
5. Преобразование кубического положения R обратно в нужную систему координат.

Здесь несколько этапов преобразований, но каждый из них довольно прост. Можно сократить некоторые из этих этапов, определив поворот непосредственно в осевых координатах, но векторы шестиугольников не работают с координатами смещения, и я не знаю, как сократить этапы для координат смещения. См. также обсуждение других способов вычисления поворота на 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 для центра. Для вычисления площади используйте эту формулу.

Обход шестиугольников таким способом можно также использовать для вычисления диапазона перемещения (см. выше).

Область видимости

Что видимо из заданного положения с заданным расстоянием, и не перекрывается препятствиями? Простейший способ определить это — нарисовать линию к каждому шестиугольнику в заданном диапазоне. Если линия не встречается со стенами, то вы видите шестиугольник. Перемещайте мышь по шестиугольникам [на схеме в оригинале статьи], чтобы увидеть отрисовку линий к этим шестиугольникам и стены, с которыми линии встречаются.

Этот алгоритм может быть медленным на больших площадях, но его легко реализовать, поэтому рекомендую начать с него.

Существует много разных определений видимости. Хотите ли вы видеть центр другого шестиугольника из центра начального? Хотите ли вы видеть любую часть другого шестиугольника из центра начального? Может быть, любую часть другого шестиугольника из любой точки начального? Мешающие взгляду препятствия меньше полного шестиугольника? Область видимости — это более хитрое и разнообразное понятие, чем кажется на первый взгляд. Начнём с простейшего алгоритма, но ждите, что он обязательно правильно вычислит ответ в вашем проекте. Бывают даже случаи, когда простой алгоритм даёт нелогичные результаты.

В руководстве Кларка Вербрюгге описывается алгоритм для вычисления области видимости «начинаем с центра и двигаемся наружу». См. также проект Duelo, у которого есть на Github онлайн-демо области видимости с направлениями. Также можете прочитать мою статью об расчёте 2d-видимости, в ней есть алгоритм, работающий с многоугольниками, в том числе и с шестиугольниками. У сообщества любителей roguelike есть хороший набор алгоритмов для сеток квадратов (см. здесь, здесь и здесь). Некоторые из них можно адаптировать под сетки шестиугольников.

Шестиугольники в пиксели

Для перевода из шестиугольников в пиксели полезно изучить схему размеров и расположения, представленную в разделе «Геометрия». В случае осевых координат к преобразованию из шестиугольников в пиксели надо подходить, рассматривая базисные векторы. На схеме стрелка 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)

К сожалению, координаты смещения не имеют базисных векторов, которые можно использовать вместе с матрицей. Это одна из причин того, почему преобразования из пикселей в шестиугольники сложнее в координатах смещения.

Другой подход: преобразовывать координаты смещения в кубические/осевые координаты, затем использовать преобразование кубических/осевых координат в пиксели. Благодаря встраиванию кода преобразования при оптимизации он в результате будет таким же, как выше.

Из пикселей в шестиугольники

Один из самых частых вопросов заключается в том, как взять положение пикселя (например, щелчка мыши) и преобразовать его в координату сетки шестиугольников? Я покажу, как это делается для осевых или кубических координат. Для координат смещения проще всего будет преобразовать в конце кубические координаты в координаты смещения.

1. Сначала мы инвертируем преобразование из шестиугольника в пиксели. Это даст нам дробные координаты шестиугольника, показанные на рисунке маленьким синим кругом.
2. Затем мы определим шестиугольник, содержащий дробную координату шестиугольника. Он показан на рисунке подсвеченным шестиугольником.

Для преобразования координат шестиугольников в координаты пикселей мы умножили 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))).

Существует множество других способов преобразования пикселей в шестиугольники. На этой странице перечислены известные мне.

Округление до ближайшего шестиугольника

Иногда у нас получается кубическая координата (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 для получения трёх чисел с плавающей точкой в качестве входных данных вместо определения нового типа только для этой функции.

Хранение карт в осевых координатах

Чаще всего осевая система координат вызывает жалобы потому, что приводит к ненужному расходованию пространства при использовании прямоугольных карт. Это одна из причин в пользу системы координат смещения. Однако все системы координат шестиугольников приводят к расходу пространства при использовании треугольных или шестиугольных карт. Мы можем использовать одну стратегию для хранения всех этих типов карт.

Прямоугольная карта

Треугольная карта

Шестиугольная карта

Ромбовидная карта

Заметьте на схеме, что неиспользуемое пространство находится справа и слева от каждой строки (за исключением ромбовидных карт). Это даёт нам три варианта стратегий хранения карты:

1. Игнорировать проблему. Использовать сплошной массив с нулями или другими индикаторами неиспользуемого пространства. Для этих стандартных форм карт неиспользуемое пространство может занимать максимум половину массива. Возможно, использование более сложных решений нерационально.
2. Использовать вместо сплошного массива хеш-таблицу. Это позволяет использовать карты произвольной формы, в том числе и с отверстиями. Когда нужно получить доступ к шестиугольнику в q,r мы вместо этого получаем доступ к hash_table(hash(q,r)). Инкапсулируем её в геттер/сеттер в классе сетки, чтобы остальная часть игры не должна была знать о ней.
3. Сместить строки влево и использовать строки с переменным размером. Во многих языках двухмерный массив является массивом массивов. Массивы необязательно должны быть одной длины. Это позволяет избавиться от неиспользуемого пространства справа. Кроме того, если начинать массивы с самого левого столбца вместо 0, то удалится неиспользуемое пространство слева.

   Чтобы применить эту стратегию в произвольных выпуклых картах, необходимо хранить дополнительный массив «первых столбцов». Когда нужно получить доступ к шестиугольнику в 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*, алгоритма Дейкстры или Флойда-Уоршелла поиск пути на сетках шестиугольников не отличается от поиска пути на сетках квадратов. Пояснения и код из моего руководства по поиску пути применимы и для сеток шестиугольников.

[В оригинале статьи пример интерактивен, нажатиями мыши можно добавлять и удалять стены]

1. Соседи. Пример кода, представленный в руководстве по поиску пути, вызывает для получения соседних с положением элементов graph.neighbors. Используйте для этого функцию в разделе «Соседние шестиугольники». Отфильтровывайте непроходимые соседние шестиугольники.
2. Heuristic. В примере кода алгоритма A* используется функция heuristic, получающая расстояние между двумя положениями. Используйте формулу расстояний, умноженную на затраты на передвижение. Например, если перемещение стоит 5 единиц на шестиугольник, то умножайте расстояние на 5.

Дополнительное чтение

У меня есть руководство по реализации собственной библиотеки сеток шестиугольников с примерами кода на C++, Java, C#, Javascript, Haxe и Python.

• В моём руководстве по сеткам я рассматриваю осевые системы координат и обработку граней и углов квадратов, треугольников и шестиугольников. Также я объясняю, как связаны сетки квадратов и шестиугольников.
• Лучшим ранним руководством, которое я видел, стало руководство Кларка Вербрюгге, написанное в 1996 году.
• Впервые я увидел кубическую систему координат в посте 1994 года Чарльза Фу в rec.games.programmer.
• В DevMag есть хороший визуальный обзор математики шестиугольников, включая способы представления площадей, таких как полуплоскости, треугольники и четырёхугольники. Существует версия в PDF, которая немного подробнее. Крайне рекомендуется к изучению! Библиотека GameLogic Grids реализует эти и многие другие типы сеток в Unity.
• У Джеймса Макнейла есть хорошее визуальное объяснение преобразований сеток.
• Обзор типов координат шестиугольников: ступенчатых (со смещением), чередуемых, трёхмерных (кубических) и трапецеидальных (осевых).
• Библиотека Rot.js содержит список систем координат шестиугольников: неортогональной (осевой), с нечётным сдвигом (со смещением), двойной ширины (чередуемой), кубической.
• Диапазон в кубических координатах: какие шестиугольники находятся на заданном расстоянии от заданного?
• Определение расстояний в сетках шестиугольников с помощью кубических координат и объяснение причин использования кубических координат вместо координат смещения.
• В этом руководстве объясняются основы измерения и отрисовки шестиугольников с помощью сетки смещения.
• Преобразование кубических координат шестиугольников в координаты пикселей.
• В этом посте объясняется, как генерировать кольца.
• В системе HexPart используются как шестиугольники, так и прямоугольники для упрощения работы с некоторыми алгоритмами.
• Есть ли плюсы и минусы у шестиугольников с плоским и острым верхом?
• Линия видимости в сетке шестиугольников с координатами смещения, разделение шестиугольников на треугольники. [Нерабочая ссылка]
• Hexnet объясняет, что соотношение между шестиугольниками и кубами намного глубже, чем я описал в этой статье, и обобщает связь до большего количества измерений.
• Я использовал PDF с сетками шестиугольников с этой страницы, когда работал над некоторыми алгоритмами.
• Обобщённая сбалансированная троичная система счисления для координат шестиугольников выглядит интересно; я пока не изучал её.
• Hex-Grid Utilities — это библиотека C# с открытым исходным кодом для математики сеток шестиугольников с определением соседних шестиугольников, сетками, поиском диапазонов и путей, областью видимости. Лицензия MIT.
• В обсуждениях на Reddit, Hacker News и MetaFilter есть больше комментариев и ссылок.

Код [оригинала] этой статьи написан на смеси Haxe и Javascript: Cube.hx, Hex.hx, Grid.hx, ScreenCoordinate.hx, ui.js и cubegrid.js (для анимации кубов/шестиугольников). Однако если вы хотите написать свою библиотеку сеток шестиугольников, то рекомендую вместо этого кода изучить моё руководство по реализации.

Я хочу в дальнейшем расширять это руководство. У меня есть список на Trello.

Автор: PatientZero

Источник