Готовый перевод Game Programming Patterns / Паттерны программирования в играх: 3.1 Bytecode
Цель
Дать поведению гибкость данных путём кодирования его в виде инструкций виртуальной машины.
Мотивация
Создание игр может быть увлекательным делом, однако же оно не такое простое.
Современные игры требуют огромных, сложных кодовых баз.
Производители консолей и модераторы магазинов приложений выставляют строгие требования к качеству продукта и одна ошибка с последующим падением приложения может закрыть вашей игре путь на рынок.
Я работал над игрой, которая состояла из шести миллионов строк кода на языке C++ .
Для сравнения, ПО, контролирующее марсоход Curiosity, насчитывает меньше половины этой величины.
В тоже время, мы хотим выжать производительность для каждой платформы до последней капли.
Игры нагружают аппаратное обеспечение как никакое другое программное обеспечение и мы неустанно должны оптимизировать свой код просто чтобы идти в ногу с конкурентами.
Чтобы справиться с требованиями высокой стабильности и производительности, мы обращаемся к супер-тяжёлым языкам, вроде C++, которые имеют как низкоуровневую выразительность, чтобы по-максимуму использовать возможности оборудования, так и богатую систему типов для предотвращения, или хотя бы изолирования, ошибок.
Мы гордимся своим мастерством, но всё имеет свою цену.
Будучи опытным программистом с годами соответствующей подготовки, после всего этого вы вынуждены бороться с самим масштабом вашей кодовой базы.
Время сборки больших игр может колебаться где-то от «пойду выпью кофе» и до «пойду прожарю свои собственные бобы, вручную перемелю их, заварю эспрессо, добавлю немного молока и попрактикуюсь в искусстве пить латте».
В дополнение к этим проблемам, игры имеют ещё одно неприятное ограничение: разработка должна проходить с удовольствием.
Игроки требуют ощущений от игры, как от романа, но она всё ещё должна быть хорошо сбалансирована.
Для этого требуются постоянные итерации, но если для каждой правки требуется теребить инженера, чтобы он покопался в дебрях низкоуровневого кода, а затем ждать остужающую пыл перекомпиляцию, вы убьёте своё творческое настроение.
Бой заклинаниями!
Предположим, мы работает над магическим файтингом.
Пара волшебников принимают боевую стойку и бросаются друг в друга заклинаниями до тех пор, пока не будет объявлен победитель.
Мы могли бы определить эти заклинания в коде, но это означало бы, что необходимо каждый раз привлекать инженера для изменения каждого заклинания.
Когда дизайнер захочет подправить несколько цифр, и посмотреть, что получится, нужно будет перекомпилировать всю игру, перезагружать её и снова возвращаться к бою.
Как и большинство сегодняшних игр, нам так же необходимо иметь возможность обновлять её после распространения, как для правки ошибок, так и для добавления нового содержимого.
Если все заклинания жёстко заданы в коде, обновление будет означать фактическую правку исполняемого файла игры.
Давайте пойдём немного дальше и скажем, что мы также хотим поддерживать модификацию игры.
Мы хотим позволить игрокам создавать их собственные заклинания.
Если все они зашиты в коде, то это означает, что каждый моддер должен иметь полный набор инструментов для построения игры, а мы должны выпустить её исходный код.
Хуже того, если они допустили ошибку в своём заклинании, это может обрушить игру на машинах других игроков.
Данные > код
Понятно, что язык реализации нашего движка не подходит для этих целей.
Нам нужно, чтобы заклинания были безопасно отгорожены от ядра игры.
Мы хотим, чтобы их можно было легко изменять и перезагружать, так же мы хотим физически отделить их от остальной части исполняемого файла.
Не знаю, как насчёт вас, но для меня это звучит как что-то, очень похожее на данные.
Если бы мы смогли определить наше поведение в отдельных файлах с данными, которые игровой движок загружал и в некотором роде «выполнял», мы бы достигли всех наших целей.
Нам просто нужно понять, что значит «выполнить» применительно к данным.
Как сделать некоторые байты в файле выражающими поведение?
Есть несколько способов.
Я думаю, оценить сильные и слабые стороны этого шаблона нам поможет сравнение с другим шаблоном: Интерпретатор.
Шаблон Интерпретатор
Я мог бы написать целую главу об этом шаблоне, однако четверо других парней уже сделали это за меня.
Вместо этого я втисну сюда кратчайшее введение.
Оно начинается с языка — думайте о нём, как о языке программирования — который вы хотите выполнить.
Скажем, для примера, он поддерживает арифметические выражения вроде таких:
(1 + 2) * (3 - 4)
Вы берёте каждую часть этого выражения, каждое правило в грамматике языка, и превращаете его в объект.
Числовые литералы будут объектами:
В основном, это просто маленькие обёртки над сырыми значениями.
Операторы также будут объектами и они будут ссылаться на свои операнды.
Если принять во внимание скобки и приоритет, это выражение магическим образом превращается в маленькое дерево объектов:
Что это за «магия»?
Всё просто: разбор.
Парсер принимает строку символов и превращает её в абстрактное синтаксическое дерево разбора — набор объектов, представляющих грамматическую структуру текста.
Сделайте на скорую руку один из них и вы получите половину компилятора.
Шаблон Интерпретатор говорит не о создании такого дерева, а о его выполнении.
Способ, с помощью которого всё работает, довольно умный.
Каждый объект в дереве является выражением или подвыражением.
В истинном объектно-ориентированном стиле мы позволим выражению вычислять самоё себя.
Сперва мы определим базовый интерфейс, который будут реализовывать все выражения:
class Expression
{
public:
virtual ~Expression() {}
virtual double evaluate() = 0;
};
Затем мы определим класс, реализующий его для каждого вида выражений в грамматике нашего языка.
Простейший из них — для числа:
class NumberExpression : public Expression
{
public:
NumberExpression(double value)
: value_(value)
{}
virtual double evaluate()
{
return value_;
}
private:
double value_;
};
Выражение для числового литерала вычисляется просто в его значение.
Выражения для сложения и умножения являются более сложными, поскольку они содержат подвыражения.
Поэтому перед тем, как вычислить себя, они должны рекурсивно вычислить свои подвыражения.
Например, так:
class AdditionExpression : public Expression
{
public:
AdditionExpression(Expression* left, Expression* right)
: left_(left)
,
right_(right)
{}
virtual double evaluate()
{
// Вычисляем операнды.
double left = left_->evaluate();
double right = right_->evaluate();
// Складываем их.
return left + right;
}
private:
Expression* left_;
Expression* right_;
};
Я уверен, что вы сами выясните, как выглядит реализация операции умножения.
Довольно просто, не так ли?
Буквально пара простых классов и теперь мы можем представлять и вычислять сложные арифметические выражения.
Нам просто нужно создать правильные объекты и правильно их соединить.
Реализация Ruby была примерно такой же где-то 15 лет назад.
Но в версии 1.9 они перешли к виду виртуальных машин с байт-кодом, описываемых далее в этой главе.
Посмотрите, сколько времени я вам сэкономил!
Это красивый, простой шаблон, но у него есть несколько проблем.
Взгляните на иллюстрации.
Что вы видите?
Большое количество маленьких прямоугольников и большое количество стрелок между ними.
Код представляется разросшимся фрактальным деревом маленьких объектов.
Это влечёт несколько неприятных последствий:
Загрузка кода с диска требует создания и настройки тонны этих маленьких объектов.
Объекты и указатели на них используют слишком много памяти.
На 32-х битной машине это маленькое арифметическое выражение займёт как минимум 68 байт, без учёта выравнивания.
Если вы воспроизведёте пример, не забудьте учесть указатели виртуальной таблицы функций.
Обход по указателям подвыражений убивает ваш кэш данных.
В тоже время, все эти вызовы виртуальных методов сеют хаос в кэше инструкций.
Смотрите главу Местоположение данных, что бы узнать, что такое кэш и как он влияет на производительность.
Сложим всё вместе, и что сделается с заклинаниями?
МЕ-Е-Е-ЕДЛЕННО.
По этой причине большинство широко используемых языков программирования не используют шаблон Интерпретатор.
Он просто слишком медленный и использует очень много памяти.
Виртуальный машинный код
Рассмотрим нашу игру.
Когда мы запускаем её, компьютер игрока не обходит огромную структуру грамматического дерева C++ во время выполнения.
Вместо этого мы компилируем его загодя в машинный код и процессор запускает именно его.
Что даёт нам машинный код?
Он плотный.
Это непрерывный кусок двоичных данных и ни один бит не пропадает даром.
Он линейный.
Инструкции упакованы вместе и выполняются одна за другой.
Нет прыжков по памяти (конечно, только если вы сами не поменяли фактический поток выполнения)
Он низкоуровневый.
Каждая инструкция делает одну относительно небольшую вещь, а интересное поведение составляется из их комбинаций.
Он быстр.
Как следствие всего этого (ну, а также потому что он реализован непосредственно в «железе»)
, машинный код работает неимоверно быстро.
Это прозвучит странно, но нам не нужен машинный код для наших заклинаний.
Позволяя пользователям предоставлять нашей игре машинный код, который она будет выполнять, мы просто напоремся на проблемы безопасности.
Нам нужен компромисс между производительностью машинного кода и безопасностью шаблона Интерпретатор.
Что, если вместо загрузки и непосредственного исполнения реального машинного кода, мы определим собственный виртуальный машинный код?
Мы бы тогда могли бы написать его небольшой эмулятор в нашей игре.
Он был бы похож на машинный код — плотный, линейный, относительно низкоуровневый — но в тоже время обрабатывался бы целиком в нашей игре, так что мы могли бы безопасно ограничить его.
Именно поэтому многие игровые консоли и iOS не позволяют программам выполнять машинный код, загруженный или сгенерированный во время выполнения.
Они сопротивляются, поскольку реализации самых быстрых языков программирования делают именно это.
Они содержат компилятор «точно-в-срок» или JIT (just-in-time), который транслирует языковые команды в оптимизированный машинный код на лету.
Мы бы назвали наш маленький эмулятор «виртуальной машиной», а синтетический двоичный машинный код, который он запускает — «байт-кодом».
Этому подходу присуща гибкость и простота определения вещей в данных, но так же и лучшая производительность, нежели высокоуровневое представление, как в шаблоне Интерпретатор.
В среде языков программирования термины «виртуальная машина» и «интерпретатор» являются синонимами и я использую их здесь как взаимозаменяемые.
Когда же я ссылаюсь на шаблон Интерпретатор «Банды четырёх», я использую термин «шаблон», чтобы внести ясность.
Однако, всё это звучит слишком сложно.
Моей целью до конца этой главы становится показать вам, что если вы держите свой список хотелок урезанным, то этот подход на самом деле доступен каждому.
Даже если вы в конечном итоге не будете использовать этот шаблон сами, по крайней мере вы станете лучше понимать Lua и многие другие языки, которые реализуются с его помощью.
Шаблон
Низкоуровневые операции, которые могут выполнятся, определяется набором инструкций.
Они кодируются последовательностью байт.
Виртуальная машина выполняет эти инструкции по одной, используя стек для промежуточных значений.
Путём комбинирования инструкций могут быть определены сложные высокоуровневые поведения.
Когда его использовать
Это наиболее сложный шаблон во всей книге и его не так-то просто внедрить в вашу игру.
Используйте его, когда у вас есть много поведений, которые вам необходимо определить, а язык реализации вашей игры не подходит, потому что:
Он слишком низкоуровневый, что делает программирование на нём утомительным, а программы — подверженными ошибкам.
Одна итерация при разработке занимает слишком много времени из-за медленной компиляции или из-за других особенностей инструментария.
Ему доверяется слишком многое.
Если вы хотите гарантировать, что определяемое поведение не сломает игру, вы должны ограничить его от остальной кодовой базы.
Конечно, этот список описывает кучу всего в вашей игре.
Кто же не хочет более быстрой итерации разработки или большей безопасности?
Тем не менее, ничто не даётся даром.
Байт-код медленнее родного кода, так что он не является хорошим выбором для критических к производительности частей вашего движка.
Что следует знать
Есть что-то соблазнительное в создании собственного языка или системы внутри системы.
Здесь я приведу минимальный пример, но в реальном мире эти вещи разрастаются как виноградная лоза.
Для меня, разработка игр соблазнительна в том же смысле.
В обоих случаях я пытаюсь создать виртуальное пространство для других, где можно поиграться и проявить свой творческий потенциал.
Каждый раз, когда я вижу, как кто-то определяет свой собственный маленький язык или скриптовую систему, они говорят: «Не волнуйся, она будет крошечной».
Затем, это неизбежно, они добавляют всё больше и больше небольших возможностей, пока в конце концов это не станет полноценный язык программирования.
За исключением того, что в отличии от некоторых других языков, он вырос в оперативной органическом стиле и обладает архитектурной элегантностью трущоб.
Для примера можете взглянуть на любой язык шаблонов.
Конечно, нет ничего плохого в создании полноценного языка программирования.
Просто убедитесь, что вы делаете это сознательно.
В противном случае будьте очень осторожны, управляя областью ответственности, которую может выразить ваш байт-код.
Держите его на коротком поводке, пока он не сбежал от вас.
Вам понадобится внешний интерфейс
Низкоуровневые инструкции байт-кода великолепны для повышения производительности, но двоичный формат байт-кода — это не то, что ждут от автора пользователи.
Одна из причин, по которым мы перемещаем поведение вовне кода — это то, что мы сможем выразить его на более высоком уровне.
Если уж C++ — это слишком низкий уровень, заставлять пользователей эффективно писать на ассемблере — даже если он спроектирован вами — это не улучшение!
Оспариванием этого утверждения занимается почётная игра RoboWar.
В этой игре игроки пишут небольшие программы управления роботом на языке, очень похожем на ассемблер и с набором инструкций, которые мы будем здесь обсуждать.
Это было моё первое знакомство с ассемблеро-подобным языком.
Как и в шаблоне Интерпретатор «Банды четырёх», здесь предполагается, что вы уже умеете каким-то образом генерировать байт-код.
Как правило, пользователи описывают своё поведение в неком высокоуровневом формате, а инструмент транслирует его в байт-код, понимаемый нашей виртуальной машиной.
Другими словами, у нас есть компилятор.
Я знаю, это звучит страшно.
Поэтому я и упоминаю его здесь.
Если у вас нет ресурсов для построения средств разработки, то байт-код не для вас.
Но, как мы увидим позже, всё может быть не так уж и плохо, как вы подумали.
Вы потеряете свой отладчик
Программирование трудно.
Мы знаем, что мы хотим, чтобы делала машина, но не всегда можем правильно сказать ей об этом — мы пишем с ошибками.
Чтобы помочь их найти и исправить, мы накопили кучу инструментов, которые помогают нам понять, что наш код делает неправильно, и как он должен делать это правильно.
У нас есть отладчики, статические анализаторы, декомпиляторы и прочее, и прочее.
Все эти инструменты предназначены для работы с некоторым существующим языком: либо с машинным кодом, либо с чем-то более высокоуровневым.
Когда вы определяете свой собственную виртуальную машину, вы выкидываете все эти инструменты.
Конечно, вы можете пройтись по коду виртуальной машины в отладчике, но он скажет, что делает сама виртуальная машина, а не тот байт-код, который она интерпретирует.
Он, конечно, не поможет вам отобразить байт-код обратно в ту высокоуровневую форму, из которой он был получен.
Если поведение, что вы определяете, простое, вы можете свести концы с концами и без большинства этих инструментов, помогающих в отладке.
Но с ростом масштабов вашего содержимого, нужно запланировать инвестиции реального времени в возможности, которые помогут пользователям увидеть, что делает их байт-код.
Эти возможности могут не грузиться в вашей игре, но они будут иметь решающее значение в обеспечении того, чтобы ваша игра всё же загрузилась.
Конечно, если вы хотите, что бы ваша игра поддерживала модификации, вы должны будете грузить эти возможности и они будут ещё более важными.
Пример кода
После предыдущих разделов, вы можете быть удивлены, как проста его реализация.
Сперва нам нужно определиться с набором инструкций нашей виртуальной машины.
Перед тем, как мы начнём думать о байт-коде и сопутствующих вещах, давайте подумаем о нём, как об API.
API магии
Если мы определяем заклинания прямо в коде на C++, какое API нам потребуется для этого?
Каковы базовые операции в игровом движке, в терминах которых определяются заклинания?
Большинство заклинаний, в конечном итоге, изменяют одну их характеристик волшебника, так что мы начнём с пары из них:
void setHealth(int wizard, int amount)
;
void setWisdom(int wizard, int amount)
;
void setAgility(int wizard, int amount)
;
Первый параметр определяет волшебника, к которому применяется функция, пусть 0 будет означать игрока, а 1 — его оппонента.
Таким образом, лечебные заклинания могут влиять на нашего волшебника, в то время как повреждающие атаки несут ваше возмездие.
Эти три маленьких метода охватывают удивительно широкий спектр магических эффектов.
Если заклинания будут просто молча влиять на характеристики, с игровой логикой всё будет в порядке, но игра в ЭТО может довести игроков до истерики.
Давайте поправим это недоразумение:
void playSound(int soundId)
;
void spawnParticles(int particleType)
;
Эти методы не влияют на игровой процесс, но они усиливают впечатления от игры.
Мы могли бы добавить больше таких штук, например, дрожание камеры, анимацию и т.д.
, но для начала достаточно и этого.
Набор инструкций для магии
Давайте теперь посмотрим, как мы можем превратить этот программный API в нечто, чем мы сможем управлять из данных.
Давайте начнём с малого, а затем постепенно усложним результат.
Конкретно сейчас, уберём все параметры из этих методов.
Скажем, что методы set___() всегда действуют на нашего волшебника и всегда максимизируют характеристики.
Точно также, визуальные операции всегда проигрывают один жёстко заданный звук и эффект частиц.
Примем также, что заклинание — это просто последовательность инструкций.
Каждая инструкция определяет, какую операцию мы хотим выполнить.
Мы можем перечислить их:
enum Instruction
{
INST_SET_HEALTH = 0x00,
INST_SET_WISDOM = 0x01,
INST_SET_AGILITY = 0x02,
INST_PLAY_SOUND = 0x03,
INST_SPAWN_PARTICLES = 0x04
};
Для кодирования заклинаний в данных, мы просто будем хранить массив значений перечисления.
У нас есть всего несколько различных примитивов, поэтому диапазон значений перечисления легко укладывается в байт.
Это значит, что заклинание будет списком байтов — или, более ёмко, «байт-кодом».
Некоторые виртуальные машины с байт-кодом используют более одного байта для каждой инструкции и могут иметь более сложные правила их декодирования.
Реальный машинный код большинства чипов, вроде x86, значительно более сложный.
Однако однобайтовый код используется в виртуальной машине Java (JVM) и общеязыковой исполняющей среде Microsoft (CLR), которая является основой платформы .NET и это хорошо для нас.
Для выполнения одной инструкции мы смотрим на примитив и вызываем соответствующий метод API:
switch (instruction)
{
case INST_SET_HEALTH:
setHealth(0, 100);
break;
case INST_SET_WISDOM:
setWisdom(0, 100);
break;
case INST_SET_AGILITY:
setAgility(0, 100);
break;
case INST_PLAY_SOUND:
playSound(SOUND_BANG)
;
break;
case INST_SPAWN_PARTICLES:
spawnParticles(PARTICLE_FLAME)
;
break;
}
Таким образом, наш интерпретатор формирует мост между миром кода и миром данных.
Мы можем обернуть всё это в небольшую виртуальную машину, которая выполняет целое заклинание таким образом:
class VM
{
public:
void interpret(char bytecode[], int size)
{
for (int i = 0; i < size; i++)
{
char instruction = bytecode[i];
switch (instruction)
{
// Случаи для каждой инструкции...
}
}
}
};
Наберите этот код и вы напишете свою первую виртуальную машину.
К сожалению, она не очень гибкая.
Мы не можем определить заклинание, действующее на оппонента или понижающее характеристики.
Мы можем проиграть только один звук!
Чтобы получить что-то, напоминающее выразительность настоящего языка программирования, нам нужно научиться получать параметры.
Стековая машина
Чтобы выполнить сложное вложенное выражение, вы начинаете с самых внутренних подвыражений.
Вы их вычисляете и результат поступает наружу в качестве аргументов выражения, содержащего данное, и так продолжается до тех пор, пока всё выражение не будет вычислено.
Шаблон Интерпретатор моделирует это явно в качестве дерева вложенных объектов, но мы то хотим скорости плоского списка инструкций.
Нам всё ещё нужно обеспечить передачу результатов из подвыражения в правильное окружающее выражение.
Но, поскольку наши данные плоские, мы должны будем использовать порядок инструкций для управления этим процессом.
Мы сделаем это также, как это делает процессор: будем использовать стек.
Такая архитектура без изысков названа стековой машиной.
Языки программирования вроде Forth, PostScript и Factor выставляют эту модель непосредственно пользователю.
class VM
{
public:
VM()
: stackSize_(0)
{}
// Другие вещи...
private:
static const int MAX_STACK = 128;
int stackSize_;
int stack_[MAX_STACK];
};
Виртуальная машина поддерживает внутренний стек значений.
В нашем примере единственными видами значений, с которыми работают наши инструкции, являются числа, поэтому мы можем использовать просто массив целых чисел типа int.
Всякий раз, когда порция данных должна пройти от одной инструкции до другой, она проходит через стек.
Как следует из их названий, значения могут заталкиваться и выталкиваться из стека, поэтому давайте добавим соответствующие методы:
class VM
{
private:
void push(int value)
{
// Проверка на переполнение стека.
assert(stackSize_ < MAX_STACK)
;
stack_[stackSize_++] = value;
}
int pop()
{
// Убедимся, что стек не пуст.
assert(stackSize_ > 0);
return stack_[--stackSize_];
}
// Другие вещи...
};
Когда инструкции требуется получить параметры, она выталкивает их из стека вот таким образом:
switch (instruction)
{
case INST_SET_HEALTH:
{
int amount = pop();
int wizard = pop();
setHealth(wizard, amount)
;
break;
}
case INST_SET_WISDOM:
case INST_SET_AGILITY:
// Тоже самое, что и выше...
case INST_PLAY_SOUND:
playSound(pop());
break;
case INST_SPAWN_PARTICLES:
spawnParticles(pop());
break;
}
Чтобы загрузить некоторые значения в стек, нам понадобится ещё одна инструкция: литерал.
Она представляет сырое целочисленное значение.
Но откуда она получает своё значение?
Как нам избежать бесконечного цикла с топтанием на месте?
Хитрость заключается в том, что на самом деле наш поток инструкций является просто последовательностью байт: мы может записать число прямо в потоке инструкций.
Мы определим ещё один тип инструкций для числового литерала:
case INST_LITERAL:
{
// Читаем следующий байт из байт-кода.
int value = bytecode[++i];
push(value)
;
break;
}
Здесь я просто считываю однобайтовое значение, чтобы избежать неудобного кода, требуемого для декодирования многобайтных целых чисел, но в реальной реализации вы захотели бы, чтобы литералы покрывали весь числовой диапазон.
Она читает следующий байт в потоке байт-кода в число и заталкивает его в стек.
Давайте объединим некоторые из этих инструкций вместе и посмотрим, как интерпретатор будет их выполнять, чтобы прочувствовать, как работает стек.
Мы начинаем с пустого стека и интерпретатора, указывающего на первую инструкцию:
Сперва выполняется первая инструкция INST_LITERAL.
Она читает следующий байт из байт-кода (0) и заталкивает его в стек:
Затем выполняется вторая инструкция INST_LITERAL.
Она читает значение 10 и заталкивает его в стек:
Наконец, выполняется инструкция INST_SET_HEALTH.
Она выталкивает 10 и сохраняет его в переменной amount, затем выталкивает 0 и сохраняет его в переменной wizard.
Далее вызывается setHealth() с этими двумя параметрами.
Та-дам!
У нас есть заклинание, устанавливающее нашему волшебнику здоровье в десять единиц.
Теперь у нас достаточно гибкости для определения заклинаний, устанавливающих любому волшебнику такие характеристики, какие мы захотим.
Также мы можем проиграть различные звуки и породить различные частицы.
Однако... это всё ещё больше формат данных.
Мы не можем, например, поднять здоровье волшебника на половину его мудрости.
Наши дизайнеры хотят иметь возможность выражать заклинания через правила, а не только значения.
Поведение = композиция
Если мы думаем о нашей маленькой виртуальной машине, как о языке программирования, всё что он поддерживает — это пара встроенных функций и константные параметры для них.
Чтобы байт-код стал больше похож на поведение, нужно добавить то, что мы упустили — композицию.
Наши дизайнеры должны иметь возможность создавать выражения, комбинирующие различные значения интересными способами.
В качестве простого примера, они хотят заклинания, изменяющие характеристику на определённую величину вместо установки характеристики в определённую величину.
Для этого требуется учитывать текущее значение характеристики.
У нас есть инструкции для записи характеристик, нам просто нужно добавить ещё пару для их чтения:
case INST_GET_HEALTH:
{
int wizard = pop();
push(getHealth(wizard))
;
break;
}
case INST_GET_WISDOM:
case INST_GET_AGILITY:
// Ну, вы поняли идею...
Как вы можете заметить, они работают со стеком в обоих направлениях.
Они выталкивают параметр для определения того, для какого волшебника запрашивается характеристика, затем они смотрят значение характеристики и заталкивают его обратно в стек.
Это позволяет нам писать заклинания, копирующие статистику.
Мы можем написать заклинание, устанавливающее ловкость волшебника в значение его мудрости или странные чары, устанавливающие здоровье волшебника таким же, как у оппонента.
Уже лучше, но всё равно есть ограничения.
Далее нам нужна арифметика.
Пора научить нашу маленькую виртуальную машину складывать 1 и 1. Добавим ещё несколько инструкций.
К этому моменту, вы, вероятно, уже научились это делать и можете предположить, как они выглядят.
Я просто покажу, что нужно добавить:
case INST_ADD:
{
int b = pop();
int a = pop();
push(a + b)
;
break;
}
Как и другие наши инструкции, она выталкивает пару значений, проводит с ними небольшую работу и заталкивает результат обратно.
До сих пор каждая новая инструкция давала нам постепенное улучшение выразительности, но с этой мы только что совершили большой прыжок.
Это не очевидно, но теперь мы можем обрабатывать любые виды сложных, глубоко вложенных арифметических выражений.
Давайте рассмотрим несколько более сложный пример.
Скажем, мы хотим заклинание, увеличивающее здоровье на среднее между ловкостью и мудростью.
В коде это будет выглядеть так:
setHealth(0, getHealth(0) +
(getAgility(0) + getWisdom(0)) / 2);
Вы можете подумать, что нам нужны инструкции для обработки явной группировки, которую дают скобки, но стек её уже неявно поддерживает.
Вот как мы могли бы вычислить это вручную:
Получить текущее здоровье нашего волшебника и запомнить его.
Получить текущее ловкость нашего волшебника и запомнить её.
Сделать тоже самое с его мудростью.
Получить два последних значения, сложить их и запомнить результат.
Разделить его на два и запомнить результат.
Вспомнить здоровье волшебника и добавить его к результату.
Взять результат и установить здоровье волшебника в это значение.
Видите все эти «запомнить» и «вспомнить»? «Запомнить» соответствует заталкиванию в стек, а «вспомнить» — выталкиванию из стека.
Это означает, что мы довольно легко можем перевести этот алгоритм в байт-код.
Например, первой строкой мы получаем текущее здоровье волшебника:
LITERAL 0
GET_HEALTH
Этот кусочек байт-кода заталкивает здоровье нашего волшебника в стек.
Если мы механически переведём каждую строчку, как эту, в конце концов у нас будет кусок байт-кода, вычисляющий оригинальное выражение.
Чтобы дать вам прочувствовать, как составляются инструкции, я ниже сделал это.
Чтобы посмотреть, как изменяется стек с течением времени, мы вычислим пример, в котором текущие характеристики волшебника таковы: здоровье — 45 единиц, ловкость — 7 единиц и мудрость — 11 единиц.
Рядом с каждой инструкцией показано, как выглядит стек после её выполнения, а также расположен комментарий, объясняющий смысл инструкции.
LITERAL 0 [0] # Индекс волшебника
LITERAL 0 [0, 0] # Индекс волшебника
GET_HEALTH [0, 45] # getHealth()
LITERAL 0 [0, 45, 0] # Индекс волшебника
GET_AGILITY [0, 45, 7] # getAgility()
LITERAL 0 [0, 45, 7, 0] # Индекс волшебника
GET_WISDOM [0, 45, 7, 11] # getWisdom()
ADD [0, 45, 18] # Складывает ловкость и мудрость
LITERAL 2 [0, 45, 18, 2] # Делитель
DIVIDE [0, 45, 9] # Среднее между ловкостью и мудростью
ADD [0, 54] # Добавляем среднее к текущему здоровью
SET_HEALTH [] # Устанавливаем здоровье в результат
Если вы посмотрите на стек на каждом шаге, вы сможете увидеть, как данные протекают через него, словно по волшебству.
Мы затолкнули 0 в качестве индекса волшебника в самом начале и он просто висит в нижней части стека до тех пор, пока он не понадобился в последней инструкции SET_HEALTH.
Может быть мой порог для «магии» здесь слишком низкий.
Виртуальная машина
Я мог бы продолжать двигаться, добавляя всё больше и больше инструкций, но наступило подходящее время для остановки.
Сейчас у нас есть небольшая славная виртуальная машина, которая позволяет нам определять довольно открытое поведение, используя простой, компактный формат данных.
Хотя слова «байт-код» и «виртуальная машина» звучат устрашающе, вы можете увидеть, что часто они также просты, как и стек, цикл и выражение switch.
Помните, что нашей первоначальной целью было иметь поведение, красиво отгороженное в песочнице?
Теперь, когда вы увидели, как именно реализуется виртуальная машина, стало очевидно, что мы достигли цели.
Байт-код не может сделать ничего вредоносного или обратиться к странным частям игрового движка, поскольку мы определили только несколько инструкций, которые только слегка затрагивают оставшуюся часть игры.
Мы контролируем, сколько памяти он использует, насколько большой стек мы создаём и мы проявляем осторожность, чтобы быть уверенным, что переполнения не будет.
Мы даже можем контролировать, насколько долго он используется.
В нашей инструкции организации цикла мы можем отследить, как долго он работает и вырулить из положения, если превышен некоторый лимит.
Контроль времени исполнения не так необходим в нашем примере, поскольку у нас нет инструкций для организации циклов.
Мы могли бы ограничить время выполнения просто ограничив общий размер байт-кода.
Также это означает, что наш байт-код не является Тьюринг-полным.
Осталась только одна нерешённая проблема: непосредственное создание байт-кода.
До сих пор мы брали кусочки псевдокода и компилировали их в байт-код вручную.
Это не будет работать на практике, если только у вас есть куча свободного времени.
Инструменты для колдовства
Одной из наших первоначальных целей было иметь высокоуровневый способ задания авторского поведения, но мы пошли дальше и создали нечто более низкоуровневое, чем C++. Решение обладает производительностью и безопасностью, как мы и хотели, но оно абсолютно недружественно к дизайнеру.
Чтобы заполнить этот пробел, нам нужно несколько инструментов.
Нам нужна программа, позволяющая пользователям определять высокоуровневое поведение заклинания, а затем генерирующая из него соответствующий низкоуровневый байт-код стековой машины.
Это звучит даже сложнее, чем создание виртуальной машины.
Многие программисты прошли курс создания компиляторов в колледже и не почерпнули из него ничего, кроме посттравматического стрессового расстройства, вызванного книгой с драконом на обложке или словами «lex» и «yacc».
Я, конечно же, ссылаюсь на классическую книгу «Компиляторы: принципы, технологии и инструменты».
По правде говоря, компиляция текстовых языков не так уж сложная задача, хотя эта тема слишком объёмная, чтобы втиснуть её сюда.
Однако, вы не будете этого делать.
Когда я сказал, что нам нужен инструмент — я не имел ввиду, что это обязательно должен быть компилятор, входной формат которого — текстовый файл.
Напротив, я призываю вас подумать о построении графического интерфейса, позволяющего пользователям определять собственное поведение, особенно, если люди, использующие его не являются технарями.
Написание текста, свободного от синтаксических ошибок — сложная задача для людей, которые не потратили годы для привыкания к ругани компилятора.
Вместо этого вы можете построить приложение, которое позволит пользователям «писать скрипт» путём перетаскивания прямоугольничков, или выбором варианта в выпадающем меню, или чем-нибудь ещё, что имеет смысл для того вида поведения, которое вы хотите создать.
Скриптовая система, которую я написал для игры «Henry Hatsworth in the Puzzling Adventure» («Генри Хатсворт в головоломном приключении») работает подобным образом.
Хорошей новостью является то, что ваш интерфейс может сделать невозможным для пользователя создать «неверную» программу.
Вместо рвотных сообщений об ошибках, вы просто можете заблаговременно отключать кнопки или предоставлять значения по умолчанию для того, что бы та вещь, которую пользователи создали, была верной всё время.
Я хотел бы подчеркнуть, как важна обработка ошибок.
Как программисты, мы склонны рассматривать человеческие ошибки как постыдный изъян личности, который мы стремимся в себе уничтожить.
Для того же, чтобы сделать систему, приносящую пользователям наслаждение, вы должны принять их человечность, включая их подверженность ошибкам.
Ошибки — вот что делают люди, и это фундаментальная часть творческого процесса.
Их изящная обработка, с возможностями вроде отмены, поможет вашим пользователям лучше сосредоточиться на творчестве и создать лучшую работу.
Это избавляет нас от проектирования грамматики и написания парсера для маленького языка.
Однако, я знаю, что некоторые из вас найдут программирование с помощью визуального интерфейса неприятным.
Что ж, в таком случае, у меня для вас нет хороших новостей.
В конечном счёте, этот шаблон о выражении поведения удобным для пользователя, высокоуровневым способом.
Вы должны выработать опыт взаимодействия с пользователем.
Для эффективного выполнения поведения вы должны преобразовать его в низкоуровневую форму.
Это сложная работа, но, если вы справитесь с этой задачей, она может окупиться.
Проектные решения
Я попытался сохранить эту главу такой простой, как только возможно, но сейчас мы действительно будем создавать язык программирования.
Это довольно неограниченное по времени проектирование.
Его исследование может доставлять тонну удовольствия, так что убедитесь, что вы не забудете завершить свою игру.
Так как это самая продолжительная глава в этой книге, кажется, я провалил эту задачу.
Как инструкции взаимодействуют со стеком?
Виртуальные машины на основе байт-кода делятся на два основных типа: стековые и регистровые.
В стековых виртуальных машинах инструкции всегда работают с вершиной стека, как в наших примерах кода.
Например, инструкция INST_ADD выталкивает два значения, складывает их и заталкивает результат.
Регистровые виртуальные машины всё ещё имеют стек.
Разница между ними в том, что инструкции могут считывать свои сходные данные из его более глубоких слоёв.
Инструкция INST_ADD, вместо выталкивания своих операндов имеет два индекса, сохранённые в байт-коде, которые определяют, откуда из стека нужно прочитать операнды.
Стековая виртуальная машина:
Инструкции меньше.
Поскольку каждая инструкция неявно ищет свои аргументы на вершине стека, вам не нужно хранить никаких данных для этого.
Это означает, что каждая инструкция может быть очень маленькой, обычно один байт.
Генерация кода проще.
Когда вы дойдёте до написания компилятора или инструмента, выводящего байт-код, вы найдёте, что проще генерировать байт-код для стековой машины.
Поскольку каждая инструкция неявно работает с вершиной стека, вам просто нужно выводить инструкции в правильном порядке для передачи параметров между ними.
Вы имеете множество инструкций.
Каждая инструкция видит только самую вершину стека.
Это означает, что для генерирования кода для чего-нибудь, вроде a = b + c, вам необходимо разделить инструкции на перемещение b и c на вершину стека, выполнение операции и перемещения результата в a.
Регистровые виртуальные машины:
Инструкции больше.
Поскольку каждая инструкция требует аргументов для смещения в стеке, одна инструкция требует больше бит для записи.
Например, инструкции в Lua — вероятно, самой известной регистровой виртуальной машине — занимают полные 32 бита.
Они используют 6 бит для типа инструкции и остальные для аргументов.
Lua не определяет свой формат байт-кода и он меняется от версии к версии.
То, что я описываю здесь, верно для версии Lua 5.1. Для абсолютного удивительно глубокого погружения во внутренности Lua, рекомендую прочесть это.
У вас меньше инструкций.
Поскольку каждая инструкция может делать больше работы, вам не нужны многие из них.
Некоторые скажут, что вы получаете выигрыш в производительности, поскольку вам не нужно будет так часто перетасовывать значения в стеке.
Так какую же машину делать?
Моя рекомендация состоит в придерживании варианта со стековой виртуальной машиной.
Она проще в реализации и код для неё генерировать гораздо проще.
Регистровые виртуальные машины получили репутацию, как более быстрые после того, как Lua был переписан в этом стиле, но это глубже зависит от ваших инструкций и множества других подробностей вашей виртуальной машины.
Какие инструкции у вас есть?
Ваш набор инструкций определяет границы того, что может или не может быть выражено байт-код, а также имеет большое влияние на производительность вашей виртуальной машины.
Вот длинный список различных видов инструкций, которые вы можете захотеть реализовать:
Внешние примитивы.
Это такие, которые выходят за пределы виртуальной машины в остальной игровой движок и делают работу, которую видят пользователи.
Они контролируют, какой вид реального поведения может быть выражен в байт-коде.
Без них ваша виртуальная машина не делает ничего, кроме пустого сжигания процессорных циклов.
Внутренние примитивы.
Эти управляют значениями изнутри виртуальной машины — это вещи, вроде литералов, арифметических операторов, операторов сравнения и инструкций манипуляции стеком.
Управление потоком выполнения.
Наш пример не покрывает эти инструкции, но когда вы хотите поведение, которое выполняет инструкции условию или в цикле более одного раза, вам нужно управление потоком выполнения.
На низкоуровневом языке байт-кода они удивительно просты: переходы.
В нашей инструкции цикла мы имеем индекс, отслеживающий, где мы побывали в байт-коде.
Все инструкции перехода изменяют эту переменную и, таким образом, и текущее место выполнения.
Другими словами, это goto.
С его помощью вы можете построить все виды высокоуровневых конструкций, управляющих потоком выполнения.
Абстракция.
Если ваши пользователи начинают определять множество вещей в данных, в конечном итоге они захотят повторно использовать куски байт-кода, вместо его копирования и вставки.
Вы можете захотеть иметь что-то вроде вызываемых процедур.
В простейшем случае это не намного сложнее перехода.
Единственное отличие в том, что виртуальная машина поддерживает второй стек возвратов.
Когда мы выполняем инструкцию «вызова», она заталкивает текущий индекс инструкции в стек возвратов, а затем переходит на вызванный байт-код.
Когда происходит «возврат», виртуальная машина выталкивает индекс из стека возвратов и переходит обратно по этому индексу.
Как представляются значения?
Наша учебная виртуальная машина работает только с одним видом значений — целыми числами.
Это довольно просто: ведь стек — это просто стек целых чисел.
Более продвинутые виртуальные машины поддерживают различные типы данных: строки, объекты, списки и т.д.
Вы должны будете определить, как они будут храниться внутри машины.
Единый тип данных:
Простой.
Вы не должны беспокоиться о метках, преобразованиях или проверках типа.
Вы не можете работать с различными типами данных.
Очевидный недостаток.
Впихивать различные типы данных в единое представление — подумайте о сохранении чисел как строк — сущий кошмар.
Вариант с метками:
Это наиболее распространённое представление для динамически типизируемых языков.
Каждое значение состоит из двух частей.
Первая часть называет меткой типа — перечисление — которое определяет, какой тип данных хранится в значении.
Оставшаяся часть битов интерпретируется согласно этому типу, например:
enum ValueType
{
TYPE_INT,
TYPE_DOUBLE,
TYPE_STRING
};
struct Value
{
ValueType type;
union
{
int intValue;
double doubleValue;
char* stringValue;
};
};
Значения знают свой собственный тип.
Что хорошо в этом представлении — вы можете проверить тип значения во время выполнения.
Это особенно важно для динамической диспетчеризации и гарантирует, что вы не попытаетесь выполнить не поддерживаемую типом операцию.
Он занимает больше памяти.
Каждое значение должно хранить несколько дополнительных бит для идентификации своего типа.
В некоторых низкоуровневых виртуальных машинах несколько бит тут и там накапливаются очень быстро.
Объединение без меток:
В этой форме, как и в предыдущей, используется объединение union, но не хранится метка типа.
У вас есть небольшой кусочек битов, которые могут представлять более одного типа и на вас лежит забота их правильной интерпретации.
Так представляют в памяти вещи статически типизируемые языки.
Поскольку система типов во время компиляции гарантирует, что вы не будете неправильно интерпретировать значения, их не нужно проверять во время выполнения.
Также таким образом хранят значения безтиповые языки, например, ассемблер и Forth.
Эти языки оставляют за пользователем контроль того, что он не напишет код, который неправильно проинтерпретирует тип значения.
Это не для слабонервных!
Оно компактное.
Вы не можете хранить значение более эффективно хранения просто его битов.
Оно быстрое.
Отсутствие меток типов подразумевает отсутствие траты циклов на проверки во время выполнения.
Ото одна из причин, почему статически типизируемые языки обычно быстрее динамически типизируемых.
Оно небезопасное.
Конечно, всему есть своя цена.
Плохой кусок байт-кода может вызвать неправильную интерпретацию значения и, например, начать рассматривать число в качестве указателя или наоборот, что может нарушить защищённость вашей игры или вызвать её падение.
Если ваш байт-код компилируется из статически типизируемого языка, вы можете подумать, что он безопасен, поскольку компилятор не будет генерировать небезопасный байт-код.
Это может быть правдой, однако не забывайте, что недобросовестный пользователь может вручную написать злобный байт-код в обход вашего компилятора.
Именно поэтому, например, виртуальная машина Java всё же проводит проверку байт-кода при загрузке программы.
Интерфейс:
Объектно-ориентированное решение для значения, которое может быть одним из нескольких типов, через полиморфизм.
Интерфейс предоставляет виртуальные методы для различных проверок и преобразований типа, как здесь:
class Value
{
public:
virtual ~Value() {}
virtual ValueType type() = 0;
virtual int asInt() {
// Может быть вызван только для целых чисел
assert(false)
;
return 0;
}
// Другие методы для преобразований...
};
Затем вы создаёте конкретные классы для каждого типа данных, например:
class IntValue : public Value
{
public:
IntValue(int value)
: value_(value)
{}
virtual ValueType type() { return TYPE_INT; }
virtual int asInt() { return value_; }
private:
int value_;
};
Он расширяем.
Вы можете определять новые типы значений за пределами ядра виртуальной машины до тех пор, пока они реализуют базовый интерфейс.
Он объектно-ориентирован.
Если вы придерживаетесь принципов ООП, этот метод реализует «правильный» способ использования полиморфной диспетчеризации для типо-зависимого поведения вместо переключения по метке типа.
Он многословен.
Вы должны определять отдельный класс со всем связанным с этим церемониальным словоблудием для каждого типа данных.
Обратите внимание, что в прошлых примерах мы показали полное определение всех типов значений.
Здесь же мы рассмотрели всего один тип!
Он неэффективен.
Для применения полиморфизма вы должны пройти по указателю, что означает, что даже крошечные значения вроде булевых и чисел нужно оборачивать в объекты и размещать их в куче.
Каждый раз, как вы запрашиваете значение, вы вызываете виртуальный метод.
Где-то вроде ядра виртуальной машины небольшие потери в производительности, как здесь, нарастают, как снежный ком.
По сути, это решение страдает теми же самыми проблемами, которые побудили нас отказаться от шаблона Интерпретатор, за исключением того, что теперь проблемы связаны со значениями, а не с кодом.
Моя рекомендация: если вы можете придерживаться одного типа данных, делайте это.
Если нет, используйте объединение с метками.
Практически тоже самое делает каждый языковой интерпретатор в мире.
Как генерировать байт-код?
Я отложил самый важный вопрос напоследок.
Я провёл вас через код чтения и интерпретации байт-кода, но это не поможет вам написать что-нибудь, что его создаст.
Типичным решением будет написание компилятора, но это не единственный вариант.
Если вы определяете текстовый язык:
Вы должны определить синтаксис.
Как любители, так и профессиональные проектировщики языка категорически недооценивают, насколько трудно это сделать.
Определить грамматику, с которой легко справится парсер.
Грамматику, с которой легко и приятно работать пользователям — трудно.
Проектирование синтаксиса — это проектирование пользовательского интерфейса, и этот процесс не становится легче от ограничения пользовательского интерфейса строкой символов.
Вы должны реализовать парсер.
Несмотря на свою репутацию, эта часть довольно лёгкая.
Либо используем генератор парсеров, вроде ANTLR или Bison, или — как это делаю я — пишем небольшой рекурсивный спуск и всё готово.
Вы должны обрабатывать синтаксические ошибки.
Это одна из наиболее важных и наиболее трудных частей процесса.
Когда пользователи совершают синтаксические и семантические ошибки — а они будут, постоянно — вашей задачей становится увести их обратно на правильный путь.
Давать полезную информацию не так-то просто, когда всё что вы знаете, так это то, что ваш парсер наткнулся на какой-то неожиданный символ пунктуации.
Это, скорее всего, отпугнёт не технических пользователей.
Мы, программисты, любим текстовые файлы.
В сочетании с мощностью инструментов командной строки, мы думаем о них, как о вычислительных блоках LEGO: простые, но легко объединяемые миллионом разных способов.
Большинство не-программистов думают о текстовых файлах не так.
Для них, это как заполнение налоговой декларации для роботизированного аудитора, который кричит на них, если они забудут точку с запятой.
Если вы определите графический инструмент создания:
Вы должны реализовать пользовательский интерфейс.
Кнопки, нажатия, перетаскивания и прочие подобные вещи.
Некоторых передёргивает только при одной мысли об этом, но лично я его люблю.
Если вы идёте по этому пути, важно рассматривать пользовательский интерфейс как основную часть вашей работы, а не как неприятную задачу, которую необходимо как можно быстрее закончить.
Каждая небольшая дополнительная работа, которую вы проделаете здесь, сделает ваш инструмент проще и приятнее в использовании, что непосредственно влияет на качество наполнения вашей игры.
Если вы посмотрите на многие любимые игры, часто вы обнаружите, что их секрет в потрясающих инструментах для создания содержимого.
Вы будете иметь меньше ошибочных ситуаций.
Поскольку пользователь строит поведение интерактивно, шаг за шагом, ваше приложение может ограждать их от ошибок по мере их возникновения.
С текстовыми языками, инструмент не видит пользовательского содержимого до тех пор, пока он не бросит файл на него.
Это делает более трудным предотвращение и обработку ошибок.
Переносимость затруднена.
Текстовые компиляторы хороши тем, что текстовые файлы универсальны.
Простой компилятор просто читает один файл и пишет в другой.
Портирование между операционными системами тривиально.
За исключением символов окончания строки.
Эх...
Когда вы создаёте пользовательский интерфейс, вы можете выбрать, какой фреймворк использовать, а многие из них специфичны для какой-то одной ОС.
Конечно, существуют кросс-платформенные инструменты разработки пользовательского интерфейса, но зачастую эта вездесущность достигается за счёт одинакового внешнего вида: и они выглядят одинаково чужеродно на всех платформах.
Смотрите также
Этот шаблон являет близким родственником шаблона Интерпретатор «Банды четырёх».
Оба дают нам способ выразить сборное поведение в терминах данных.
В конечном итоге, часто вы будете использовать оба шаблона.
Инструмент, используемый вами для генерирования байт-кода, внутри будет содержать дерево объектов, представляющих код.
Это именно то, о чём говорит шаблон Интерпретатор.
В процессе компиляции в байт-код, вы рекурсивно обойдёте дерево также, как вы интерпретировали его с шаблоном Интерпретатор.
Единственная разница лишь в том, что вместо немедленного выполнения примитивных кусочков поведения, вы будете записывать инструкции байт-кода, которые сделают это позже.
Язык программирования Lua — это наиболее широко используемый скриптовый язык в играх.
Внутри он реализован как очень компактная регистровая виртуальная машина байт-кодов.
Kismet — это графический инструмент скриптования, встроенный в UnrealEd, редактор движка Unreal engine.
Мой собственный маленький скриптовый язык, Wren — простой стековый интерпретатор байт-кодов.
Переведено на Нотабеноиде
http://notabenoid.org/book/51192/215222
Переводчики: Mingun, zwyagel
Настройки
Готово:
100.00%
КП = 1.0