游戏编程模式笔记——第十一章 字节码

发表于   |   分类于   |  

通过将行为编码成虚拟机指令，而使其具备数据的灵活性。

动机

任何的对游戏进行更新修改，都需要进行重新编译，这会浪费更多的时间，同时如果要支持mod，那么就必须要开放源码给玩家，同时确保玩家的代码不会出错，这是很糟糕的设计。
我们需要把类似法术从游戏核心转移到安全沙箱中。我们要让它们易于修改，易于重新加载并且在物理上与游戏的可执行文件相分离。

解析器模式

参考GOF设计模式一书中的解释器模式。解析器模式会带来一些令人糟心的副作用：

  • 从磁盘加载它需要进行实例化并串联成堆的小对象。
  • 这些对象和他们之间的指针占用大量内存。在32位机上，及时不考虑内存对齐，这个小小的表达式也要占用68字节。
  • 从每个指针遍历子表达式都会大量消耗数据缓存，而虚函数调用也会对指令缓存造成很大压力。
    所以就一个字：慢！它太慢了，并且占用了大量的内存。

虚拟机器码

游戏运行时计算机并不会去遍历C++语法结构树，而是执行我们再编译期编译成的机器码。为什么要用机器码？

  • 高密度。它是坚实连续的二进制数据块，不浪费任何一个字节。
  • 线性。 指令被打包在一起顺序执行。不会在内存中跳跃访问（除非你确实写了控制流）。
  • 底层。每个单独的指令仅仅完成一个小动作，各种有趣行为都是这些小动作的组合。
  • 迅速。以上几点让机器码急行如风（当然还得算上机器码由硬件实现这一点）。

为用户提供游戏执行的机器码，会当来很多安全问题，我们只能在机器码的效率和解释器模式的安全性之间的这种考虑。
我们不去加载真正的机器码，而去定义自己的虚拟机器码，我们在游戏中实现一个执行它们的模拟器。这些虚拟机器码与机器码相似（高密度、线性、相对底层）同时它完全收到游戏本身的安全管理。
我们将这个小模拟器称为虚拟机（VM），这个虚拟机所执行的语义上的“二进制机器码”称为字节码。它具备在数据内定义对象的灵活性和易用性，同时也比解析器这种高级呈现方式更高效。

字节码模式

指令集定义了一套可以执行的底层操作。一系列指令被编码为字节序列。虚拟机逐条执行指令栈上这些指令。通过组合指令，即可完成很多高级行为。

使用情境

仅当你的游戏中需要定义大量行为，而且实现游戏的语言出现下列情况时才应该使用:

  • 编程语言太底层了，编写起来繁琐易错
  • 因编译时间太长或工具问题，导致迭代缓慢。
  • 它的安全性太依赖编码者。你想确保定义的行为不会让程序崩溃，就得把他们从代码库转移至安全沙箱中。

使用须知

这里只做个最小化的示例，在实际项目中，麻烦可多多了。

你需要个前端界面

就像GOF的解析器模式一样，它假定你能够以某种方式生成字节码。通常用户会在更高级的层次上编辑，一个工具负责将它转换成虚拟机能够理解的字节码。这个工具的名字就是编译器。

你会想念调试器的

我们有调试器、静态分析器、反编译工具等来让我们找出代码错在哪里，如何去改正。当你定义自己的字节码虚拟机时，你就没法使用这些工具了。
如果你定义的行为很简单，那么你可以再调试时勉强回避掉各种繁琐的辅助工具。但是随着内容规模的增长，你得规划好如何让用户能实时看到他们的字节码所带来的效果。这些功能可能不会随着游戏发布，但是它们是你游戏可发布的绝对保障。

示例

法术API

绝大多数法术会改变巫师身上的某个状态，我们就从一组状态开始：

1
2
3
void setHealth(int wizard, int amount);
void setWisdom(int wizard, int amount);
void setAgility(int wizard, int amount);

然而如果法术只是闷声改变状态，那么这虽然在游戏逻辑上不会有问题，但是玩这样的游戏会让玩家无聊到哭的，我们来做写调整：

1
2
void playSound(int soundId);
void spawnParticles(int particleType);

法术指令集

现在让我们看看如何将这些程序API转换成数据可控的形式。让我们由简入繁来完成整件事。首先拿掉这些函数中所有的参数。假设所有的“set— ()”函数都会影响玩家的法师并强化其对应属性。类似的FX系列操作会播放一个硬编码的音效或者粒子特效。
在这个前提之下，法术就是一系列的指令。每个指令定义一个你想要执行的操作。我们可以枚举它们：

