Heresy #01 16 мая 1999

Игры

WarGames - как сделать War Game.

      ▀██▀ ▀██▀   ▐▌   ▀██▀█▄  ▄█▀▄▄   ▐▌   ▀█▄ ▄█▀ ███▀▀█
       ▐▓   ▓▌    ██    ▓█  █ ▐▓   ▀   ██    ▓█▓█▓  ▐▓▌
        ▒   ▒    ░▌▐░   ▒█  ▓ ▒░ ▄▄▄  ░▌▐░   ▒▐▒▌▒  ▐▒▀▀
        ░ ░ ░    ▒▓█▒   ░█▄█▀ █    █  ▒▓█▒   ░ ░ ░   ░
        ▒ ▒ ▒   ▐▓▌▐▓▌  ▒█ █▌ ▒░  ██ ▐▓▌▐▓▌  ▒   ▒  ▐▒  a$h
       ▐▓▐▓▌▓▌  ▐█  █▌  ▓█ ▐█ ▓▒░▒▓█ ▐█  █▌ ▐▓▌ ▐▓▌ ▐▓▌
      ▄███▀███▄ ██▌▐██ ▄██ ▐█ ▐▓▒▓▀█ ██▌▐██ ███ ███ ███▄▄█▄
        ▀   ▀    ▀  ▀   ▀   ▓  ▀▀▀ █  ▀  ▀   ▀   ▀   ▀

 (С) Сергей Бобровский

                    ВОЕННЫЕ ИГРЫ - WARGAMES

     Сегодня  мы  рассмотрим  методы программирования достаточно
популярного  во  всем мире жанра военных игр. Конечно, многие из
них  имеют  весьма  существенные  алгоритмические  различия,  но
большинство весьма схожи. Вспомним легендарных Повелителей Войны
(~WarLords~),   или   недавно   вышедший  аркадно-стратегический
вариант     ~Wing     Commander    -~    ~Armada~,    насыщенную
технико-тактическими  характеристиками  боевых звездолетов ~When
Two  Worlds War~ или космическую версию "Цивилизации" ~Master of
Orion~, чем-то похожую на ~SimCity~ и ~Warlords~ программу ~UFO~
и  многопользовательскую ~VGA Planets~ - всех их объединяет одна
игровая  идеология.  Да  это  и  немудрено, ведь wargames своими
родителями имеют всем нам известные с детства настольные игры. И
сегодня  бизнес  настольных  игр  во  всем  мире является весьма
доходным,   только   теперь   новые  хиты  в  случае  их  успеха
реализуются и на компьютерах. Так, многие известные компьютерные
программы  являются версиями настольных игр. Это ~Harpoon~ Ларри
Бонда  и  Тома  Клэнси,  ~Second  Front~  Гарри Григсби и многие
другие.

     К  сожалению,  военные компьютерные игры не занимают первые
(и  даже  вторые)  строчки  среди  компьютерных  игр, приносящих
максимальную  прибыль.  Да,  здесь,  как  и в puzzle-жанре или в
традиционных   играх,   надо   много   думать,  что  существенно
сказывается  на  спросе.  Недаром,  "как  сказал  один из героев
В.Суворова,  любые  военные  действия  намного сложнее по своему
стратегическому  замыслу любой придуманной человечеством игры, в
том  числе  и  шахмат"  (журнал  "CD-ROM  игры"). Поэтому фирмам
приходится идти на различные ухищрения типа трехмерного дизайна,
оригинального  сценария и усложнения сюжета аркадными вставками,
но  иногда  чистая  классическая  линия  настольных  игр выводит
компьютерную   программу   в   относительные  лидеры,как  было с
~WarLords II~.

     Итак,  сначала сформулируем основные составляющие алгоритма
