AI монстров и поиск пути с помощью тепловых карт

    image Допустим, у нас есть плоская карта, состоящая из тайлов. На некоторых тайлах стоят монстры, а на некоторых других – всякие штуки, которые монстров интересуют: игрок, оружие, зелья, боеприпасы и прочее в том же духе. Задача состоит в том, чтобы объяснить монстрам, к каким штукам им идти и как. Путь должен быть близким к оптимальному, а время вычисления – настолько маленьким, насколько это возможно. Один из самых простых способов – использовать тепловую карту дистанций до определённой цели или целей.

    Дисклеймер


    Сразу скажу, что это довольно известный метод: он использовался и для ИИ противников в играх (например, brogue), и для РТС-ботов и для обеспечения движения частиц, и много для чего ещё. Ниже я буду обсуждать рогалик, то есть допущу, что мир состоит из дискретных квадратных тайлов и каждый объект находится хотя бы на одном из них, [отя в принципе то же самое можно сделать с любой топологией мира, которая изоморфна (связному) графу. Картинки позаимствованы из этой статьи на roguebasin.com

    Зомби


    Чтобы объяснить, как работают тепловые карты, я для начала создам самого простого возможного монстра – зомби. Он должен просто гнаться за игроком, не отвлекаясь на весь остальной мир, а оказавшись рядом – кидаться в рукопашную. Жизнь нам упростит ещё и тот факт, что в рогаликах ближняя атака и перемещение традиционно выполняются одной командой, так что на самом деле зомби делает ровно одну вещь: прёт кратчайшим путём в направлении игрока. Весь ИИ, соответственно, сводится к поиску этого самого кратчайшего пути.

    Для поиска пути нам понадобится двумерный массив размером с карту, каждая ячейка которого содержит расстояние от этого тайла до игрока. Пусть значение в тайле, в котором находится игрок, равно нулю; в соседних тайлах оно равно единице, в следующем ряду двойке и так далее. В общем случае, значение тайла на единицу больше, чем наименьшее значение среди его соседей. Непроходимые тайлы игнорируются, то есть туда ставится None или какое-нибудь запредельно большое число. Должно получиться примерно вот так:

    image

    Теперь зомби достаточно на каждом ходу узнавать значения соседних тайлов, выбирать из них наименьшее и шагать в соответствующем направлении. Если там уже стоит другой зомби или что-то ещё мешает войти – брать вариант чуть похуже и так далее, пока есть тайлы со значением не больше текущего. Если одинаково хороших вариантов несколько – выбирать случайным образом. В общем-то, всё. Зомби уверенно движутся к игроку, подрываясь на минах и подставляясь под огонь, как им и положено по законам жанра. Вот, кстати, интерактивное демо на HaxeFlixel.


    Первое достоинство такого метода очевидно: он быстрый. При обходе в ширину сложность пересчёта в худшем случае линейна от площади карты. На практике большая часть ходов игрока либо не меняет карту вовсе (если он стоит на одном месте), либо влияет только на соседние клетки. Время, которое сами зомби тратят на выбор хода, пренебрежимо мало. Из этого, кстати, следует второе достоинство: сколько угодно зомби могут пользоваться одной и той же картой, то есть повышение численности монстров почти не увеличивает время, потраченное на ход. Неважно, один зомби на экране или тысяча – они всё равно будут ориентироваться за примерно одинаковое время.

    Множественные аттракторы


    Для демонстрации чуть более сложного поведения можно создать гоблина. У него в жизни есть две цели: нападать на игрока, аналогично зомби, и собирать золото. Соответственно, в начале расчёта карты мы не только ставим ноль под игроком, но и указываем какое-нибудь значение под каждым тайлом, на котором лежит хотя бы одна монетка. Расстояния расчитываются так же, как и в предыдущем примере. На картинке ниже для золота указано значение -4, то есть гоблин готов идти за золотом несколько дальше, чем за шансом превратиться в десять единиц экспы.


    Возникает очевидная проблема: что, если добавить в одну игру и зомби, и гоблинов? Они имеют разное поведение и уже не могут использовать одну и ту же карту. А если завести по тепловой карте для каждого типа ИИ, преимущество в скорости может быстро сойти на нет. Решение состоит в том, чтобы создать по карте для каждого типа аттрактора. Каждый ИИ тогда будет брать значения из всех интересующих его карт и выбирать следующий шаг на основании взвешенной суммы. Каким образом “Карта с игроком”, “Карта с золотом” и “Карта со стрелами” быстрее, чем “Карта для зомби”, “Карта для гоблинов” и “Карта для кентавров”? Всё дело в частоте обсчёта. Карту нужно обновлять только тогда, когда меняются её аттракторы. Как правило, игрок либо двигается, либо подбирает с пола золото, либо стреляет в монстра, но не всё одновременно. То есть за ход обычно обновляется всего одна карта, а в случае отдельных карт с ИИ пришлось бы пересчитывать все сразу.

    Расширяем ИИ


    Гоблину нужно думать ещё об одной проблеме, которая не волновала зомби. Подразумевается, что он хочет собрать золото, но тепловая карта может приказать ему только подойти к нему. К счастью, искусственный интеллект не ограничивается одной только картой. Проверка направления движения происходит уже после того, как монстр выяснил, что в текущей локации ему делать, собственно, нечего. Можно увеличить быстродействие, проверяя возможность других действий только в локальных минимумах карты, но это обычно преждевременная оптимизация: многие клетки, на которых монстру на самом деле есть чем заняться, локальными минимумами не являются.

    Ещё один минус описанной имплементации: зомби будет биться об игрока, даже если у него остался 1 HP, а умирающий от голода гоблин не перестанет собирать золото. Окей, для этих двух существ такое скорее норма, но вообще-то у монстра должно быть несколько типов поведения в зависимости от обстоятельств. Как обычно, здесь нам поможет конечный автомат. Особенность в случае тепловых карт только в том, что для каждого состояния автомата задан свой вектор весов карт. Тяжелораненный противник будет скорее отступать от игрока, то есть умножать значение из соответствующей карты на что-то отрицательное, но со всех ног бежать к ближайшей лечилке, отдавая большой вес значению из карты зелий. Голодный будет таким же образом стремиться к еде, стараться не попадаться на глаза игроку и вовсе игнорировать лежащие на полу боеприпасы.

    Подводные камни


    Таковых лично я нашёл три. Во-первых, путей из точки A в точку B может быть больше одного. Для ИИ это не проблема: монстры, идущие к игроку разными путями, чуть меньше тыкают в глаза детерминированностью своего поведения и даже выглядят чуть умнее, чем они есть на самом деле. Но в статье на roguebasin предлагается с помощью тех же карт показывать путь от игрока до курсора при навигации с помощью мышки или стрельбе. Это очень плохая идея: путь, который таким образом отображается на экране, может быть, и оптимальный, но не обязан совпадать с путём, которым в ту же точку отправится персонаж. Для стрельбы или заклинаний эта проблема ещё серьёзнее, потому что карты не запрещают обходить углы и двигаться по кривой (если это позволяет топология карты). А стрелять за угол должна только положенная на бок мортира из известного анекдота.

    Во-вторых, этот метод игнорирует поле зрения монстров. Зомби вполне способен гнаться за игроком через полкарты, даже если он его ни разу не видел и не должен бы вообще знать о его существовании. Можно допустить, что если игрок видит монстра – то монстр его видит тоже (с поправкой на скрытность). Тогда тепловая карта обновляется только в пределах поля зрения игрока и тайлы за его пределами игнорируются так же, как непроходимые. Это костыль, но, увы, честное поле зрения для всех NPC на коленке не обсчитаешь.

    В-третьих, каждый противник действует сам по себе. Создав карту с монстрами в качестве аттракторов, можно задать поведения типа “Сбиваться в стаю” или “Следовать за лидером”, но сложное тактическое взаимодействие монстров тоже требует более серьёзной работы над искусственным интеллектом.

    Заключение


    Вот так из спичек и желудей можно собрать неплохой искусственный интеллект. Он не будет гениальным, но при удачной балансировке весов карт и хорошо настроенном конечном автомате противники выглядят сильно умнее, чем они есть на самом деле.

    PS: Этот метод, оказывается, называется алгоритмом Ли. Спасибо Shtucer за поправку.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 26
      +1
      В демке на HaxeFlixel если не трогать аттрактор, ограничить область справа и сделать выход из неё в 1 точку по правому краю, то сикеры будут выходить за карту и не возвращаться. :)
        +5
        «Тепловые карты»? Алгоритм Ли
          +2
          Ваша правда, добавил правку в статью. Проблема ещё в том, что этот метод описывается сильно разными терминами в разных источниках. На «Алгоритм Ли» я не наткнулся, пока рылся по англоязычным туториалам, связанным с геймдевом, но видел «Heat maps», «Dijkstra maps», «Distance maps», «Wavefront algorithm» и, кажется, «Weighted map».
            +4
            На геймдевовских русскоязычных сайтах я его чаще всего встречал под названием «Волновой алгоритм».
              +1
              Волновой алгоритм (я бы сказал просто поиск в ширину), это способ расчета этой самой тепловой карты. Фишка тепловой карты, насколько я понял, в том что она одна считается для целей, а не для тех, кто строит путь. На каждого зомби пускать волну и рассчитывать путь ресурсов не напасёшься, вот тогда мы и переворачиваем ситуацию. Очень элегантно!
              +1
              Ну потому то это не совсем волновой алгоритм.
              Алгоритм Мура-Ли узкоспециализированный и ищет только кратчайший путь на планарном графе. Во время работы этого алгоритму каждой ячейке на карте присваивается стоимость движения из точки А с учетом возможных весов перехода из ячейки в ячейку (в простейшем случае это 1), после чего из точки В (куда нужно придти) восстанавливаем путь последовательно выбирая ячейки с наименьшим весом. Ну да, похоже, но только пока аттрактор один.

              Здесь же описан частный случай метода потенциальных полей (Potential Field Method) — при наличии одного аттрактора на графе в контексте поиска пути от А (стартовой позиции агента) до В (положения аттрактора), собственно и получаем этот совсем частный случай — алгоритм Мура-Ли.
              Если же аттракторов несколько, если пристувуют еще и силы отталкивания, и если все эти силы будут еще и разные, то тогда агент будет двигаться по градиенту (ну или против градиента как в данном случае), пока не свалиться в локальный минимум, который не всегда находится там же где и целевая точка В (в отличии от волнового алгоритма, где путь находится всегда). Ну и метод потенциальных полей применим не только к решетчатым моделям, а к любым http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.431.9504&rep=rep1&type=pdf
            +1
            Год назад была неплохая статья по теме: https://habrahabr.ru/post/262181/ (у вас упоминается оригинал, здесь перевод)
              +1
              Круто, спасибо! Одна из тех тем, что будучи прочитанными кажутся элементарными и интуитивными. Словно и это и раньше знал. Хотя не знал. :) У себя в игре я ничего подобного и не додумался применить, хотя мог бы и испытываю местами проблемы с производительностью.
                +3
                По поводу видимости игрока для монстра:
                — Это элементарно. Сравниваете расстояние (полученое алгоритмом поиска пути) от монстра до игрока с учетом препятствий и без. Если расстояния равны, то монстр видит игрока
                  0
                  Это не совсем верно. Представьте себе карту где можно ходить только по горизонтали и вертикали, непроходимый квадрат на этой карте и монстра с игроком на противоположных углах квадрата. Как то так:
                  e___
                  _##_
                  _##_
                  ___p

                  Расстояние между ними кратчайшее, а видимости нет.

                  Предложенный вами метод работает скорей всего только для плоской карты и расстояния определяемого по теореме Пифагора.
                    +1
                    Кратчайшее расстояние — диагональ, пройти можно только по сторонам. Расстояния не равны — не видят. Вроде работает.
                      0
                      Если ходить можно только по горизонтали и вертикали, то каким бы способом не шел, то всегда шесть ходов (пппннн или пнпнпн)
                      –2
                      В вашем примере кратчайшее расстояние с учетом препятствий равно 6, кратчайшее расстояние без учета препятствий равно 3. Расстояния не равны — монстр не видит игрока.

                      Прежде, чем писать критические комментарии, научитесь внимательно читать и думать головой.
                        –2
                        Я пронял вашу логику — вы исключаете движение по диагонали.

                        В этом случае задача бессмыслена, т.к. не имеет решения. Любое расположение препятствия можно считать как «монстр видит игрока» и «монстр не видит игрока».
                        Даже вот такой пример можно расценивать двояко:
                        е_


                        Поэтому ваша задача (с исключением движения по диагонали) изначально абсурда. Так что — думайте головой
                          0
                          Впредь я буду стараться думать головой!

                          Рассмотрите следующий пример допуская движения по диагонали:
                          e_________
                          __________
                          _________p

                          Пример вообще без препятствий. Расстояние между игроком и монстром по прямой короче любого адекватного пути между ними по дискретным клеткам по этому монстр не будет видеть игрока по вашему алгоритму.

                          В случае же если местность непредставима в виде дискретного графа, то к такой задаче рассматриваемый в статье класс алгоритмов не применим вообще.

                            0
                            Вы не совсем поняли суть идеи. Брать нужно не прямой отрезок от сикера до аттрактора, а путь, полученный поиском, не учитывающим препятствия.
                            То есть прогоняется алгоритм два раза: 1) обычный поиск пути, 2) тот же самый поиск пути, только с отключенными препятствиями.
                            И сравниваются уже их длины.
                            Если длины одинаковые — препятствия нет, сикеру чтобы достичь аттрактор нужен прямой путь.
                            Если разница есть — значит сикер должен будет что-то обойти, прежде чем достигнет аттрактора, и значит, что он его не видит.
                              0
                              Может оказаться неоднозначно, если имеется несколько оптимальных путей. Например, вот так:
                              A . . . .
                              . . . . .
                              . . # . .
                              . . . . B

                              Существует два оптимальных пути, один из которых проходит через препятствие, другой не проходит. Заслоняет ли стена А от В? Хороший вопрос. Некоторые имплементации линии зрения (кажется, даже классический Брезенхэм) превращают стену в полупрозрачную, то есть А видит B, но не наоборот; если считать, что стена в сечении квадратная со стороной в тайл, то линия из центра A в центр B её пересекает и должна заслонять.
                                0
                                Да, контрпример для этой идеи я описал в своем первом комментарии:
                                e___
                                _##_
                                _##_
                                ___p

                                А предыдущий написал в ответ на предположение что надо сравнивать с прямым расстоянием.

                                Вообщем если видимость считается не по тем же правилам по которым можно передвигаться, то все весьма нетривиально.

                            0
                            Может, я скажу полнейшую глупость, но нельзя ли в таком случае иметь две тепловые карты — передвижения и видимости? Карта передвижения строится с учётом только вертикальных и горизонтальных передвижений, а видимости — уже с учётом диагональных ходов. Тогда по карте видимости можно будет определить, видит ли монстр игрока, а передвигаться будет уже по другой карте.
                            По-моему, это даже не слишком похоже на костыль, потому что и в реальной жизни мы можем видеть что-то, но не иметь возможности добраться до этого объекта по прямой.
                            В этом случае можно будет использовать «прозрачные» препятствия (окна, ловушки, заборы), сквозь которые монстр может увидеть игрока, но будет вынужден преследовать его по другому пути.
                              +1
                              Я уверен, что ваша идея будет работать корректно.

                              Сложность тут заключается в том, что все рассматриваемые в статье и в коментариях классы алгоритмов основаны на том, что движение транзитивно, тоесть если из А можно попасть в B, а из B в C, то из А можно попасть в C. К сожалению это не верно для видимости по прямой. По этому для построения карт видимости придется применять принципиально более сложные алгоритмы из области геометрии.
                          0
                          Тогда тепловая карта обновляется только в пределах поля зрения игрока и тайлы за его пределами игнорируются так же, как непроходимые.

                          А как вам вариант, если зомби будет запоминать тепловую карту и обновлять её, только заметив игрока? Тогда он прибежит в ту точку где последний раз видел игрока, помоему довольно честно
                            +1
                            При достаточно большой карте и многочисленных зомби будут немаленькие требования к памяти. Если это не проблема — тогда да, конечно.
                            0
                            А почему видимость монстрами игрока не проверять по той же тепловой карте по треш-холду? Причем треш-холд и по прямому расстоянию и по расстоянию траектории доступности. То есть, просто не прибавляем аттрактор к весу рассматриваемого направления, если его значение в рассматриваемой ячейке меньше порогового.
                              0
                              Первое достоинство такого метода очевидно: он быстрый

                              Насколько я понимаю, это частный случай поиска в ширину, самого ресурсоемкого и затратного метода поиска пути.
                                +2
                                Зато поиск не нужно делать для каждого «монстра» каждый ход. Карта пересчитывается только при смене позиции игрока, и общая для всех зомбей.
                                +1
                                В случае одного монстра и одной цели — да, тот же A* был бы быстрее. Но на практике одно построение карты и два десятка обращений к ней получаются быстрее, чем гонять по полноценному A* для каждого противника.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое