Я пишу пошаговую игру с элементами симуляции. Одна из задач, над которой я сейчас зациклен, - это поиск пути. Что я хочу сделать, так это перемещать каждый ход ИИ-приключенца на одну клетку ближе к своей цели, используя его текущие x, y и его цель x, y.
Пытаясь понять это самостоятельно, я могу определить 4 направления без проблем, используя
dx = currentX - targetY
dy = currentY - targetY
но я не уверен, как определить, какое из 6 направлений является «лучшим» или «самым коротким» маршрутом.
Например, то, как он настроен в настоящее время, я использую Восток, Запад, NE, NW, SE, SW, но чтобы добраться до тайла NE, я перемещаюсь на восток, затем на NW, вместо того, чтобы просто перемещать NW.
Надеюсь, это было не так просто. Даже одна или две ссылки, чтобы начать, было бы неплохо. Большая часть информации, которую я нашел, касается рисования сеток и создания странной необходимой системы координат.
источник
Ответы:
Несколько ответов!
Система координат, которую я чаще всего видел для обхода на основе гекса, - это система, в которой игрок может двигаться в любом нормальном направлении 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 * является распространенным и достаточно хорошим подходом к поиску путей. Он будет обрабатывать не только странные макеты, не связанные с сеткой, но и с удовольствием справится с препятствиями и даже с препятствиями / медленным движением.
источник
Я только что опубликовал библиотеку утилит с шестигранной сеткой на CodePlex.com здесь: https://hexgridutilities.codeplex.com/ Библиотека включает поиск пути (используя A- * a la Eric Eric Lippert) и включает утилиты для автоматического преобразования между зубчатые (называемые пользователем) координаты и не зубчатые (называемые каноническими) координаты. Алгоритм поиска пути позволяет варьировать стоимость шага для каждого узла как в шестнадцатеричной, так и в шестнадцатеричной частях входа (хотя приведенный пример проще). Также предусмотрено повышенное поле зрения с использованием отбрасывания теней, [править: слова удалены].
Вот пример кода, который легко конвертируется между тремя шестигранными системами координат:
IntMatrix2D и IntVector2D являются целочисленными реализациями affine2D Graphics Vector и Matrix. Окончательное деление на 2 для векторных приложений заключается в повторной нормализации векторов; это может быть скрыто в реализации IntMatrix2D, но тогда причина 7-го аргумента для конструкторов IntMatrix2D менее очевидна. Обратите внимание на комбинированное кэширование и ленивую оценку нетоковых формулировок.
Эти матрицы для случая:
Упомянутая выше библиотека кода обеспечивает такой же элегантный механизм для выбора гексагона (т. Е. Для идентификации гексагона, выбранного с помощью щелчка мыши).
В канонических координатах 6 кардинальных векторов направления равны (1,0), (0,1), (1,1) и их инверсиям для всех шестиугольников без асимметрии зубчатых координат.
источник
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); } }
Это решенная проблема, с большим количеством литературы, чтобы поддержать это. Лучший ресурс, который я знаю, посвящен играм Red Blob: https://www.redblobgames.com/grids/hexagons/ .
Короче говоря, наиболее вероятной причиной является то, что вы начали с неправильной системы координат. Использовать систему координат Cube, реализующую алгоритм A *, довольно просто. Смотрите демо-версию по ссылке выше.
Если вы действительно хотите использовать какую-то другую систему, то при необходимости конвертируйте в и из.
источник