военных   игр,   предварительно  договорившись  о  терминологии.
Назовем   Боевой   Единицей   (БЕ)  одиночную  фигуру,  будь  то
пехотинец,  дракон, звездолет или ракетный крейсер. Каждая из БЕ
имеет ряд технико- тактических характеристик, таких как скорость
передвижения  по  различным видам грунтов, вероятность поражения
различных  типов  БЕ  противника  и т.п. Группы БЕ могут (или не
могут)  объединяться  в  Боевой  Отряд  (БО),  характеризующийся
максимально   допустимым   количеством   БЕ.  Сами  БО  способны
объединяться  друг  с  другом с учетом ограничений на количество
БЕ.  БО  может  содержать  и всего одну БЕ, таким образом в игре
будут существовать не БЕ, а только БО.

     Карта  игры - прямоугольник размером M x N условных единиц.
В  каждой  из  клеток  может находиться не более одного БО любой
стороны.  Значение  каждой  из  клеток  описывает грунт в данной
точке игрового пространства. Например, 0 - нормальный грунт, 1 -
проселочная  дорога,  2  - шоссе, 3 - горы, 4 - песок и т.п. Как
уже   упоминалось,  карта  совсем  не  обязательно  должна  быть
прямоугольной, клетки ее могут быть и шестиугольными, и сама она
может  быть  построена в форме графа, как в ~Armada~ или ~Master
of Orion~. Мы же для наглядности выберем версию ~WarLords~.

     Примем Количество Сторон (игроков) большим или равным 2.

     Первоначально  на  карте  расположено  некоторое количество
ГОРОДОВ  (разумеется, в реальной игре это могут быть планеты или
морские  базы),  большинство  из  которых нейтральны, то есть не
принадлежат  ни  одной  из  сторон.  Каждый  из городов обладает
такими  характеристиками,  как  Доход  за  один  игровой  цикл и
Текущее производство, описывающее производимую в данный момент в
Городе БЕ и Время, оставшееся до ее "выхода в свет".

     Допустим  также  возможность  участия  в  игре Транспортных
Средств,  способных  перемещать  БО  по  некоторым видам грунтов
(допустим, по воде). Транспортные Средства характеризуются своей
Грузоподъемностью и Скоростью передвижения.

     И,  конечно,  каждая  из играющих сторон обладает некоторым
запасом   Кредитов   -   денежных   средств,   необходимых   для
производства БЕ.

     Теперь   опишем   основные   элементы  игрового  алгоритма.
Первоначально    создается    игровая    Карта.    Для   большей
реалистичности  желательно создавать ее не случайно, а "ручками"
для  большего  соответствия  достоверности. На ней расставляются
Города,    первоначально   нейтральные,   и   в   соответствии с
количеством  играющих  по  одному  городу, по-видимому, в разных
концах   карты,   объявляются   принадлежащими   соответствующей
стороне.  Первоначально  количество  Кредитов у каждой из сторон
принимается  равным  нулю.  Затем  начинается  собственно  игра.
Сторона,  чья  очередь  хода,  отдает  приказ  каждому  (или  не
каждому) своему БО либо на перемещение, либо на атаку вражеского
БО,  либо  на  атаку Города. Некоторым из Городов, принадлежащих
данной   стороне,   может  быть  отдан  приказ  на  производство
определенной  БЕ,  разумеется, при наличии Кредитов. Вычисляются
уничтоженные отряды, произведенные новые БЕ и игра продолжается,
как  правило,  до  полного  уничтожения всех сторон, кроме одной
(как в "Горце" - из бессмертных останется только один).

     Под  эту  схему  подходит  большинство военных игр. Уберите