1
2
3
4
5
6
7
8
enum Instruction
{
    INST_SET_HEALTH = 0x00,
    INST_SET_WISDOM = 0x01,
    INST_SET_AGILITY = 0x02,
    INST_PLAY_SOUND = 0x03,
    INST_SPAWN_PARTICLES = 0x04
};

为了将法术编码成数据，我们在数据中存储一系列枚举值。我们只有几种基本操作，所以枚举值长度取一个字节足矣，这意味着法术代码都是一个字节列表——这就是所谓的字节码。
执行一条指令时，我们首先找到对应的基础属性，然后调用正确的API：

1
2
3
4
5
6
7
8
9
10
switch(instruction)
{
    case INST_SET_HEALTH:
        setHealth(0,100);
        break;
    case INST_SET_WISDOM:
        setWisdom(0, 100);
        break;
    //...
}

借此，我们的解释器在代码和数据这两个世界间搭建了一座桥梁。我们可以将它封装进一个小型的虚拟机中，像下面这样来释放一个完整的法术：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class VM
{
public:
    void interpret(char bytecode[], int size)
    {
        for(int i = 0; i < size; i++)
        {
            char instruction = bytecode[i];
            switch(instruction)
            {
                // Cases for each instruction...
            }
        }
    }
};

把这段代码写进去，你就完成你的第一个虚拟机。可惜它还不够灵活。我们没办法去定义一个能够伤害到对手或者削弱某个属性的法术，而只是播个音效罢了。
为了多一点真正语言的感觉，我们需要在这里引入参数。

栈机

要执行一个复杂的嵌套表达式，你得从最内层的子表达式开始。内层表达式的结果在计算完后，将被作为包含它的外层表达式的参数传给外层表达式。但由于我们的数据是被展平的，因此我们得通过指令的顺序去控制。我们会采用与你的CPU相同的方式——堆栈。

1
2
3
4
5
6
7
8
9
10
11
class VM
{
public:
    VM() : stackSize_(0) {}
    
    //Other stuff...
private:
    static const int MAX_STACK = 128;
    int stackSize_;
    int stack_[MAX_STACK];
};

这个虚拟机内部包含了一个值堆栈。在我们的例子中，与指令相关的唯一数据类型是数字，所以我们可以使用一个int型数组。当一段数据要求指令逐一执行下去，实际上就是在遍历堆栈。
顾名思义，数值可以往这个堆栈中入栈或出栈。因此，让我们为它添加出入栈方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class VM
{
private:
    void push(int value)
    {
        // Check for stack overflow.
        assert(stackSize_ < MAX_STACK);
        stack_[stackSize_++] = value;
    }
    int pop()
    {
        // Make sure the stack isn't empty.
        assert(stackSize_ > 0);
        return stack_[--stackSize_];
    }
    // Other stuff...
};

当某个指令需要输入参数时，它会按照下面的方式从堆栈中弹出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
switch(instruction)
{
   case INST_SET_HEALTH:
   {
        int amount = pop();
        int wizard = pop();
        setHealth(wizard, amount);
        break;
   }
    // Similar for SET_WISDOM and SET_AGILITY...
   case INST_PLAY_SOUND:
   {
        playSound(pop());
        break;
   }
   case INST_SPAWN_PARTICLES:
   {
        spawnParticles(pop());
        break;
   }
}

为了向堆栈中添加一些数值，我们需要一个新的指令：字面值。它表示一个字面上的整数数值。但是它又从哪里获得这个值呢？这里究竟该如何避免死循环呢？
这个小技巧就是利用指令流是字节序列的特性——我们可以将数值直接塞进字节数值。我们用如下方式定义一个字面数值的指令类型：

1
2
3
4
5
6
7
8
9
10
11
switch(instruction)
{
    //Other instrution cases...
    case INST_LITERAL:
   {
        // Read the next byte from the bytecode.
        int value = bytecode[++i];
        push(value);
        break;
   }
}

它读取了字节码流中的下一个字节，将它作为一个数值写入堆栈。
| 0x03 | 123 |
|————-|—–:|
| 字面数值| 数值|

这感觉更像是数据结构。我们没法做到诸如将巫师的生命提高其法力值一半的操作。我们的设计师想要指定法术的计算规则，而不仅是数值。

组合就能得到行为

