Поиск пути в играх. Алгоритм поиска пути A*

В этом видео мы наглядно разберём каждый этап работы алгоритма A* для поиска кратчайшего пути между двумя точками.
В настоящий момент А* является самым популярным алгоритмом по поиску пути в игровой индустрии благодаря своей высокой производительности, гибкости и универсальности.

[@dmitrywroclaw9165]

Самое понятное и наглядное объяснение алгоритма. Спасибо большое!

[@oleggopp4388]

Начал делать свою игрулю, ничего не понимая в алгоритмах поиска пути, но тут наткнулся на это видео. Автор всё разложил по полочкам. Хороший видос, лайк подписка, было бы интересно узнать про другие алгоритмы Джакарту и прочее!

[@gamedevru3833]

Скоро будут ещё видео по игрострою. Спасибо за подписку и удачи вам в ваших начинаниях)

[@poltos7235]

За хардбасс на фоне ставлю дополнительный лайк)

[@АртурБерков-х8ч]

Одновременно просто и гениально. Возьму на вооружение.

[@mar_kha]

Пишу вкр на тему "Подбор подходящего маршрута...", и искала материал по алгоритмам поиска Интересный и наглядный разбор - спасибо! 👍

[@petergorelov6852]

Великолепно. Когда читал про этот алгоритм в книге - вообще не понимал зачем нужен этот примитив. Но здесь хорошо показано насколько он изощрённый.

[@Desotterro]

Про 3ехмерный поиск пути было бы очень интересно

[@АзатМингалеев-в1к]

А разве трёхмерная сетка принципиально отличается? Просто берем соседние индексы для i, j и k.

[@renonmay]

ххахаха лучшее объяснение что я видел и с хардбассом на фоне! как же я люблю свой народ

[@flugenkehhannen]

Дай бог тебе здоровья

[@ВасилийГригорьев-з9х]

Вау. Впечатлен подачей и объяснением алгоритма

[@goshator]

Спасибо, помог до конца понять алгоритм перед экзаменом!)

[@isgris5153]

Я: Просто смотрю видео для изучения алгоритма🗿 Также хардбасс на фоне:🕺🕺🕺🕺

[@romansharpe1131]

Спасибо, очень доступно разъяснено

[@Андрей-в7и6ь]

Крутая тема, интересная! Спасибо за видео! Очень мало хороших видосов на русском.

[@romanyefimenko5812]

Спасибо большое)) На некоторых деталях правда малый акцент, пришлось пару раз посмотреть чтобы осознать логику

[@ТестТест-в3ъ]

Здарова ! Огромное спасибо ! Я посмотрел весь твой канал , и ты один из бриллиантов в Ютубе , не бросай пж это дело! Если нужно идея , то как на счёт Алгоритм Гилберта - Джонсона - Кирти

[@kuk3637]

Интересен разбор конкретно точек с телепортацией.

[@S1yGus]

Очень понятное и наглядное объяснение. Спасибо!

[@KirillBreuss]

Спасибо!) Божественно разжевал всё!)

[@friendsgaming4822]

Великолепное видео) Очень жду разбор трёхмерный поиск пути Спасибо за старания!

[@BobSmith-qg9wn]

Самое простое и наглядное объяснение

[@MihailOnuchin]

Спасибо! Очень наглядно.

[@ebtyx]

Вычесление быстрейшего способа завязать шнурки на адидас кросовках

[@Андрей-в7и6ь]

Ты гений! Спасибо за подробное чёткое разъяснение!

[@nexgenua]

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

[@uebyCyka]

а можно поточнее описать?

[@ЦиклЖизни]

Ого! Я раньше пытался эту задачу через графы решить. Наверное неделю Мучался, но так ничего и не понял, а тут всё так элементарно решено, аж стыдно стало, что сам к такому решению не смог дойти.

[@gamedevru3833]

Можно сказать, что здесь так же использовались графы, только в виде квадратных клеток, так что теперь и остальные алгоритмы должны стать более понятны. Так или иначе, рад что смог доступно изложить материал.

[@jtcnjtc]

дык это все равно задача на графах

[@modjaid3907]

пытался решить задачу на графах до сих пор не зная, что такое графы, мддааа

[@АлександрКакушкин-л9ж]

Только в алгоритме допущена небольшая ошибка. Функция оценки остатка пути должна давать нижнюю границу. Иначе алгоритм может сформировать не оптимальный путь. Или потратить больше времени (но это не так опасно). Манхеттенское расстояние в данном случае может давать завышенное значение. Лучше использовать функцию max(dx,dy)*10 + min(dx,dy)*4, дающую точную нижнюю границу (остаток пути на свободной от препятствий площадке).

[@gamedevru3833]

