Алгоритм поиска пути

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Ответить
Darkness
Сообщения: 36
Зарегистрирован: 13 апр 2012, 18:47

Алгоритм поиска пути

Сообщение Darkness » 10 мар 2017, 18:15

Наткнулся на хабре на интересный алгоритм:https://habrahabr.ru/post/162915/
Кто-нибудь его реализовывал/разбирал? Если да, то поделитесь опытом, реально перевести его в хексы при случае?

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Алгоритм поиска пути

Сообщение Максим Кич » 10 мар 2017, 22:46

Darkness писал(а):
10 мар 2017, 18:15
Наткнулся на хабре на интересный алгоритм:https://habrahabr.ru/post/162915/
Кто-нибудь его реализовывал/разбирал? Если да, то поделитесь опытом, реально перевести его в хексы при случае?
Навскидку нагуглил (на вражеском):
Скрытый текст: ПОКАЗАТЬ
Cayley graphs are one way to say “uniform grid”. To express a 2d rectangular grid, you could give a group presentation, which is something like saying “There are four directions, north, south, east west. North followed by South comes back to the same place, East followed by West comes back to the same place, and North East West South comes back to the same place.”. (Actually, you would say that all directions have inverses because it is a group, and so there would be two generators and one word, but group theory might be too rigid, you might want semigroups or monoids – I just want to point out that there are ways of describing uniform grids.)

A hexagonal grid can be presented with three generators, each equal to its own inverse, and going around in a hexagon (abcabc) leads back to the same place. It’s easy to construct hyperbolic grids, too. For example, the 2-3-7 triangle group (there’s an image here http://en.wikipedia.org/wiki/%282,3,7%29_triangle_group ) can be described as having two generators x and y, such that xx comes back to the same place, yyy comes back to the same place and (xy)^7 comes back to the same place. Probably, there is a presentation of the movement of a chess knight, though I don’t know it (I’m pretty sure it’s the same group as the usual 2d rectangular grid, just a different presentation).
То есть:
«Вершинно-транзитивные графы — это один из способов представить «равномерную сетку». Чтобы представить двухмерную прямоугольную сетку, вы можете дать представление группы, вроде «Есть четыре направления: север, юг, восток и запад. Шаг на север после шага на юг вернёт вас на исходную. Шаг на восток после шага на запад вернёт вас на исходную, и наг на северозапад после юговостока вернёт вас на исходную» (На самом деле, вы скажете, что у каждого направления есть обратное, потому что это группа, и поэтому будет два генератора и одно слово (??? возможно опечатка, и это «один мир»), но теория групп может оказаться слишком жёсткой и вы захотите полугруппы или моноиди — я просто хочу показать, что равномерные сетки можно описывать по-разному.

Гексагональная сетка может быть представлена тремя генераторами, каждый со своим обратным направлением, и которые идут вокруг шестиугольника (abcabc) попарно возвращая на исходную. Так же легко создать гиперболические сетки. Например, группа треугольника (2,3,7) может быть описана как имеющая два генератора x и у, так что на исходную вернут сочетания xx, yyy или (xy)^7. Вероятно, есть представление для движение шахматного коня, но я не знаю (я весьма уверен, что это такая же группа, как и обычная двухмерная прямоугольная, просто с другим представлением»
Так что это должно быть элементарной задачей для любого, кто закончил институт по специальности «Математик-теоретик» и при этом не сжёг себе мозги.
Dump the screen? [y/n]

Darkness
Сообщения: 36
Зарегистрирован: 13 апр 2012, 18:47

Re: Алгоритм поиска пути

Сообщение Darkness » 11 мар 2017, 06:21

Это как раз понятно, и выходит из определения области применения алгоритма. Можно использовать его и на треугольной сетке, при желании. Момент, который я еще до конца не разобрал - как считать точки прыжка на хексах?
То есть в квадратной сетке вся просто - диагонали и прямые. А в шестиугольной?

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: Алгоритм поиска пути

Сообщение kipar » 11 мар 2017, 07:08

в шестиугольной по-моему еще проще, там все направления равноправны. Получается как на прямоугольной при движении по горизонтали, один настоящий сосед и до двух вынужденных.

Darkness
Сообщения: 36
Зарегистрирован: 13 апр 2012, 18:47

Re: Алгоритм поиска пути

Сообщение Darkness » 11 мар 2017, 11:48

Нет, вынужденных соседей не должно быть, так как нет диагональных переходов. Но сомнения в этой гипотезе еще не все развеял, поэтому я хотел уточнить у сообщества.

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: Алгоритм поиска пути

Сообщение kipar » 11 мар 2017, 12:57

медскиллз:
Untitled.png
Untitled.png (6.52 КБ) 5426 просмотров
на картинке кружочком обведены клетки которые могут быть вынуждеными соседями если на предыдущей есть препятствие. Ну, я алгоритм не реализовывал, только мельком посмотрел, может чего-то не понимаю.

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Алгоритм поиска пути

Сообщение Максим Кич » 11 мар 2017, 14:32

Darkness писал(а):
11 мар 2017, 11:48
Нет, вынужденных соседей не должно быть, так как нет диагональных переходов. Но сомнения в этой гипотезе еще не все развеял, поэтому я хотел уточнить у сообщества.
Насколько я понимаю, для шестиугольника как раз будет три разных типа переходов, так что то, что изобразил kipar — это как раз оно и есть.
Dump the screen? [y/n]

Darkness
Сообщения: 36
Зарегистрирован: 13 апр 2012, 18:47

Re: Алгоритм поиска пути

Сообщение Darkness » 12 мар 2017, 06:41

Максим Кич писал(а):
11 мар 2017, 14:32
Darkness писал(а):
11 мар 2017, 11:48
Нет, вынужденных соседей не должно быть, так как нет диагональных переходов. Но сомнения в этой гипотезе еще не все развеял, поэтому я хотел уточнить у сообщества.
Насколько я понимаю, для шестиугольника как раз будет три разных типа переходов, так что то, что изобразил kipar — это как раз оно и есть.
Наоборот, вот смотри как получается. Зеленые это варианты, черные препятствия. Получаем лишь количество соседей разное, но без вынужденных добавлений.
Вложения
HexGridLandscapeBase.png
HexGridLandscapeBase.png (10.73 КБ) 5406 просмотров

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: Алгоритм поиска пути

Сообщение kipar » 12 мар 2017, 07:57

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

Darkness
Сообщения: 36
Зарегистрирован: 13 апр 2012, 18:47

Re: Алгоритм поиска пути

Сообщение Darkness » 12 мар 2017, 16:23

Первый шаг неправильный. Зеленые это не соседи, т.к. до них можно добраться кратчайшим путем и без зеленой клетки.
Нет, если идти право-низ, то всегда три соседа будет. И будут все естественные, несмотря на препятствие.
С другой стороны, может я алгоритм не так понял, т.к. непонятно как тогда вообще до этих точек добираться (а в исходном алгоритме на квадратной сетке такой проблемы вроде нет). В общем, надо пробную версию сделать.
Вот и я так же. С одной стороны все просто и понятно, с другой - возникают вопросы. Поэтому и спрашивал - может уже кто пробовал.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя