Нахождение кратчайшего пути на гексагональной сетке

14

Я пишу пошаговую игру с элементами симуляции. Одна из задач, над которой я сейчас зациклен, - это поиск пути. Что я хочу сделать, так это перемещать каждый ход ИИ-приключенца на одну клетку ближе к своей цели, используя его текущие x, y и его цель x, y.

Пытаясь понять это самостоятельно, я могу определить 4 направления без проблем, используя

dx = currentX - targetY
dy = currentY - targetY

но я не уверен, как определить, какое из 6 направлений является «лучшим» или «самым коротким» маршрутом.

Например, то, как он настроен в настоящее время, я использую Восток, Запад, NE, NW, SE, SW, но чтобы добраться до тайла NE, я перемещаюсь на восток, затем на NW, вместо того, чтобы просто перемещать NW.

Надеюсь, это было не так просто. Даже одна или две ссылки, чтобы начать, было бы неплохо. Большая часть информации, которую я нашел, касается рисования сеток и создания странной необходимой системы координат.

Тимоти Мэйс
источник
5
A * дает вам кратчайший путь независимо от формы вашего графика (сетка, гекс, произвольная форма ..)
Яри ​​Комппа

Ответы:

21

Несколько ответов!

Система координат, которую я чаще всего видел для обхода на основе гекса, - это система, в которой игрок может двигаться в любом нормальном направлении NSEW, а также в NW и SE. Затем вы просто визуализируете каждую строку на половину квадрата смещения. Например, местоположение (2,7) считается смежным с (1,7), (3,7), (2,6), (2,8), и странными: (1,6) и (3,8). Между тем, если предположить, что (2,7) отображается в центре экрана, (2,6) будет отображаться вверх-вправо, (2,8) будет отображаться вниз-и-до -лево, (1,7) и (3,7) будут заключать его в скобки слева и справа соответственно, а (1,6) и (3,8) будут располагаться сверху-слева и снизу-справа соответственно.

Диаграмма того, что я имею в виду:

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

Если вы делаете это таким образом, то найти кратчайший прямой путь несложно - пройдите максимально возможное расстояние NW / SE, не превышая вашу цель вдоль кардинальной оси, а затем двигайтесь прямо вдоль этой оси к цели.

Но, конечно, это с радостью проведет вас прямо через горы или другие непроходимые местности. Чтобы ответить на вопрос, который вы еще не задавали: Алгоритм поиска A * является распространенным и достаточно хорошим подходом к поиску путей. Он будет обрабатывать не только странные макеты, не связанные с сеткой, но и с удовольствием справится с препятствиями и даже с препятствиями / медленным движением.

ZorbaTHut
источник
Спасибо за ссылку на алгоритм поиска A *. Единственный способ, которым я могу представить возможность пройти nsew и nw / se, это наклонный гекс. Что выглядит странно в моей голове. Можете ли вы связать меня с примером этого?
Тимоти Мэйс
4
Я говорю, что ваше изображение не должно иметь большого сходства с внутренней структурой. Я предлагаю внутренне использовать NSEW и NW / SE, но вы отображаете их пользователю, как если бы это была сетка. Прикрепление пояснительной схемы к исходному ответу :)
ZorbaTHut
2
Интересное представление для шестнадцатеричной сетки. Я обычно делаю зубчатый рисунок, поэтому смежность различна для нечетных и четных рядов. Это вносит дополнительную минимальную сложность в поиск пути, но более эффективно использует двумерный массив (предполагая, что вся игровая зона представляет собой прямоугольник.
Panda Pajama
2
@PandaPajama: jagged работает лучше для эффективного хранения прямоугольных карт; с помощью этого трюка
amitp
2
@PandaPajama, есть еще один интересный трюк, который вы можете использовать: вы можете использовать не зубчатое представление для координат, а затем абстрагировать основу для хранения данных за чем-то, что использует «зубчатый» метод. Я обнаружил, что с системой координат без зазубрин гораздо проще иметь дело, но, конечно, как только она отвлечена, бэкэнд может делать все, что угодно, чтобы сделать вещи эффективнее :)
ZorbaTHut
5

Я только что опубликовал библиотеку утилит с шестигранной сеткой на CodePlex.com здесь: https://hexgridutilities.codeplex.com/ Библиотека включает поиск пути (используя A- * a la Eric Eric Lippert) и включает утилиты для автоматического преобразования между зубчатые (называемые пользователем) координаты и не зубчатые (называемые каноническими) координаты. Алгоритм поиска пути позволяет варьировать стоимость шага для каждого узла как в шестнадцатеричной, так и в шестнадцатеричной частях входа (хотя приведенный пример проще). Также предусмотрено повышенное поле зрения с использованием отбрасывания теней, [править: слова удалены].

