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

Поделиться
HTML-код
  • Опубликовано: 11 дек 2024

Комментарии • 97

  • @dmitrywroclaw9165
    @dmitrywroclaw9165 3 года назад +19

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

  • @poltos7235
    @poltos7235 Год назад +4

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

  • @oleggopp4388
    @oleggopp4388 4 года назад +23

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

    • @gamedevru3833
      @gamedevru3833  4 года назад +1

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

  • @flugenkehhannen
    @flugenkehhannen 5 месяцев назад +1

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

  • @antonbukhman5018
    @antonbukhman5018 Месяц назад

    Wow, Friend! Thank you very much)) You explanation is excellent! After this video I became your subscriber...

  • @АртурБерков-х8ч
    @АртурБерков-х8ч 4 года назад +7

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

  • @ronallik
    @ronallik Год назад

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

  • @petergorelov6852
    @petergorelov6852 Год назад

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

  • @ЦиклЖизни
    @ЦиклЖизни 4 года назад +8

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

    • @gamedevru3833
      @gamedevru3833  4 года назад +2

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

    • @jtcnjtc
      @jtcnjtc 4 года назад +2

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

    • @modjaid3907
      @modjaid3907 4 года назад +4

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

  • @mar_kha
    @mar_kha 2 года назад

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

  • @worldofonline7316
    @worldofonline7316 Год назад

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

  • @ВасилийГригорьев-з9х
    @ВасилийГригорьев-з9х 5 месяцев назад

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

  • @renonmay
    @renonmay 4 года назад +4

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

  • @goshator
    @goshator Год назад

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

  • @soundsbeard
    @soundsbeard 4 года назад +5

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

    • @gamedevru3833
      @gamedevru3833  4 года назад +1

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

    • @ivan.enzhaev
      @ivan.enzhaev 4 года назад +1

      @@gamedevru3833 вкусы могут быть разные, всем ну угодишь. Лично мне нравится, когда в видео нет музыки, тогда я могу включить, что мне нравится. В процессе написания этого сообщения я слушал данное видео с музыкой: ruclips.net/video/m1uLQ7arzKs/видео.html

  • @isgris5153
    @isgris5153 Год назад +2

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

  • @Денис-р5в4з
    @Денис-р5в4з 2 года назад

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

  • @romansharpe1131
    @romansharpe1131 4 года назад +4

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

  • @kuk3637
    @kuk3637 4 года назад

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

  • @Desotterro
    @Desotterro 4 года назад +35

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

    • @АзатМингалеев-в1к
      @АзатМингалеев-в1к 3 года назад +8

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

  • @romanyefimenko5812
    @romanyefimenko5812 4 года назад +1

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

  • @MihailOnuchin
    @MihailOnuchin 2 года назад

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

  • @VonBreuss
    @VonBreuss 3 года назад +1

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

  • @Андрей-в7и6ь
    @Андрей-в7и6ь 3 года назад +2

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

  • @S1yGus
    @S1yGus 3 года назад

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

  • @Книголюб-х4ь
    @Книголюб-х4ь 3 года назад

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

  • @ТестТест-в3ъ
    @ТестТест-в3ъ 4 года назад +3

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

  • @BobSmith-qg9wn
    @BobSmith-qg9wn 2 года назад +1

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

  • @friendsgaming4822
    @friendsgaming4822 3 года назад

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

  • @tim-mal8735
    @tim-mal8735 3 года назад

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

  • @Андрей-в7и6ь
    @Андрей-в7и6ь 3 года назад

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

  • @samserious5483
    @samserious5483 2 года назад

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

  • @nexgenua
    @nexgenua 4 года назад +4

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

    • @uebyCyka
      @uebyCyka 2 года назад

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

  • @edgaredgar4160
    @edgaredgar4160 Год назад

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

  • @SergeyPatuk
    @SergeyPatuk 4 года назад

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

    • @SergeyPatuk
      @SergeyPatuk 4 года назад

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

  • @ebtyx
    @ebtyx 5 месяцев назад

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

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

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

    • @gamedevru3833
      @gamedevru3833  4 года назад +2

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

    • @АлександрКакушкин-л9ж
      @АлександрКакушкин-л9ж 4 года назад +2

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

  • @Салфетка-ь1ы
    @Салфетка-ь1ы 2 года назад +1

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

    • @vitalii2321
      @vitalii2321 Год назад +1

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

  • @3akycka690
    @3akycka690 3 года назад +1

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

  • @Артёмфомин-ш1ы
    @Артёмфомин-ш1ы 3 месяца назад

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

  • @dDevusS89
    @dDevusS89 Год назад

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

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

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

  • @softwet4341
    @softwet4341 3 года назад +1

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

  • @RafaelShepard
    @RafaelShepard 7 месяцев назад

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

  • @slava_zxz
    @slava_zxz 9 месяцев назад

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

  • @MikeAillen
    @MikeAillen Год назад +1

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

  • @dentiller
    @dentiller 10 месяцев назад

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

  • @zahar_AI
    @zahar_AI 2 года назад +1

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

    • @uebyCyka
      @uebyCyka 2 года назад +2

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

  • @Desotterro
    @Desotterro 4 года назад +2

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

    • @gamedevru3833
      @gamedevru3833  4 года назад +1

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

    • @Desotterro
      @Desotterro 4 года назад +1

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

  • @uebyCyka
    @uebyCyka 4 года назад +2

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

    • @uebyCyka
      @uebyCyka 2 года назад

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

  • @Regin-cb4qd
    @Regin-cb4qd 2 года назад

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

  • @circus-overlord
    @circus-overlord 3 года назад

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

  • @AizarkLizard
    @AizarkLizard Год назад

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

    • @coolkingdom1502
      @coolkingdom1502 11 месяцев назад

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

  • @maxwad
    @maxwad 2 года назад

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

  • @barbaferam4762
    @barbaferam4762 4 года назад

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

    • @rKvinty
      @rKvinty 3 года назад

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

  • @павелмак-в8ж
    @павелмак-в8ж 4 года назад +1

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

    • @rKvinty
      @rKvinty 3 года назад +3

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

    • @FanTopRU
      @FanTopRU 2 года назад

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

  • @ЛёшаАркитов
    @ЛёшаАркитов 4 месяца назад

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

    • @liquid_name1068
      @liquid_name1068 2 месяца назад

      Клетка находится на расстоянии 1 от стартовой точки, 1*10 = 10

  • @DobinSergei
    @DobinSergei 5 месяцев назад

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

  • @nikitas3729
    @nikitas3729 4 года назад

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

    • @supernova8486
      @supernova8486 3 года назад +2

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

    • @foundersl
      @foundersl 3 года назад +2

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

    • @nikitas3729
      @nikitas3729 3 года назад

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

    • @foundersl
      @foundersl 3 года назад +2

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

  • @ЕдуардБездухов
    @ЕдуардБездухов 4 года назад +2

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

    • @Тестыбомжатскихвидеокарт
      @Тестыбомжатскихвидеокарт 4 года назад +2

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

    • @ЕдуардБездухов
      @ЕдуардБездухов 4 года назад +1

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

    • @Тестыбомжатскихвидеокарт
      @Тестыбомжатскихвидеокарт 4 года назад +1

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

    • @ЕдуардБездухов
      @ЕдуардБездухов 4 года назад +1

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

    • @Тестыбомжатскихвидеокарт
      @Тестыбомжатскихвидеокарт 4 года назад +1

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

  • @stepanbazrov6330
    @stepanbazrov6330 4 года назад +2

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

  • @mega_mak
    @mega_mak 4 года назад

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

  • @НикитаБуров-ъ6р
    @НикитаБуров-ъ6р Год назад +1

    great explanation, terrible music 8-)

  • @Trepetsky
    @Trepetsky 8 месяцев назад

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