Поиск пути на гексагональной сетке

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

И так что у нас уже есть:
Поиск на обычной прямоугольной сетке.
Что нам надо:
Поиск по гексагональной сетке с минимальными усилиями.

Общая структура сетки

Первая же идея просто через столбец все сместить:
image
Тогда соседи текущей клетки выглядят примерно так:
image
Как видно, связи между клетками по идее должны образовывать как раз гекс:
image
Но сразу же закрадывается подозрения, что тут должны быть совсем не квадраты, а прямоугольники:
image
Как не трудно посчитать k на рисунке будет равно sqrt(3)/2
В результате получаем сетку
image
Где размеры каждой клетки соотвествено w=sqrt(3)/2, h= 1, при это каждый нечетный столбец(если начинать отсчет с 0) смещен на 0,5

Трансформация координат

Дальше все идет проще, чтобы перевести координаты в номер клетки с поправкой на четный/нечетный столбец:
(x,y)=>(x/w, (y-(x/w)%2)/h)
Чтобы наоборот, клетку поля перевести в координаты:
(i,k)=>(i*w, k*h+h/2*(i%2))

Соседи

Теперь нам надо получить всех соседей выбранной клетки.
Они будут выглядеть примерно так, для четных столбцов(и симметрично для нечетных).
image

(i,k)=>(
(i+1,k),
(i-1,k),
(i,k+1),
(I,k-1),
(i+1,k+(1-2*i%2)),
(i-1,k+(1-2*i%2)))


Расстояние между двумя клетками

Теперь для полноценной реализации не хватает только способа нахождения расстояния между двумя клетками, можно конечно использовать банально Евклида, но это не наш вариант. За базовую основу возьмем диагональное расстояние на обычной сетке:
xd = abs(p1.X - p2.X);
yd = abs(p1.Y - p2.Y);
diagonal = min(xd, yd);
straight = xd + yd;
result = sqrt(2) * diagonal + (straight - (2 * diagonal)));


У нас ситуация ситуация похожая(тоже есть диагональные ходы), только чтобы сместится по вертикали(рассматривая ориентацию сетки как в примере), можно либо сделать один шаг по вертикали, либо 2 по горизонтали.
//если хватает горизонтального расстояния
if (xd >= yd * 2)
{
result = xd;
}
//если всеже придется идти строго вверх
else
{
result = xd + (yd – xd/2);
}

Но и тут есть маленькая деталь, если расстояние измеряется между двумя клетками из разных столбцов, то там будет еще не учтенное смещение в пол клетки. Поэтому yd надо определять чуть иначе:
yd =abs((p1.Y + (p1.X%2)/2) – (p2.Y + (p2.X%2)/2));

Теперь осталось натравить A* на это все, например как я это сделал тут, и тадам:
image

Вместо послесловия

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

