Алгоритмы, применяемые в играх

Содержание

Введение
Игры класса Аrcade - семейство "Платформы и лестницы"
Игры типа Adventure
Имитаторы
Воздушные имитаторы
Двумерные имитаторы
Спортивные имитаторы
Sport-Arcade игры
Спортивные стратегические игры
Логические (традиционные) игры
Менеджментские игры
Список ссылок

Введение

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

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

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

Поэтому представляет особый интерес анализ коммерческого успеха тех или иных игр с точки зрения сложности как алгоритмов, заложенных в их основу, так и их программирования. Вообще степень сложности программирования игр считается самой высокой. Это объясняется рядом причин, о которых мы скажем ниже. При оценке игр следует принимать во внимание такой факт. Практически все фирмы, занимающиеся разработкой компьютерных игр, имеют готовые библиотеки по таким направлениям, как поддержка быстрой графики, анимация, создание и подключение к программе музыки и т.п. Очевидно, имеются и тщательно охраняемые разработки по поддержке трехмерной графики для создания имитаторов или игр типа DOOM, а также готовые макеты для быстрого создания игр различных жанров. Мы не будем учитывать эти разработки при анализе сложности игр; интерес представляют лишь достаточно оригинальные разработки.

Игры класса Аrcade - семейство "Платформы и лестницы"

Игры класса Аrcade охватывают огромную область, имеющую лишь один объединяющий признак, - высокие требования к спинному мозгу. Поэтому практически невозможно описать и проанализировать один алгоритм на всех. В самом деле, что общего между PipeDream и Принцами Персии? Поэтому здесь можно выделить, например, одну большую группу, в которой главный герой перемещается по бесчисленным лабиринтам замков или космических кораблей, дерется на мечах или стреляет из бластера в тучи мерзких существ, выскакивающих из всех дыр и дверей, перепрыгивает ямы и ловушки и подбирает различные полезные или вредные предметы, которые могут пригодиться в дальнейшем или просто приносят очки. Конечная цель здесь бывает различной в игровом смысле - или спасти принцессу, или Вселенную, или найти Волшебную чашу, но внутри игры конечной целью является, как правило, нахождение хорошо спрятанного объекта. Эта группа имеет название "Платформы и лестницы"

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

Итак, рассмотрим возможные структуры данных в типичных platforms & ladders- играх. Во-первых, это сам лабиринт. Он представляется трехмерным массивом (LxNxM). Первое измерение - это список из L уровней, отличающихся друг от друга конфигурацией лабиринтов и их сложностью. Второе и третье измерения описывают двумерный массив размером NхM, определяющий конкретную структуру L-го лабиринта. В реальности параметры M и N могут определять как длину и ширину при виде сверху, так длину и высоту при виде сбоку.

Конкретный элемент массива определяет наличие в месте (i,j) стены и прочих персонажей игры. Для визуализации лабиринта используется специальная таблица связей значений элементов этого массива с кодами спрайтов, служащих для отображения этого элемента на экране. Экран представляет собой прямоугольную матрицу, каждый элемент которой соответствует некоторому элементу игрового массива со сдвигом от начала в зависимости от местоположения героя. Как правило, на экране присутствует не весь лабиринт, а только его маленькая часть. Хотя это может показаться удивительным, но "ВСЕ" игры этого жанра построены именно так.

Хотя герой вроде бы может передвигаться в стороны на 1-2 пиксела, а квадраты изображения имеют размеры не менее 20 пикселов, но здесь нет ошибки. Дело в том, что спрайт героя на экране может быть привязан к точным координатам, но перемещение его по внутреннему массиву программы происходит по дискретным координатам. Если герой смещен относительно подъемника на 5 пикселов, то попытка подняться вверх либо ни к чему не приведет, либо поставит героя "ТОЧНО" в центр лестницы (ее новых позиций в массиве). Вы можете убедиться в этом самостоятельно. Этот принцип является основополагающим и фундаментальным для большинства компьютерных игр, таких как военные, RPG и многих других. Мы еще встретимся с этой идеей в дальнейшем.

Отображение экрана (крайне условное, так как на практике происходит предварительное формирование образа экрана в буфере, подготовительные анимационные процедуры и т.д.) выглядит так:

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

Каждый конкретный код стены напрямую привязывается к его изображению на экране. Некоторые диапазоны значений соответствуют одному изображению, некоторые значения индивидуальны. Например, наклонный пол записан в ячейках игрового поля (5,5),(6,6),(7,7). На экране каждый из этих элементов отображается в виде наклонного участка.

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

В многих играх присутствует такой элемент стен как движущиеся платформы. Несмотря на свою принадлежность к типу стен, внутри программы они относятся к совсем другому типу движущихся объектов. Об этом будет сказано ниже.

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

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

Если стена остается на месте, то, очевидно, ничего делать не надо.

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

Допустим, если вы хотите разместить примерно пять жизней в лабиринте размером 50 х 50, то исходный текст будет выглядеть примерно так:

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

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

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

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

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

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

Вот небольшой пример проверки съедания героя монстрами:

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

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

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

Сам алгоритм platforms & ladders-игр похож на алгоритмы из многих других типов игр. Попробуем его описать.

1. Проинициализировать все начальные значения в игре, создать текущий уровень лабиринта.
2. Опросить клавиатуру или джойстик. Если человек ничего не делает, то перейти к п.5.
3. Если передвижение героя, то
   • вычислить новые координаты;
   • если передвижение вперед возможно, то передвинуть героя, проверить достижение цели и наличие в новой точке других объектов (ключ, платформа, монстр и т.д.) При наличии сделать необходимые действия.
   • иначе восстановить старые координаты;
   • Если герой выстрелил, то добавить объект "пуля" в список динамических объектов.