Да, я думал над этим моментом. В процессе тестирования гонял алгоритм по сетке 10 000 х 10 000 клеток, но так и не получил никаких видимых сбоев в построении оптимального пути. Потому посчитал, что не стоит усложнять расчёты для видео.

[@АлександрКакушкин-л9ж]

Тут важен не размер Неправильный путь легко получить на относительно маленькой сетке. Для этого потребуется всего ничего. Например. ___________ Н_ППП __ППП __ППП __ППП _____________Ц На картинке препятствие в виде прямоугольника. Начало поиска находится слева, вровень с верхним краем препятствия, с одной пустой ячейкой. Цель в ряду непосредственно под препятствием, вправо сдвинута так, что можно пройти по диагонали в ряд над препятствием. В том виде, что у тебя, алгоритм идёт по нижнему пути, хотя верхний явно короче. Картинка , кстати достаточно типичная. Препятствие То, что оценка остатка пути не должна превышать действительного остатка, особо подчёркивается во всех серьёзных описаниях этого алгоритма. Кроме предложенного мной годится более простая эвристика: max(dx,dy)*10. Это более грубая оценка, придётся анализировать больше вариантов, но она тоже даст кратчайший путь.

[@tim-mal8735]

Большое спасибо!!!

[@samserious5483]

Очень понятно, спасибо

[@MikeAillen]

Эвристика слабая , так он будет неправильно считать дальние расстояния, в случае с блокировками стартовых соседей. Лучше квадрат разницы по X + квадрат разницы по Y не умножая на 10

[@edgaredgar4160]

Возникла идея решить это через дп, но не знал как это перенести в игровое пространство

[@SergeyPatuk]

Когдато лет 7 тому назад я думал что это чтото гениальное.

[@SergeyPatuk]

@Dark Crafter Чем занимаешся ?

[@slava_zxz]

А что за визуализатор на видео?

[@3akycka690]

Ребята, алгоритм несомненно огонь, сам его повторил, но может кто-нибудь дать ссылку на хардбасс?

[@RafaelShepard]

давненько я памп не слышал

[@ЛёшаАркитов]

2:16 откуда взялось 10 единиц? Это мы сами от балды придумываем? Или как?

[@dDevusS89]

Просто и понятно) пошел писать свой код

[@zahar_AI]

Привет! А в чем существенное отличие от алгоритма Дейкстры? Можно же это все перерисовать в граф, или Дейкстра будет медленнее работать на больших картах?

[@uebyCyka]

Дейкстра находит кратчайшее расстояние до ВСЕХ точек из исходной. А а* только до одной нужной. Таким образом, если стартовая точка сместилась, вычислять всё придётся по новой. А раз так, лучше же снова искать путь до одной точки, а не до всех?

[@СтаніславДеркач-щ6и]

Чувствую себя преисполнившись

[@Desotterro]

Родненький, ты где?

[@gamedevru3833]

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

[@Desotterro]

@@gamedevru3833 фуух, а то я уж думал все, с концами, удачи, ждемс

[@uebyCyka]

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

[@uebyCyka]

Ага, я тупой был, извините

[@Салфетка-ь1ы]

Почему на 5:52 мы резко переместились на активную клетку сверху?

[@vitalii2321]

Потому как идет выбор по наименьшему весу из всех открытых клеток

[@Regin-cb4qd]

а что за музон?

[@DobinSergei]

Зачем умножать на 10 и 14? Это же 5 и 7. Музыка на фоне очень мешает!

[@AizarkLizard]

Жалко не описали ситуацию когда путь невозможно найти, по какой логике это определяется. Наверное по количеству переборов что сделано...

[@coolkingdom1502]

Если в открытом списке нет больше ячеек, то значит пути нет Просто же

[@павелмак-в8ж]

Приветствую. Интересно, а метод поиска в ширину не проще?

[@rKvinty]

проще но долго работает

[@FanTopRU]

Ааа... какого.. он находит кратчпйший путь в невзвешенном графе ;)

[@circus-overlord]

Можете подсказать что играет на фоне?

[@barbaferam4762]

алгоритмом волны вроде как нормально работает и для 3-х измерений

[@rKvinty]

Нормально и долго

[@nikitas3729]

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

[@supernova8486]

этот как стрелять по воробьям из пушки. Алгоритм Дийсктры используется если надо найти путь от текущей вершины ко всем вершинам в графе

[@foundersl]

Указанный способ визуализации и является графом. Любой переход между клетками - ребро, а клетка - узел. Недоступная клетка - отсутствие узла и, соответственно ребер к ней. Параметры проходимости - это суть параметры на ребрах, ведущих в эти клетки

[@nikitas3729]

