Допустим, у нас есть плоская карта, состоящая из тайлов. На некоторых тайлах стоят монстры, а на некоторых других – всякие штуки, которые монстров интересуют: игрок, оружие, зелья, боеприпасы и прочее в том же духе. Задача состоит в том, чтобы объяснить монстрам, к каким штукам им идти и как. Путь должен быть близким к оптимальному, а время вычисления – настолько маленьким, насколько это возможно. Один из самых простых способов – использовать тепловую карту дистанций до определённой цели или целей.Дисклеймер
Сразу скажу, что это довольно известный метод: он использовался и для ИИ противников в играх (например, brogue), и для РТС-ботов и для обеспечения движения частиц, и много для чего ещё. Ниже я буду обсуждать рогалик, то есть допущу, что мир состоит из дискретных квадратных тайлов и каждый объект находится хотя бы на одном из них, [отя в принципе то же самое можно сделать с любой топологией мира, которая изоморфна (связному) графу. Картинки позаимствованы из этой статьи на roguebasin.com
Зомби
Чтобы объяснить, как работают тепловые карты, я для начала создам самого простого возможного монстра – зомби. Он должен просто гнаться за игроком, не отвлекаясь на весь остальной мир, а оказавшись рядом – кидаться в рукопашную. Жизнь нам упростит ещё и тот факт, что в рогаликах ближняя атака и перемещение традиционно выполняются одной командой, так что на самом деле зомби делает ровно одну вещь: прёт кратчайшим путём в направлении игрока. Весь ИИ, соответственно, сводится к поиску этого самого кратчайшего пути.
Для поиска пути нам понадобится двумерный массив размером с карту, каждая ячейка которого содержит расстояние от этого тайла до игрока. Пусть значение в тайле, в котором находится игрок, равно нулю; в соседних тайлах оно равно единице, в следующем ряду двойке и так далее. В общем случае, значение тайла на единицу больше, чем наименьшее значение среди его соседей. Непроходимые тайлы игнорируются, то есть туда ставится None или какое-нибудь запредельно большое число. Должно получиться примерно вот так:
Теперь зомби достаточно на каждом ходу узнавать значения соседних тайлов, выбирать из них наименьшее и шагать в соответствующем направлении. Если там уже стоит другой зомби или что-то ещё мешает войти – брать вариант чуть похуже и так далее, пока есть тайлы со значением не больше текущего. Если одинаково хороших вариантов несколько – выбирать случайным образом. В общем-то, всё. Зомби уверенно движутся к игроку, подрываясь на минах и подставляясь под огонь, как им и положено по законам жанра. Вот, кстати, интерактивное демо на HaxeFlixel.
Первое достоинство такого метода очевидно: он быстрый. При обходе в ширину сложность пересчёта в худшем случае линейна от площади карты. На практике большая часть ходов игрока либо не меняет карту вовсе (если он стоит на одном месте), либо влияет только на соседние клетки. Время, которое сами зомби тратят на выбор хода, пренебрежимо мало. Из этого, кстати, следует второе достоинство: сколько угодно зомби могут пользоваться одной и той же картой, то есть повышение численности монстров почти не увеличивает время, потраченное на ход. Неважно, один зомби на экране или тысяча – они всё равно будут ориентироваться за примерно одинаковое время.
Множественные аттракторы
Для демонстрации чуть более сложного поведения можно создать гоблина. У него в жизни есть две цели: нападать на игрока, аналогично зомби, и собирать золото. Соответственно, в начале расчёта карты мы не только ставим ноль под игроком, но и указываем какое-нибудь значение под каждым тайлом, на котором лежит хотя бы одна монетка. Расстояния расчитываются так же, как и в предыдущем примере. На картинке ниже для золота указано значение -4, то есть гоблин готов идти за золотом несколько дальше, чем за шансом превратиться в десять единиц экспы.
Возникает очевидная проблема: что, если добавить в одну игру и зомби, и гоблинов? Они имеют разное поведение и уже не могут использовать одну и ту же карту. А если завести по тепловой карте для каждого типа ИИ, преимущество в скорости может быстро сойти на нет. Решение состоит в том, чтобы создать по карте для каждого типа аттрактора. Каждый ИИ тогда будет брать значения из всех интересующих его карт и выбирать следующий шаг на основании взвешенной суммы. Каким образом “Карта с игроком”, “Карта с золотом” и “Карта со стрелами” быстрее, чем “Карта для зомби”, “Карта для гоблинов” и “Карта для кентавров”? Всё дело в частоте обсчёта. Карту нужно обновлять только тогда, когда меняются её аттракторы. Как правило, игрок либо двигается, либо подбирает с пола золото, либо стреляет в монстра, но не всё одновременно. То есть за ход обычно обновляется всего одна карта, а в случае отдельных карт с ИИ пришлось бы пересчитывать все сразу.
Расширяем ИИ
Гоблину нужно думать ещё об одной проблеме, которая не волновала зомби. Подразумевается, что он хочет собрать золото, но тепловая карта может приказать ему только подойти к нему. К счастью, искусственный интеллект не ограничивается одной только картой. Проверка направления движения происходит уже после того, как монстр выяснил, что в текущей локации ему делать, собственно, нечего. Можно увеличить быстродействие, проверяя возможность других действий только в локальных минимумах карты, но это обычно преждевременная оптимизация: многие клетки, на которых монстру на самом деле есть чем заняться, локальными минимумами не являются.
Ещё один минус описанной имплементации: зомби будет биться об игрока, даже если у него остался 1 HP, а умирающий от голода гоблин не перестанет собирать золото. Окей, для этих двух существ такое скорее норма, но вообще-то у монстра должно быть несколько типов поведения в зависимости от обстоятельств. Как обычно, здесь нам поможет конечный автомат. Особенность в случае тепловых карт только в том, что для каждого состояния автомата задан свой вектор весов карт. Тяжелораненный противник будет скорее отступать от игрока, то есть умножать значение из соответствующей карты на что-то отрицательное, но со всех ног бежать к ближайшей лечилке, отдавая большой вес значению из карты зелий. Голодный будет таким же образом стремиться к еде, стараться не попадаться на глаза игроку и вовсе игнорировать лежащие на полу боеприпасы.
Подводные камни
Таковых лично я нашёл три. Во-первых, путей из точки A в точку B может быть больше одного. Для ИИ это не проблема: монстры, идущие к игроку разными путями, чуть меньше тыкают в глаза детерминированностью своего поведения и даже выглядят чуть умнее, чем они есть на самом деле. Но в статье на roguebasin предлагается с помощью тех же карт показывать путь от игрока до курсора при навигации с помощью мышки или стрельбе. Это очень плохая идея: путь, который таким образом отображается на экране, может быть, и оптимальный, но не обязан совпадать с путём, которым в ту же точку отправится персонаж. Для стрельбы или заклинаний эта проблема ещё серьёзнее, потому что карты не запрещают обходить углы и двигаться по кривой (если это позволяет топология карты). А стрелять за угол должна только положенная на бок мортира из известного анекдота.
Во-вторых, этот метод игнорирует поле зрения монстров. Зомби вполне способен гнаться за игроком через полкарты, даже если он его ни разу не видел и не должен бы вообще знать о его существовании. Можно допустить, что если игрок видит монстра – то монстр его видит тоже (с поправкой на скрытность). Тогда тепловая карта обновляется только в пределах поля зрения игрока и тайлы за его пределами игнорируются так же, как непроходимые. Это костыль, но, увы, честное поле зрения для всех NPC на коленке не обсчитаешь.
В-третьих, каждый противник действует сам по себе. Создав карту с монстрами в качестве аттракторов, можно задать поведения типа “Сбиваться в стаю” или “Следовать за лидером”, но сложное тактическое взаимодействие монстров тоже требует более серьёзной работы над искусственным интеллектом.
Заключение
Вот так из спичек и желудей можно собрать неплохой искусственный интеллект. Он не будет гениальным, но при удачной балансировке весов карт и хорошо настроенном конечном автомате противники выглядят сильно умнее, чем они есть на самом деле.
PS: Этот метод, оказывается, называется алгоритмом Ли. Спасибо Shtucer за поправку.
Комментарии (26)
Shtucer
08.08.2016 18:14+5«Тепловые карты»? Алгоритм Ли
synedra
08.08.2016 18:19+2Ваша правда, добавил правку в статью. Проблема ещё в том, что этот метод описывается сильно разными терминами в разных источниках. На «Алгоритм Ли» я не наткнулся, пока рылся по англоязычным туториалам, связанным с геймдевом, но видел «Heat maps», «Dijkstra maps», «Distance maps», «Wavefront algorithm» и, кажется, «Weighted map».
Shtucer
08.08.2016 18:43+4На геймдевовских русскоязычных сайтах я его чаще всего встречал под названием «Волновой алгоритм».
OlegKozlov
08.08.2016 21:40+1Волновой алгоритм (я бы сказал просто поиск в ширину), это способ расчета этой самой тепловой карты. Фишка тепловой карты, насколько я понял, в том что она одна считается для целей, а не для тех, кто строит путь. На каждого зомби пускать волну и рассчитывать путь ресурсов не напасёшься, вот тогда мы и переворачиваем ситуацию. Очень элегантно!
CrazyFizik
09.08.2016 05:18+1Ну потому то это не совсем волновой алгоритм.
Алгоритм Мура-Ли узкоспециализированный и ищет только кратчайший путь на планарном графе. Во время работы этого алгоритму каждой ячейке на карте присваивается стоимость движения из точки А с учетом возможных весов перехода из ячейки в ячейку (в простейшем случае это 1), после чего из точки В (куда нужно придти) восстанавливаем путь последовательно выбирая ячейки с наименьшим весом. Ну да, похоже, но только пока аттрактор один.
Здесь же описан частный случай метода потенциальных полей (Potential Field Method) — при наличии одного аттрактора на графе в контексте поиска пути от А (стартовой позиции агента) до В (положения аттрактора), собственно и получаем этот совсем частный случай — алгоритм Мура-Ли.
Если же аттракторов несколько, если пристувуют еще и силы отталкивания, и если все эти силы будут еще и разные, то тогда агент будет двигаться по градиенту (ну или против градиента как в данном случае), пока не свалиться в локальный минимум, который не всегда находится там же где и целевая точка В (в отличии от волнового алгоритма, где путь находится всегда). Ну и метод потенциальных полей применим не только к решетчатым моделям, а к любым http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.9504&rep=rep1&type=pdf
DmitryMry
08.08.2016 19:26+1Год назад была неплохая статья по теме: https://habrahabr.ru/post/262181/ (у вас упоминается оригинал, здесь перевод)
OlegKozlov
08.08.2016 21:42+1Круто, спасибо! Одна из тех тем, что будучи прочитанными кажутся элементарными и интуитивными. Словно и это и раньше знал. Хотя не знал. :) У себя в игре я ничего подобного и не додумался применить, хотя мог бы и испытываю местами проблемы с производительностью.
VitaZheltyakov
08.08.2016 23:37+3По поводу видимости игрока для монстра:
— Это элементарно. Сравниваете расстояние (полученое алгоритмом поиска пути) от монстра до игрока с учетом препятствий и без. Если расстояния равны, то монстр видит игрока
vlaeda
09.08.2016 09:22Это не совсем верно. Представьте себе карту где можно ходить только по горизонтали и вертикали, непроходимый квадрат на этой карте и монстра с игроком на противоположных углах квадрата. Как то так:
e___
_##_
_##_
___p
Расстояние между ними кратчайшее, а видимости нет.
Предложенный вами метод работает скорей всего только для плоской карты и расстояния определяемого по теореме Пифагора.vlivyur
09.08.2016 11:34+1Кратчайшее расстояние — диагональ, пройти можно только по сторонам. Расстояния не равны — не видят. Вроде работает.
CrazyNiger
09.08.2016 11:53Если ходить можно только по горизонтали и вертикали, то каким бы способом не шел, то всегда шесть ходов (пппннн или пнпнпн)
VitaZheltyakov
09.08.2016 17:28-2В вашем примере кратчайшее расстояние с учетом препятствий равно 6, кратчайшее расстояние без учета препятствий равно 3. Расстояния не равны — монстр не видит игрока.
Прежде, чем писать критические комментарии, научитесь внимательно читать и думать головой.
VitaZheltyakov
09.08.2016 17:54-2Я пронял вашу логику — вы исключаете движение по диагонали.
В этом случае задача бессмыслена, т.к. не имеет решения. Любое расположение препятствия можно считать как «монстр видит игрока» и «монстр не видит игрока».
Даже вот такой пример можно расценивать двояко:
е_
#р
Поэтому ваша задача (с исключением движения по диагонали) изначально абсурда. Так что — думайте головойvlaeda
09.08.2016 19:42Впредь я буду стараться думать головой!
Рассмотрите следующий пример допуская движения по диагонали:
e_________
__________
_________p
Пример вообще без препятствий. Расстояние между игроком и монстром по прямой короче любого адекватного пути между ними по дискретным клеткам по этому монстр не будет видеть игрока по вашему алгоритму.
В случае же если местность непредставима в виде дискретного графа, то к такой задаче рассматриваемый в статье класс алгоритмов не применим вообще.
Duster
10.08.2016 10:04Вы не совсем поняли суть идеи. Брать нужно не прямой отрезок от сикера до аттрактора, а путь, полученный поиском, не учитывающим препятствия.
То есть прогоняется алгоритм два раза: 1) обычный поиск пути, 2) тот же самый поиск пути, только с отключенными препятствиями.
И сравниваются уже их длины.
Если длины одинаковые — препятствия нет, сикеру чтобы достичь аттрактор нужен прямой путь.
Если разница есть — значит сикер должен будет что-то обойти, прежде чем достигнет аттрактора, и значит, что он его не видит.synedra
10.08.2016 11:19Может оказаться неоднозначно, если имеется несколько оптимальных путей. Например, вот так:
A . . . .
. . . . .
. . # . .
. . . . B
Существует два оптимальных пути, один из которых проходит через препятствие, другой не проходит. Заслоняет ли стена А от В? Хороший вопрос. Некоторые имплементации линии зрения (кажется, даже классический Брезенхэм) превращают стену в полупрозрачную, то есть А видит B, но не наоборот; если считать, что стена в сечении квадратная со стороной в тайл, то линия из центра A в центр B её пересекает и должна заслонять.
vlaeda
10.08.2016 17:29Да, контрпример для этой идеи я описал в своем первом комментарии:
e___
_##_
_##_
___p
А предыдущий написал в ответ на предположение что надо сравнивать с прямым расстоянием.
Вообщем если видимость считается не по тем же правилам по которым можно передвигаться, то все весьма нетривиально.
inborn_killer
10.08.2016 18:54Может, я скажу полнейшую глупость, но нельзя ли в таком случае иметь две тепловые карты — передвижения и видимости? Карта передвижения строится с учётом только вертикальных и горизонтальных передвижений, а видимости — уже с учётом диагональных ходов. Тогда по карте видимости можно будет определить, видит ли монстр игрока, а передвигаться будет уже по другой карте.
По-моему, это даже не слишком похоже на костыль, потому что и в реальной жизни мы можем видеть что-то, но не иметь возможности добраться до этого объекта по прямой.
В этом случае можно будет использовать «прозрачные» препятствия (окна, ловушки, заборы), сквозь которые монстр может увидеть игрока, но будет вынужден преследовать его по другому пути.vlaeda
11.08.2016 05:00+1Я уверен, что ваша идея будет работать корректно.
Сложность тут заключается в том, что все рассматриваемые в статье и в коментариях классы алгоритмов основаны на том, что движение транзитивно, тоесть если из А можно попасть в B, а из B в C, то из А можно попасть в C. К сожалению это не верно для видимости по прямой. По этому для построения карт видимости придется применять принципиально более сложные алгоритмы из области геометрии.
wey
09.08.2016 05:20Тогда тепловая карта обновляется только в пределах поля зрения игрока и тайлы за его пределами игнорируются так же, как непроходимые.
А как вам вариант, если зомби будет запоминать тепловую карту и обновлять её, только заметив игрока? Тогда он прибежит в ту точку где последний раз видел игрока, помоему довольно честноsynedra
09.08.2016 05:21+1При достаточно большой карте и многочисленных зомби будут немаленькие требования к памяти. Если это не проблема — тогда да, конечно.
trapwalker
09.08.2016 05:21А почему видимость монстрами игрока не проверять по той же тепловой карте по треш-холду? Причем треш-холд и по прямому расстоянию и по расстоянию траектории доступности. То есть, просто не прибавляем аттрактор к весу рассматриваемого направления, если его значение в рассматриваемой ячейке меньше порогового.
Altium
09.08.2016 09:55Первое достоинство такого метода очевидно: он быстрый
Насколько я понимаю, это частный случай поиска в ширину, самого ресурсоемкого и затратного метода поиска пути.CrazyNiger
09.08.2016 10:42+2Зато поиск не нужно делать для каждого «монстра» каждый ход. Карта пересчитывается только при смене позиции игрока, и общая для всех зомбей.
synedra
09.08.2016 10:20+1В случае одного монстра и одной цели — да, тот же A* был бы быстрее. Но на практике одно построение карты и два десятка обращений к ней получаются быстрее, чем гонять по полноценному A* для каждого противника.
Lain_13
В демке на HaxeFlixel если не трогать аттрактор, ограничить область справа и сделать выход из неё в 1 точку по правому краю, то сикеры будут выходить за карту и не возвращаться. :)