4. Просканировать список динамических объектов. Для тех, у кого подошла периодичность действия:
   Для объектов типа платформа: вычислить новые координаты, переместиться;
   Для объектов типа монстр : вычислить новые координаты, переместиться, проверить наличие жертвы в новой точке, при необходимости совершить нужное действие;
   Для объектов типа пуля : переместиться в новую точку. Если она не пуста, то:
   • если в ней поражаемая цель, то изменить характеристики цели (понизить запас энергии, вычеркнуть из списка объектов); вычеркнуть себя из списка динамических объектов.
5. Перейти к п.2.

Конечно, современные platforms & ladders-игры во многом сложнее приведенного нами алгоритма. Они представляют собой, как правило, сложное сочетание лабиринтной идеологии с крутыми аркадными вставками, менеджментом, но основа их остается неизменной. Многие разновидности и новые версии известных игр являются, по сути, старыми играми с новыми картинками спрайтов и измененным количеством персонажей с различными характеристиками. Сложность этого типа игр сегодня заключается практически только в оптимальном подборе параметров, придумыванию хорошего сюжета и качественного дизайна.

Сегодня появляются новые игры этого жанра, например, DOOM. Качественным их отличием от себе подобных является увеличение числа измерений до трех. Правда, это не сильно меняет структуру программы. Хотя герой теперь имеет возможность перемещаться не дискретно - по квадратам, а непрерывно, то есть как и в реальной жизни, перемещаться в любую доступную точку помещения, но по сути ничего не меняется. Конечно, исчезает базовый массив, описывающий структуру лабиринта, а задача проверки столкновения героя со стенами ложится на программу, но принцип остается схожим. Теперь программа содержит только описания координат стен и их толщин и проверяет допустимость координат героя:

Соответственно появляется по аналогии с списком динамических объектов и список статических объектов (PowerUp List). При этом на каждом шаге героя проверяется его близость к тому или иному предмету и при необходимости совершается соответствующее действие. Некоторые предметы надо специально брать, для чего служит специальная клавиша. Но в целом структура базового алгоритма не меняется. Введение третьего измерения по сути аналогично новым уровням игры, когда подъем наверх имитирует переход на другой уровень или вход в другой лабиринт в обычных играх этого типа. На самом деле создатели игр типа DOOM исповедуют оба подхода. Например, в игре Terminator:Rampage фирмы Bethesda Softworks с 3-Д графикой, практически идентичной Id Software, положение героя тоже дискретно, а расположение комнат и коридоров на каждом из уровней заложены в массив 100х100 элементов. Но на внешнем виде игры этот нюанс никак не сказывается.     

Игры типа Adventure

Эти широко известные игры, такие как "Leisure Suit Larry", "Loom", имеют, на первый взгляд, схожий с предыдущим типом алгоритм. Здесь герой вроде бы также осуществляет поиск в некотором пространстве необходимых предметов и пытается добраться до конца некоего лабиринта ситуаций. Отличия заключаются в наличии персонажей, с которыми надо общаться - поговорить, что-то узнать; в запутанном порядке достижения цели - пока что-то не сделал, дальше не продвинуться; и в связи с этим с необходимостью исследования игрового пространства. Кроме того, принципиально отличная от "Платформ и лестниц" организация интерфейса, основанная на диалоговом, подчас чисто словесном общении, делает внутреннюю структуру этого типа программ достаточно оригинальным.

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

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

Базовый массив (LxNxM) определяет набор из L локаций, каждая из которых в принципе повторяет структуру лабиринта игр Arcade, только образ ее на экране более закамуфлирован. Это может быть площадка из домиков среди гор, причем переходами в другие локации являются входы в домики, тропинки между горами и так далее, как, например, в "Loom". При этом функции стен выполняют такие элементы дизайна, как подножия гор или просто промежутки между проходами, недостижимые в игре.

Сложность таких псевдолабиринтов низка, она не является самоцелью, а лишь выполняет вспомогательную цель приближения экранного образа к реальному. Но они выполняют важную в адвентюрах роль виртуального пространства, которое играющий должен исследовать. Более важными в схеме алгоритма является описание и хранение тех событий и/или объектов, которые должны встретиться в данной локации. Это могут быть спрятанные в разных местах бананы, как в "Secret of" "Monkey Island I", или препятствия, которые можно преодолеть с помощью различных приспособлений, таких как бюстгальтер в "Страстной Патти". Они кодируются определенными значениями в массиве, но не всегда отображаются на экране, например, пока герой не выполнит некоторого действия-исследования в данной точке типа "посмотреть повнимательнее" или если герой не имеет с собой предмета, активизирующего данное событие. Например, процесс поиска Инди Джонсом ключа в доме Генри может быть запрограммирован примерно так:

В дальнейшем по значению "Мастер-прошел" можно определять, на каком этапе находится развитие сюжета в данной локации.

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

Сам объект ГЕРОЙ содержит в себе большое количество флажков, определяющих наличие у героя тех или иных вещей, а также его возможное здоровье и прочую вспомогательную информацию. Здесь содержится такая информация, как наличие у Роджера Вилко картриджа в "Space Quest I" или флейты у Брандона в "The Legend of Kyrandia I".

В играх данного типа, как правило, нет автономно движущихся объектов, как в Arcade. Вы редко встретите здесь монстров, разгуливающих по горам, или роботов, бесцельно болтающихся по отсекам звездолета. Все сценки встреч обычно заранее предопределены, и проигрываются на экране, как простые анимационные вставки без вмешательства со стороны игрока. Хотя нельзя забывать и о том, что герой игры нередко может в этих сценах стартовать диалог или же применять какие-либо предметы. Кроме того, для игр в концепции "виртуального театра" "полубестолковое" движение персонажей вполне возможно и даже почти обязательно. Существует также такое семейство игр, как "аркадная адвентюра", к сожалению редко встречающееся на IBM-совместимых машинах, хотя по технологии программирования они скорее попадают в раздел, посвященный жанру Arcade (см. выпуск N7).

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