如果将我们的虚拟机看作是一种编程语言，它目前所支持的仅是些内置函数，以及它们的常量参数。为了让字节码更接近行为，我们得进行组合。
我们的设计师想要创建一些表达式，能够将不同的值通过有趣的方式组合起来。举个简单的例子，他们想让一个法术对某种属性造成一个相对量的变化，而不是改变到一个绝对的量。
那就需要考虑状态的当前值。我们已经有了写入状态的指令，但还得加上些读取它们的指令：

1
2
3
4
5
6
7
8
9
case INST_GET_HEALTH:
{
    int wizard = pop();
    push(getHealth(wizard));
    break;
}
case INST_GET_WISDOM:
case INST_GET_AGILITY:
    // You get the idea...

如你所见，它对堆栈做了双向操作。它首先出栈一个参数，来确定要获取哪个巫师的状态，然后找到这个状态值并入栈。
这使得我们能够编写任意拷贝状态值的法术。我们能够创造一个巫术将巫师的敏捷值设定为其智力值，甚至是神奇地复制对手的生命值。
比之前好了一点儿，但还差得多。接下来我们需要算术。是时候让我们的虚拟机学1+1了。我们得添加些新的指令。下面是加法：

1
2
3
4
5
6
7
case INST_ADD:
{
    int b = pop();
    int a = pop();
    push(a + b);
    break;
}

和其他指令一样，它出栈一些数值，做一些处理，然后将结果入栈。到现在为止，每个指令都提高了一点儿我们对表达式的支持，但这是个很大的跨越。它看起来不起眼，但我们能够处理各种复杂的、深层嵌套的算数表达式了。

一个虚拟机

像它现在这样，我们有了一个不错的小虚拟机，好让我们能使用简单又可压缩的数据根式来定义相对可扩展的指令。虽然“字节码”和“虚拟机”听起来有点吓人，但你会发现它们往往简单到一个堆栈、一个循环或是一个switch语句。
还记得我们最初的目标是让字节码能够得到很好的沙箱化吗？现在你看过了虚拟机的整个实现过程，很明显我们已经做到了。字节码没法深入引擎的各个部分做有恶意的事情，因为我们只定义了少量访问引擎内部的指令。
我们通过控制堆栈尺寸来限制它的可用内存，我们要当心以免内存溢出。我们甚至可以限制它的执行时间。在指令循环中，我们可以记录它已经运转了多久，在超出某个时间限制时，取消其执行。
只剩下一个问题了：真正去创建字节码。眼下我们将一段伪代码编译成了字节码。除非你真的很闲，否则这在实践中根本行不通。

语法转换工具

我们的一个最初目标是在较高的层次上编写行为，但是我们已经做了些比C++还底层的东西。它能兼顾我们需要的运行时性能和安全性，但是彻底缺乏对设计师友好的可用性。
为填补这个缺陷，需要制作些工具。我们需要一个程序，让用户在高层次上定义法术的行为，并能够生成对应的低层次栈机字节码。
这听起来比创建一个虚拟机还难。很多程序员在大学时被塞进一门编译器课程中，其所得只有课本封面上那条龙或者”lex”和”yacc”等词引发的创伤后应激障碍症。（没错这里黑的就是《编译器：原则、技术和工具》）
我指的是我们需要一个工具，并不一定得是个能编译输入文本的编译器。
恰恰相反，我希望你考虑做一个图形界面来让用户定义行为，特别面向那些不太擅长技术的人。对于一个不熟悉编译器的各种错误以及如何修复的人来说，书写语法正确的问题本太难了。
反之，你可以创建一个应用，让用户通过点击和拖拽一些小方块、点选菜单或者其他对创建行为有意义的脚本化工作。
这么做的好处是你的UI让用户几乎难以创建“非法的”程序。你可以前瞻性得禁用按钮或者提供默认值来保证他们创建的东西在任何时候都是合法的程序。你可以通过对按钮进行禁用、提供默认值来确保用户所创建出来的东西在游戏中总是合法的，而不是抛出一大堆错误信息。
最终这个模式还是关于如何以用户友好的、以高层次可编辑的方式来表达行为。你得去精心营造用户体验。为了获得高执行效率，你又得将它翻译成低级形式。这就是你真正要做的，如果你接受这个挑战，那么它会给你回报的。

设计决策

指令如何访问堆栈

