Текст книги "Создание игр для мобильных телефонов"

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

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

► Блуждающий ИИ определяет, как объект перемещается по виртуальному игровому миру;

► Поведенческий ИИ определяет, насколько агрессивно объект ведет себя по отношению к другому объекту игры;

► Стратегический ИИ определяет лучший ход в стратегической игре с фиксированным набором хорошо определенных правил.

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

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

Реализовать блуждающий ИИ достаточно просто, обычно изменяется скорость или положение одного объекта (инопланетянина) относительно положения другого объекта (корабля игрока). Блуждание объекта можно задать случайным или определенным образом. Существует несколько типов блуждающего ИИ: преследующий, убегающий и шаблонный.

Преследующий ИИ

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

Ниже приведен пример простого преследующего алгоритма для кораблей пришельца и игрока:

if (xAlien > xShip)

xAlien–;

else if (xAlien < xShip)

xAlien++;

if (yAlien > yShip)

yAlien–;

else if (yAlien < yShip)

yAlien++;

Как вы видите, координаты пришельца (xAlien, yAlien) изменяются в зависимости от положения корабля игрока (xShip, yShip). Единственная потенциальная проблема с этим кодом – это то, что он может работать слишком хорошо. Пришелец настигнет игрока в любом случае, не давая шанса игроку ускользнуть. Вероятно, это именно то, что вам необходимо, но, скорее всего, вам потребуется, чтобы корабль пришельца полетал вокруг корабля игрока, прежде чем настигнет его. Возможно, вы захотите сделать преследование неидеальным, оставляя игроку шанс сбежать от преследователя.

Один из способов доработки алгоритма преследования – это добавить случайность:

if (Math.abs(rand.nextInt()) % 3) == 0) {

if (xAlien > xShip)

xAlien–;

else if (xAlien < xShip)

xAlien++;

}

if ((rand() % 3) == 0) {

if (yAlien > yShip)

yAlien–;

else if (yAlien < yShip)

yAlien++;

}

В приведенном коде пришелец может преследовать игрока в любом направлении с вероятностью 1/3. Даже несмотря на такую вероятность, пришелец все равно пытается настигнуть игрока, однако при этом оставляет шанс на спасение. Вы можете подумать, что один шанс из трех – не так уж и много, но помните, что пришелец изменяет направление движения в погоне за игроком. Умный игрок поймет это и будет часто изменять направление своего движения.

Если вам не очень понравился метод погони со случайным изменением направления, вы можете применить подход с заданной траекторией. Но прежде давайте рассмотрим на уклоняющийся ИИ.

Уклоняющийся ИИ

Уклонение – это противоположность преследованию, это другой тип блуждающего ИИ. В данном случае объект пытается уклониться от другого объекта или нескольких объектов. Уклонение осуществляется аналогично преследованию:

if (xAlien > xShip)

xAlien++;

else if (xAlien < xShip)

xAlien–;

if (yAlien > yShip)

yAlien++;

else if (yAlien < yShip)

yAlien–;

Этот код делает противоположное тому, что делал алгоритм преследования. Отличие состоит лишь в операциях (++ и —), используемых для изменения положения. Здесь объект убегает от преследователя. Аналогично преследованию, уклонение может быть «смягчено» случайностью или определенностью движения. Хороший пример уклонения – это привидения из известной игры Pac-Man, которые убегают от игрока, когда тот съедает энергетический шарик. Конечно, привидения преследуют игрока большую часть времени тогда, когда он не может их съесть.

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

Заданное перемещение

Заданное перемещение – это тип блуждающего ИИ, который использует предопределенный набор движений игрового объекта. Хороший пример заданного перемещения – это пришельцы в аркаде Galaga, которые выполняют акробатические движения к нижней части экрана. Для задания перемещений можно использовать окружности, восьмерки, зигзаги или более сложные фигуры. Более простой пример заданного перемещения – в игре Space Invaders, в которой пришельцы медленно и методично двигаются вверх и вниз по экрану.

В копилку Игрока

В действительности пришельцы в игре Galaga используют комбинацию алгоритмов случайного и предопределенного преследования. Несмотря на это, задачей пришельцев является преследование игрока. Кроме того, при переходе игрока на новый уровень блуждающий ИИ начинает больше работать по алгоритму преследования, нежели по алгоритму предопределенного преследования, усложняя игру. Это демонстрирует, как полезно комбинировать различные типы блуждающего ИИ. Речь об этом пойдет в следующей главе, когда вы будете знакомиться с поведенческим ИИ.