@@foundersl Если честно, то я за 4 месяца уже понял это))

[@foundersl]

@@nikitas3729 ну так вдруг у кого-то еще такой же вопрос будет)

[@ЕдуардБездухов]

Эмм... А на чем ты игру пишешь?) Я не спорю, вся эта лобуда работает (привет теорие алгоритмов), но в Unity, например, есть такая штука как AI (если коротко: движок сам вычислит допустимый и оптимальный путь для ботов). Думаю, что в Край и Анриал энджен это всё тоже как то автоматизировно. Вобщем, твой видос полезен если игра будет писаться без движка (то ещё извращение) или для изучения этого алгоритма на реалистичном примере. Но вообще, думаю, что можно и лайк поставить - это же не челендж с изолентой)

[@Тестыбомжатскихвидеокарт]

Нифига, Unity вычисляет это только в Nav Mesh Agent, только в 3D, только по осям xz . Если пишешь 2D по осям xy, а по объектам то можно ходить, то нельзя, нужно писать свой алгоритм.

[@ЕдуардБездухов]

@@Тестыбомжатскихвидеокарт , можно написать 2д и в координатах ХZ, а для реализации "то можно ходить, то нельзя" использовать ту же фишку что и при создании дверей в 3д. Навмеш можно изменить динамически (например, так работают движущиеся платформы, двери и т. д.) А если боитесь что динамическое изменение навмеша навернёт оптимизацию то тригери вам в помощь. И всё это всё ещё проще, чем писать алгоритм с нуля, как по мне

[@Тестыбомжатскихвидеокарт]

2D в координатах XZ сделать нельзя. Только в XY. Спрайты можно повернуть на XZ, но тогда пропадают Polygon collider'ы, они не поворачиваются вместе со спрайтами, найти настройки этого я не смог. Как ни пытался, ничего больше придумать не смог. Пришлось повернуть игровую карту вместе с камерой, и теперь у меня 3D персонажи бегают по XY и направлены головой в сторону Z. И мне надо алгоритм, чтобы они бегали по XY спрайтам, при этом не наступали на запрещённые им спрайты.

[@ЕдуардБездухов]

@@Тестыбомжатскихвидеокарт , окей, протупил. 2.5д в XZ сделать можно, а 2д - нет. Можно сделать костыль: мир по XZ, всех персонажей и графон лепить на квады как спрайты и располагать очень близко к самому 2д миру (если мир по оси У 0, то персонажи по оси У 0.001). Не уверен что это рационально, но возможно. А что за игра у вас, кстати?

[@Тестыбомжатскихвидеокарт]

У меня спрайты наложены на плоскость XY - это страны. По странам должны бегать 3D войска, причём, бегать можно только по своей стране, вражеской и тем, которые дали разрешение на это. Если играл в CK2, HOI4 и EU4, поймёшь, как это выглядит. Распилить мир на 5000 регионов я не могу по причине количества, поэтому в игре только территории 200 стран как спрайты, а войска могут бегать в любую указанную точку. Мне надо сделать так, чтобы войска бегали в указанную точку только по тем территориям, в которых это можно. Nav Mesh Agent бегает только по XZ, на плоскости XY не работает, причём, ему нельзя просто так взять и указать разрешённые страны как список объектов класса.

[@НикитаБуров-ъ6р]

great explanation, terrible music 8-)

[@Trepetsky]

Так себе объяснение.

[@soundsbeard]

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

[@gamedevru3833]

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

[@ivanenzhaev2373]

@@gamedevru3833 вкусы могут быть разные, всем ну угодишь. Лично мне нравится, когда в видео нет музыки, тогда я могу включить, что мне нравится. В процессе написания этого сообщения я слушал данное видео с музыкой: kzbin.info/www/bejne/o2LYfYRtltetgdU

[@Артёмфомин-ш1ы]

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

[@dentiller]

Уважуха за DJ Blyatman друг) но оно мешает видосу

[@softwet4341]

я о обычно волновой алгоритм использую

[@mega_mak]

Я наоборот за научной составляющей иду к этим ресурсам, а вы говорите: "бла бла бла". Вообще ничего непонятно.

[@Денис-р5в4з]

Спасибо. Почти понятно, осталось реализовать руками)

[@ronallik]

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

[@worldofonline7316]

Самое понятное и наглядное объяснение! Супер!

[@maxwad]

"Затем мы получаем Манхэттенское значение..." Так а как получаем? Конкретно что надо сделать?

[@ЕвгенийКолосов-ф5н]

за гугли просто. Вроде на вики доступно описано.

[@stepanbazrov6330]

Ну надо глубже объяснять, рассказал бы, что такое графы

[@Книголюб-х4ь]

Отличный разбор, спасибо большое.