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

[@lospolos1802]

Всё предельно понятно и без воды. Спасибо большое! Не первый раз выручаете)

[@mrgeroi_]

Копался с этим 3 дня, наткнулся на данное видео - за ночь разобрался, и составил необходимую для себя функцию, большое спасибо!

[@glebkaistro100]

В половину четвертого утра до меня наконец-то дошло, благодаря вашему видео. Спасибо!)

[@NermanFrost]

Спасибо! Благодаря Вашим объяснениям реализовал рабочий код на C++. До этого слабо понимал как это вообще работает, истратил кучу времени и нервов, а тут буквально час - два и есть 100% рабочий код, как я рад)) Спасибо большое!

[@粘土玉米]

Отличные видео. Больше бы таких!

[@IgorAherne]

Здравствуйте, Владимир, Скажите пожалуйста, какой код не смотрю, везде есть добавление в Closed List, но мы никогда не изымаем ноды и него... В таком случае, если наш персонаж должен идти с Севера на Юг, но между стартом и финишем преграда в виде подковы: a \_/ b Следовательно, в наш закрытый список попадут ноды: от A до дна подковы, от дна до кромки, от кромки до B и герой будет бежать не-есстесвенно (должен был от старта бежать сразу к кромке) (Принимая во внимание простейшую эвристическую финкцию, по т. Пифагора) Большое спасибо!

[@IgorAherne]

+Igor Aherne Ага, понял, вот статья которая показывает несколько примеров buildnewgames.com/astar/ (Владимир тоже давал похожый линк, но там слишком быстро проигрывалась анимация) Вобщем, мы будем добавлять ноды в Closed List, и "подкова" заполнится этими "закрытыми" нодами. как только мы дойдем до конца, путь буудет выстроен *от финиша* к концу, в этом и вся загвоздка (было упомянуто в видео). Таким образом, мы просто не попадем в дно подковы (учитывая что мы перезаписывали веса у нодов при надобности, во время поиска)

[@SuperGamervideo]

То есть, в каждой ячейке (ноде), должна быть записана информация о том, что находится на этой ячейке и находится ли вообще? И как лучше записывать соседей ячейки, как их находить, возможно при генерации сетки в цикле как то записывать? Трудности у меня с нахождением соседей клетки. И еще. Что такое стоимость, много про это читал, ничего не понял. Это какая то гипотетическая величина, суть которой сколько персонаж потратит своей энергии при переходе на клетку (очки передвижения, если сравнивать с стратегиями) или что это?

[@evgeniy4472]

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

[@xVitOSx]

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

[@kadzikag]

Очень не хватает простенького примера рабочего кода

[@kadzikag]

@ẞrėäŧĥë вот это ты вовремя 😹✊

[@vsevolodvolkogonov8245]

@@kadzikag здравствуйте, нашли ли гит азхахх, просто пытаю удачц)

[@kadzikag]

@@vsevolodvolkogonov8245 😹я уже успел написать 100500 велосипедов, найти 666 примеров на гите, и забить на всё это болт

[@vsevolodvolkogonov8245]

@@kadzikag жаль хаха, в таком случае , удачи вам )

[@ФедорПупков-е1й]

выполнял все по инструкции - если имеются 2 блока непроходимых расположенных по диагонали рядом то путь проходит между ними. В общем путь срезает углы в чем может быть проблема? Нужно чтобы огибал такие места.

[@user-fghjiydsvjk975]

Владимир, решил посмотреть ваше видео в надежде, что вы мне поможете разобраться с главным вопросом и мне кажется вы это сделали Вопрос следующий: как реализовать эвристическую функцию? Дело в том, что на вики и в других источниках примеры выполняются с заранее заявленным h(v) для вершин в графе или же на клеточном поле Вы дали ответ: чем лучше можно оценить h, тем лучше работает алгоритм. Правильно ли я понимаю, что если у меня есть граф с кучей вершин и ребер, и нет никакого клеточного поля, чтобы оценить реально расстояние до искомой вершины, то данный алгоритм будет уступать тому же Дейстре, потому что я не смогу нормально вычислить удаленность? спасибо, вам, за видео, немного скомкано, но полезно

[@VladimirMozhenkov]

