Об опыте написания AI к простенькому 2D шутеру

Приветствую хаброчитателей, хочу вам рассказать об опыте написания AI к простенькой 2D игрушке в далеких уже 2003-2004 годах. Скажу сразу что написание сочинений в жизни мне никогда не удавалось, однако я буду стараться.
Скорее всего специалистам геймдева данный пост покажется нубским, но надеюсь что остальным будет интересно, итак, начнем с начала.

Игровой мир

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

игровой мир

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

Система приоритетов

Суть AI бота построена на системе приоритетов. Каждая значимая точка на карте на которой можно стоять заносится в массив и для каждого элемента рассчитывается вес исходя из текущей ситуации.
К значимым точкам относятся позиции аптечек, брони, оружия и местоположение врагов, если они в данный момент находятся на земле. Вес позиции с аптечкой обратно пропорционален количеству уровня здоровья и времени необходимому для попадания в точку и прямо пропорционален некой величине условного веса подобранного для аптечек.
Если уровень здоровья полный, то совершенно понятно что вес данной точки обнуляется. Аналогично дело обстоит и с другими значимыми точками. Позиции врагов более приоритетны если у них низкий уровень здоровья или отсутствует оружие. Позиции оружия повышают вес при его отсутствии и равны нулю при его наличии. Пересмотр цели происходит раз в несколько секунд, либо по достижении позиции текущей цели.
Казалось бы все рассказал, но есть ещё один момент без которого описанный AI не мог бы работать — расчет времени достижения значимой точки.

Кратчайший путь

Для того чтобы система AI не тормозила процесс игры при старте карты производится рассчет передвижений. При этом каждой точке на которой можно стоять присваивается порядковый номер, расстояние между точками равно одному шагу игрока. До начала игры производился полный расчет передвижений. Бот последовательно ставился в каждую из этих точек и совершал возможные для себя действия: шаг влево, шаг вправо, прыжок влево слабый, прыжок влево сильный и т.д.
После совершения действия игровой процесс продолжался до момента пока бот не приходил в состояние покоя после чего сохранялся результат в двухмерный массив вида "[точка старта][действие] = {точка приземления, время перемещения}". Данный механизм позволял боту использовать телепорты, джамперы и любые другие элементы игрового мира, т.к. бот просто знал что если находясь в точке X и шагнув влево — мы появляемся в точке Y через N секунд.
Имея данный массив для всего мира строился массив передвижений вида "[точка старта][точка финиша]={минимально время передвижения}". Для этого использовался достаточно распространенный волновой алгоритм:
волновой алгоритм

только с бОльшим количеством действий:
волновой алгоритм

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

Самообучение

Для подбора оптимальных весовых параметров (что важнее аптечка, оружие или убить слабого врага) был организован мини турнир. В каждом участвовало по 10 ботов у каждого из которых весовые параметры отличались на некоторую случайную величину. После 20 минут спаринга выделялся сильнейший и переходил на следующий уровень сражения, где умерщвлял уже более сильных соперников. В результате получился достаточно неплохой соперник живому игроку — его нельзя конечно назвать идеально умным, но вовремя отступить и сбегать за аптечкой или патронами он в состоянии.
Остальные моменты вроде прицеливания или выбора оптимального оружия достаточно скучны и не стоят Вашего внимания.
Надеюсь что Вы дочитали до конца. Ну и наконец небольшое видео сего действа:
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 22
  • +2
    Суда по тексту, похожий подход описан в книге «Programming Game AI by Example» от Matt Buckland, там для топ-даун шутера использовалась нечеткая логика в принятии решений для выбора следующей цели, и интересный паттерн организации целей. Советую посмотреть, если занимаетесь этим и еще не смотрели.
    • +6
      Вижу у вас в игре есть реплей функция. Скажите пожалуйста как вы организовали запись всего что происходит в игре на экране чтобы потом показать реплей?
      • +1
        насколько я помню просто тупо сохранялись состояние всего игрового мира с позициями игроков, их состоянием и т.д.
        К сожалению давно это было :)
        • 0
          Это итак понятно, а каким образом вы сохраняли состояние мира каждую секунду? Неужели у каждого объекта для каждой долисекунды хранились где-то его координаты?
          • 0
            Так во многих играх и реализована запись демо. Например Call of Duty 4: MW — там в демо записывается весь «интернет-трафик» (около четырех килобайт в секунду) игры, а потом воспроизводится (эмулируется).
            • 0
              именно ) объём инфы на самом деле относительно небольшой
        • +2
          Оу, ёжики в quake! Помнится занимался написанием аналогичных ботов для другой похожей игры — Need For Kill (и далее для своей TFK). Искали путь по адаптированному для side-шутера A*, имели приоритеты по поиску предметов (отжирались), стреляли ракетницей «наперёд» и уворачивались от вражеских ракет. Весёлое было время )
          • +2
            Да было время… студенчество — куча времени, оптимизма и возможность заниматься теми проектами, которыми хочется…

            NFK помню, она появилась как раз таки благодаря ёжикам ([3d]Power не даст соврать), TFK уже к сожалению не видел :(
            поделитесь линкой?
        • 0
          Спасибо за информацию.

          У Антона Карлова в последнем постмортеме Зомботрона описан интересный опыт работы с AI.
          • +3
            Побольше бы интересных статей о геймдеве на хабре
            • +1
              Хотел опубликовать перевод о создании мач-3 на флэш, но кармы маловато для профильного топика.
              А вообще, с удовольствием читаю все статьи о геймдеве. Их всегда не хватает.
              • 0
                Спасибо плюсующим, вашими силами будет больше статей.

                Вопрос к автору топика, чем занимается на данный момент? Есть ли еще какие интересные проекты?
              • +1
                Пользуясь случаем — уже готов отчет/постмортем по моей игре, обсуждение которой случайно нашел на хабре в теме о Playbook, но не могу опубликовать ее вообще нигде.
                Также была в планах статья о Sweep And Prune и Separating Axis Theorem для обнаружения столкновений в игре (широкая/узкая фаза), но из-за облома с первой статьей пока писать не стал.
              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  Поиграйте быстрый бой в StarCraftII против AI на Hard. Если переживете раш, то потом есть шанс увидеть какие чудеса он порою творит =)
                  • НЛО прилетело и опубликовало эту надпись здесь
                • +2
                  Слушайте, возможно задам глупый вопрос (не самый я продвинутый человек в этой теме), но прям «чешется спросить»… А зачем при каждом старте карты просчитывать время достижения точек? Ведь по-сути оно не меняется раз от раза. Соответственно можно было бы либо при создании карты это делать (всяко же поди себе редактор какой наваяли), либо при самом первом запуске (а потом хранить каким-нибудь ресурсом). Нет?!
                  • 0
                    Да ) хорошая идея кстати, как то не пришла в голову
                    Правда на самом деле время было совсем не критично и на небольших картах было даже незаметным
                    • +1
                      Ну во первых чтоб не хранить. Для хранения и записи в файл, его считывание и проверка — дополнительный код на которы надо тратитть время. Во вторых если можно что то вычислить и это не будет очень долго — лучше вычислить. Если например проапдейтить игру и изменить немного параметры скорости при наличии подобных ресурсов где уже все посчитанное хранится придется проверять к какой версии игры они относятся и все вытекающие из этого проблемы.
                      • +1
                        + если ботов будет несколько моделей с разными ТТХ и если будет возможность кастомизации модели…
                        Такой подход универсальнее.

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