[Перевод] Создание сеток шестиугольников23.01.2017 11:03

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

© Habrahabr.ru