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