Допустим, у нас есть плоская карта, состоящая из тайлов. На некоторых тайлах стоят монстры, а на некоторых других – всякие штуки, которые монстров интересуют: игрок, оружие, зелья, боеприпасы и прочее в том же духе. Задача состоит в том, чтобы объяснить монстрам, к каким штукам им идти и как. Путь должен быть близким к оптимальному, а время вычисления – настолько маленьким, насколько это возможно. Один из самых простых способов – использовать тепловую карту дистанций до определённой цели или целей.Дисклеймер
Сразу скажу, что это довольно известный метод: он использовался и для ИИ противников в играх (например, brogue), и для РТС-ботов и для обеспечения движения частиц, и много для чего ещё. Ниже я буду обсуждать рогалик, то есть допущу, что мир состоит из дискретных квадратных тайлов и каждый объект находится хотя бы на одном из них, [отя в принципе то же самое можно сделать с любой топологией мира, которая изоморфна (связному) графу. Картинки позаимствованы из этой статьи на roguebasin.com
Зомби
Чтобы объяснить, как работают тепловые карты, я для начала создам самого простого возможного монстра – зомби. Он должен просто гнаться за игроком, не отвлекаясь на весь остальной мир, а оказавшись рядом – кидаться в рукопашную. Жизнь нам упростит ещё и тот факт, что в рогаликах ближняя атака и перемещение традиционно выполняются одной командой, так что на самом деле зомби делает ровно одну вещь: прёт кратчайшим путём в направлении игрока. Весь ИИ, соответственно, сводится к поиску этого самого кратчайшего пути.
Для поиска пути нам понадобится двумерный массив размером с карту, каждая ячейка которого содержит расстояние от этого тайла до игрока. Пусть значение в тайле, в котором находится игрок, равно нулю; в соседних тайлах оно равно единице, в следующем ряду двойке и так далее. В общем случае, значение тайла на единицу больше, чем наименьшее значение среди его соседей. Непроходимые тайлы игнорируются, то есть туда ставится None или какое-нибудь запредельно большое число. Должно получиться примерно вот так:
Теперь зомби достаточно на каждом ходу узнавать значения соседних тайлов, выбирать из них наименьшее и шагать в соответствующем направлении. Если там уже стоит другой зомби или что-то ещё мешает войти – брать вариант чуть похуже и так далее, пока есть тайлы со значением не больше текущего. Если одинаково хороших вариантов несколько – выбирать случайным образом. В общем-то, всё. Зомби уверенно движутся к игроку, подрываясь на минах и подставляясь под огонь, как им и положено по законам жанра. Вот, кстати, интерактивное демо на HaxeFlixel.
Первое достоинство такого метода очевидно: он быстрый. При обходе в ширину сложность пересчёта в худшем случае линейна от площади карты. На практике большая часть ходов игрока либо не меняет карту вовсе (если он стоит на одном месте), либо влияет только на соседние клетки. Время, которое сами зомби тратят на выбор хода, пренебрежимо мало. Из этого, кстати, следует второе достоинство: сколько угодно зомби могут пользоваться одной и той же картой, то есть повышение численности монстров почти не увеличивает время, потраченное на ход. Неважно, один зомби на экране или тысяча – они всё равно будут ориентироваться за примерно одинаковое время.
Множественные аттракторы
Для демонстрации чуть более сложного поведения можно создать гоблина. У него в жизни есть две цели: нападать на игрока, аналогично зомби, и собирать золото. Соответственно, в начале расчёта карты мы не только ставим ноль под игроком, но и указываем какое-нибудь значение под каждым тайлом, на котором лежит хотя бы одна монетка. Расстояния расчитываются так же, как и в предыдущем примере. На картинке ниже для золота указано значение -4, то есть гоблин готов идти за золотом несколько дальше, чем за шансом превратиться в десять единиц экспы.
Возникает очевидная проблема: что, если добавить в одну игру и зомби, и гоблинов? Они имеют разное поведение и уже не могут использовать одну и ту же карту. А если завести по тепловой карте для каждого типа ИИ, преимущество в скорости может быстро сойти на нет. Решение состоит в том, чтобы создать по карте для каждого типа аттрактора. Каждый ИИ тогда будет брать значения из всех интересующих его карт и выбирать следующий шаг на основании взвешенной суммы. Каким образом “Карта с игроком”, “Карта с золотом” и “Карта со стрелами” быстрее, чем “Карта для зомби”, “Карта для гоблинов” и “Карта для кентавров”? Всё дело в частоте обсчёта. Карту нужно обновлять только тогда, когда меняются её аттракторы. Как правило, игрок либо двигается, либо подбирает с пола золото, либо стреляет в монстра, но не всё одновременно. То есть за ход обычно обновляется всего одна карта, а в случае отдельных карт с ИИ пришлось бы пересчитывать все сразу.
Расширяем ИИ
Гоблину нужно думать ещё об одной проблеме, которая не волновала зомби. Подразумевается, что он хочет собрать золото, но тепловая карта может приказать ему только подойти к нему. К счастью, искусственный интеллект не ограничивается одной только картой. Проверка направления движения происходит уже после того, как монстр выяснил, что в текущей локации ему делать, собственно, нечего. Можно увеличить быстродействие, проверяя возможность других действий только в локальных минимумах карты, но это обычно преждевременная оптимизация: многие клетки, на которых монстру на самом деле есть чем заняться, локальными минимумами не являются.
Ещё один минус описанной имплементации: зомби будет биться об игрока, даже если у него остался 1 HP, а умирающий от голода гоблин не перестанет собирать золото. Окей, для этих двух существ такое скорее норма, но вообще-то у монстра должно быть несколько типов поведения в зависимости от обстоятельств. Как обычно, здесь нам поможет конечный автомат. Особенность в случае тепловых карт только в том, что для каждого состояния автомата задан свой вектор весов карт. Тяжелораненный противник будет скорее отступать от игрока, то есть умножать значение из соответствующей карты на что-то отрицательное, но со всех ног бежать к ближайшей лечилке, отдавая большой вес значению из карты зелий. Голодный будет таким же образом стремиться к еде, стараться не попадаться на глаза игроку и вовсе игнорировать лежащие на полу боеприпасы.
Подводные камни
Таковых лично я нашёл три. Во-первых, путей из точки A в точку B может быть больше одного. Для ИИ это не проблема: монстры, идущие к игроку разными путями, чуть меньше тыкают в глаза детерминированностью своего поведения и даже выглядят чуть умнее, чем они есть на самом деле. Но в статье на roguebasin предлагается с помощью тех же карт показывать путь от игрока до курсора при навигации с помощью мышки или стрельбе. Это очень плохая идея: путь, который таким образом отображается на экране, может быть, и оптимальный, но не обязан совпадать с путём, которым в ту же точку отправится персонаж. Для стрельбы или заклинаний эта проблема ещё серьёзнее, потому что карты не запрещают обходить углы и двигаться по кривой (если это позволяет топология карты). А стрелять за угол должна только положенная на бок мортира из известного анекдота.
Во-вторых, этот метод игнорирует поле зрения монстров. Зомби вполне способен гнаться за игроком через полкарты, даже если он его ни разу не видел и не должен бы вообще знать о его существовании. Можно допустить, что если игрок видит монстра – то монстр его видит тоже (с поправкой на скрытность). Тогда тепловая карта обновляется только в пределах поля зрения игрока и тайлы за его пределами игнорируются так же, как непроходимые. Это костыль, но, увы, честное поле зрения для всех NPC на коленке не обсчитаешь.
В-третьих, каждый противник действует сам по себе. Создав карту с монстрами в качестве аттракторов, можно задать поведения типа “Сбиваться в стаю” или “Следовать за лидером”, но сложное тактическое взаимодействие монстров тоже требует более серьёзной работы над искусственным интеллектом.
Заключение
Вот так из спичек и желудей можно собрать неплохой искусственный интеллект. Он не будет гениальным, но при удачной балансировке весов карт и хорошо настроенном конечном автомате противники выглядят сильно умнее, чем они есть на самом деле.
PS: Этот метод, оказывается, называется алгоритмом Ли. Спасибо Shtucer за поправку.