города  - и Вы получите модель локальной схватки, как в схватках
отряда XCom с инопланетянами в "UFO"; замените города на планеты
-   получите   "Master  of  Orion"  или  "Armada".  Для  большей
динамичности  некоторые  игры  вносят в сюжет имитацию развития,
когда  новые, более мощные типы вооружения становятся доступными
не   сразу,   а   по   мере  "взросления"  стороны  играющего. В
приведенном  выше общем описании это легко достигается контролем
за   уровнем   Кредитов,   который  очень  сильно  коррелирует с
размерами  построенной  империи.  Новые  виды  вооружений  могут
стоить  очень  дорого,  и  как  только игрок накопит достаточное
количество  Кредитов,  что  невозможно  без активной экспансии и
захвата новых городов, приносящих прибыль, то выдается сообщение
о  достижении игроком нового технологического уровня, и в список
доступных  для  производства  типов  вооружений включается новый
вид.  Легко  включаются  в эту схему и дипломатические контакты,
когда  некоторые  из  сторон  договариваются не нападать друг на
друга.

     Определенную     проблему     представляет     компьютерное
моделирование  поведения сторон, за которые играет не человек, а
программа.  Пока, несмотря на громогласные заявления многих фирм
об  "уникальных алгоритмах искусственного интеллекта", серьезные
научные   разработки   здесь   практически   не  используются, и
поведение  моделируемых  БО при внимательном рассмотрении весьма
туповато.  Они  действуют весьма похоже на Терминатора, который,
несмотря   на   внешне  идентичный  человеку  вид  и  поведение,
руководствовался примитивной программой поиска нужного объекта с
помощью  небольшого  списка  стандартных  возможностей.  Так и в
играх внешне сложное поведение внутри оказывается простой смесью
разновероятных   примитивных   альтернатив,   это   своего  рода
высказывание    академика   Колмогорова   "сложное   похоже   на
случайное"  наоборот.  В  основном  все военные игры строятся на
наборах  достаточно  простых  правил,  аналогичных тем, которыми
пользуется  игрок среднего класса. Проблема в том, что обычно не
удается   точно  сформулировать  эти  правила  и  возникает  ряд
оговорок,  оговорок  к  оговоркам  и  т.д. Сложность же игры, ее
более  высокие  уровни  зависят  не от каких-то новых алгоритмов
имитации  поведения,  а  от  более-менее  явного  гандикапа  для
компьютерных армий, такого как высокий начальный запас Кредитов,
более  выгодное  расположение городов, более высокие вероятности
выигрыша   в   схватках   и   т.п.  Вообще  тема  искусственного
интеллекта  и  его  использования  в  компьютерных  играх  очень
интересна, и мы обязательно коснемся ее в ближайших выпусках.

     Теперь  перейдем  к  детальному  описанию алгоритма военных
компьютерных игр. Начнем со структур данных.

     Карта  -  массив  размера  N  x  M  клеток. На экране может
отображаться  как целиком, так и отдельной частью. Каждая клетка
имеет фиксированное значение, соответствующее типу грунта.

     Тип Боевая-Единица - структура с следующими полями:

      - тип вооружения от 1 до МАКС_ЧИСЛО_ВООР;
      - текущие координаты X и Y.

     В  массиве ТТХ (технико-тактические характеристики) от 1 до
МАКС_ЧИСЛО_ВООР  хранятся ТТХ для каждого из типов вооружений. В
них входят:

     -  скорость  передвижения  по  каждому  из  видов грунтов в
условных   единицах   (дальность  перемещения  в  квадратах,  по
горизонтали  и  вертикали  и, может быть, диагонали) или 0, если
грунт непроходим;

     -  вероятность  поражения  каждого  из  видов  вооружений в
