DonNews #21 27 марта 2005

Программирование

ТЕОРИЯ AI - Рассуждения о построении искусственого интеллекта в играх.

__________________________________________

Теория AI                 





(c)SpoozE/oHg/XXL
 
 Здрасте всем! 
 Сразу о главном. В этой статье я расскажу
Вам о реализации искуственного  интеллекта 
(далее - AI), в масштабах  нашего  с  вами 
SPECCY. Для начала в общих чертах, что  же 
такое AI и к чему надо  стремиться при его 
написании.
  К  разработке  AI надо подходить  весьма
внимательно, так как каждая задача требует 
узко специализированного  и "подогнанного" 
алгоритма  ее  решения.  В связи с этим, я 
буду поэтапно  описывать создание  AI  для 
широко известной игры "BATTLE CITY". Итак,  
самым первым нашим шагом будет оценка тре-
буемых действий от  AI-объектов ( далее  -
боты). В нашем случае требуется, чтобы та-
нки: ездили просто так,охраняли базу,напа-
дали  на  базу  противника, ошибались. Хм,  
возможно некоторых смутил последний пункт, 
но ошибки в  действиях ботов  очень важны, 
мы ведь хотим создать реалистичную  модель  
поведения.  Если  в  игровой ситуации  все 
танки устремятся к вражеской базе,  то это 
будет  выглядеть  мягко  говоря  не  очень 
реалистично, да и геймплей от  этого изме-
нится далеко не  в лучшую сторону, так что 
пока оставим полный поиск пути и поговорим 
о хаотическом  движении. 
 Самое простое - конечно же просто случай-
ным  образом  выбирать  направление  через 
какие-то промежутки времени, но  смотрется 
это будет  не  совсем  так, как нам нужно. 
Мне на момент разработки показалось  целе-
сообразным  ввести для каждого танка счет- 
чик  смены направления  и  типа  движения.
 Про смену типа движения расскажу  немного 
позже, а сейчас про смену направления. Как 
это  работает?  В счетчик ложим  случайное 
число - количество ходов до смены  направ-
ления (диапозон  зависит от масштабов кар-
ты, но можно ввести зависимость от  модели 
поведения ). Затем  каждый  тик  (интервал 
времени, за который обрабатывается игровая 
ситуация),мы уменьшаем счетчик на единицу, 
и если он равен нулю, то  опять  обновляем 
направление и счетчик. Также счетчик  сле-
дует   обнулять   при   неудачной  попытке 
сделать ход  (например танк  столкнулся  с 
другим танком или со стеной).Таким образом 
мы достигли достаточно реалистичного  дви-
жения "наугад". Но, увы,  в  данном случае 
вероятность достижения танком определенных 
позиций зависит от пространственной конфи-
гурации блоков  и  может быть очень  мала. 
Как видно на рисунке










-вероятность того, что танк пройдет в дыру 
в стене близка к нулю. В таких случаях для 
экономии аппаратных  ресурсов, вместо тру-
доемких  рассчетов  выгоднее  использовать 
так   называемые   чекпойнты  (  от  англ. 
Checkpoint - точка проверки). В моей  реа-
лизации чекпойнты  представляют собой мас-
сив таких же блоков, как и уровень, только 
блоки имеют значения смены  направления  и 
еще несколько свойств. Таким  образом каж-
дый тик идет проверка танков,на чекпойнты, 
если танк находится на позиции с  чекпойн-
том, то идет несколько дополнительных про-
верок  ( чекпойнты  могут  быть   например 
только  для  красных  танков ), и в случае 
успеха танк принимает направление, которое 
соответствует  чекпойнту. Немного  забегая 
вперед, хочу отметить  тот факт, что в со-
ответствии  с  поставленной  целью  у  нас 
должно  быть  несколько  моделей поведения 
танков. Я обозначил две - атакующие и обо-
роняющиеся.  Атакующие  стремятся  к  базе 
противника,  используя  волновой  алгоритм 
поиска  пути (о котором ниже), а обороняю-
щиеся просто разъезжают по карте. В  связи 
с  этим  чекпойнты  различаются  по модели 
поведения  танков, которые  будут по  этим 
чекпойнтам ездить. Например чекпойнт может 
быть только для команды красных  и  только 
для атакующих танков (можно придумать свои 
критерии   дифференцирования ).  Итак  нам 
нужно  реализовать  полный алгоритм поиска 
пути.  Самый  простой  способ  -  волновой 
алгоритм.  Реализуется он  элементарно, по 
следующему алгоритму:
  1. Начальная  точка  -  пункт назначения 
бота, в нашем случае - база противника.
  2. Разбиваем поле на условные  квадраты, 
целесообразно будет разбить на те же  раз-
меры, что и  блоки и  чекпойнты.
  3. Забиваем клетки с  "непроезжими" бло-
ками  например  #FF
  4. Присваиваем  клетке  с   координатами 
цели  значение  ноль.
  5. Всем   пустым  и  "проезжим"  клеткам 
вокруг нее присваиваем значение на единицу 
больше.
  6. Обрабатываем   каждую  из  помеченных 
клеток аналогично.
 В  случае  с  танками мы сформировали два 
поля  AI - для  красной  и для синей базы. 
Теперь  чтоб пройти  по кратчайшему пути к 
объекту, надо  всего лишь  двигаться  в ту 
клетку, где  значение  меньше.






















  Легче всего идентифицировать движение по 
этому  алгоритму, как пятое направление  и 
выбирать  его  так  же как и  вверх, вниз, 
влево и вправо,  но только для  нападающих 
танков. То  есть при  нулевом счетчике,  у 
нападающего танка  есть возможность выбора 
движения  по кратчайшему пути к  вражеской 
базе.  Но  как только  счетчик  становится 
равен нулю,танк может поехать и по обычно-
му направлению,что ведет к реалистичности. 
Также стоит учесть, что движение по волно-
вому алгоритму приоритетней, чем  движение 
по  чекпойнту  и   при  "наступлении"   на 
чекпойнт проверять, не движется ли танк по 
пятому направлению. 
Фух.  На сегодня  я, пожалуй,  закончу, но 
даже и не надейтесь отвязаться ;)                  
  
                              2 b cont...