Из газеты Don News #21, Ростов-на-Дону, 28.04.2005
 
 

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

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

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