Способы организации интерфейса человека с персонажами игры мы не будем здесь рассматривать. Это может быть простая строка для ввода текстовой информации (типа "use little flag on little hole" в "Future Wars" для использования найденного в туалете флажка) или выбор мышкой пиктограммки РОТ и РУКА в "ECOQUEST II" для разговора с отцом и вытаскивания из ящика Экорекордера. Вы можете пробовать самые невероятные сочетания действий с предметами для нахождения единственно верного в данной ситуации решения.

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

1. Загрузить новую локацию.
2. Ожидать перемещения мышки или нажатия ее кнопки.
3. Если мышка расположена над xy-полем игрового массива с непустым значением, то вывести соответствующую информацию о наличии в данном месте экрана определенных возможностей, иначе стереть старую информацию.
4. Если нажата кнопка мыши над пустым полем, доступным герою, то переместить его в новую позицию.
5. Если нажата кнопка мыши над непустым полем, то при наличии включенных флажков совершить соответствующее действие (открыть дверь, взять предмет, вывести необходимый текст).
6. Если выбрано определенное действие из списка возможных, то проверить положение героя в нужной точке для выполнения данного действия и наличие необходимых вещей для изменения обстановки и откорректировать соответствующие переменные. При необходимости проиграть соответствующий сюжет.
7. Перейти к п.2.

Разумеется, наши читатели понимают, что приведенный алгоритм представляет собой предельно упрощенный вариант. В большинстве современных игр используются более сложные алгоритмы: во-первых, дело может несколько усложниться постоянной фоновой анимацией - типа горящих огней, развевающихся флагов и еще чего угодно - вы видели это много раз. Во-вторых, часто встречаются экзотические отклонения - типа ситуации "не трогай крысу" в "Secret of Monkey Island I". В-третьих, в такой алгоритм не вписываются действия, ограниченные по реальному или псевдореальному времени, а также действия пользователя в рамках активного мультфильма - типа "битвы" со снежным человеком в "King's Quest V".

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

Имитаторы

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

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

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

Каждый объект окружающего пространства описывается в таких программах, как массив фиксированного количества многогранников или частей шаров конкретного цвета. Так представлены самолеты, пирамиды, дома в многих имитаторах, например, "LHX".

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

Плохо здесь то, что объекты меняются не непрерывно, а дискретно. Правда, при разрешении экрана 320х200 это практически незаметно. Современные фирмы-создатели имитаторов постоянно совершенствуют свои алгоритмы визуализации, повышая скорость матричных преобразований, создавая новые математические методы и добиваясь удивительных эффектов. Новые игры на этом рынке отличаются использованием режимов более высокого разрешения и очень точной имитацией реальности. Примером здесь может служить Microsoft Flight Simulator.

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

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

Воздушные имитаторы

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

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

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

Некоторые игровые объекты, атакующие самолет героя, программируются иначе. Они в реальности не выстреливают снаряды, живущие в игре, а действуют по иному алгоритму. Когда ваш самолет попадает в поле их контроля, то по заданным вероятностям, меняющимся в зависимости от уровня, просто определяется сам факт поражения вашего истребителя и размеры ущерба. Это, конечно, сопровождается визуальными эффектами - кабина дрожит, экран заволакивают клубы дыма, и звуковыми - грохот взрывов. Например:

1. Выбрать очередную миссию, проинициализировать все начальные значения в игре, установить игровым объектам их координаты и характеристики. Начать полет.
2. Переместить самолет, изменить вид из кабины.
3. Опросить клавиатуру или джойстик. Если человек ничего не делает, то перейти к п.6.
4. Если человек управляет самолетом, то внести коррективы в скорость, направление движения и т.д.
5. Если герой выстрелил, то добавить объект "пуля" в список динамических объектов.
6. Просканировать список динамических объектов.
   Для объектов типа самолет противника: переместиться по алгоритму маневрирования, по заданному закону распределения вероятности вести огонь по самолету героя;
   Для наземных объектов типа танк: если самолет героя в зоне обнаружения, то начать огонь по случайному закону;
   Для объектов типа пуля: переместиться в новую точку в соответствии с возможностью автоматического преследования;
   Если она не пуста, то:
   • если в ней поражаемая цель, то изменить характеристики цели (нанести технический урон, вычеркнуть из списка объектов);
   • вычеркнуть себя из списка динамических объектов.
7. Перейти к п.2.

1. Соответствие самолету-прототипу по геометрическим размерам, общему виду (пропорциям), камуфляжу, маркировке, расположению приборов и оборудования в кабине.
2. Разнообразие имитируемых самолетов соответствующего исторического периода.
3. Соответствие прототипам самолетов противника по внешнему виду, составу вооружения, летным характеристикам.
4. Сложность и насыщенность воздушной обстановки.
5. Сложность и насыщенность наземной обстановки (объекты своих войск и цели противника).
6. Реалистичность изображения наземных целей.
7. Логическая последовательность и сложность заданий.
8. Специальные (нетиповые) задачи.
9. Исторические задания.
10. Дружественность интерфейса пользователя при планировании заданий, возможность настройки опций.
11. Звуковая имитация.
12. Музыка.
13. Оцифрованная речь.
14. Увлекательность игрового пространства.
15. Общая привлекательность графики.
16. Простота освоения.

1. Соответствие прототипу по летно-техническим характеристикам.
2. Управление самолетом в полете. Понятие "летно-технические характеристики" охватывает целую область знаний, выражающихся в конкретных имитаторах параметрами максимальной скорости и кривыми ее набора, скоростью изменения мощности двигателя, устойчивости самолета в различных погодных условиях, характеристиках выполнения поворота, необходимых углах наклона при этом и т.д. Все эти параметры описываются соответствующими математическими моделями из учебников по авиадинамике, а сами имитаторы отличаются друг от друга лишь степенью приближения используемых алгоритмов к реальности.
   
   Понятно, что пока невозможно на IBM PC смоделировать турбулентные потоки вокруг крыла изменяющейся формы, но, с другой стороны, примитивные арифметические методы типа "жму [Up] - скорость увеличивается, жму [Left] - вектор скорости смещается влево" не позволяют сымитировать более-менее реальное движение самолета и пригодны лишь для простых авиастрелялок, не являющихся авиаимитаторами в полном смысле этого слова.
