Содержание материала
Общий алгоритм
Этот раздел — самая важная часть всей статьинеобходимоA*поймёте смыслreachableexploredДальше я изложу ядро алгоритмаpreviousreachablereachablepreviousЭтокаждогоA*почемуАлгоритм Дейкстры (Dijkstra)
Этот алгоритм назван по имени создателя и был разработан в 1959 году. В процессе выполнения алгоритм проверит каждую из вершин графа, и найдет кратчайший путь до исходной вершины. Стандартная реализация работает на взвешенном графе — графе, у которого каждый путь имеет вес, т.е. «стоимость», которую надо будет «заплатить», чтобы перейти по этому ребру. При этом в стандартной реализации веса неотрицательны. На клетчатом поле вес каждого ребра графа принимается одинаковым (например, единицей).
Видео
Адаптирование игрового мира
Компьютер не может просто посмотреть на камень и сказать, что это камень. Поэтому ему надо описать игровой мир в виде чисел и выбрать набор признаков, по которым будет определяться, что между двумя точками можно пройти.
Большая часть алгоритмов строится на графах — в математике так называется фигура, которая состоит из точек и соединяющих их линий (рёбер). Поэтому пути прохода по игровому миру превращают в графы. В качестве точек-кружочков обычно берут минимальную площадь мира, в которой передвижение от одного края до второго происходит мгновенно (или же за достаточно маленькое время, чтобы считать его мгновенным). Иначе говоря, в играх эти кружочки — это позиции персонажа. Рёбра же обозначают тот факт, что ты с первого куска мира можешь перейти на второй.
Пример построения графа (игра «Депония»)
Одна из простых вариаций графа — игровая сетка, где кружочками являются клетки, а рёбра проводятся между любыми соседними клетками, свободными от препятствий. Проще всего разобраться в этом на примере пошаговых игр, у которых сетку видно невооружённым глазом, вроде Sneaky-Sneaky или Return of the Necrodancer.
Примерная сетка в игре Sneaky-Sneaky
Клетки, на которых стоят непреодолимые препятствия, обозначаются крестиком, а проходимые места — пустотой. Или, если говорить на языке программирования, клетки обозначаются 0 или 1, где 0 означает, что пройти нельзя, а 1 — что пройти можно. Более сложные игры вроде Heroes of Might and Magic III отличаются только тем, что их сетка рисуется более произвольно, а клетки, которые расположены на разных типах земли, отнимают разное количество шагов.
При работе с трёхмерными мирами можно использовать двухмерную карту проекции ландшафта с указанием высот в точках. В этом случае на каждой ячейке написана её высота, а проходимость определяется через разницу высот соседних клеток.
В Death Stranding упрощённую карту для поиска пути можно увидеть при сканировании местности. Крестиками показываются непроходимые места, жёлтым — проходимые с трудом, голубым — легко проходимые.
Зачастую адаптация игрового мира — это самая сложная часть, потому что алгоритмы поиска оптимальных маршрутов изобретены давно, можно даже найти готовый код для них. Поэтому разработчики внедряют один из алгоритмов и потом экспериментируют с разными моделями и вариациями сравнений двух путей, или комбинируют разные алгоритмы в попытках добиться наилучшего и наименее затратного результата.
Не магический, но довольно потрясающий A*
кратчайший путьминимальное расстояниерасстояние городских кварталовabs(Ax - Bx) + abs(Ay - By)sqrt( (Ax - Bx)^2 + (Ay - By)^2 )слишкомchoose_nodeэвристикойA*Поиск по первому наилучшему совпадению (Best-First Search)
Усовершенствованная версия алгоритма поиска в ширину, отличающаяся от оригинала тем, что в первую очередь развертываются узлы, путь из которых до конечной вершины предположительно короче. Т.е. за счет эвристики делает для BFS то же, что A* делает для алгоритма Дейкстры.
Алгоритм A*
Визуализация алгоритма A* в игре Factorio
Алгоритм А* пытается усидеть на обоих стульях сразу: найти кратчайшее расстояние, но сделать это за меньшее время, чем алгоритм Дейкстры. Поэтому следующая точка на рассмотрение выбирается по минимальной сумме расстояний до начала и до конца пути. Это единственное отличие от предыдущих алгоритмов.
Есть и другие алгоритмы, которые дают преимущества при разных условиях. Сами алгоритмы по поиску пути довольно просты, но они работают для сферических идеальных условий в вакууме. В реальных играх существует много нюансов, которые могут усложнить алгоритм. Например, может быть несколько вариантов перемещений, повороты, препятствия могут двигаться, могут быть узкие места, в которых врагам желательно не толпиться. Каждое такое условие делает движение более интересным, но и замедляет работу алгоритма. Из-за этого приходится что-то упрощать или выкручиваться по-другому для оптимизации работы игры.
Несколько интересных примеров можно прочитать в статьях про новый алгоритм поиска пути в Factorio и про устройство поведения полчищ крыс в A Plague Tale: Innocence.