схватке   в   процентах   в   виде   таблицы   МАКС_ЧИСЛО_ВООР х
МАКС_ЧИСЛО_ВООР,  где (i,j)- й элемент соответствует вероятности
поражения j-го типа БЕ i-ой;

     - стоимость производства.

     Кроме  того,  имеется  таблица  размером (МАКС_ЧИСЛО_ВООР х
МАКС_УРОВ_ЗАЩИТЫ),  содержащая  вероятности  захвата  i-м  типом
вооружения город с j-й степенью защиты.

     Тип Боевой-Отряд - массив структур (максимальное количество
-  МАКС_КОЛВО_ОТРЯДОВ  >=  1)  из  БЕ.  Если  МАКС_КОЛВО_ОТРЯДОВ
принимает   значение  1,  то  это  означает,  что  БЕ  не  могут
объединяться   в  отряды.  Тип  Боевой-Отряд  имеет  также  поле
"текущее  количество  БЕ"  >=  1  и координаты конечной точки на
карте,  к которой необходимо переместиться, или подвижную цель -
например, номер преследуемого вражеского БО из массива АРМИИ. БЕ
внутри  БО должны быть упорядочены по принципу "от слабейшей - к
сильнейшей", чтобы в схватку первыми вступали слабейшие БЕ.

     Города - массив из 'Количество_Городов' структур, каждая из
которых содержит следующие поля:

     - координаты на карте X и Y, - принадлежность стороне i >=1
или  0  в  случае нейтральности города, - уровень защиты от 1 до
МАКС_УРОВ_ЗАЩИТЫ,  -  тип производимого вооружения Т >= 1 или 0,
если  ничего  не  производится,  -  количество  игровых  циклов,
которые   остались   до   построения   Т-го  типа  производимого
вооружения, - размер дохода за один цикл.

     Динамический    массив    АРМИИ   из   (Количество_Отрядов,
переменная   величина)   структур  типа  БО  описывает  все  БО,
существующие   на   данный  момент  в  игре.  Он  необходим  для
корректной   отрисовки   экрана   и   для  некоторых  внутренних
вычислений.

       1.  Инициализация.  Загрузить  Карту, проинициализировать
  список  Городов,  отметить нейтральные и принадлежащие той или
  иной  стороне,  в  АРМИИ занести начальные БО каждой из сторон
  (как правило, по одной на каждого игрока).

       2. Выбрать очередную сторону, чья очередь хода. Для нее:

       -  увеличить Кредиты в зависимости от количества городов,
  принадлежащих данному игроку и дохода каждого из этих городов;

       -  проверить  список  Городов, если в каком-нибудь из них
  построена БЕ, то выпустить ее в свет в Городе или около оного,
  по  возможности  присоединить  к  уже  имеющимся рядом БО, при
  необходимости добавить новый БО к списку АРМИИ;

       -  начать  по  желанию  и  средствам  строительство  БЕ в
  различных Городах игрока, вычесть стоимость БЕ из Кредитов;

       -  отдать  приказы  каждому (или не каждому) БО игрока на
  передвижение,  и  совершить  это передвижение. Если в конечной
  точке стоит свой БО, то произвести их объединение;

       -  отдать  приказы  определенным  БО  атаковать некоторые
  Города. При этом атака Города происходит так:

       -  если  в  городе расположены БО, то сначала сразиться с
  каждым  из  БО города (этот процесс описан ниже). Когда все БО
  противника уничтожены, перейти к следующему пункту, иначе (наш
  БО уничтожен) вычеркнуть БО из списка АРМИИ;

         -  в  цикле для каждой БЕ атакующего БО (с минимального
    типа):

         -  взять  из  таблицы  вероятность  захвата БЕ города с
    текущим  уровнем  защиты,  с помощью датчика случайных чисел
    определить результат;

         -  либо город захватывается, и цикл заканчивается, либо
    БЕ гибнет, БО сжимается, и цикл продолжается. Если все БЕ из
    БО уничтожены, то город остался неприступен, а БО погиб. При
    этом его необходимо вычеркнуть из массива АРМИИ;

         -  если  город  захвачен,  то сделать его принадлежащим
    текущей стороне;

       -  отдать  приказы  некоторым БО атаковать БО противника.
  При этом атака вражеского БО происходит так:

       - в цикле для каждой БЕ атакующего БО: в цикле для каждой
  БЕ  атакуемого  БО:  взять  из таблицы вероятность уничтожения
  атакующей  БЕ  атакуемую  БЕ  в  соответствии  с  их типами, с
  помощью  датчика случайных чисел определить результат - гибнет
  либо   наша   БЕ,   либо  БЕ  противника,  соответствующее  БО
  сжимается,  и  цикл  продолжается.  Если  все  БЕ из нашего БО
  уничтожены,  то БО противника остался цел, а наш БО погиб. При
  этом    его    необходимо   вычеркнуть   из   массива   АРМИИ.
  Соответственно,  если  первыми уничтожены все БЕ из вражеского
  БО, то в схватке победили мы, и вычеркивается из массива АРМИИ
  БЕ противника.

     3.  Проверка  на  конец  игры.  Если  все  Города некоторой
