PatientZero Jun 20 2017 at 11:24

Введение в алгоритм A*

10 min

178K

Game development*Algorithms*

Translation

+68

Comments 20

Steed Jun 20 2017 at 17:32

Спасибо, отличная вводная статья с понятными картинками и не переусложненным кодом. Разобраться было просто. Более того, захотелось еще поэкспериментировать (а что будет, если поменять эвристику A* и т.п.) :)

khim Jun 20 2017 at 21:01

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

TheShock Jun 20 2017 at 22:05

А у меня в этом сервисе A* выдает разные маршруты

khim Jun 20 2017 at 22:09

Никто не обещал, что A* выдаст тот же самый маршрут. Может и другой, если оптимальных больше, чем один.

В этой самом статье, которую мы комментируем, написано чего требуется от эвристики.

Steed Jun 20 2017 at 23:20

Цитата из статьи: "A* гарантированно найдёт кратчайший путь, если эвристика никогда не больше истинного расстояния."
Что понятно, т.к. при нулевом коэффициенте при расстоянии она становится жадным алгоритмом. Мне сразу интересно: равенство коэффициентов — это фазовый переход, или нет? Т.е. есть ли сценарии, когда истинное расстояние меньше эвристики, но при этом алгоритм всегда находит кратчайший путь.

confa Jun 20 2017 at 20:42

Отличная статья для начинающих с понятным описанием. В свое время пользовался вот этим сервисом для наглядности и примера работы большей части pathfind алгоритмов.

Zoolander Jun 20 2017 at 22:52

Спасибо, реквестую еще

XopHeT Jun 21 2017 at 09:38

Только недавно с этими алгоритмами разобрался сам.
Эта статья значительно сократила бы время на изучение.
Спасибо!

AstarothAst Jun 21 2017 at 09:56

А если нужно искать пути в трехмерном пространстве, как, например, в Dwarf Fortress, то какие алгоритмы используются? Можно ожидать статьи по ним?

khim Jun 21 2017 at 10:01

Вы бы статью-то прочитали перед тем, как комментировать, а? Желательно — до конца.

AstarothAst Jun 21 2017 at 10:05

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

khim Jun 21 2017 at 10:36

Алгоритмам, о которых идёт речь в статье, в общем-то, пофигу, сколько у вас там измерений (и даже неважно — конечно ли их часто), они слишком общие. Для двухмерных/трёхмерных и прочих частных случаев, разумеется, есть отдельные алгоритмы — но это уже совсем другая история.

slavenski Jun 23 2017 at 09:16

Хорошая статья, хотелось бы узнать, а при большом количестве вершин, сравним ли А* с муравьиными алгоритмами?, заранее прошу прощения, если задал неуместный вопрос.

Idot Jun 26 2017 at 10:57

А можно модифицировать так чтобы он давал не самый оптимальный маршрут?

А то беда шутеров: когда противник ломится по наикратчайшему пути давая себя легко расстрелять, и никто даже не пытается обойти с тыла или с фланга.

PatientZero Jun 26 2017 at 11:08

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

khim Jun 26 2017 at 12:55

Можно и в поиске путей. Просто повысьте «цену» каждого метра, который ты проходишь «под дулом» автомата (а это, как бы, и итуитивно ясно, ведь правда?) — и все противники пойдут в обход как миленькие.

Проблема в другом: как только противник всему этому научится, станет всё верно рассчитывать и оценивать — получится у вас AlphaGo. И? Кто потом это купит?

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

PatientZero Jun 26 2017 at 13:10

Да, понятно, что нет никаких проблем сделать бота всевидящим, всезнающим и раздающим хедшоты с одного выстрела. Но разнообразное поведение интересно игроку: один враг отвлекает стрельбой из укрытия, остальные обходят с флангов и потом, естественно, все они эффектно погибают :)

Idot Jun 26 2017 at 13:23

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

dmagin Jun 27 2017 at 15:42

Традиционно в подобных темах не вижу алгебраического подхода.
Поэтому оставляю ссылки на свои статьи на хабре — Первая часть и Вторая часть.
В которых показано, что можно один раз рассчитать дистанционную матрицу между всеми узлами графа и потом легко находить пути между двумя заданными узлами через возмущение потенциалов узлов.
Кроме того, необязательно также пересчитывать всю матрицу, если изменились параметры какой-либо связи — есть простые формулы корректировки матрицы.
Единственное ограничение — если узлов очень много (тысячи), то первоначальный расчет может быть долгим — используется обращение матрицы.

i_osipov Nov 4 2017 at 01:13

Было интересно почитать, спасибо за ссылки на оригиналы

Show the best of all time