Створення сіток шестикутників

image

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

На малюнку максимальні значення виділено кольором. Зауважте також, що кожен колір позначає одну з шести «діагональних» напрямків.

GIF

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

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
точках і обчислюється, в яких шестикутниках знаходяться ці семпли.

GIF

  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)))

Цей цикл проходить лише по потрібним координатами. На малюнку кожен діапазон є парою ліній. Кожна лінія — це нерівність. Ми беремо все шестикутники, що задовольняють шести нерівностям.

GIF

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

Можна підійти до цієї проблеми з точки зору алгебри або геометрії. Алгебраїчно кожна область виражається як умови нерівностей у формі
N ≤ dx ≤ N
, і нам потрібно знайти перетин цих умов. Геометрично кожна область є кубом в тривимірному просторі, і ми перетнемо два куба в тривимірному просторі для отримання прямокутного паралелепіпеда в тривимірному просторі. Потім ми проектуємо його назад на площину
x + y + z = 0
, щоб отримати шестикутники. Я буду вирішувати цю задачу алгебраїчно.

По-перше, ми перепишемо умову
N ≤ dx ≤ N
в більш загальній формі
x<sub>min</sub> ≤ x ≤ x<sub>max</sub>
, і приймемо
x<sub>min</sub> = center.x - N
та
x<sub>max</sub> = 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
, а потім використовувати вкладений цикл для генерування списку шестикутників в перетині. Для однієї області шестикутників ми приймаємо
x<sub>min</sub> = H. x - N
and
x<sub>max</sub> = H. x + N
, аналогічно для
y
та
z
. Для перетину двох областей шестикутників ми приймаємо
x<sub>min</sub> = max(H1.x - N, H2.x - N)
та
x
max = min(H1.x + N, H2.x + N), аналогічно для
y
та
z
. Той же шаблон працює для перетину трьох або більше областей.

GIF

Перешкоди
При наявності перешкод найпростіше виконати заливку з обмеженням по відстані (пошук в ширину). На малюнку нижче ми обмежуємося чотирма ходами. У коді
fringes[k]
— це масив всіх шестикутників, яких можна досягти за
k
кроків. При кожному проході по основному циклу ми розширюємо рівень
k-1
на рівень
k
.

function cube_reachable(start, movement):
var відвідали = set()
add to start 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 відвідали, not blocked:
add neighbor to visited
fringes[k].append(neighbor)

return відвідали






Повороти
Для заданого вектора шестикутника (різницю між двома шестикутниками) нам може знадобитися повернути його, щоб він вказував на інший шестикутник. Це просто зробити, маючи кубічні координати, якщо дотримуватися повороту на 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 для центру. Для обчислення площі використовуйте цю формулу.

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



Область видимості
Що мабуть із заданого стану з заданою відстанню, і не перекривається перешкодами? Найпростіший спосіб визначити це — намалювати лінію до кожного шестикутнику в заданому діапазоні. Якщо лінія не зустрічається зі стінами, то ви бачите шестикутник. Переміщуйте мишу по шестикутник [на схемі в оригіналі статті], щоб побачити малювання ліній до цих шестикутник і стіни, з якими лінії зустрічаються.

Цей алгоритм може бути повільним на великих площах, але його легко реалізувати, тому рекомендую почати з нього.

GIF

Існує багато різних визначень видно. Чи хочете ви бачити центр іншого шестикутника з центру початкового? Чи хочете ви бачити будь-яку частину іншого шестикутника з центру початкового? Може бути, будь-яку частину іншого шестикутника з будь-якої точки початкового? Заважають погляду перешкоди менше повного шестикутника? Область видимості — це більш хитра і різноманітне поняття, ніж здається на перший погляд. Почнемо з найпростішого алгоритму, але чекайте, що він обов'язково правильно розрахувати відповідь у вашому проекті. Бувають навіть випадки, коли простий алгоритм дає нелогічні результати.

керівництві Кларка Вербрюгге описується алгоритм для обчислення області видимості «починаємо з центру і рухаємося назовні». См. також проект 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)

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

Інший підхід: перетворювати координати зміщення в кубічні/осьові координати, потім використовувати перетворення кубічних/осьових координат в пікселі. Завдяки вбудовуванню коду перетворення при оптимізації він в результаті буде таким же, як вище.



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

GIF

  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)
і шістьма його поворотами.

GIF



Пошук шляху
При використанні пошуку шляху на графах, наприклад алгоритму пошуку A*, алгоритму Дейкстри або Флойда-Уоршелла пошук шляху на сітках шестикутників не відрізняється від пошуку шляху на сітках квадратів. Пояснення і код з мого посібники з пошуку шляху застосовні і для сіток шестикутників.



[В оригіналі статті приклад інтерактивний, натисканнями миші можна додавати і видаляти стіни]

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


Додаткове читання
У мене є керівництво по реалізації власної бібліотеки сіток шестикутників з прикладами коду на C++, Java, C#, Javascript, Haxe і Python.

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

Я хочу надалі розширювати це керівництво. У мене є список на Trello.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.