Получить кольцо плиток в шестиугольной сетке

17

Благодаря этому сообщению: шестиугольные плитки и находя их соседних соседей , я могу собрать соседние плитки к данной плитке. Но я в значительной степени застрял в алгоритме, который дает мне только «кольцо» плиток, указанных смещением. Алгоритм, приведенный в этом посте Stack Overflow, не совсем заботит порядок, в котором он собирает тайлы.

Я знаю, что с каждым смещением добавляются 6 плиток.

  • Смещение 1 дает вам 6 плиток (первые смежные плитки).
  • Смещение 2 дает вам 12.
  • Смещение 3 дает 18 и т. Д.

Существует постоянный рост 6 с каждым смещением. Поэтому я предполагаю, что должно быть правило, которое адаптируется к этим смещениям. Я не могу точно понять это. Кто-нибудь?

Sidar
источник

Ответы:

23

Шестиугольное кольцо с радиусом N состоит из 6 прямых линий, каждая из которых имеет длину N - см. Мой чрезвычайно грубый пример ниже :) Для N = 2:

введите описание изображения здесь

Стрелки покрывают 2 гекса каждый.

Я предполагаю, что у вас есть некоторые функции, которые дают соседний тайл в определенном направлении, например, север (), юго-восток () и т. Д. Таким образом, ваш алгоритм в псевдокоде должен выглядеть примерно так:

var point = startingPoint.north(N)
for i = 0..N-1:
    result.add(point)
    point = point.southeast(1);
for i = 0..N-1:
    result.add(point)
    point = point.south(1);
for i = 0..N-1:
    result.add(point)
    point = point.southwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.northwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.north(1);
for i = 0..N-1:
    result.add(point)
    point = point.northeast(1);

Обратите внимание, что это должно работать и для краевых случаев N = 1, возвращающих 6 плиток, и N = 0, возвращающих пустой набор.

Я знаю, что код не идеален :) Здесь есть некоторая избыточность. В моих проектах, использующих регулярные мозаичные карты (шестиугольные или иные), у меня обычно есть перечисление «Направление», которое позволяет мне делать это более плавно:

var point = startingPoint.inDir(N, Direction.North)
var dir = Direction.SouthEast.
for d = 0..Direction.count():
    for i = 0..N-1:
        result.add(point)
        point = point.inDir(1, dir);
    dir = nextDirection(dir);
Liosan
источник
Это должно подтолкнуть меня в правильном направлении. Благодарность!
Сидар
2
Обратите внимание, что образец кода добавит дубликаты точек для первых пяти сегментов. Тем не менее, это хороший ответ.
MichaelHouse
@ Byte56 Да, я понял. Но, по крайней мере, я вижу связь между сдвигами в направлении!
Сидар
1
@ Byte56 Правда? Гектометр Я пытался избежать этого ... 0..N-1 дает 0..1 для N = 2, так что это i = 0 и i = 1, что составляет 2 значения. 2 значения с каждого раза 6 направлений это 12 плиток, как и должно быть ...?
Лиосан
Нет. Ты прав. Так как каждый цикл добавляет точку из последнего цикла, я был отключен на один для циклов, моя ошибка. Это умный алгоритм.
MichaelHouse
2

Я нашел эту статью очень хорошим справочником по алгоритмам гексагональной сетки, а ее раздел «Расстояния» предоставляет метод для определения количества шагов между двумя тайлами. Если вы конвертируете осевые координаты (xy) в координаты куба (xyz), расстояние всегда равно наибольшему из смещений координат между двумя плитками или max (| dx |, | dy |, | dz |).

О(N2)

введите описание изображения здесь

KPM
источник