73

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

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


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


Надеюсь, что это будет кому то полезным.

Дубликаты не найдены

+3

Спасибо, интересно!

раскрыть ветку 2
+5

Спасибо за отзыв. Значит не зря старался)

раскрыть ветку 1
0

Да, реально интересно. Мне это интересно практически, т.к. я тихонько пилю симулятор железной дороги и как раз подхожу к моменту, когда мне надо будет делать поиск пути.

+2

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

+2

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

Сам варюсь в теме попроще, разработка софта с позиции аналитика/менеджера проекта.

раскрыть ветку 1
+3

По мере возможности буду снимать подобные видео. Тем уже много себе накидал. Найти бы на всё это время...

+1

Скажите ленивому, там теория графов? Я посмотрел первые 30 сек,  дальше ле

раскрыть ветку 8
+1

Никакой теории графов. Лишь наглядное, пошаговое объяснение принципов работы алгоритма А*

раскрыть ветку 5
0

Понял, спасибо, из алгоритмов поиска кратчайшего пути я знаком лишь с графами:) думал это панацея на все подобные случаи:)

раскрыть ветку 4
0

Про графы ни слова не было. Просто описание алгоритма довольно простого и демонстрация его работы.

раскрыть ветку 1
0

Спасибо:)

+1
Уйди! Нет, только не алгоритмы поиска!!!!!!! Сгинь!!!!
0

Вот бы кто рассказал, как искать пути в вертикальной карте, с платформами, разными прыжками, разной скоростью и высотой юнита.

0

Было бы интересно послушать про алгоритм такого плана, или хотя бы узнать его название, если подобное существует)


Берём точку А и точку Б, пытаемся наступить на клетку, которая по прямой в сторону точки Б, если мы не можем пройти вперёд, то считаем клетку влево, если не можем пройти по ней, то считаем клетку вправо от той на которую наступили и так по очереди, прямо, лево, право и пока не достигнем цели.

раскрыть ветку 2
0

Вижу сразу несколько слабых сторон такого метода.
- Как "прыгать на клетку влево/вправо" Если точки А и Б находится не на 1 линии сетки, а под углом, например в 30градусов? По диагонали, или двигаться только ортодоксально?
- Как алгоритм решит задачу на скриншете? Убежит вниз и начнёт тыкаться в стенки застряв в нижнем правом углу?
- Даже если методом перебора доберётся до цели, то нашли ли мы при этом кратчайший из возможных путей? Мы же нигде не сохраняем информацию о длине пути и оптимальном маршруте, а просто перебираем клетки пытаясь достигнуть финиша.

Хотя в теории это применимо для просторных карт без сложных преград. Если нужно обходить врагов, или выпуклые препятствия в пару клеток.

Иллюстрация к комментарию
раскрыть ветку 1
0
- Как "прыгать на клетку влево/вправо" Если точки А и Б находится не на 1 линии сетки, а под углом, например в 30градусов? По диагонали, или двигаться только ортодоксально?

По диагонали тоже можно


- Как алгоритм решит задачу на скриншете? Убежит вниз и начнёт тыкаться в стенки застряв в нижнем правом углу?

Сначала убежит вниз, потом упрётся в заданный лимит по отдалению точки и начнёт просчет вверх


- Даже если методом перебора доберётся до цели, то нашли ли мы при этом кратчайший из возможных путей? Мы же нигде не сохраняем информацию о длине пути и оптимальном маршруте, а просто перебираем клетки пытаясь достигнуть финиша.

Да, в данном случае получается не по кротчайшему, а по первому найденному


Ну да, теперь я и сам вижу унылость метода)

0

В свое время тоже надо было запрогать, наткнулся на отличное объяснение с интерактивными примерами, правда на английском. Там заодно разобран и жадный алгоритм и Дийкстра.
https://www.redblobgames.com/pathfinding/a-star/introduction...

0

Не совсем понял, почему по диагонали на 4 единицы больше?

раскрыть ветку 9
+1

В данном случае движение по диагонали = движение по гипотенузе равностороннего треугольника. По теореме Пифагора гипотенуза равностороннего треугольника в 1,414 раза длиннее его стороны. Потому движение по диагонали я и считаю в 1.4 раза дороже ортогонального движения.

раскрыть ветку 8
0

В таком случае непонятно почему вы используете манхэттенское расстояние для эвристики

раскрыть ветку 6
0

Понял вас, спасибо!

0

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

0

Круто. Вопрос такой: в видео алгоритм для клеточных игр, а, например, для симулятора футбола как поиск пути происходит? Или это вообще отдельная тема?

раскрыть ветку 3
+1

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

раскрыть ветку 2
+2

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

раскрыть ветку 1
0

Ну, ёбана. Только что читал мангу, где это было. Синдром Бендера из Майкопа

-1

В Ютубе много видео по данному вопросу, скажите пикабутяне, чем этот лучше ?

раскрыть ветку 1
+1

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

-3

Я отказываюсь смотреть 9 минут.

Всегда пользовался правилом, которое вычитал еще в "Занимательной математике" Перельмана - держаться рукой правой стены (всегда поворачивать направо)

раскрыть ветку 1
+2

тогда заблудитесь в четырех квадратах

-4

Нонче такое в обучательных целях с помощью генетических алгоритмов решают, а описанное настолько очевидно что курс computer science такое и не рассматривает

раскрыть ветку 1
+1

Я изучал этот алгоритм на Postgrad курсе computer Science, допустим

Похожие посты
Возможно, вас заинтересуют другие посты по тегам: