Координатная сетка и расстояния в хексах?

Question

[Сергей]

Есть поле из хексов



Нужно выбрать систему координат (x, y) и посчитать для нее формулу расстояний между двумя хексами.


Посоветуйте вариант который будет ближе всего для человеческого восприятия.

Answer 1

[youngmysteriouslight]

Человек сразу выделяет три направления (см. рисунок ниже). Поэтому можно выбрать косоугольную систему координа (на рисунке: красные линии — горизонтальное направление и наклонное) с углом 60°. Тогда вдоль красных направление соотв. координата будет возрастать, а вдоль голубого — одновременно две. Расстояния между центрами будет вычислятся по формуле

Где Г — матрица Грамма этой косоугольной системы:
Это в случае, когда расстояния между центрами соседей 1.

Comments

[Сергей]

Не совсем вас понял… Осей координат получается две или три?

[Искандер Гиниятуллин]

две оси координат, просто не перпендикулярных.

голубая линия нарисована чтобы пояснить идею как считать координаты точек, которые на ней находятся.

Answer 2

[vinxru]

Использовать стандартную двумерную декартову систему координат. Единственная особенность, есть запрещенные положения.



Плюсы
1) Это понятно и естественно. Даже запрещенные состояния есть в нашем мире (При́нцип Па́ули).
2) Расстояние вычисляется по формуле = sqrt( (x1-x0) ^ 2 + (y1-y0) ^ 2 )
3) Если x1!=x0 и y1!=y0, значит это различные координаты (в отличии от трехкомпонентной системы)

Comments

[Сергей]

На рисунке длина единичного отрезка получается разная по осям X и Y, так что формулу такую для расстояния использовать нельзя.

Но идея интересная :) Особенно, если одну ось на 60° к другой поставить

[vinxru]

Это можно компенсировать поправочным коэффициентом = sqrt( (k*(x1-x0)) ^ 2 + (y1-y0) ^ 2 ).

Answer 3

[Олег Торбасов]

Если под расстоянием Вы понимаете минимальное число переходов между двумя смежными гексами, образующих непрерывный путь от одного гекса к другому, то всё очень просто. Ось абсцисс проводим обычным образом, горизонтально, ось ординат — под углом 60° к ней. Расстояние между гексами (x₁, y₁) и (x₂, y₂) вычисляем следующим образом:

• обозначим для простоты δx = x₂ − x₁ и δy = y₂ − y₁;
• при δy ≥ 0 расстояние ρ ((x₁, y₁), (x₂, y₂)) =
  
  
  • δx + δy, если δx > 0;
  • δy, если − δy ≤ δx ≤ 0;
  • − δx, если δx ≤ − δy.
  
  
• При δy < 0 переставляем точки местами или, что то же самое, переобозначаем δx = − δx и δy = − δy, после чего применяем ту же формулу.

Comments

[Сергей]

Нет. Обычное расстояние, между двумя точками в стандартной прямоугольной системе координат на плоскости

Answer 4

[Виталий Желтяков]

В подобном вопросе «приближение к человеческому варианту» отражается на скорости работы.
Если Вы не извращенец, то будете использовать какой-нибудь алгоритм поиска в ширину. А его, как не странно, оптимально применять над одномерным представлением.

Answer 5

[joger]

для моей игры на Canvas тоже рисовал похожее поле :) с той лишь разницей, что у меня оно повёрнуто на 90 градусов. система координат 2-мерная. Х — как обычно, Y идёт змейкой. чтобы с этим нормально работать приходится Y разделять ещё на чётные и нечётные, но это плата за шестигранники. чтобы определить, куда нажали, пришлось вспомнить тригонометрию, но там всё более-менее просто. самое главное — ничего не забыть :)