стороны уничтожены (это достигается сканированием списка Городов
в  поисках хотя бы одного Города, принадлежащего рассматриваемой
стороне),  и  у  него  нет  больше отрядов (аналогичная проверка
списка  АРМИИ),  то  сторона  считается проигранной. Если в игре
остался  только один игрок, то он объявляется победителем. Иначе
происходит возврат к п.2.

                    *        *        *

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

     1.  "Бей  все,  что  движется".  Определяется  ближайший БО
противника, выбирается в качестве цели и преследуется, пока либо
он, либо сам БО-преследователь из-за атак других БО не погибнут.
Сама  по себе эта тактика не способна принести реальной победы в
игре, но может доставить другим сторонам массу проблем. Не имеет
смысла  использовать  только ее для одной из сторон, так как без
захвата городов невозможно будет строить новые БЕ.

     2.  "Захватывай  города противника". Определяется ближайший
город,    принадлежащий   какой-нибудь   стороне   противника, и
выбирается  для цели атаки. Этот метод предназначен для борьбы с
врагами где-то в разгаре игры.

     3.  "Захватывай  свободные  города". Определяется ближайший
город,  не  принадлежащий  ни  одной из сторон, и выбирается для
цели  атаки.  Этот  метод желательно применять в начале игры для
скорейшего  захвата как можно большего числа городов и получения
максимальной  прибыли  для  строительства  мощных  БЕ, которые и
решают, в принципе, исход военных игр.

     4. "Атакуй прохожих". Во время передвижения к цели БО может
встречать на своем пути БО противника. Они обычно проходят мимо,
но  иногда  можно  нападать  на  них, особенно если они заведомо
слабее.  В  зависимости  от  характера стороны вероятность атаки
случайно  проходящих  мимо  БО  врага  может  колебаться в самых
широких пределах - от "не тратить силы зря, не нападая никогда",
что  полезно  в  дебюте  игры  при  захвате новых городов до "не
давать  прохода  никому"  в  миттельшпиле,  когда главный акцент
обычно делается на уничтожение вражеских сил.

     Примечание:  в  понятие  "ближайший  объект (Отряд, Город)"
корректнее  всего  включить не просто "ближайший ", а "ближайший
из не выбранных другими БО своей стороны".

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

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

     1.  Увеличивать защиту Города. Это имеет смысл для ключевых
Городов,   расположенных   в   центре   карты,   что   позволяет
производимым  в  нем БЕ быстро добираться в любую точку игрового
поля.

     2.  Копить  деньги  для  постройки мощных типов вооружений.
Подходит  для середины игры, когда сферы влияния уже определены,
и  необходимы  более  крутые  силы  для  преодоления  вражеского
сопротивления.

     3.  Сразу  строить  доступные  по  средствам БЕ минимальных
уровней  и  быстро  отправлять  их  на захват ничейных или чужих
неохраняемых  городов со слабой защитой. Полезный метод в начале
игры.

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

     Оценка  сложности  программирования  -  6-7 из 10, основной
проблемой  здесь  является  контроль,  отображение  и управление
большим  количеством (до нескольких сотен) динамических объектов
и корректная их взаимосвязь.