3. Соответствие прототипу по составу и алгоритмам работы бортового оборудования.
   
   Большинство меняющихся во время полета параметров типа высоты, наклона самолета, количества топлива, наличия вооружения, работы радара и сигнальных устройств зависят от точности и близости к реальности математической модели имитатора, а также полнотой реализации внешнего вида кабины и наличия соответствующих приборов. Например, для моделирования работы высотомера в текст программы, отвечающий за увеличение/уменьшение высоты самолета, вставляется вызов процедуры ShowNewHeight( CurrentHeight ), которая отображает нужным способом - стрелкой или цифрами - текущую высоту CurrentHeight на экране.
4. Соответствие прототипу по составу и режимам работы бортового радиоэлектронного оборудования и систем радиоэлектронной борьбы.
   
   Принцип реализации радиолокатора достаточно очевиден. В каждый момент времени, когда в программе происходит вычисление новых координат самолета, проводится сканирование списка динамических объектов и вычисление расстояния от данного объекта до самолета (по теореме Пифагора). Если это расстояние меньше некоего параметра, характеризующего в игре дальность действия самолетного радара, выбираемого из соображений максимального соответствия прототипу, то на экране локатора появляется точка с окраской, характеризующей определенные параметры обнаруженного объекта (танк, истребитель). Зная наши координаты, а также координаты объекта и дальность действия радара, легко определить координаты точки в масштабной сетке радара:
   
   

   { цикл по всем динамическим объектам игры : } for i := 1 to CurrentObjectNum do { если i-й объект может быть обнаружен радаром : }   if List[i].SightForRadar then   begin     X := Main.X - List[ i ].X;     Y := Main.Y - List[ i ].Y;     { координата Z нужна для обнаружения летящих объектов : }     Z := Main.Z - List[ i ].Z;     { если расстояние от i-го объекта до самолета     меньше максимального действия радара : }     if sqrt( X*X + Y*Y + Z*Z ) < Main.RadarDistance then     { то отобразить на радаре i-й объект в точках,     пропорциональных размеру радара с учетом типа объекта     RadarType, характеризующего цвет отображения его на радаре}     Main.ShowObjectOnRadar(     round(X * RADAR_SIZE / Main.RadarDistance),     round(Y * RADAR_SIZE / Main.RadarDistance),     List[ i ].RadarType );

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

   { Отрисовка i-го объекта: } { ... нарисовать объект ... } { если i-й объект выделен в качестве цели : } if i = TargetNumber then { нарисовать выделение объекта: }   DrawOnScreenAsTarget( TargetNumber );

   
   
   Самонаводящиеся ракеты после их запуска попадают в список динамических объектов и действуют уже автономно, в соответствии со своими параметрами и заданной мишенью, независимо от играющего.
   
7. Специальное оборудование и его функции.
   К понятию специальное оборудование относятся, как правило, фантастические приспособления в космических имитаторах типа защитных силовых экранов, различных типов двигателей - химических, фотонных и т.п. Здесь все зависит только от фантазии сценариста и мастерства программиста.
8. Возможности управления и связи.
9. Воздушная навигация.
   Способы организации управления и процесса связи в большинстве авиаимитаторов достаточно похожи. С помощью клавиш-стрелок или джойстика самолет может закладывать виражи, космический корабль выделывать более сложные маневры с помощью своих дюз, а траектория его движения получается из используемой математической модели. Связь с базой имитируется обычно достаточно примитивно способом типа получения очередного задания в виде бегущей строчки на экране в момент выполнения очередного пункта боевой задачи или в начале игры.
   
10. Уровень летной подготовки и интеллекта (тактика действий) воздушного противника.
    Эта тема относится к области искусственного интеллекта и вообще-то заслуживает отдельного разговора. Мы ограничимся здесь одной цитатой из напечатанного в PC-Review интервью с фирмой DIGITAL INTEGRATION. Ее программист Ник Маскаль в ответ на вопрос "Как работают перехватчики противника, которыми управляет компьютер? Они на самом деле выполняют какие-то маневры по заданной программе, или действуют сообразно с обстоятельствами?" ответил так: "Да, сообразно с обстоятельствами запускаются очень простые алгоритмы маневрирования типа "ножниц". Хотя, конечно, реальные алгоритмы более изощренны".
    
11. Имитация атмосферных явлений (облачность, туман, дымка, осадки и т.д.)
    
12. Имитация времени года и суток.
    Светлое и темное время суток, а также некоторые атмосферные явления можно имитировать подбором соответствующей цветовой палитры. Например, день - небо голубое, ночь - черное. В тумане помимо цветовой настройки-напыления молочного цвета меняется дальность видимости объектов. Если в солнечную погоду танки противника появляются на экране при приближении самолета к ним, условно, на пять километров, то в ночное время или в дымке это расстояние снижается до одного-двух километров.
    
13. Имитация местности.
    
14. Имитация общей инфраструктуры на местности (населенные пункты, дороги, мосты и т.д.)
    
15. Имитация водной поверхности.
    Эти имитации в основном создаются сценаристами и гэйм-дизайнерами, как статические объекты в игре. Их реальность отображения зависит исключительно от качества используемых 3D-библиотек и мастерства художников.
    
16. Сложность и насыщенность системы ПВО противника.
    
17. Соответствие характеристик средств вооружения и тактики действий ПВО.
    