Движения обычно задаются массивами скоростей или смещений от положения (приращениями), которые при необходимости изменяют траекторию объекта, например:

int[][] zigzag = { {3, 2}, {-3, 2} };

xAlien += zigzag[patternStep][0];

yAlien += zigzag[patternStep][1];

Этот код показывает, как создать очень простое движение по вертикальному зигзагу. Массив целых чисел zigZag содержит пары приращений координат XY, используемых для задания движения. Переменная patternStep – это целочисленная величина, определяющая текущий этап в движении. Когда объект движется по зигзагу, за один игровой цикл он перемещается на 2 пикселя вверх, смещаясь при этом на 3 пикселя влево или вправо.

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

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

Для каждого типа поведения пришельца вы зададите определенный процент использования того или иного поведения, отделяя их таким образом друг от друга. Например, для агрессивного пришельца модель поведения можно задать так: преследование – 50 %, уклонение – 10 %, полет по траектории – 30 % и случайные перемещения – 10 %. С другой стороны, для более пассивного пришельца подошла бы такая модель: преследование – 10 %, уклонение – 50 %, полет по заданной траектории – 20 %, случайное перемещение – 20 %.

Такой подход хорошо работает и приводит к удивительным результатам, несмотря на простоту реализации. Обычно для реализации используется конструкция switch или вложенная конструкция if-else, например:

int behavior = Math.abs(rand.nextInt()) % 100;

if (behavior < 50)

// преследование

else if (behavior < 60)

// уклонение

else if (behavior < 90)

//полет по траектории

else

//случайное перемещение

Как вы видите, создание и применение определенного типа поведения – это область, в которой вы можете проявить свою фантазию. Один из лучших способов почерпнуть идеи поведения тех или иных игровых объектов – это найти аналогии в животном мире (и, к сожалению, в мире человека тоже!). Факт, что обычная система ИИ «летай или стреляй» может творить чудеса, если грамотно применить ее к различным типам игровых объектов. Фантазируйте, создавайте разнообразные модели поведения!

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

В копилку Игрока

Каждые несколько лет лучшие игроки в шахматы соревнуются с компьютерными шахматными программами, чтобы увидеть, насколько далеко продвинулись работы над созданием искусственного интеллекта. В 2003 году чемпион мира по шахматам Гарри Каспаров сразился в поединке «Человек против Шахматного компьютера» (Man vs. Machine Chess Championship), проходившем в Нью-Йорке, с компьютерным чемпионом мира Дип Джуниор (Deep Junior). Несмотря на то что в 1997 году Каспаров уступил шахматной программе Deep Blue, выпущенной компанией IBM, он вернул нас на прежний уровень, сыграв вничью с Deep Junior в 2003 году.

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

Тем не менее есть множество способов подсчета взвешенных баллов в стратегических играх. Используя метод прогнозирования и взвешивания, стратегический ИИ может проверять все возможные ходы каждого игрока, в том числе прогнозируя игру на несколько шагов вперед, после чего определяя, какой ход является наилучшим. Этот метод известен как «метод наименее худшего хода». Он называется именно так, а не «метод наилучшего хода», потому что при таком подходе выбирается ход, менее всего выгодный другому игроку. Несмотря на то что исход приблизительно одинаков, в этом случае интересно понаблюдать за развитием игры. Хотя метод прогнозирования при создании ИИ очень полезен, он может потребовать достаточно большого объема вычислительных мощностей, если необходимо выполнить достаточно «глубокий» прогноз (иначе говоря, если компьютер должен быть очень сообразительным).

Чтобы лучше понять стратегический ИИ, рассмотрим компьютерного игрока в нарды. Компьютер должен выбрать от двух до четырех движений из всех возможных вариантов, а также решить, сдваивать фигуры или нет. Реальная программа для игры в нарды может присвоить комбинациям положений различные веса.

Затем будет выполнен расчет веса каждого возможного хода, что обычно является очень трудной задачей даже в игре с простыми правилами, как нарды. Теперь давайте перенесем такой сценарий на военную игру с несколькими дюжинами боевых единиц, каждая из которых имеет свои уникальные характеристики, а также ландшафт и различные факторы, еще более усложняющие расчет. При таких условиях и при ограниченных вычислительных ресурсах нельзя составить оптимальный алгоритм стратегического ИИ.

Решение в данном случае – это метод «достаточно хороший ход», а не «лучший ход». Один из лучших способов поиска «достаточно хорошего хода» – это заставить компьютер играть за обе стороны, используя различные алгоритмы веса для каждой из сторон. Затем откиньтесь в кресле и понаблюдайте, кто одержит победу. Такой подход обычно требует большого числа экспериментов и изменений кода, однако в результате можно создать действительно сильного компьютерного противника, а понаблюдать за баталиями крайне интересно.

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

