Статья "Поиск пути" (astralax.ru/articles/pathway)

Разговоры на любые темы

Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Gudvin » Пн мар 13, 2017 7:40 pm

форум жив? :roll: есть вопрос относительно статьи http://www.astralax.ru/articles/pathway
непонятна связка волной дискретных клеток с подготовленными районами. бьюсь над алгоритмом уже долго. никак не доходит! могу ли я надеется на ответ? я подготовлю небольшой вопрос в виде своей наработки в картинках\гифках\видео.
Gudvin
 
Сообщения: 6
Зарегистрирован: Ср мар 01, 2017 12:53 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Gudvin » Ср мар 15, 2017 12:32 pm

> Дискретные клетки: заливка районов, хранение связей
на картинке внимание уделено связям районов для дальнейшей работы с волновым алгоритмом (в моем понимании).
"маркер", "время создания", массив для пометки районов и т.п. упоминать не стал, но они тоже должны быть в массиве discrete_arr)
Изображение


> Иллюстрация мостов для хранения связей между дискретными клетками
Изображение


> Так дискретные клетки видят связи друг друга в обработке соседей (p.s. а как ваш алгоритм понимает короткий путь?)
Изображение

> Волновой алгоритм
Иллюстрация из вики: результат работы волнового алгоритма
Изображение

дискретный массив (discrete_arr) так же хранит для каждой д.клетки указатель на temp-список "проходимых районов" (данные списка верны только для одного вызова алгоритма, новый поиск пути будет по другому шагать по д.клеткам и перезаполнять списки)
итак, волна пошла:

- старт (зеленая точка, идет до красной-финиша) считывает район на котором стоит и добавляет его в список "проходимых" для текущей д.клетки (размер листа 1)

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

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

Изображение


ПРОБЛЕМНАЯ СИТУАЦИЯ: первый шаг волны "2" считается проходимым относительно предыдущего шага "1" слева, второй шаг волны "2" уже не сможет попасть на верх, т.к. д.клетка уже помечена этим же шагом и поэтому игнорируется. до финиша не добраться, при том что проход имеется.

PS
голову уже сломал. перечитывал вашу статью десятки раз. не доходит до меня, как распространяется волна по д.клеткам с учетом районов :( если тыкните носом, буду бесконечно благодарен. :)
вот переписал игрушку-стратегию с сеги на комп https://youtu.be/_n9BxlwpKGA
хочу увеличить масштабы баталий. встроенный в конструктор "gamemaker" поиск пути на большее способен. перешел на c++.

PSS
в статье некоторые картинки "поехали", пофиксил пока распечатывал. возможно вам пригодится.
http://i1.imageban.ru/out/2017/03/15/57 ... fa7914.gif
http://i1.imageban.ru/out/2017/03/15/47 ... 23f9e6.gif (дискретные клетки проще понимаются, если их дополнительно обвести)
http://i2.imageban.ru/out/2017/03/15/57 ... e86398.gif
http://i6.imageban.ru/out/2017/03/15/8e ... 8c7253.gif
Gudvin
 
Сообщения: 6
Зарегистрирован: Ср мар 01, 2017 12:53 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Odin_KG » Ср мар 15, 2017 2:20 pm

Форум жив, только пишут нечасто :-)

Вопрос чересчур объемно сформулирован - мне в это всё въезжать немного лень. Давай как-то более по простому что-ли...

Каким образом у вас выглядит связь между дискретными клетками 2.1 и 2.0 ? У вас должно быть для клетки 2.1 указано, что оттуда можно попасть в 2.0. через район 1. Соответственно, если это не указано, то дискретная волна туда и не пойдет.

И еще.... вы понимаете, что у вас в клетку 2.1 должно быть как бы два независимых входа? первый через район 1, а второй через район 2. И это будет 2 независимые волны. При этом район 2 у вас тупиковый, и на этом данная волна должна заглохнуть, а зато район 1 должен иметь выход в клетку 2.0.
Аватара пользователя
Odin_KG
Administrator
Administrator
 