Подробнее
Реклама
Комментарии 24
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Этот рисунок аппроксимирует нарисованное на сетку, судя по всему
      • 0
        К слову сказать вы правы, это был баг в оптимизации(точнее в предположении), что я могу помещать посещаемую точку сразу в список закрытых(даже еще не обработав её).
        • НЛО прилетело и опубликовало эту надпись здесь
          • +1
            Потому что поверху он считается заблокированным, почему сверху посчитался заблокированным а снизу такая же клетка — нет, думаю проблема где-то с округлением просто
      • +1
        Периодически создаётся ощущение, что написание всяческого рода костылей и велосипедов программисту доставляет гораздо больше, чем использование кладезя человеческой мудрости, накопленной за года придумывания алгоритмов людьми.
        • +2
          Написание своих велосипедов лично мне помогает разобраться и понять эти самые кладези. Плюс, судя потому что видел много разных представлений и трансформаций, единой общепринятой практики нету для этого случая(возможно ошибаюсь и сходу не распознал общей простой идеи, тогда буду благодарен за разъяснения на пальцах).
          А в этом велосипеде мне нравится, что он получился локальным(все изменения, не выходят далеко за пределы клетки) и простым (минимум лишнего умножения и деления на что-то, отличное от 2)
        • +2
          Я конечно рискую схватить минусов, но вы пробовали к примеру узнать об A*? В своё время я, разрабатывая поиск пути для Pocket Fallout, переизобрёл этот алгоритм и несколько жалел о потраченном времени, которое могло бы быть потрачено на более полезные штуки.
          И не надо заводить речь про «сложную математику», ибо при желании этот алгоритм разбирается на ура, даже не очень сведущими в теории графов людьми.
          • 0
            Так именно A* и использовался здесь, поэтому в конце и написано:
            «Теперь осталось натравить A* на это все, например как я это сделал тут...»
            Статья вообще о том как легко привести обычную сетку к гексагональной, как раз в контексте использования её A*. Ведь все что требуется алгоритму поиску пути на основании алг. Дейкстры, если задуматься, это: перевод координаты в вершину, вершину в координаты, взять все дуги конкретной вершины, плюс для A* еще эстимация расстояния между двумя врешинами. Вот как раз один из способов реализация этих методов и расписан.
            • 0
              Ясно, просто после диагонального прочтения мне показалось, что вы сделали свой алгоритмический велосипед для поиска пути на гексагональной сетке.

              P.S.: Всё-таки, на мой взгляд, удобнее производить преобразование по наклонённым осям (т.е. квадратная по координатам карта будет рисоваться не квадратом, а ромбом), в общем, смотрите классику в виде первого и второго Fallout'а.
              • 0
                Вот этот кстати пункт, что квадратная карта будет рисоваться ромбом, меня тоже насторожил, во первых уж сильно все преобразуется, а во-вторых, адресация памяти может стать сложнее (так двумерном массиве x+y*width вот тебе и элемент в массиве, а как там надо еще смотреть). Возможно зря боюсь, надо просто сесть и разобраться, но у меня был на руках поиск по обычной сетке, и пришла идея как быстро и просто сделать из него поиск по гексагнальной… попробовал, получилось, вот и решил поделится.
          • +1
            А всего напросто, достаточно было изменить функцию поиска соседей (которая кстати простейшая) в любом из алгоритмов поиска пути, и не придумывать никакие отображения гексагонов в параллелепипеды… Вычисление расстояний между клетками вообще ужас, так как расстояние между соседними гексоганальными клетками одинаковое
            • 0
              Пардон, конечно, параллелограммы
              • 0
                Уф. Пойдем по порядку:
                Функция поиска соседей вообще-то зависит от представления данных, и для конкретного этого случая она действительно простейшая (и была приведена);
                Отображение гексагонов было в прямоугольники(тоже простейшие) и нужно было именно для того, чтобы могли перевести обычные координаты в конкретный гексагон и обратно (а иначе пользы от всего этого, если даже не можем определить по какому из них только что мышкой тыкнули?)
                Про одинаковое расстояние между соседями согласен, вот только расстояния мы измеряем не между соседями, а между любыми двумя гексами (это опять же, потому что используем A*, где необходима нижняя оценка оставшегося пути до цели, а не просто Дейкстру)
                • 0
                  1 В данном случае речь идет о двумерном массиве.
                  2 Вычислить клетку, на которую кликнул пользователь не составляет особого труда даже без представления клетки, как прямоугольника, что кстати является крайне не точной аппроксимацией, для этого достаточно знать ширину и длину клетки.
                  3 Для А* достаточно знать расстояние между двумя соседними клетками (и то это в том случае если у вас переход между клетками не равен 1)
                  • 0
                    1. И все же, я так и не понял что именно в поиске соседей описанном мною, вам не понравилось? И что можно было сделать в нем еще проще?
                    2. Но наличие ширины и длины у клетки, как раз и делает ее прямоугольником, опять же, если я что-то перемудрил с представлением клетки, буду рад услышать как можно проще вычислить клетку на которую кликнули.
                    3. Мне кажется, вы путаете A* с алгоритмом Дейкстры, знать расстояние между соседними достаточно только для оригинального алгоритма Дейкстры, для A* нам нужно еще уметь ранжировать текущие открытые вершины. Чаще всего для этого используется f(x) = g(x) + h(x), где g(x) длина пройденного пути, h(x)- оптимистичная оценка оставшегося пути. Вот именно для h(x) — и нужно знать расстояния между не соседними клетками.
                    • 0
                      1 Изначально я написал, что мне не понравилось представление гексагональной сетки в виде прямоугольной.
                      2 Наличие ширины и длины не делает клетку прямоугольной, так как она гексагональная изначально. И как мне кажется, x/w не даст правильную координату х, потому что при клике в крайние «треугольные области» клетки точно нельзя сказать куда кликнул пользователь.
                      • 0
                        1. Изначально написали% «достаточно было изменить функцию поиска соседей (которая кстати простейшая) в любом из алгоритмов поиска пути»- но как сделать легко и просто в вашем понимании я пока так и не понял.
                        2. Да, я прекрасно понимаю, что это только аппроксимация, но если учесть на сколько она проста, и какая у нее ошибка, то компромисс как по мне достаточно хорош, чтобы иметь право на жизнь.

                        Вообще(по моему личному убеждению) одно из главных качеств ориентированных на игры программистов- это как раз уметь увидеть и сделать адекватную аппроксимацию какой-либо модели
                        • 0
                          1 Ну с описанным вами способом я согласен.
                          2 С учетом того, что эти области занимают чуть ли не четверть клетки, я бы не назвал это удачной аппроксимацией.
                          • 0
                            2. В вас говорит или заядлый математик, или идеалист-программист:-)
                            Да, погрешность 1/8 клетки в сумме получается, может это и много (особенно если гексы большие), но именно свойство локальности изменений, позволяет при необходимости большей точности, дописать к ней дополнения, учитывающие и эти крайние треугольники.
                            • 0
                              На мой взгляд, это не настолько сложная задача, что бы сразу ее сделать правильно, что даст максимальный комфорт пользователю, так как он будет тыкать куда считает нужным и точно знать, что при этом произойдет. И идеализм тут не причем, это обычное юзабилити. Т.к. я с 100% уверенностью могу сказать, что после 5-10 кликов после, которых следует неверное поведение, пользователь просто забьет.
                              • 0
                                К слову сказать, такую аппроксимацию (или похожую на эту) тоже достаточно много описывают, например даже тут:
                                www-cs-students.stanford.edu/~amitp/game-programming/grids/
                                Но вообщем то, каждый сам решает какая ему точность нужна :-)
            • 0
              А чистый алгоритм Дейкстры вам чем не угодил?
              • 0
                A* -это расширение над над алгоритмом Дейкстры, и позволяет достичь в общем случае лучшей производительности и (при правильной эвристике) сделать это без потери качества.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.