+null56 Тут смотря на то, на сколько плохая ваша функция. То есть (кажется я это в видео упомянал) если ваша функция всегда дозвращает константу, то этот алгоритм становится копией дейкстры, просто с дополнительными ненужными шагами. А вот если получится так, что h(v) выдаёт не просто константу, а например заведомо ложные данные, то алгоритм будет тянуть куда-то "всторону" от нужного результата. И да, тогда он станет хуже.

[@johnysm.5295]

Это вопрос в том числе и скорости реализации функции. Владимир предложил в уроке Пифагора. Отрезок есть кратчайшее растояние между двумя точками, а это Пифагор. Точнее некуда. Если уж реализовать под целочисленные вычисления можно считать так: dx*dx + dy*dy От того, что вы будете сравнивать корень квадратный или его же в квадрате, соотношение результатов не изменится. Хотя эти прописные истины по-моему второй класс программирования. Если честно, то H оно не эврестическое скорее. Разумнее было бы назвать такую оценку оптимистической. И вот тут интересная засада. Хотя есть много игр где можно ходить и по диагонали, вроде бы max( dx, dy ) и есть минимальное количество ходов, но не смотря на точность оно сделает алгоритм только медленнее. На мой взгляд dх+dy или приведенная выше формула одни из вариантов. Утверждать что лучшие не могу.

[@13danyocean13]

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

[@VladimirMozhenkov]

+13danyocean13 Для A* вам нужна какая-то функция, которая "предположительно" говорит как долго вам осталось. Какую функцию вы предлагаете здесь? Количество квадратиков в правильной позиции? Мне кажется это приведёт к неверным тупиковым комбинациям, из которых потом придётся выбираться. Я где-то читал про алгоритм, который для этой игры используется, но сейчас не могу вспомнить что это было. Поищите может найдёте. Но A* скорее всего здесь не подойдёт.

[@13danyocean13]

+Vladimir Mozhenkov покопал еще немного и нашел Информированный алгоритм IDA*, видимо он более применим к этой задаче.

[@Agent009neutral]

Здравствуйте! Большое спасибо за видео. Смотрю его уже 4ый раз и не могу понять одну вещь. Интересуют следующие строки: TEMP_G = G[CURR] + DIST(CURR,NEIGHBOUR); IF(NEIGHBOUR NOT IN OPEN OR TEMP_G < G[NEIGHBOUR]) Хотелось бы разобраться, что брать в качестве G[NEIGHBOUR]. Насколько я понимаю: 1) Ищем от стартового узла соседа с минимальным F; 2) Если данный сосед и есть наша цель - успех, иначе пункт 3. 3) Для всех незакрытых соседей от уже нового узла (тот у которого было минимальное F) ищем TEMP_G с помощью сложения: G[CURR] - стоимость прохода от стартового узла, который был первой нодой до соседа с минимальным F, который является текущей нодой; DIST(CURR,NEIGHBOUR) - стоимость прохода от текущей ноды до соседа. Чему же тогда равно G[NEIGHBOUR]? Какой день не могу дойти, заранее спасибо. С уважением!

[@VladimirMozhenkov]

***** Это зависит от того, что происходило в предыдущих итерациях. Если до этого момента мы ещё не рассматривали узлов, у которых есть именно этот сосед (ведь могут быть несколько путей идущих через узел NEIGHBOUR), тогда там находится "бесконечность" (на самом деле записывается просто очень большое число, в надежде, что оно будут больше чем что-либо встречающееся нам, например MAXINT). Если мы уже рассматривали узлы соседствующие с этим NEIGHBOUR, тогда там будет информация о минимальном пути известном до сих пор. Эта информация оказывается там на пару строк ниже, посмотрите, мы-же записываем TEMP_G туда. А алгоритм циклический, так что предыдущие циклы влияют на то, что мы видим сейчас.

[@Agent009neutral]

Vladimir Mozhenkov Большое спасибо, понял.

[@triviumfan9411]

Было бы намного яснее, если бы Вы на конкретном примере прогнали алгоритм. Но по псевдокоду и этому истолкованию я не разобрался, хотя знаком с алгоритмом Дейкстры.

[@professorbis7530]

такой формат объяснения с кодом на доске не для всех, я тоже не понял

[@volodymyr2665]

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

[@RusArtSnipe]