Сообщения: 841
Зарегистрирован: Чт янв 15, 2009 2:57 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Gudvin » Ср мар 15, 2017 3:38 pm

Каким образом у вас выглядит связь между дискретными клетками 2.1 и 2.0 ?

У вас должно быть для клетки 2.1 указано, что оттуда можно попасть в 2.0. через район 1.
Соответственно, если это не указано, то дискретная волна туда и не пойдет.

все связи записаны. их можно легко определить. обновляются вместе с соседями при изменении д.клетки. любая клетка точно знает все доступные связи с соседями. запись: (мой район N) == направление N район соседа
Изображение
И еще.... вы понимаете, что у вас в клетку 2.1 должно быть как бы два независимых входа? ...

входы есть (картинка выше). если стартовую точку переставить на 2.2, то волна спокойно дойдет до финиша.
проблема в том, что волна сама перекрывает "взгляд" будущим шагам на правильных соседей: волна вышла из 0.2 ... из 1.1 наступаю на 2.1 и помечаю волной, т.к могу попасть в его район "два".
и только уже после, из списка клеток для обработки выходит клетка 2.2 и не может посмотреть на связи соседа 2.1, так как не проходит через условие "если д.клетка не помечена, то ... проверяем связи... есть связь, добавляем клетку в список следующего шага"
... первый через район 1, а второй через район 2. И это будет 2 независимые волны.

как может быть две волны? зачем? разве одной из "старта" не достаточно? похоже я не могу уловить именно это.
я представляю дискретные клетки как обычные, и тупо из старта распускаю одну единственную волну, которая перебирает заготовленные связи с соседями - если есть связь по районам, то пометил, иначе игнорирую, так или иначе иду дальше. и так до финиша.
Вопрос чересчур объемно сформулирован

тег споилера не работает. а так бы сложил туда лишнее. :mrgreen:
Gudvin
 
Сообщения: 6
Зарегистрирован: Ср мар 01, 2017 12:53 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Odin_KG » Ср мар 15, 2017 5:16 pm

Кажется, я понял, чего вы не понимаете.

В статье это выражается фразой:
Т. е. говорить о дискретной клетке с координатами 100,100 бессмысленно, так как не хватает еще номера района.


У вас клетка 2.1 состоит из двух НЕЗАВИСИМЫХ частей, т.е. волна может её посетить 2 раза. В первый раз волна входит в район №2, а второй раз из клетки 2.2 в район №1. Это действие у вас не выполняется, так как вы помечаете клетку как "посещенную" после первого вхождения в район №2, а это неверно. Дискретные клетки вообще не имеют понятия "посещённые", это относится именно к районам в них.

как может быть две волны?

я тут имел в виду, второй заход в одну и ту же дискретную клетку.
Аватара пользователя
Odin_KG
Administrator
Administrator
 
Сообщения: 841
Зарегистрирован: Чт янв 15, 2009 2:57 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Gudvin » Чт мар 16, 2017 6:32 pm

Кажется, я понял, чего вы не понимаете.
...
Дискретные клетки вообще не имеют понятия "посещённые", это относится именно к районам в них.


то что нужно! БОЛЬШОЕ СПАСИБО! буду переосмысливать.

Изображение
-------------------------------
Изображение

Код: Выделить всё
//поигрался с районами в паинте. смог дойти до финиша
- пометил район "старта" волной
- добавил д.клетку "старта" в список обработки
- цикл (пока есть д.клетки для обработки)
   - вытащил с конца новую д.клетку
   - цикл соседей д.клетки (направ. 0-7)
      - цикл моих связующих районов с соседом
         - если мой связующий район помечен волной
            - если связующий район соседа не помечен волной
               - помечаем район соседа волной (+ откуда пришла волна)
               - если д.клетка соседа еще не обрабатывалась, помечаем "обработанной", добавляем в список обработки
Gudvin
 