Если ваша главная цель – это разработка игры, которая развлекает и захватывает действием, выбирайте самый простой ИИ. Попробуйте сначала использовать самый простейший ИИ вне зависимости от ваших целей, вы в любой момент сможете усложнить его. Если вам кажется, что в вашей игре не подойдет ни один из описанных мною типов ИИ, вы можете поискать другие варианты, подобрать что-то более подходящее для решения задачи. Важно отметить, что на разработку ИИ должно быть отведено много времени, поскольку 90 % уйдет на то, чтобы заставить работать алгоритм так, как это требуется.

С чего начинать работу? Многие программисты любят писать код непосредственно при разработке алгоритма. Хотя такой подход может давать хорошие результаты в некоторых случаях, все же лучше предварительно провести разработку на листе бумаги. Кроме того, постарайтесь ограничить разработку областью игрового ИИ. Начните с небольшой карты или сетки с простыми правилами совершения ходов. Напишите код, проводящий одного оппонента из точки А в точку Б.

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

Хороший способ попрактиковаться с созданием ИИ – это написать алгоритм игры компьютерного противника в настольной игре, например, шашки. Для большинства популярных игр есть подробные описания ИИ, которые вы можете найти в сети. Другой хороший способ потренироваться – это модифицировать уже существующую игру, попробовать сделать управляемых компьютером персонажей немного умнее. Например, вы могли бы изменить игру Henway так, чтобы спрайты ускорялись или замедлялись, тем самым, усложняя задачу цыпленку. Или вы можете создать собственный спрайт, который знает, как преследовать другие спрайты на различных уровнях агрессии… экспериментируйте!

Ранее в этой главе речь шла о преследующем блуждающем искусственном интеллекте. Объект достаточно умен, чтобы преследовать другие объекты, обычно управляемые игроком. Теперь вы готовы создать и реализовать спрайт, который будет преследовать другие объекты. Вы сможете улучшить игру High Seas, разработанную в предыдущей главе, сделать ее интереснее.

Условия для разработки преследующего спрайта таковы: есть целевой спрайт, преследователь, преследователь постоянно движется в направлении цели. Представьте игру в салки, в которой вы – догоняющий, точно так же себя ведет и преследующий спрайт. Чтобы понять, как может работать такой спрайт, вы должны представить себе игру в салки в заторможенном состоянии. Например, предположим, что вы расположены в точке с координатами XY, например, недалеко от крыльца дома. Вы можете использовать любую единицу измерения, которую пожелаете, – метры, аршины, попугаи. все что угодно! Пусть тот, кого вы будете догонять, будет расположен в другой точке с координатами XY относительно крыльца дома.

Зная координаты преследователя и преследуемого, вы обладаете всем необходимым для планирования дальнейших действий. Чтобы определить в каком направлении следует двигаться относительно оси X, из координаты X преследуемого вычтите координату X вашего положения. Отрицательное значение говорит о том, что вы должны двигаться на запад, а положительное – на восток. Аналогичные вычисления следует сделать с координатами Y. Отрицательный результат говорит о том, что вы должны двигаться на север, а положительный – на восток.

На рис. 13.3 показано, как в рассмотренном примере принимается решение двигаться в определенном направлении.

Рис. 13.3. Направление, в котором должен двигаться преследователь, легко определить простым вычитанием координат XY преследователя и преследуемого

Рисунок 13.3 иллюстрирует, как, зная координаты преследующего и преследуемого, вы, используя простые вычисления, можете определить направление движения преследующего. Стоит отметить, что показанный на рисунке подход к преследованию имеет одну существенную проблему, с которой вы сталкиваетесь при попытке написания кода. Она заключается в том, что преследователь не идеален. Иначе говоря, преследующий постоянно подстраивает направление своего движения даже в том случае, если он бежит прямиком к цели. Это происходит потому, что преследователь старается предугадать поведение преследуемого. Решение этой проблемы заключается в том, чтобы задать область значений разницы координат, в которой преследователь не будет ничего предпринимать, чтобы догнать преследуемого. Чтобы понять, о чем я говорю, посмотрите на рис. 13.4.

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

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

Если эти рассуждения показались вам не более чем теорией, то, вероятно, реальный код поможет все расставить на свои места. Вы, несомненно, оцените пользу преследующего спрайта, когда чуть позже будете работать над совершенствованием игры High Seas 2.