18. Поражающие возможности средств ПВО.
    В начале этой главы мы приводили пример программирования атаки наземным устройством летящего истребителя. Моделирование работы ПВО происходит аналогично. Требуется лишь детальная и точная подгонка различных параметров, чтобы функционирование ПВО в игре более-менее соответствовало реальному сражению.
    
19. Возможность управления тактическими операциями (звено-эскадрилья).
    
20. Возможность управления оперативно-тактическими операциями (полк-дивизия).
    
21. Возможность управления стратегическими операциями.
    Включение в игру возможностей влияния своими действиями (например, уничтожением командного пункта противника) на общий исход сражения выводит игру далеко за рамки простого симулятора военного самолета. Например, в игре "Секретное оружие Люфтваффе" имитатор совмещен с элементами стратегических или военных игр. Эту тему мы рассмотрим подробно в разделе WarGames.
    
22. Возможность реализации карьеры пилота и записи заданий.
    По мере успешного выполнения героем боевых миссий он повышается в звании. Это отслеживается пропорционально степени сложности выполненного задания, когда за более ответственное задание вы можете получить более высокое звание. Сохранение текущего состояния игры осуществляется обычно в соответствии с именем игрока, вводимого в начале игры. В дальнейшем, когда вы снова запускаете программу и указываете свое имя, то программа ищет в списке сохраненных заданий запись с соответствующим именем и восстанавливает ранее отложенную игровую ситуацию.
    
23. Требования к ресурсам компьютера.
    Имитаторы, как правило, не предъявляют слишком высоких требований к компьютеру. Для реализации быстрой графики обычно используется 256-цветный режим 320х200 точек, поддерживаемый даже MCGA. Желательно наличие сопроцессора для более быстрого вычисления трехмерных преобразований. Компактное (векторное) представление большинства игровых объектов позволяет использовать небольшие по размеру файлы данных. В последнее время прослеживается явная тенденция к усложнению игр этого класса, включаются элементы военной стратегии, увеличивается до сотен количество боевых миссий, повышается качество и детальность графики, поэтому можно спрогнозировать увеличение требований к компьютеру. Минимальной конфигурацией в ближайшие годы будет 386DX компьютер, 4 Мб оперативной памяти и более ста мегабайт на жестком диске (для хранения еще и других игр).

Двумерные имитаторы

К этой группе относятся имитаторы подводных лодок и наземных средств передвижения типа автомобилей или танков. Эта группа значительно проще предыдущей. Моделирование изгибающейся дороги тривиально, меняющийся пейзаж легко создается с помощью фоновой FLI-анимации, прокручиваемой непрерывно в одну или другую сторону. Таким образом устроены игры типа "Formula One" или "Test Drive". Ряд других игр использует стандартные трехмерные анимационные пакеты для создания более реалистичной обстановки, которая требуется, как правило, в боевых играх на большом театре действий. Это игры "Steel Thunder", "Tank", где используется типичное моделирование окружающих объектов - горок, деревьев, пушек и БМП противника и т.д.

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

К этой же группе относятся и имитаторы подводных лодок. Под водой имитируются только днища кораблей и само плоское дно, что является, скорее, не 3-х, а 2.5-мерным моделированием, а уже на поверхности океана перемещение чисто двумерное, когда 3D-имитация используется в процессе скольжения лодки по поверхности для изображения кораблей противника. В целом эти симуляторы не имеют отличий от воздушных имитаторов и имеют такой же базовый алгоритм и структуру данных. Надо отметить, что в последнее время появляются полноценные трехмерные подводные имитаторы, в которых достигается изумительное по качеству и детализации трехмерное изображение, недоступное пока авиаимитаторам из-за высокой скорости их перемещения в отличие от плавного движения субмарин. Таким великолепным стратегическим имитатором является "SUBWAR 2050"

Спортивные имитаторы

Sport-Arcade игры

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

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

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

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

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

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

1. Инициализация параметров игры. Выбрать некоторого спортсмена для управления.
2. Если игрок нажал клавишу, то выбрать действие:
   • перемещение: переместить выбранного спортсмена;
   • дриблинг: перемещать спортсмена с проверкой сопротивления игроков противника; при необходимости отдать мяч;
   • пас: в соответствии с длиной паса и индивидуальными характеристиками спортсмена определить точку приземления мяча;
   • оборона: рассчитать вероятность отбора мяча у игрока противника в соответствии с индивидуальными характеристиками;
   • удар по воротам: с учетом положения игрока по отношению к воротам и их защищенностью игроками противника рассчитать вероятность попадания в створ ворот; по индивидуальным характеристикам вратаря рассчитать вероятность ловли мяча.
3. Для i-го игрока, управляемого компьютером, выполнить простейшие действия:
   • если мяч или игрок команды соперников с мячом в зоне контроля данного игрока, то перемещаться к нему и попытаться отобрать мяч;
   • если мяч у игрока своей команды, то перемещаться вперед до границы своей зоны;
   • если мяч у игрока чужой команды, то перемещаться назад до границы своей зоны;
   • если мяч у самого игрока, то в зависимости от функций (нападающий, защитник) и распределения вероятностей рассчитать необходимость паса/дриблинга/удара по воротам.
4. Вернуться к п.2.

Спортивные стратегические игры

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

Внутри программы порядок распасовки или дриблинга на территории противника устанавливается некоторым распределением вероятностей между задачами игрока. Для футбола в тактические параметры игрока могут входить: пас, дриблинг, удар по воротам. Вы задаете расстановку игроков на футбольном поле (например, по системе 4+4+2) и указываете для каждого игрока цель для паса, частоту ударов по воротам для нападающих или попытку дриблинга для сольного прохода. В программе каждому объекту-игроку соответствует список параметров, описывающий его поведение. Например, для защитника, когда он оказывается с мячом, указываются номера игроков, которым он должен будет отдавать пас:

1. Проинициализировать начальные параметры и расстановки игроков каждой команды.
2. Если мяч находится у i-го игрока j-й команды, то определить его действия с мячом - дриблинг, пас или удар по воротам.
   • дриблинг: для траектории до конечной точки перемещения игрока определить возможных защитников противника, находящихся в некоторой эпсилон-окрестности траектории дриблинга, и для каждого из них проверить факт отбора мяча в соответствии с индивидуальными характеристиками игрока и защитника. В случае отбора поменять хозяина мяча;
   • пас: в соответствии с индивидуальной точностью паса рассчитать точку приземления мяча; определить ближайших к мячу игроков в некотором радиусе приземления, и если игроков окажется несколько из разных команд, то начать борьбу за мяч, как в дриблинге. При необходимости поменять хозяина мяча;
   • удар по воротам: с учетом технической характеристики игрока "точность удара по воротам", расстояния до ворот и угла удара определить вероятность попадания мяча в створ ворот. При удачном раскладе учесть качество "непробиваемости" вратаря и уже в случае пропуска мяча вратарем засчитать гол.
3. Если мяч не находится ни у одного из игроков, то вступить в борьбу за него (см.выше). Определить обладателя мяча и перейти к п.2.
4. Увеличить время на некоторый квант. Проверить окончание игры. Перейти к п.2.
5. Если забит гол, то изменить счет, передать мяч определенному игроку пропустившей гол команды в центре поля и перейти к п.2.

Логические (традиционные) игры

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

В этом отношении игра "SPOT"("пятнышко") безусловно выделяется отлично сбалансированными правилами. Ее автор фирма "Virgin Games", известная такими играми, как "Dune 2", впоследствии переименовалась в "Virgin Interactive Entertainment". Ее CD-ROM хит "7-й Гость" включает в себя в качестве одной из 23 головоломок, которые вы решаете, путешествуя по мрачному дому, свою игру "пятно", тоже, можно сказать, превратившуюся из "Game" в "Interactive Entertainment".

Надо сказать, что хотя логические игры никогда не занимают верхних строчек в любых таблицах популярности компьютерных игр, но тем не менее пользуются устойчивым спросом и способны приносить своим создателям немалый доход. К примеру, всем известный "Chess Master" фирмы "Software Toolworks", реализованный в семи версиях (CM2000, CM2100, CM3000), в том числе для компьютеров ATARI, AMIGA и MAC, для среды WINDOWS, в конце 1993-го года - еще до выхода очередной суперверсии "ChessMaster 4000 Turbo" имел устойчивый объем ежемесячных продаж четыре тысячи копий. А программа разрабатывается уже более десяти лет! Кроме того, в ряде традиционных игр, таких как шахматы или Го, призы за победу над чемпионом мира достигают миллионов долларов, что намного превышает прибыли от самых лучших компьютерных игр других жанров.

В некоторых странах логические игры возводятся в ранг религии. Так, в Японии древнейшая игра Го приносит своим чемпионам поистине божественное поклонение. Можно с уверенностью сказать, что человек, способный создать сильную программу в Го, на уровне лучших японских мастеров, обессмертит свое имя в Стране Восходящего Солнца и получит миллионные доходы. Уже официально объявлен приз в один миллион долларов для программы, играющей в силу 1-го дана. Но игра Го отличается от других игр подобного плана именно сложностью эффективной реализации на компьютерах, поэтому появление сильнейшей программы в Го предсказывается к 2050-му году (для примера, в шахматы - к 2010-му).

Возможности, предоставляемые программами класса традиционных игр, стандартны. Вы всегда видите перед собой игровую доску в двумерной или трехмерной проекции. Изображения фигур могут быть как соответствующими типовым, так и оригинальными - например, короли и королевы, солдаты, рыцари и т.п. - как в "Battle Chess". Дополнительно на экране отображается много вспомогательной информации - время, список ходов, имена игроков. Вы можете сохранить или восстановить из базы ранее сыгранные партии, ваши или других игроков и профессионалов, просмотреть их по ходам вперед-назад, продолжить текущую партию с любого места, выбрать свой цвет, установить контроль времени и силу игры программы, ее настройку цветов и т.д. Но все эти технические дополнения требуют чисто рутинной работы. А как же программа выбирает лучший ход? Именно этот момент является ключевым в программировании традиционных игр.

Подавляющее большинство программ построено на так называемом методе "грубой силы" - "brute force" (полный перебор). Из текущей позиции определяются все возможные ходы - в шахматах их в среднем бывает около 50, в Го - 100-300, в калах - до 6. Они запоминаются в массиве Moves[][], где первым измерением является глубина перебора (исходно 0), а вторым - список ходов из позиции на i-м уровне. Затем выбирается очередной ход из нерассмотренных на данном уровне, совершается, опять определяются все возможные ходы (уже за другую сторону), снова выбирается очередной ход, и так происходит до достижения некоторой заданной глубины. В конце варианта происходит оценка возникшей позиции с помощью экспертных оценок (например, значения фигур плюс позиционная составляющая - конь в центре-хорошо, король открыт-плохо), и из всех позиций, перебирающихся на заданной глубине, выбирается одна с максимальной оценкой, и первый ход, ведущий по ветке в эту позицию, объявляется лучшим.

Эта методика стандартна, она описана во множестве статей и учебников по игровому программированию. Но посмотрим, а на какую-же реальную глубину сможем мы рассчитать варианты? Ведь количество ходов в дереве вариантов явно подчиняется геометрической прогрессии. В шахматы для игры на мастерском уровне требуется считать не менее чем на четыре-пять ходов (или 8-10 полуходов - ходов одной стороны) плюс форсированные продолжения - взятия, шахи и превращения. Тогда программе за две минуты стандартного контроля времени в официальных партиях потребуется просмотреть минимально 50 в десятой степени ходов, что составляет 10 в пятнадцатой степени позиций (миллион миллиардов). Лучшие программы на 486-м процессоре в секунду анализируют не более тысячи позиций. За две минуты это составит 120000 позиций. Для расчета на глубину 10 полуходов программе потребовалось бы 10 миллиардов секунд или около сорока лет!

