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

[Steed]

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

[khim]

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

[TheShock]

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

[khim]

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

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

[Steed]

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

[confa]

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

[Zoolander]

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

[XopHeT]

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

[AstarothAst]

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

[khim]

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

[AstarothAst]

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

[khim]

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

[slavenski]

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

[Idot]

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

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

[PatientZero]

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

[khim]

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

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

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

[PatientZero]

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

[Idot]

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

[dmagin]

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

[i_osipov]

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