Сообщения: 6
Зарегистрирован: Ср мар 01, 2017 12:53 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Odin_KG » Чт мар 16, 2017 7:37 pm

то что нужно! БОЛЬШОЕ СПАСИБО! буду переосмысливать.

Ну и отлично :D

У вас на последнем анимированном скриншоте почему-то волна не зашла в район №3 клетки 1.1, по крайней мере, на анимации я этого не вижу. Если это у вас видео с программы, то тут может быть недоработка.
Аватара пользователя
Odin_KG
Administrator
Administrator
 
Сообщения: 841
Зарегистрирован: Чт янв 15, 2009 2:57 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Gudvin » Чт мар 16, 2017 9:25 pm

волна не зашла в район №3 клетки 1.1
...
Если это у вас видео с программы, то тут может быть недоработка.


от кодинга отдых взял. прога пока так не умеет. :mrgreen:
над волной с учетом районов "по-новому" надо еще подумать + статью перечитать с новым взглядом.

1.1-№3 не пометил намерено. гифку собирал из старых скринов с проги. а уже в паинте заливал районы цветом, осмысливая таким образом волну.
логика получилась сходу такая: "если район д.клетки сам никем не помечен, то и районы соседа помечать не может".
иначе после старта "0.1-№1" сразу пометит район финиша "0.0", и пришедшая волна с правой стороны туда не попадет, т.к: "если район уже помечен, игнорирую, иначе помечаю и записываю источник"

можно еще вот как попробовать, тогда "1.1-№3" будет помечен:
"если район сам помечен, тогда может помечать другие районы, иначе если не помечен но моя д.клетка уже отработана (попадала в списки заливки), помечаю ...". только будет ли это работать на большой карте...

в общем впереди еще куча тестов. логику почувствую по ошибкам. главное вы меня с места сдвинули. :!: :!: :!:
Gudvin
 
Сообщения: 6
Зарегистрирован: Ср мар 01, 2017 12:53 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Gudvin » Вт мар 21, 2017 11:20 pm

потестил в проге волну с учетом районов. крутой алгоритм! даже лабиринты нипочем. есть такой алгоритм Jump Point Search - улучшенный A*, говорят очень быстрый. вкупе с дискретными клетками это будет бомба.

Jump Point Search:
https://habrahabr.ru/post/162915/
http://qiao.github.io/PathFinding.js/visual/

На скриншотах:
> зеленые длинные стрелки - для наглядности, указывает на случайную клетку итогового района следующей дискретной клетки пути (просто тест, первая клетка в цикле заливки района)
> белые стрелки на зеленом фоне - распространение волны, т.е с какого направления пришел сосед
> голубые стрелки на зеленом фоне - реверс обратного пути от финиша, итоговые районы всего пути от старта к финишу (направление на след. дискретную клетку)
> желтые цифры - номера районов
> серый фон района - необработанный район

Изображение Изображение Изображение Изображение Изображение
Gudvin
 
Сообщения: 6
Зарегистрирован: Ср мар 01, 2017 12:53 pm

Re: Статья "Поиск пути" (astralax.ru/articles/pathway)

Сообщение Odin_KG » Ср мар 22, 2017 9:43 am

потестил в проге волну с учетом районов. крутой алгоритм! даже лабиринты нипочем.

Благодарю на добром слове!

есть такой алгоритм Jump Point Search - улучшенный A*, говорят очень быстрый. вкупе с дискретными клетками это будет бомба.

Вполне возможно. Если вы любите "маньячить" с оптимизациями, то можете попробовать дискретные клетки в свою очередь еще раз разбить на родительские дискретные клетки, только уже более больших размеров. Не знаю, насколько это будет эффективно, но для большой карты, скорее всего будет очень эффективно.
Аватара пользователя
Odin_KG
Administrator
Administrator
 
Сообщения: 841
Зарегистрирован: Чт янв 15, 2009 2:57 pm


Вернуться в Оффтопик

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

Сейчас этот форум просматривают: Majestic-12 [Bot] и гости: 6

cron