Но, к счастью, умные люди придумали специальные эвристики, позволяющие существенно сократить объем перебора. Это, в первую очередь, алгоритм ветвей и границ, затем служба лучших ходов, хэш-таблицы и еще несколько других. Таких эвристик в мире известно немного, около десятка, и за каждую новую математики всех ведущих научных центров мира готовы платить огромные суммы - ведь большое количество прикладных задач решается именно методом перебора. Более подробно интересующиеся методами программирования переборных задач могут почитать статью о программировании игры в калах с исходными текстами алгоритмов на языке Си в одном из номеров PC-Review.

Отсюда становится понятной проблема программирования игры в Го. Если в шахматах коэффициент геометрической прогрессии 50 позволяет лучшим программам быстро рассчитывать варианты на пять-шесть ходов, то в Го количество ходов в начале партии составляет 19*19 = 361 ход, а в середине, когда начинается основная борьба - около двухсот. Понятно, что в лучшем случае программа сможет сделать расчет на четыре, максимум пять полуходов, что совсем недостаточно для сильнейшей игры. Го игра во многом позиционная, но, к сожалению, проблема обучения программ позиционной игре остается пока открытой.

Недавно появившаяся программа "Chess Master 4000 Turbo" помимо нового дизайна содержит очень интересные нововведения. Во-первых, она способна оценить с позиционной точки зрения словесными выражениями любой ваш ход с помощью комментариев типа "этот ход хорош тем, что ладья занимает открытую линию d" или "этот ход плох тем, что конь уходит из центра, ослабляя контроль над полем f5". Такая, безусловно полезная для подавляющего большинства игроков возможность, достигается сравнением оценок позиции до и после хода и выявлением тех позиционных составляющих, которые дают основную разницу в оценках. Каждой из таких составляющих приписан набор стандартных фраз на английском, и они выводятся на экран.

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

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

Отметим также чемпиона мира последних лет среди компьютерных программ для IBM PC - английскую программу "Hiarcs-Master 3.0" Марка Униаке, имеющую рейтинг выше 2500 (гроссмейстер), а в блице около 2600 - сильный международный гроссмейстер. Конечно, на процессоре Р6, когда он появится, рейтинг программы возрастет еще больше, так как скорость расчета напрямую зависит от быстродействия компьютера и объема свободной памяти. Ее автору удалось найти достаточно оптимальное соотношение между необходимостью глубокого расчета и сложностью позиционной оценки.

Ведь для увеличения глубины анализа вариантов, чем отличаются два других конкурента "Хайрекса" на гроссмейстерском уровне - программа "Fritz" немецкой фирмы "ChessBase", производящей шахматные справочные системы, и "Genius" Ричарда Лэнга, выигравшая недавно у Каспарова матч из двух партий в блиц на компьютере с Pentium-процессором, приходится жертвовать качеством позиционного оценивания. Кстати, после проигрыша Каспарова большинство ведущих гроссмейстеров потребовало запретить с 1995-го года участие компьютеров в турнирах людей.

Последняя программа известна любителям шахмат по шахматным компьютерам "Мефисто" с мощным специализированным процессором, в память которых зашит "Genius". Интересно, что автор сначала писал программу исключительно для этих автоматов, и лишь затем перенес программу в MSDOS. Ричард Лэнг пишет свои программы исключительно на ассемблере, начиная от дизайна и кончая логической частью. Такое мастерство потрясает, впрочем, по собственному признанию автора, он и не знает других языков программирования, кроме ассемблера.

Благодаря "вылизанному" коду эти две программы способны осуществлять глубокий расчет, не очень заботясь о качестве позиционной оценки. Да это и понятно - ведь более качественный анализ каждой из миллионов позиций существенно тормозит скорость работы и, как следствие, снижает глубину расчета. Но так ли важен грубый расчет? Может быть, достаточно считать на некоторую не очень большую глубину, но более качественно оценивать позицию, используя специализированную шахматную информацию, как это делает человек? Этой проблеме столько же лет, сколько и первой шахматной программе, и пока сильнейшие программы одерживали победу с помощью лишь далекого расчета.

Но вот наконец англичанин Марк Униаке написал свой "Hiarcs" (в свободное от работы время, он даже просит не присылать ему по электронной почте письма о его программе на работу, только домой!), который считает не очень глубоко (относительно, конечно), но интеллектуально подходит к оценке каждой позиции, что дает ему существенное преимущество, особенно при игре с большим контролем времени, когда на первый план выходит не глубина расчета, а чисто шахматное понимание позиции. Московская фирма "ИнформСистемы" (939-10-24), обладающая исключительными правами на распространение данной программы и ряда других сильнейших шахматных спортивных программ в России, предлагала своим постоянным клиентам - пользователям шахматной системы "Chess Assistant", сильнейшим мастерам и гроссмейстерам СНГ, при тестировании "Хайрекса" сыграть с ним несколько партий. За один месяц несколько международных мастеров и гроссмейстеров сыграли с программой более десяти партий и набрали всего пол-очка (только одна ничья), проиграв все остальные !!!

Некоторые версии шахмат, как например, "Star War Chess" вышеупомянутой фирмы "Software Toolworks", основной упор делают на графику, повторяющую в данном случае мотивы фильма "Звездные Войны", когда трехмерные фигуры роботов и космических рейнджеров схватываются в красивых мультяшках, причем игра ведется не чисто по шахматным правилам, а с целью уничтожить главного вражеского предводителя, или "Terminator 2. Chess Wars" фирмы Capstone с фигурами и видеовставками из одноименного фильма. Развивая идею игр с нестандартными правилами, "Software Toolworks" выпустила трехмерную версию игры в нечто, похожее на шахматы, на девятиклеточной доске.

