Начал делать свою игрулю, ничего не понимая в алгоритмах поиска пути, но тут наткнулся на это видео. Автор всё разложил по полочкам. Хороший видос, лайк подписка, было бы интересно узнать про другие алгоритмы Джакарту и прочее!
Ого! Я раньше пытался эту задачу через графы решить. Наверное неделю Мучался, но так ничего и не понял, а тут всё так элементарно решено, аж стыдно стало, что сам к такому решению не смог дойти.
Можно сказать, что здесь так же использовались графы, только в виде квадратных клеток, так что теперь и остальные алгоритмы должны стать более понятны. Так или иначе, рад что смог доступно изложить материал.
спасибо большое, всё максимально доступно. было бы интересно ещё в это всё дело ввести координату z и посмотреть, многое ли изменится. единственное замечание - это музыка. она, скажем мягко, на любителя.
@@gamedevru3833 вкусы могут быть разные, всем ну угодишь. Лично мне нравится, когда в видео нет музыки, тогда я могу включить, что мне нравится. В процессе написания этого сообщения я слушал данное видео с музыкой: ua-cam.com/video/m1uLQ7arzKs/v-deo.html
Здарова ! Огромное спасибо ! Я посмотрел весь твой канал , и ты один из бриллиантов в Ютубе , не бросай пж это дело! Если нужно идея , то как на счёт Алгоритм Гилберта - Джонсона - Кирти
у этого алгоритма есть баг, не знаю как его побороть, если например клетка 9 х 9 и мы двигаемся из нижнего левого в верхний правый и ровно посередине стоит вертикальная преграда, то по этому алгоритму оно всегда будет идти вверх, что приводит к увеличению ходов примерно в 2 раза
Только в алгоритме допущена небольшая ошибка. Функция оценки остатка пути должна давать нижнюю границу. Иначе алгоритм может сформировать не оптимальный путь. Или потратить больше времени (но это не так опасно). Манхеттенское расстояние в данном случае может давать завышенное значение. Лучше использовать функцию max(dx,dy)*10 + min(dx,dy)*4, дающую точную нижнюю границу (остаток пути на свободной от препятствий площадке).
Да, я думал над этим моментом. В процессе тестирования гонял алгоритм по сетке 10 000 х 10 000 клеток, но так и не получил никаких видимых сбоев в построении оптимального пути. Потому посчитал, что не стоит усложнять расчёты для видео.
Тут важен не размер Неправильный путь легко получить на относительно маленькой сетке. Для этого потребуется всего ничего. Например. ___________ Н_ППП __ППП __ППП __ППП _____________Ц На картинке препятствие в виде прямоугольника. Начало поиска находится слева, вровень с верхним краем препятствия, с одной пустой ячейкой. Цель в ряду непосредственно под препятствием, вправо сдвинута так, что можно пройти по диагонали в ряд над препятствием. В том виде, что у тебя, алгоритм идёт по нижнему пути, хотя верхний явно короче. Картинка , кстати достаточно типичная. Препятствие То, что оценка остатка пути не должна превышать действительного остатка, особо подчёркивается во всех серьёзных описаниях этого алгоритма. Кроме предложенного мной годится более простая эвристика: max(dx,dy)*10. Это более грубая оценка, придётся анализировать больше вариантов, но она тоже даст кратчайший путь.
Привет! А в чем существенное отличие от алгоритма Дейкстры? Можно же это все перерисовать в граф, или Дейкстра будет медленнее работать на больших картах?
Дейкстра находит кратчайшее расстояние до ВСЕХ точек из исходной. А а* только до одной нужной. Таким образом, если стартовая точка сместилась, вычислять всё придётся по новой. А раз так, лучше же снова искать путь до одной точки, а не до всех?
Эвристика слабая , так он будет неправильно считать дальние расстояния, в случае с блокировками стартовых соседей. Лучше квадрат разницы по X + квадрат разницы по Y не умножая на 10
А можно пожалуйста объяснить как при показе тестов этого алгоритма получилось так, что бот погонял по всему полю, но все равно нашел оптимальный путь, а не оставил тот, в котором он обхолит все поле?
Указанный способ визуализации и является графом. Любой переход между клетками - ребро, а клетка - узел. Недоступная клетка - отсутствие узла и, соответственно ребер к ней. Параметры проходимости - это суть параметры на ребрах, ведущих в эти клетки
Эмм... А на чем ты игру пишешь?) Я не спорю, вся эта лобуда работает (привет теорие алгоритмов), но в 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 не работает, причём, ему нельзя просто так взять и указать разрешённые страны как список объектов класса.
![Алгоритмы Поиска Пути на Python. Алгоритм А*, Дейкстры, Поиск в ширину [ Pygame ]](http://i.ytimg.com/vi/xXvNDrF4obQ/mqdefault.jpg)
![🗺️ NavMesh - поиск пути и перемещение по карте [Unity 3D] [Tutorial]](/img/n.gif)
Самое понятное и наглядное объяснение алгоритма. Спасибо большое!
Начал делать свою игрулю, ничего не понимая в алгоритмах поиска пути, но тут наткнулся на это видео. Автор всё разложил по полочкам.
Хороший видос, лайк подписка, было бы интересно узнать про другие алгоритмы Джакарту и прочее!
Скоро будут ещё видео по игрострою.
Спасибо за подписку и удачи вам в ваших начинаниях)
Спасибо за отличную подачу материала. Благодаря Вашему видео, наконец-то, понял и решил задачу. Спасибо.
За хардбасс на фоне ставлю дополнительный лайк)
Одновременно просто и гениально. Возьму на вооружение.
Ого! Я раньше пытался эту задачу через графы решить. Наверное неделю Мучался, но так ничего и не понял, а тут всё так элементарно решено, аж стыдно стало, что сам к такому решению не смог дойти.
Можно сказать, что здесь так же использовались графы, только в виде квадратных клеток, так что теперь и остальные алгоритмы должны стать более понятны.
Так или иначе, рад что смог доступно изложить материал.
дык это все равно задача на графах
пытался решить задачу на графах до сих пор не зная, что такое графы, мддааа
Великолепно. Когда читал про этот алгоритм в книге - вообще не понимал зачем нужен этот примитив. Но здесь хорошо показано насколько он изощрённый.
Самое понятное и наглядное объяснение! Супер!
Пишу вкр на тему "Подбор подходящего маршрута...", и искала материал по алгоритмам поиска
Интересный и наглядный разбор - спасибо! 👍
Спасибо, помог до конца понять алгоритм перед экзаменом!)
Вау. Впечатлен подачей и объяснением алгоритма
спасибо большое, всё максимально доступно. было бы интересно ещё в это всё дело ввести координату z и посмотреть, многое ли изменится.
единственное замечание - это музыка. она, скажем мягко, на любителя.
Спасибо за отзыв. В следующих видео ответственнее подойду к выбору музыкального сопровождения.
@@gamedevru3833 вкусы могут быть разные, всем ну угодишь. Лично мне нравится, когда в видео нет музыки, тогда я могу включить, что мне нравится. В процессе написания этого сообщения я слушал данное видео с музыкой: ua-cam.com/video/m1uLQ7arzKs/v-deo.html
Я: Просто смотрю видео для изучения алгоритма🗿 Также хардбасс на фоне:🕺🕺🕺🕺
Про 3ехмерный поиск пути было бы очень интересно
А разве трёхмерная сетка принципиально отличается? Просто берем соседние индексы для i, j и k.
Дай бог тебе здоровья
ххахаха лучшее объяснение что я видел и с хардбассом на фоне!
как же я люблю свой народ
Интересен разбор конкретно точек с телепортацией.
Спасибо. Почти понятно, осталось реализовать руками)
Самое простое и наглядное объяснение
Спасибо, очень доступно разъяснено
Отличный разбор, спасибо большое.
Спасибо! Очень наглядно.
Очень понятное и наглядное объяснение. Спасибо!
Спасибо!) Божественно разжевал всё!)
Спасибо большое)) На некоторых деталях правда малый акцент, пришлось пару раз посмотреть чтобы осознать логику
Крутая тема, интересная! Спасибо за видео! Очень мало хороших видосов на русском.
Ты гений! Спасибо за подробное чёткое разъяснение!
Здарова ! Огромное спасибо ! Я посмотрел весь твой канал , и ты один из бриллиантов в Ютубе , не бросай пж это дело! Если нужно идея , то как на счёт Алгоритм Гилберта - Джонсона - Кирти
Великолепное видео)
Очень жду разбор трёхмерный поиск пути
Спасибо за старания!
у этого алгоритма есть баг, не знаю как его побороть, если например клетка 9 х 9 и мы двигаемся из нижнего левого в верхний правый и ровно посередине стоит вертикальная преграда, то по этому алгоритму оно всегда будет идти вверх, что приводит к увеличению ходов примерно в 2 раза
а можно поточнее описать?
Очень понятно, спасибо
Большое спасибо!!!
Возникла идея решить это через дп, но не знал как это перенести в игровое пространство
Только в алгоритме допущена небольшая ошибка.
Функция оценки остатка пути должна давать нижнюю границу. Иначе алгоритм может сформировать не оптимальный путь. Или потратить больше времени (но это не так опасно).
Манхеттенское расстояние в данном случае может давать завышенное значение. Лучше использовать функцию max(dx,dy)*10 + min(dx,dy)*4, дающую точную нижнюю границу (остаток пути на свободной от препятствий площадке).
Да, я думал над этим моментом. В процессе тестирования гонял алгоритм по сетке 10 000 х 10 000 клеток, но так и не получил никаких видимых сбоев в построении оптимального пути.
Потому посчитал, что не стоит усложнять расчёты для видео.
Тут важен не размер
Неправильный путь легко получить на относительно маленькой сетке. Для этого потребуется всего ничего. Например.
___________
Н_ППП
__ППП
__ППП
__ППП
_____________Ц
На картинке препятствие в виде прямоугольника. Начало поиска находится слева, вровень с верхним краем препятствия, с одной пустой ячейкой.
Цель в ряду непосредственно под препятствием, вправо сдвинута так, что можно пройти по диагонали в ряд над препятствием. В том виде, что у тебя, алгоритм идёт по нижнему пути, хотя верхний явно короче.
Картинка , кстати достаточно типичная. Препятствие
То, что оценка остатка пути не должна превышать действительного остатка, особо подчёркивается во всех серьёзных описаниях этого алгоритма.
Кроме предложенного мной годится более простая эвристика: max(dx,dy)*10. Это более грубая оценка, придётся анализировать больше вариантов, но она тоже даст кратчайший путь.
Вычесление быстрейшего способа завязать шнурки на адидас кросовках
Привет!
А в чем существенное отличие от алгоритма Дейкстры? Можно же это все перерисовать в граф, или Дейкстра будет медленнее работать на больших картах?
Дейкстра находит кратчайшее расстояние до ВСЕХ точек из исходной. А а* только до одной нужной. Таким образом, если стартовая точка сместилась, вычислять всё придётся по новой. А раз так, лучше же снова искать путь до одной точки, а не до всех?
Когдато лет 7 тому назад я думал что это чтото гениальное.
@Dark Crafter Чем занимаешся ?
Уважуха за DJ Blyatman друг) но оно мешает видосу
А что за визуализатор на видео?
Ребята, алгоритм несомненно огонь, сам его повторил, но может кто-нибудь дать ссылку на хардбасс?
Учитывая что алгоритм может просматривать диагональ не смотря, на две ячейки которые могут быть поперёк то на диагоналях он должен проскакивать в щель
Просто и понятно) пошел писать свой код
Почему на 5:52 мы резко переместились на активную клетку сверху?
Потому как идет выбор по наименьшему весу из всех открытых клеток
Чувствую себя преисполнившись
Эвристика слабая , так он будет неправильно считать дальние расстояния, в случае с блокировками стартовых соседей.
Лучше квадрат разницы по X + квадрат разницы по Y не умножая на 10
2:16 откуда взялось 10 единиц? Это мы сами от балды придумываем? Или как?
Клетка находится на расстоянии 1 от стартовой точки, 1*10 = 10
А можно пожалуйста объяснить как при показе тестов этого алгоритма получилось так, что бот погонял по всему полю, но все равно нашел оптимальный путь, а не оставил тот, в котором он обхолит все поле?
Ага, я тупой был, извините
Приветствую. Интересно, а метод поиска в ширину не проще?
проще но долго работает
Ааа... какого.. он находит кратчпйший путь в невзвешенном графе ;)
а что за музон?
давненько я памп не слышал
я о обычно волновой алгоритм использую
Можете подсказать что играет на фоне?
Родненький, ты где?
Прямо сейчас работаю над новым видео. Надеюсь, что закончу и опубликую его в ближайшее время.
@@gamedevru3833 фуух, а то я уж думал все, с концами, удачи, ждемс
Жалко не описали ситуацию когда путь невозможно найти, по какой логике это определяется. Наверное по количеству переборов что сделано...
Если в открытом списке нет больше ячеек, то значит пути нет
Просто же
"Затем мы получаем Манхэттенское значение..." Так а как получаем? Конкретно что надо сделать?
за гугли просто. Вроде на вики доступно описано.
Просто глупый вопрос, а можно ли представь нашу "местность" в виде графа и решить через алгоритм декстера?
этот как стрелять по воробьям из пушки. Алгоритм Дийсктры используется если надо найти путь от текущей вершины ко всем вершинам в графе
Указанный способ визуализации и является графом. Любой переход между клетками - ребро, а клетка - узел. Недоступная клетка - отсутствие узла и, соответственно ребер к ней. Параметры проходимости - это суть параметры на ребрах, ведущих в эти клетки
@@foundersl Если честно, то я за 4 месяца уже понял это))
@@nikitas3729 ну так вдруг у кого-то еще такой же вопрос будет)
алгоритмом волны вроде как нормально работает и для 3-х измерений
Нормально и долго
Зачем умножать на 10 и 14? Это же 5 и 7.
Музыка на фоне очень мешает!
great explanation, terrible music 8-)
Ну надо глубже объяснять, рассказал бы, что такое графы
Эмм... А на чем ты игру пишешь?) Я не спорю, вся эта лобуда работает (привет теорие алгоритмов), но в 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 не работает, причём, ему нельзя просто так взять и указать разрешённые страны как список объектов класса.
Я наоборот за научной составляющей иду к этим ресурсам, а вы говорите: "бла бла бла". Вообще ничего непонятно.
Так себе объяснение.