Просто БУУУМ - бошка взорвалась. Я нихрена не понял, слишком замудренно описываете. Мне просто нужно узнать порядок действий в цикле, а не всякие эврестические функции и т.д. Банально можно обьяснить к примеру так: - есть сетка на плоскости, состоящая из точек на одинаковом расстоянии, образующая квадрат 20 на 20, с шагом точки от точки 30 пикселей. -Нужно добраться до точки [10, 20] из точки [5, 5]. - ВОпросы, как сканировать соседние точки циклом?? - в каком направлении двигатся из точки старта ??? ведь есть + к точке к примеру по оси +X, а есть -X. Так же к примеру если точки старта и финиша располагаются горизонтально друг против друга, опять же либо +Y либо -Y ?? И самый сок это по диагонали.. - если из каждой точки, сканировать соседнюю, после которой сканировать еще соседнюю, и т.д. Сколько это вариантов в миллиардах выходит ???? - Я вообще пишу бота для игры с видом сверху, может есть проще действия, без использования алгоритмов ?? PS я просто уверен, что эти алгоритмы в принципе несложные, просто их объяснений по той логике, что воспринимает обычный человек (программист delphi\C#) не существует, все хотят казаться более умными и даже свои коды мудрят так, что хрен поймешь что и куда. А псевдо-код вообще не образует из себя никакого реального кода.

[@mvpupe]

можете, пожалуйста, привести как именно выглядит эвристическая функция птичьего полета? я не могу ее найти под таким названием в интернете, а мне очень нужен ее математический вид

[@volodymyr2665]

потому что это дворовое сельское название... эвристических функций есть несколько. например манхэтенская эвристика

[@DrStrangeLove2050]

Алгоритм поиска A* часто называют алгоритмом на графах.... Для графов часто используют представления - список смежности и матрица смежности... Какое из этих двух представлений используют с алгоритмом поиска A* ??

[@VladimirMozhenkov]

DrStrangeLove2050 Ну как написан сам алгоритм, там используют несколько матриц. Но можно написать его используя другие форматы данных в принципе.

[@craftic7]

Во всех примерах поле поделено на небольшое количество квадратов, как в тетрисе. А что делать, если на карте много точек (1000х1000 например). Долго же будет работать.

[@VladimirMozhenkov]

craftic7 Эвристическая функция будет его тянуть по самому прямому пути и проверять этот путь первым. Тут вопрос не в том что "долго" или "не долго". А в том, чтобы найти самый оптимальный возможный подход. Если более оптимального нет (то есть этот алгоритм лучше остальных), то вы будете использовать его.

[@VladimirMozhenkov]

craftic7 Вот хорошая анимация, когда клеток много: commons.wikimedia.org/wiki/File:Weighted_A_star_with_eps_5.gif

[@thomasmorgan9043]

Vladimir Mozhenkov Вот есть визуализация работы и других алгоритмов qiao.github.io/PathFinding.js/visual/

[@niktaub6407]

Это лучший алгоритм поиска пути ?

[@mesut1046]

кажется есть улучшенная версия этого. IDA*

[@KBA696]

Спс за видео. Но уже облазил все рассказа об алгоритмах поиска в принципе как работает в 2 д варианте понятно а вот как же его применяют в 3д. Не могли бы раскрыть эту тему немного по подромнее как должно выглядеть по меньше кода по больше рассказа о принципе его работы так как даже представить не могу как сделать чтобы юнит зашел в дом и поднялся на 3 этаж

[@FreeCoder]

Мужик жжет!

[@ИванМельников-з1з]

спасибо

[@annasereda6170]

в конце уже очень запутанно начали объяснять( пересмотрела несколько раз все равноне до конца поняла(

[@ЕвгенийГорелов-е1з]

Потому-что баба не может быть программистом)

[@haruko5318]

@@ЕвгенийГорелов-е1з гениально

[@ЕвгенийГорелов-е1з]

@@haruko5318 Это просто правда))

[@haruko5318]

Евгений Горелов почему?

[@ЕвгенийГорелов-е1з]

@@haruko5318 у них плохо с конструированием, женщины программисты - это все про рутину, но не про креативность, оптимизацию и понимание происходящего на низком уровне

[@ioretcio]

kzbin.info/www/bejne/Y32QiJqBgquonqc здесь человечек лучше показал