Основная сложность программирования в традицоннных играх ложится на оптимальное построение алгоритма перебора, позволяющего за заданное время анализировать как можно больше позиций. Здесь подчас недостаточно знания программирования, необходимы еще знания математики и теории игр. Сложность программирования - от 5 до 9 баллов из 10 в зависимости от игры, подлежащей программированию. Некоторые игры, например, калах, легко поддаются перебору из-за небольшого числа вариантов, и выигрывают у любого, пусть даже самого сильного, игрока-человека, другие, как Го, позволяют создавать программы пока не сильнее второго разряда.     

Менеджментские игры

История менеджментских, или финансовых, игр берет свое начало с середины 50-х годов, когда роль коммерческого директора фирмы возросла настолько, что возникла необходимость в быстрых и эффективных методах обучения управлением предприятием или банком. Простые курсы уже не давали желаемого эффекта, на первый план выходил опыт, который, казалось, можно приобрести лишь учась на собственных ошибках. Но в реальной жизни ошибка менеджера подчас может привести к существенному ухудшению финансового положения фирмы, вплоть до ее банкротства. Поэтому в 1956-м году Американская ассоциация управления разработала игру "Имитация решений в высшем управленческом звене". Она проводилась, конечно, не на компьютерах, а с помощью специальных бланков и человека-координатора (типа Dungeon-Master), выполняющего роль вычислителя по особым таблицам, отражающим взаимосвязи между различными параметрами игры.

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

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

Некоторые игры перекочевали на домашние компьютеры, практически полностью сохранив исходную математическую модель полной профессиональной игры для специалистов, поэтому они могут реально научить играющего некоторым законам ведения бизнеса без риска потерять свои настоящие деньги. В инструкциях к подобным играм указывается, что набрав соответствующее количество очков, вы можете смело наниматься в любую фирму в качестве менеджера, только показав свои результаты! Отметим здесь серию "Миллионеров", очень точно имитирующую фондовую биржу, и "American Investor" (обе игры фирмы "Britannica Software"), причем последняя была создана при самом непосредственном участии Американской фондовой биржи. В России недавно вышли русифицированные версии некоторых из этих игр, появились оригинальные игры "Президент" фирмы "ИНФОРТ", серия игр "Как добиться успеха" пензенской фирмы "Ижица", отличающаяся качественным графическим интерфейсом.

На чем же основаны математические алгоритмы всех этих игр? Как уже упоминалось выше, математическая теория была разработана достаточно давно, десятки лет назад, и с тех пор изменилась не очень сильно. Так, знаменитая игра "SimCity" базируется на имитационной игре CLUG (Community Land Use Game), разработанной Алланом Фельдтом из Центра по изучению жилищного строительства и охраны среды при Корнеллском университете в 1963-м году. Выпущенная в настольном виде, она завоевала невероятную популярность, породив массу продолжений, издавался даже специальный журнал по этой игре, ее стратегии и т.п.

Подобные исследования проводились и в нашей стране. Здесь необходимо отметить уникальную Имитационную Модель Процессов Экономического Кругооборота, разработанную научным коллективом во главе с В.М.Ефимовым в конце 80-х годов, в которой моделировалась вся экономическая деятельность страны, причем с очень большой степенью достоверности. Конечно, эта игра предназначалась для исследовательских целей, а не для массового рынка.

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

• величина ежемесячного спроса в штуках на автоматы обратно пропорциональна цене, которую вы назначите (гиперболическая зависимость). Проще говоря, по цене 1 доллар вы мгновенно продадите весь выпущенный объем; по цене 10000 долларов вы не продадите ни одной штуки.
• величина себестоимости будет снижаться по мере увеличения и постоянства вкладов в НИОКР, но не линейно, а гиперболически, снижаясь все медленнее и медленнее по мере приближения к некоему естественному минимуму.
• величина ежемесячного спроса в штуках прямо пропорциональна величине вложений в рекламу, но здесь зависимость опять-таки не строго линейная, а например, с некоторым запаздыванием и т.п.

1. Ввести планируемый объем выпуска игровых автоматов (ПО). Он не может превышать некоего предела, обусловленного наличными производственными мощностями. Можно добавить возможность расширения объемов производственных мощностей, допустим, 50000 долларов на каждую дополнительную тысячу автоматов. Рассчитать расход на выпуск Р = ПО * себестоимость.
2. Ввести расходы на НИОКР, добавив их к общим расходам Р, и вычислить новое значение себестоимости.
3. Ввести расходы на рекламу и добавить их к общим расходам Р.
4. Ввести продажную цену. Рассчитать спрос С = f(1 / цена, реклама).
5. Рассчитать доход Д = min( ПО, С ) * цена. Вычесть налоги. Можно предусмотреть возможность уклонения от налогов, но тогда с некоторой вероятностью играющий может потерпеть штрафные санкции.
6. Если ПО > С, то остатки положить на склад: СЗ = СЗ + (ПО - С). Вычесть из дохода Д складские расходы: Д = Д - СЗ * расход на складирование одного автомата.
7. Если ПО < C то допродать имеющееся на складе в количестве (С - ПО).
8. Проверить чисто игровые моменты типа пожара, забастовки и т.п. При случае изменить расходы Р.
9. К имеющейся наличности Н добавить Д - Р. Если Н < 0, то либо вы объявляетесь банкротом и игра заканчивается, либо вам предоставляется возможность получения кредита в банке под определенный процент, что тоже необходимо будет учитывать в следующих циклах игры.
10. Если ваш счет еще не пуст, то переходите к п. 1.

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

Список ссылок

Статья "Практическое руководство по AI"
Статья "Алгоритмы поиска пути"