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

[Gudvin]

форум жив? есть вопрос относительно статьи http://www.astralax.ru/articles/pathway
непонятна связка волной дискретных клеток с подготовленными районами. бьюсь над алгоритмом уже долго. никак не доходит! могу ли я надеется на ответ? я подготовлю небольшой вопрос в виде своей наработки в картинках\гифках\видео.

[Gudvin]

> Дискретные клетки: заливка районов, хранение связей
на картинке внимание уделено связям районов для дальнейшей работы с волновым алгоритмом (в моем понимании).
"маркер", "время создания", массив для пометки районов и т.п. упоминать не стал, но они тоже должны быть в массиве 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

[Odin_KG]

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

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

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

И еще.... вы понимаете, что у вас в клетку 2.1 должно быть как бы два независимых входа? первый через район 1, а второй через район 2. И это будет 2 независимые волны. При этом район 2 у вас тупиковый, и на этом данная волна должна заглохнуть, а зато район 1 должен иметь выход в клетку 2.0.

[Gudvin]

Каким образом у вас выглядит связь между дискретными клетками 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 независимые волны.

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

Вопрос чересчур объемно сформулирован

тег споилера не работает. а так бы сложил туда лишнее.

[Odin_KG]

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

В статье это выражается фразой:

Т. е. говорить о дискретной клетке с координатами 100,100 бессмысленно, так как не хватает еще номера района.

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

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

я тут имел в виду, второй заход в одну и ту же дискретную клетку.

[Gudvin]

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

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


-------------------------------

Код: Выделить всё

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


[Odin_KG]

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

Ну и отлично

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

[Gudvin]

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

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

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

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

в общем впереди еще куча тестов. логику почувствую по ошибкам. главное вы меня с места сдвинули.

[Gudvin]

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

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

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

[Odin_KG]

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

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

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

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