字节码虚拟机有两种大风格：基于栈和基于寄存器。在基于栈的虚拟机中，指令总是操作栈顶，正如我们的实例代码一样。
基于寄存器的虚拟机也有一个栈顶。唯一的区别是指令可以从栈的更深层次中读取输入。不像“INST_ADD”那样总是出栈操作数，它在字节码中存储两个索引来表示应该从堆栈的哪个位置读取操作数。
基于栈的虚拟机

  • 指令很小。因为每个指令都隐式从栈顶寻找它的参数，你无需对任何数据做编码。这意味着每个指令都非常小，通常只采用一个字节。
  • 代码生成更简单。当你要编写一个编译器或生成字节码输出的工具时，你会发现基于栈的虚拟机更简单。每个指令都隐式操作栈顶，你只需要以正确的顺序输出指令，就能实现参数传递。
  • 指令数更多。每个指令都只操作栈顶。这意味着生成类似a = b + c这样的代码，你就得分别用指令把b和c各自放到栈顶，执行操作，最后将结果存入a。

基于寄存器的虚拟机

  • 指令更大。因为它需要记录参数在栈中的偏移量，单个指令需要更多的位数，例如，在众所周知的寄存器式虚拟机lua中，每个指令占用32位。其中6位存储指令类型，剩下的存储参数。
  • 指令更少。因为每个指令都能做更多的事情，其数量相应就少些。因为你无需把栈中的值挪来挪去，所以也可以说你获得了性能提升。

应该怎么选呢？我的建议是基于栈的虚拟机。它们更容易实现，生成代码也更简单。寄存器虚拟机因为Lua转换为它的格式之后执行效率更高而受到称赞，但这实际上深切依赖于你虚拟机的实际指令集设计和其他更多细节。

应该有哪些指令

你的指令集划定了字节码表达能力的界限，它对虚拟机的性能也有影响。以下详细列出了几种你可能需要的指令类型:

  • 外部基本操作：它们是位于虚拟机之外、引擎内部的，做一些玩家能看到的事情的东西。它们决定字节码能够表达的真正行为。如果没有它们，你的虚拟机除了在循环中烧CPU之外，没有任何用处。
  • 内部基本操作：他们操作虚拟机内部的值——例如字面值、算数运算符、比较运算符和操作栈的指令。
  • 控制流：我们的例子中没有这部分，但如果你想要让指令有选择地执行或是循环重复执行，那你就需要控制流。在字节码的底层语言部分中，它们极其简单——跳转。
    在我们的指令循环中，我们有一个索引指向字节码堆栈的当前位置。每条跳转指令所做的就是改变该索引的值从而改变当前的执行位置。换句话说，它是个goto。你可以用它来实现任何高级语言的控制流。
  • 抽象化：如果你的用户开始往数据中定义很多内容，那最终他们会希望能重用字节码而不是反复复制粘贴。你也许会用到可调用过程。
    最简情况下，调用过程并不比跳转复杂。唯一不同的是虚拟机要维护另一个”返回“堆栈。当它执行到一个”call“指令时，它将当前指令压入返回栈中然后跳转到调用字节码。当它遇到以恶搞”return“时，虚拟机从返回栈中弹出索引并跳转转回索引所指位置。

值应当如何表示

我们的示例虚拟机只支持一种值类型：整形。这让答案变得很简单——这个堆栈仅仅是个存放int值的栈。一个功能完善的虚拟机应当支持不同的数据类型：字符串、对象、列表等。你必须决定如何在内部存储它们。
单一数据类型

  • 它很简单。你不用担心标签、转换或者类型检查。
  • 你无法使用不同的数据类型。这个缺陷太明显了。
    标签的一个变体
    这是动态类型语言通用的形式。每个值都由两部分组成。第一部分是个标签——一个用来标志所存储数据类型的枚举值。
    1
    2
    3
    4
    5
    6
    enum ValueType
    {
        TYPE_INT,
        TYPE_DOUBLE,
        TYPE_STRING
    };

剩下的位根据这个类型来解析，例如:

1
2
3
4
5
6
7
8
9
10
struct Value
{
    ValueType type;
    union
    {
        int intValue;
        double doubleValue;
        char* stringValue;
    };
};

  • 值存储了自身的类型信息。这种呈现方式的好处是，能够在运行时对值的类型做检查。这对动态调用很重要并能够保证你不会把操作执行到不支持它们的类型上。
  • 占用更多内存。每一个值必须携带标志它们类型的额外位。在虚拟机这样的底层中。这几个位占用增长得很快。