Алгоритм поиска A*
HTML-код
- Опубликовано: 15 сен 2024
- Алгоритм поиска А-звезда используется обычно в компьютерных играх для нахождения кратчайшего пути в кратчайшее время, когда можно создать эвристическую функцию для нахождения теоретического кратчайшего пути.
Всё предельно понятно и без воды. Спасибо большое! Не первый раз выручаете)
Копался с этим 3 дня, наткнулся на данное видео - за ночь разобрался, и составил необходимую для себя функцию, большое спасибо!
В половину четвертого утра до меня наконец-то дошло, благодаря вашему видео. Спасибо!)
Спасибо! Благодаря Вашим объяснениям реализовал рабочий код на C++. До этого слабо понимал как это вообще работает, истратил кучу времени и нервов, а тут буквально час - два и есть 100% рабочий код, как я рад)) Спасибо большое!
Очень не хватает простенького примера рабочего кода
@ẞrėäŧĥë вот это ты вовремя 😹✊
@@kadzikag здравствуйте, нашли ли гит азхахх, просто пытаю удачц)
@@vsevolodvolkogonov8245 😹я уже успел написать 100500 велосипедов, найти 666 примеров на гите, и забить на всё это болт
@@kadzikag жаль хаха, в таком случае , удачи вам )
Отличные видео. Больше бы таких!
Было бы намного яснее, если бы Вы на конкретном примере прогнали алгоритм.
Но по псевдокоду и этому истолкованию я не разобрался, хотя знаком с алгоритмом Дейкстры.
такой формат объяснения с кодом на доске не для всех, я тоже не понял
Здравствуйте! Большое спасибо за видео. Смотрю его уже 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]? Какой день не могу дойти, заранее спасибо.
С уважением!
***** Это зависит от того, что происходило в предыдущих итерациях.
Если до этого момента мы ещё не рассматривали узлов, у которых есть именно этот сосед (ведь могут быть несколько путей идущих через узел NEIGHBOUR), тогда там находится "бесконечность" (на самом деле записывается просто очень большое число, в надежде, что оно будут больше чем что-либо встречающееся нам, например MAXINT).
Если мы уже рассматривали узлы соседствующие с этим NEIGHBOUR, тогда там будет информация о минимальном пути известном до сих пор.
Эта информация оказывается там на пару строк ниже, посмотрите, мы-же записываем TEMP_G туда. А алгоритм циклический, так что предыдущие циклы влияют на то, что мы видим сейчас.
Vladimir Mozhenkov Большое спасибо, понял.
Владимир, решил посмотреть ваше видео в надежде, что вы мне поможете разобраться с главным вопросом и мне кажется вы это сделали
Вопрос следующий: как реализовать эвристическую функцию?
Дело в том, что на вики и в других источниках примеры выполняются с заранее заявленным h(v) для вершин в графе или же на клеточном поле
Вы дали ответ: чем лучше можно оценить h, тем лучше работает алгоритм. Правильно ли я понимаю, что если у меня есть граф с кучей вершин и ребер, и нет никакого клеточного поля, чтобы оценить реально расстояние до искомой вершины, то данный алгоритм будет уступать тому же Дейстре, потому что я не смогу нормально вычислить удаленность?
спасибо, вам, за видео, немного скомкано, но полезно
+null56 Тут смотря на то, на сколько плохая ваша функция. То есть (кажется я это в видео упомянал) если ваша функция всегда дозвращает константу, то этот алгоритм становится копией дейкстры, просто с дополнительными ненужными шагами. А вот если получится так, что h(v) выдаёт не просто константу, а например заведомо ложные данные, то алгоритм будет тянуть куда-то "всторону" от нужного результата. И да, тогда он станет хуже.
Это вопрос в том числе и скорости реализации функции. Владимир предложил в уроке Пифагора. Отрезок есть кратчайшее растояние между двумя точками, а это Пифагор. Точнее некуда. Если уж реализовать под целочисленные вычисления можно считать так:
dx*dx + dy*dy
От того, что вы будете сравнивать корень квадратный или его же в квадрате, соотношение результатов не изменится. Хотя эти прописные истины по-моему второй класс программирования.
Если честно, то H оно не эврестическое скорее. Разумнее было бы назвать такую оценку оптимистической. И вот тут интересная засада. Хотя есть много игр где можно ходить и по диагонали, вроде бы max( dx, dy ) и есть минимальное количество ходов, но не смотря на точность оно сделает алгоритм только медленнее. На мой взгляд dх+dy или приведенная выше формула одни из вариантов. Утверждать что лучшие не могу.
Что-ж, похоже я не с того начинаю. Хочу разобраться, как вообще устроен поиск пути, но даже это видео не понял. С чего начать изучение этой темы?
Здравствуйте, Владимир,
Скажите пожалуйста, какой код не смотрю, везде есть добавление в Closed List, но мы никогда не изымаем ноды и него...
В таком случае, если наш персонаж должен идти с Севера на Юг, но между стартом и финишем преграда в виде подковы:
a
\_/
b
Следовательно, в наш закрытый список попадут ноды:
от A до дна подковы,
от дна до кромки,
от кромки до B
и герой будет бежать не-есстесвенно (должен был от старта бежать сразу к кромке)
(Принимая во внимание простейшую эвристическую финкцию, по т. Пифагора)
Большое спасибо!
+Igor Aherne
Ага, понял, вот статья которая показывает несколько примеров buildnewgames.com/astar/ (Владимир тоже давал похожый линк, но там слишком быстро проигрывалась анимация)
Вобщем, мы будем добавлять ноды в Closed List, и "подкова" заполнится этими "закрытыми" нодами.
как только мы дойдем до конца, путь буудет выстроен *от финиша* к концу, в этом и вся загвоздка (было упомянуто в видео).
Таким образом, мы просто не попадем в дно подковы (учитывая что мы перезаписывали веса у нодов при надобности, во время поиска)
нормас... это вроде как называется еще алгоритмом поиска в ширину... я его реализовывал для того чтоб определять есть ли выход из условного помещения со стенами и дверными проемами. но там не было эвристики. Я полагаю что в лабиринтах, полезность эвристики значительно ниже. Сейчас же я задаюсь вопросом пятнашек и как не странно именно этот алгоритм вместе с эвристикой должны помочь решить эту игрулину...
То есть, в каждой ячейке (ноде), должна быть записана информация о том, что находится на этой ячейке и находится ли вообще? И как лучше записывать соседей ячейки, как их находить, возможно при генерации сетки в цикле как то записывать? Трудности у меня с нахождением соседей клетки. И еще. Что такое стоимость, много про это читал, ничего не понял. Это какая то гипотетическая величина, суть которой сколько персонаж потратит своей энергии при переходе на клетку (очки передвижения, если сравнивать с стратегиями) или что это?
Владимир, Вы сказали, что этот алгоритм не очень подойдет для 3д. Вот к примеру, я хочу проложить маршрут с пола к потолку по стене, на пути могут быть препятствия. Этого алгоритма будет достаточно для подобного или лучше какой-нибудь другой алгоритм использовать?
Спс за видео. Но уже облазил все рассказа об алгоритмах поиска в принципе как работает в 2 д варианте понятно а вот как же его применяют в 3д. Не могли бы раскрыть эту тему немного по подромнее как должно выглядеть по меньше кода по больше рассказа о принципе его работы так как даже представить не могу как сделать чтобы юнит зашел в дом и поднялся на 3 этаж
выполнял все по инструкции - если имеются 2 блока непроходимых расположенных по диагонали рядом то путь проходит между ними. В общем путь срезает углы в чем может быть проблема? Нужно чтобы огибал такие места.
Просто БУУУМ - бошка взорвалась. Я нихрена не понял, слишком замудренно описываете. Мне просто нужно узнать порядок действий в цикле, а не всякие эврестические функции и т.д.
Банально можно обьяснить к примеру так: - есть сетка на плоскости, состоящая из точек на одинаковом расстоянии, образующая квадрат 20 на 20, с шагом точки от точки 30 пикселей.
-Нужно добраться до точки [10, 20] из точки [5, 5].
- ВОпросы, как сканировать соседние точки циклом??
- в каком направлении двигатся из точки старта ??? ведь есть + к точке к примеру по оси +X, а есть -X. Так же к примеру если точки старта и финиша располагаются горизонтально друг против друга, опять же либо +Y либо -Y ?? И самый сок это по диагонали..
- если из каждой точки, сканировать соседнюю, после которой сканировать еще соседнюю, и т.д. Сколько это вариантов в миллиардах выходит ????
- Я вообще пишу бота для игры с видом сверху, может есть проще действия, без использования алгоритмов ??
PS я просто уверен, что эти алгоритмы в принципе несложные, просто их объяснений по той логике, что воспринимает обычный человек (программист delphi\C#) не существует, все хотят казаться более умными и даже свои коды мудрят так, что хрен поймешь что и куда. А псевдо-код вообще не образует из себя никакого реального кода.
спасибо
Мужик жжет!
Во всех примерах поле поделено на небольшое количество квадратов, как в тетрисе. А что делать, если на карте много точек (1000х1000 например). Долго же будет работать.
craftic7 Эвристическая функция будет его тянуть по самому прямому пути и проверять этот путь первым. Тут вопрос не в том что "долго" или "не долго". А в том, чтобы найти самый оптимальный возможный подход. Если более оптимального нет (то есть этот алгоритм лучше остальных), то вы будете использовать его.
craftic7 Вот хорошая анимация, когда клеток много: commons.wikimedia.org/wiki/File:Weighted_A_star_with_eps_5.gif
Vladimir Mozhenkov Вот есть визуализация работы и других алгоритмов qiao.github.io/PathFinding.js/visual/
Алгоритм поиска A* часто называют алгоритмом на графах....
Для графов часто используют представления - список смежности и матрица смежности... Какое из этих двух представлений используют с алгоритмом поиска A* ??
DrStrangeLove2050 Ну как написан сам алгоритм, там используют несколько матриц. Но можно написать его используя другие форматы данных в принципе.
Владимир, приветствую. вопрос, будет ли оптимален этот алгоритм для реализации автоматического сбора игры "пятнашки" компьютером?
+13danyocean13 Для A* вам нужна какая-то функция, которая "предположительно" говорит как долго вам осталось. Какую функцию вы предлагаете здесь? Количество квадратиков в правильной позиции? Мне кажется это приведёт к неверным тупиковым комбинациям, из которых потом придётся выбираться.
Я где-то читал про алгоритм, который для этой игры используется, но сейчас не могу вспомнить что это было. Поищите может найдёте. Но A* скорее всего здесь не подойдёт.
+Vladimir Mozhenkov покопал еще немного и нашел Информированный алгоритм IDA*, видимо он более применим к этой задаче.
можете, пожалуйста, привести как именно выглядит эвристическая функция птичьего полета? я не могу ее найти под таким названием в интернете, а мне очень нужен ее математический вид
потому что это дворовое сельское название... эвристических функций есть несколько. например манхэтенская эвристика
в конце уже очень запутанно начали объяснять( пересмотрела несколько раз все равноне до конца поняла(
Потому-что баба не может быть программистом)
@@user-sp3hy7cw9x гениально
@@haruko5318 Это просто правда))
Евгений Горелов почему?
@@haruko5318 у них плохо с конструированием, женщины программисты - это все про рутину, но не про креативность, оптимизацию и понимание происходящего на низком уровне
Это лучший алгоритм поиска пути ?
кажется есть улучшенная версия этого. IDA*
ruclips.net/video/-L-WgKMFuhE/видео.html здесь человечек лучше показал