Вот пример кода, который легко конвертируется между тремя шестигранными системами координат:

static readonly IntMatrix2D MatrixUserToCanon = new IntMatrix2D(2,1, 0,2, 0,0, 2);
IntVector2D VectorCanon {
  get { return !isCanonNull ? vectorCanon : VectorUser * MatrixUserToCanon / 2; }
  set { vectorCanon = value;  isUserNull = isCustomNull = true; }
} IntVector2D vectorCanon;
bool isCanonNull;

static readonly IntMatrix2D MatrixCanonToUser  = new IntMatrix2D(2,-1, 0,2, 0,1, 2);    
IntVector2D VectorUser {
  get { return !isUserNull  ? vectorUser 
             : !isCanonNull ? VectorCanon  * MatrixCanonToUser / 2
                            : VectorCustom * MatrixCustomToUser / 2; }
  set { vectorUser  = value;  isCustomNull = isCanonNull = true; }
} IntVector2D vectorUser;
bool isUserNull;

static IntMatrix2D MatrixCustomToUser = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
static IntMatrix2D MatrixUserToCustom = new IntMatrix2D(2,0, 0,-2, 0,(2*Height)-1, 2);
IntVector2D VectorCustom {
  get { return !isCustomNull ? vectorCustom : VectorUser * MatrixUserToCustom / 2; }
  set { vectorCustom  = value;  isCanonNull = isUserNull = true; }
} IntVector2D vectorCustom;
bool isCustomNull;

IntMatrix2D и IntVector2D являются целочисленными реализациями affine2D Graphics Vector и Matrix. Окончательное деление на 2 для векторных приложений заключается в повторной нормализации векторов; это может быть скрыто в реализации IntMatrix2D, но тогда причина 7-го аргумента для конструкторов IntMatrix2D менее очевидна. Обратите внимание на комбинированное кэширование и ленивую оценку нетоковых формулировок.

Эти матрицы для случая:

  • Вершина шестигранного зерна;
  • Начало координат слева вверху для канонических и пользовательских координат, слева внизу для пользовательских координат;
  • Ось Y вертикально вниз;
  • Прямоугольная ось X горизонтально поперек; и
  • Каноническая ось Х к северо-востоку (т.е. вверх и вправо, на 120 градусов против часовой стрелки от оси Y).

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

В канонических координатах 6 кардинальных векторов направления равны (1,0), (0,1), (1,1) и их инверсиям для всех шестиугольников без асимметрии зубчатых координат.

Питер Гиркенс
источник
Вот это да! Всего один голос за публикацию библиотеки рабочего кода с примерами и документацией, которая отвечает на вопрос / проблему, поставленную ФП.
Питер Гиркенс
5
Хотя я не был нижестоящим (и этикет, как правило, предлагает оставить комментарий, объясняющий отрицательное голосование), я подозреваю, что отрицательное голосование было вызвано тем, что (а) сообщение перестало звучать как реклама, и (б) поместить большую часть ответа на другой сторона ссылки обычно не одобряется, потому что ссылки имеют тенденцию гнить и сайты SE пытаются быть автономными. Информация, представленная здесь, интересна, но она не отвечает на вопрос пользователя , и единственная информация, которая может ответить на вопрос, находится на другой стороне ссылки.
Стивен Стадницки,
Хорошие моменты; Спасибо. Я расширил этот пост выдержками, которые касаются вопроса о том, как эффективно поддерживать несколько координат шестигранной сетки. Библиотека размещенного кода является бесплатной
Pieter Geerkens
К сожалению! Деление на 2 работает только Ф.О. положительных целых чисел. (Еще раз спасибо, K & R.) Его следует заменить вызовом метода Normalize () в IntVector2D:
Питер Гиркенс
public IntVector2D Normalize() { if (Z==1) return this; else { var x = (X >= 0) ? X : X - Z; var y = (Y >= 0) ? Y : Y - Z; return new IntVector2D(x/Z, y/Z); } }
Питер Гиркенс
0

Это решенная проблема, с большим количеством литературы, чтобы поддержать это. Лучший ресурс, который я знаю, посвящен играм Red Blob: https://www.redblobgames.com/grids/hexagons/ .

Короче говоря, наиболее вероятной причиной является то, что вы начали с неправильной системы координат. Использовать систему координат Cube, реализующую алгоритм A *, довольно просто. Смотрите демо-версию по ссылке выше.

Если вы действительно хотите использовать какую-то другую систему, то при необходимости конвертируйте в и из.

david.pfx
источник