Приветствую хаброчитателей, хочу вам рассказать об опыте написания AI к простенькой 2D игрушке в далеких уже 2003-2004 годах. Скажу сразу что написание сочинений в жизни мне никогда не удавалось, однако я буду стараться.
Скорее всего специалистам геймдева данный пост покажется нубским, но надеюсь что остальным будет интересно, итак, начнем с начала.
Игровой мир состоит из «квадратиков» одинакового размера, доступны телепорты, джамперы и другие элементы внезапно изменяющие местоположение игрока.
По карте разбросаны полезные элементы в виде оружия, патронов, аптечек, брони и т.д. Игроку доступны затяжные прыжки в пространстве позволяющие достаточно свободно перемещаться по игровому миру.
Задача будущего бота — свободно ориентироваться на абсолютно любой новой карте дабы элегантно поддаться игроку, ну и по возможности убить как можно больше соперников.
Суть AI бота построена на системе приоритетов. Каждая значимая точка на карте на которой можно стоять заносится в массив и для каждого элемента рассчитывается вес исходя из текущей ситуации.
К значимым точкам относятся позиции аптечек, брони, оружия и местоположение врагов, если они в данный момент находятся на земле. Вес позиции с аптечкой обратно пропорционален количеству уровня здоровья и времени необходимому для попадания в точку и прямо пропорционален некой величине условного веса подобранного для аптечек.
Если уровень здоровья полный, то совершенно понятно что вес данной точки обнуляется. Аналогично дело обстоит и с другими значимыми точками. Позиции врагов более приоритетны если у них низкий уровень здоровья или отсутствует оружие. Позиции оружия повышают вес при его отсутствии и равны нулю при его наличии. Пересмотр цели происходит раз в несколько секунд, либо по достижении позиции текущей цели.
Казалось бы все рассказал, но есть ещё один момент без которого описанный AI не мог бы работать — расчет времени достижения значимой точки.
Для того чтобы система AI не тормозила процесс игры при старте карты производится рассчет передвижений. При этом каждой точке на которой можно стоять присваивается порядковый номер, расстояние между точками равно одному шагу игрока. До начала игры производился полный расчет передвижений. Бот последовательно ставился в каждую из этих точек и совершал возможные для себя действия: шаг влево, шаг вправо, прыжок влево слабый, прыжок влево сильный и т.д.
После совершения действия игровой процесс продолжался до момента пока бот не приходил в состояние покоя после чего сохранялся результат в двухмерный массив вида "[точка старта][действие] = {точка приземления, время перемещения}". Данный механизм позволял боту использовать телепорты, джамперы и любые другие элементы игрового мира, т.к. бот просто знал что если находясь в точке X и шагнув влево — мы появляемся в точке Y через N секунд.
Имея данный массив для всего мира строился массив передвижений вида "[точка старта][точка финиша]={минимально время передвижения}". Для этого использовался достаточно распространенный волновой алгоритм:
только с бОльшим количеством действий:
в результате в любой момент времени бот может получить точное время достижения цели и список последовательных действий необходимых для этого.
Для подбора оптимальных весовых параметров (что важнее аптечка, оружие или убить слабого врага) был организован мини турнир. В каждом участвовало по 10 ботов у каждого из которых весовые параметры отличались на некоторую случайную величину. После 20 минут спаринга выделялся сильнейший и переходил на следующий уровень сражения, где умерщвлял уже более сильных соперников. В результате получился достаточно неплохой соперник живому игроку — его нельзя конечно назвать идеально умным, но вовремя отступить и сбегать за аптечкой или патронами он в состоянии.
Остальные моменты вроде прицеливания или выбора оптимального оружия достаточно скучны и не стоят Вашего внимания.
Надеюсь что Вы дочитали до конца. Ну и наконец небольшое видео сего действа:
Скорее всего специалистам геймдева данный пост покажется нубским, но надеюсь что остальным будет интересно, итак, начнем с начала.
Игровой мир
Игровой мир состоит из «квадратиков» одинакового размера, доступны телепорты, джамперы и другие элементы внезапно изменяющие местоположение игрока.
По карте разбросаны полезные элементы в виде оружия, патронов, аптечек, брони и т.д. Игроку доступны затяжные прыжки в пространстве позволяющие достаточно свободно перемещаться по игровому миру.
Задача будущего бота — свободно ориентироваться на абсолютно любой новой карте дабы элегантно поддаться игроку, ну и по возможности убить как можно больше соперников.
Система приоритетов
Суть AI бота построена на системе приоритетов. Каждая значимая точка на карте на которой можно стоять заносится в массив и для каждого элемента рассчитывается вес исходя из текущей ситуации.
К значимым точкам относятся позиции аптечек, брони, оружия и местоположение врагов, если они в данный момент находятся на земле. Вес позиции с аптечкой обратно пропорционален количеству уровня здоровья и времени необходимому для попадания в точку и прямо пропорционален некой величине условного веса подобранного для аптечек.
Если уровень здоровья полный, то совершенно понятно что вес данной точки обнуляется. Аналогично дело обстоит и с другими значимыми точками. Позиции врагов более приоритетны если у них низкий уровень здоровья или отсутствует оружие. Позиции оружия повышают вес при его отсутствии и равны нулю при его наличии. Пересмотр цели происходит раз в несколько секунд, либо по достижении позиции текущей цели.
Казалось бы все рассказал, но есть ещё один момент без которого описанный AI не мог бы работать — расчет времени достижения значимой точки.
Кратчайший путь
Для того чтобы система AI не тормозила процесс игры при старте карты производится рассчет передвижений. При этом каждой точке на которой можно стоять присваивается порядковый номер, расстояние между точками равно одному шагу игрока. До начала игры производился полный расчет передвижений. Бот последовательно ставился в каждую из этих точек и совершал возможные для себя действия: шаг влево, шаг вправо, прыжок влево слабый, прыжок влево сильный и т.д.
После совершения действия игровой процесс продолжался до момента пока бот не приходил в состояние покоя после чего сохранялся результат в двухмерный массив вида "[точка старта][действие] = {точка приземления, время перемещения}". Данный механизм позволял боту использовать телепорты, джамперы и любые другие элементы игрового мира, т.к. бот просто знал что если находясь в точке X и шагнув влево — мы появляемся в точке Y через N секунд.
Имея данный массив для всего мира строился массив передвижений вида "[точка старта][точка финиша]={минимально время передвижения}". Для этого использовался достаточно распространенный волновой алгоритм:
только с бОльшим количеством действий:
в результате в любой момент времени бот может получить точное время достижения цели и список последовательных действий необходимых для этого.
Самообучение
Для подбора оптимальных весовых параметров (что важнее аптечка, оружие или убить слабого врага) был организован мини турнир. В каждом участвовало по 10 ботов у каждого из которых весовые параметры отличались на некоторую случайную величину. После 20 минут спаринга выделялся сильнейший и переходил на следующий уровень сражения, где умерщвлял уже более сильных соперников. В результате получился достаточно неплохой соперник живому игроку — его нельзя конечно назвать идеально умным, но вовремя отступить и сбегать за аптечкой или патронами он в состоянии.
Остальные моменты вроде прицеливания или выбора оптимального оружия достаточно скучны и не стоят Вашего внимания.
Надеюсь что Вы дочитали до конца. Ну и наконец небольшое видео сего действа:
