Алгоритм поиска пути
Модераторы: Sanja, Максим Кич
Алгоритм поиска пути
Наткнулся на хабре на интересный алгоритм:https://habrahabr.ru/post/162915/
Кто-нибудь его реализовывал/разбирал? Если да, то поделитесь опытом, реально перевести его в хексы при случае?
Кто-нибудь его реализовывал/разбирал? Если да, то поделитесь опытом, реально перевести его в хексы при случае?
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Re: Алгоритм поиска пути
Навскидку нагуглил (на вражеском):Darkness писал(а): ↑10 мар 2017, 18:15Наткнулся на хабре на интересный алгоритм:https://habrahabr.ru/post/162915/
Кто-нибудь его реализовывал/разбирал? Если да, то поделитесь опытом, реально перевести его в хексы при случае?
Скрытый текст: ПОКАЗАТЬ
Так что это должно быть элементарной задачей для любого, кто закончил институт по специальности «Математик-теоретик» и при этом не сжёг себе мозги.«Вершинно-транзитивные графы — это один из способов представить «равномерную сетку». Чтобы представить двухмерную прямоугольную сетку, вы можете дать представление группы, вроде «Есть четыре направления: север, юг, восток и запад. Шаг на север после шага на юг вернёт вас на исходную. Шаг на восток после шага на запад вернёт вас на исходную, и наг на северозапад после юговостока вернёт вас на исходную» (На самом деле, вы скажете, что у каждого направления есть обратное, потому что это группа, и поэтому будет два генератора и одно слово (??? возможно опечатка, и это «один мир»), но теория групп может оказаться слишком жёсткой и вы захотите полугруппы или моноиди — я просто хочу показать, что равномерные сетки можно описывать по-разному.
Гексагональная сетка может быть представлена тремя генераторами, каждый со своим обратным направлением, и которые идут вокруг шестиугольника (abcabc) попарно возвращая на исходную. Так же легко создать гиперболические сетки. Например, группа треугольника (2,3,7) может быть описана как имеющая два генератора x и у, так что на исходную вернут сочетания xx, yyy или (xy)^7. Вероятно, есть представление для движение шахматного коня, но я не знаю (я весьма уверен, что это такая же группа, как и обычная двухмерная прямоугольная, просто с другим представлением»
Dump the screen? [y/n]
Re: Алгоритм поиска пути
Это как раз понятно, и выходит из определения области применения алгоритма. Можно использовать его и на треугольной сетке, при желании. Момент, который я еще до конца не разобрал - как считать точки прыжка на хексах?
То есть в квадратной сетке вся просто - диагонали и прямые. А в шестиугольной?
То есть в квадратной сетке вся просто - диагонали и прямые. А в шестиугольной?
Re: Алгоритм поиска пути
в шестиугольной по-моему еще проще, там все направления равноправны. Получается как на прямоугольной при движении по горизонтали, один настоящий сосед и до двух вынужденных.
Re: Алгоритм поиска пути
Нет, вынужденных соседей не должно быть, так как нет диагональных переходов. Но сомнения в этой гипотезе еще не все развеял, поэтому я хотел уточнить у сообщества.
Re: Алгоритм поиска пути
медскиллз:
на картинке кружочком обведены клетки которые могут быть вынуждеными соседями если на предыдущей есть препятствие. Ну, я алгоритм не реализовывал, только мельком посмотрел, может чего-то не понимаю.- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Re: Алгоритм поиска пути
Насколько я понимаю, для шестиугольника как раз будет три разных типа переходов, так что то, что изобразил kipar — это как раз оно и есть.
Dump the screen? [y/n]
Re: Алгоритм поиска пути
Наоборот, вот смотри как получается. Зеленые это варианты, черные препятствия. Получаем лишь количество соседей разное, но без вынужденных добавлений.Максим Кич писал(а): ↑11 мар 2017, 14:32Насколько я понимаю, для шестиугольника как раз будет три разных типа переходов, так что то, что изобразил kipar — это как раз оно и есть.
- Вложения
-
- HexGridLandscapeBase.png (10.73 КБ) 5436 просмотров
Re: Алгоритм поиска пути
Первый шаг неправильный. Зеленые это не соседи, т.к. до них можно добраться кратчайшим путем и без зеленой клетки.
С другой стороны, может я алгоритм не так понял, т.к. непонятно как тогда вообще до этих точек добираться (а в исходном алгоритме на квадратной сетке такой проблемы вроде нет). В общем, надо пробную версию сделать.
С другой стороны, может я алгоритм не так понял, т.к. непонятно как тогда вообще до этих точек добираться (а в исходном алгоритме на квадратной сетке такой проблемы вроде нет). В общем, надо пробную версию сделать.
Re: Алгоритм поиска пути
Нет, если идти право-низ, то всегда три соседа будет. И будут все естественные, несмотря на препятствие.Первый шаг неправильный. Зеленые это не соседи, т.к. до них можно добраться кратчайшим путем и без зеленой клетки.
Вот и я так же. С одной стороны все просто и понятно, с другой - возникают вопросы. Поэтому и спрашивал - может уже кто пробовал.С другой стороны, может я алгоритм не так понял, т.к. непонятно как тогда вообще до этих точек добираться (а в исходном алгоритме на квадратной сетке такой проблемы вроде нет). В общем, надо пробную версию сделать.
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 35 гостей