基于虚拟机和解释器的游戏脚本系统 ——虚拟机模块设计与实现---毕业论文

本本 科科 毕毕 业业 论论 文文 基于虚拟机和解释器的游戏脚本系统基于虚拟机和解释器的游戏脚本系统 虚拟机模块设计与实现虚拟机模块设计与实现 Game Scripting System based on Virtual Machine and Interpreter -Design and Implementation of Virtual Machine 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年年 月月 摘摘 要要 随着游戏行业的飞速发展，脚本语言扮演着越来越重要的身份。游戏脚本 是计算机游戏逻辑的载体，将脚本引入到游戏开发中，可以避免游戏逻辑的硬 编码化，从而大大提高游戏的开发效率，并进一步降低成本。目前国外已经有 多个适合游戏开发的动态脚本语言（例如 Ruby、Python、Lua），而国内的游 戏开发公司则也逐渐将动态脚本语言应用到开发中。 本研究项目为基于虚拟机和解释器的游戏脚本系统（GSS）的设计与实现。 其开发的核心思路是：设计对应语法的解释器，将本研究定义的脚本语言程序 翻译成虚拟机接受的机器码并由虚拟机完成具体执行工作。该虚拟机必须是简 洁、高效的，且允许跨平台执行。 本文针对整个系统的虚拟机部分为主要研究内容。该虚拟机以 Linux GCC 为开发环境，实现了对脚本语言的正确执行，并根据游戏开发的需求，提供高 效垃圾回收机制与关联数组结构。论文针对虚拟机的设计展开，介绍脚本语言 的研究背景、现状，开发了虚拟机部分，并设计了几个程序对系统进行展示验 证。 关键字：关键字：虚拟机；脚本语言；垃圾回收 Game Scripting System based on Virtual Machine and Interpreter - Design and Implementation of Virtual Machine Abstract With the rapid development of the gaming industry, scripting language began to play an increasingly important role. Game Script is the carrier of computer game logic. Introducing script into the game development will avoid hard-coded game logic and thus greatly improve the efficiency of game development, which will further reduce costs. At present, foreign countries have a number of dynamic scripting languages (such as Ruby, Python, LUA) for game development, and the domestic game development companies have been applying the dynamic scripting language to game development. This study introduced the design and implementation of game scripting system based on virtual machine and interpreter. The core ideas of designation are to achieve the interpreter of the corresponding syntax and to translate scripting language into the machine code which will be accepted by the virtual machine and then be implemented. The virtual machine should be easily operated, highly efficient, and allow platform independence implementation In this thesis, we focus on the design of virtual machine, which is in Linux GCC development environment, and achieves a correct implementation of scripting language; In accordance with the needs of game developers, this virtual machine will provide efficient garbage collection mechanism and associative array structure. This thesis is concerned with the implementation of virtual machine. Firstly it introduced the research background and current situation of scripting language; Then it was followed by the implementation of virtual machine. Finally, a number of programs were designed to verify this game scripting system. Key words: Virtual Machine; Scripting Language; Garbage Collection 目录目录 第一章第一章 绪论绪论1 1 1.11.1研究背景与选题意义研究背景与选题意义1 1 1.21.2研究现状与存在的问题研究现状与存在的问题2 2 1.31.3主要研究内容及特色主要研究内容及特色4 4 1.41.4本文结构安排本文结构安排6 6 第二章第二章 GSSGSS 的架构设计的架构设计 7 7 2.12.1GSSGSS 系统需求分析系统需求分析 7 7 2.22.2GSSGSS 系统分析与设计系统分析与设计 7 7 2.32.3虚拟机模块构架设计虚拟机模块构架设计1111 2.42.4小结小结2020 第三章第三章 GSSGSS VMVM 的实现的实现 2121 3.13.1实现的环境和语言实现的环境和语言2121 3.23.2系统开发流程系统开发流程2222 3.33.3虚拟机实现虚拟机实现2222 3.43.4系统运行结果系统运行结果3636 3.53.5小结小结4444 第四章第四章 总结与展望总结与展望4545 参考文献参考文献4646 致谢致谢4747 Contents Chapter 1 Introduction.1 1.1Background.1 1.2Current Situation .2 1.3Contents and Tasks4 1.4Architecture of Thesis6 Chapter 2 Overall Design of GSS7 2.1Requirement Analysis of GSS.7 2.2Analysis and Design of GSS.7 2.3Framwork of GSS Virtual Machine.11 2.4Summary.20 Chapter 3 Implementation Value value; 第三章 GSS VM 的实现 23 Object; 其中，Type 为一个 enum 型变量，用于表示该数据的类型。具体的，一共 提供 8 种类别的数据类型： typedef enum T_MARK, T_NIL, T_NUMBER, T_STRING, T_ARRAY, T_FUNCTION, T_CFUNCTION, T_USERDATA, Type; T_MARK 类型：类型：设计为标记位，当函数调用、压栈等操作时，通过 T_MARK 确定边界问题。 T_NIL 类型：类型：同 C 语言的 NULL 类型，在 GSS 中未初始化的数值标记 位 T_NIL 以及用 T_NIL 来表示 False 情况。 T_NUMBER：数值类型。 T_STRING：字符串类型。 T_ARRAY：关联数组类型，即为键值对的 mapping 结构。 T_FUNCTION：GSS 函数指针类型。 T_CFUNCTION：C 语言写的库函数的类型。 T_USERDATA：用户自定义类型。 而 Object 中的 Value 类型则用于存储值，详细定义如下： typedef union Cfunction f; real n; char *s; Byte *b; struct Hash *a; void *u; Value; 即定义为一个 UNION 型，共用一块 32 位的内存区域。其中，real 类型存 储为实值，其余类型则为一个地址指针（在 C 语言中，指针为 32 位正整数） 。 在进行类型操作过程中，详细如下： Object 声明时，其 tag 被定义为 T_NIL，而 value 不需要进行特别处理。 基于虚拟机和解释器的游戏脚本系统 24 在进行赋值操作的时候，由编译器确定类型后，分两种情况：如果该 Object 非 NIL，则必须同类型或可进行强制转换的方可赋值，否则给出 出错信息。如果该 Object 为 T_NIL 型，意味着还是空白，则写入 tag 位以及 value 位。 在进行比较时，需要判断 tag 位必须相同方可进行，并依据不同的类型 进行不同的比较策略。 .2 Mapping 实现实现 Mapping 内部设计为 Hash Table 实现。而 Hash Tabel 则以开链法作为冲突 解决法，具体实现如图 3-2 所示。 Hash Table Node Node Node list 图图 3-2 Hash Table 结构结构 我们将 Hash 是实现为一个二维指针，其包含了对 list 数组的引用，而 list 本身是一个 Node 的链表。同一个 list 其哈希值是一致的。使用开链法进行索引 或者插入时，先由 Hash Function 计算出所处 list，并顺序遍历该 list 直到找到值。 节点的定义：节点为键值对，ref 为其索引值，而 val 代表具体值。同时， 节点必须拥有对下一个节点的指向。 typedef struct Node 第三章 GSS VM 的实现 25 Object ref; Object val; struct Node *next; Node; 整个 Hash Table 结构定义： typedef struct Hash char mark; unsigned int nhash; Node *list; Hash; 其中：mark 位为布尔类型，用于垃圾回收机制中，标记该 hash table 是否 使用；nhash 位为 Hash 的 Vector 长度，并用于 Hash Function 的计算。List 则为 一个二维链表结构。 Hash 暴露给外界的接口包括： 1.Hash *HashCreate(unsigned int nhash); 2.void HashDelete(Hash *h); 3.Object *HashDefine(Hash *t, Object *ref); 4.void HashMark(Hash *h); HashCreate：构造一个 Hash, 默认长度为 nhash。因为 Hash Table 的第一维 必须为 Vector 数组，故可以通过 calloc 机制申请连续空间达到数组的作用。 HashDelete：将一个 Hash Table 删除掉。这里有很重要的顺序问题：先释 放各个节点，再释放节点链，最后释放整个表。 HashDefine：查找 ref 对应的在 t 中的值，存在则返回值，不存在则构造一 个节点用于放置 ref，且值默认设置为 T_NIL。HashDefine 查找时，先定位到该 ref 所处的 list，再遍历 list 查找具体位置。定位通过 Hash Function 来达到目的。 在 GSS 中，将 Hash Function 实现为： /* 哈希函数，用于计算哈希值 */ 基于虚拟机和解释器的游戏脚本系统 26 static int CalcHash(Hash *t, PObject ref) if (Tag(ref) = T_NUMBER) /* 数值类型，哈希值定义为 num % nhash */ else if (Tag(ref) = T_STRING) /* 字符串类型，哈希值定义为：各个位 char % nhash 的累加 和 */ else /* 不应该出现其他类型的哈希定义 */ ReportBug(“unexpected arguments to index table“); HashMark：用于标记清除的 GC 机制，标记整个 Hash 表。包括先将该 Hash 的 Mark 位标记为 1（即使用中） ，并遍历整个 Hash 中的所有元素，对所 有元素亦进行标记。 另外，VM 实现了 Hash Table 的遍历操作 Next，采用类似深度搜索的机制 遍历进各个 List 查找有效位并给出具体 ref 及 val。该 next 操作同时注册为库函 数，在 GSS 中可以直接使用 i, v = next(map, curI)来获得下一个键值对。 .3 Opcodes 设定设定 虚拟机的实现是基于堆栈的，它接受的指令称为字节码，这些字节码指令 提供了操作栈的方式，以支持脚本语言中的语句、控制结构、逻辑运算等。主 要的字节码指令约定如下： NOP：空指令 PUSHNIL：将 NIL 入栈 PUSH0、PUSH1、PUSHBYTE、PUSHWORD、PUSHFLOAT：将数值堆 栈 第三章 GSS VM 的实现 27 PUSHSTRING：将 String 入栈 PUSHLOCAL0、PUSHLOCAL1、PUSHLOCAL2、PUSHLOCAL3、PUSH LOCAL4、PUSHLOCAL5、PUSHLOCAL6、PUSHLOCAL7、PUSHLOCAL8、 PUSHLOCAL9、PUSHLOCAL：将栈低元素重新压入栈（主要用于参数传值） PUSHGLOBAL：将当前 PC 所指的 Object 入栈 PUSHINDEXED：将 T_ARRAY 中元素压入栈中 PUSHMARK：将 T_MARK 类型对象入栈 PUSHOBJECT：将 Object 对象入栈 STORELOCAL、STORELOCAL1、STORELOCAL2、STORELOCAL3、S TORELOCAL4、STORELOCAL5、STORELOCAL6、STORELOCAL7、STORE LOCAL8、STORELOCAL9：将栈底元素存到 PC 所致的对象中 STOREGLOBAL：将栈顶元素存储在 PC 所指的元素中 STOREINDEXED、STOREFIELD：将栈中的 Array 元素存储在数组中 ADJUST：修正栈位 CREATEARRAY：创建一个 Array 数组, 带有一个参数 nhash。未指定则默 认 nhash 取 101 (大于 100 的第一个素数) EQOP、LTOP、LEOP、ADDOP、SUBOP、MULTOP、DIVOP、CONCOP 、MINUSOP、NOTOP：运算操作符 ONTJMP、ONFJMP、JMP、UPJMP、IFFJMP、IFFUPJMP：跳转指令 POP：偏移栈顶指针 CALLFUNC：调用一个函数体 RETCODE：对应于 CALLFUNC 操作中，当调用为 T_FUNCTION 的情况。 进行将 PC 指针、base、top 指针还原，并根据参数返回情况调整 top RESET：重置当前所处的函数 基于虚拟机和解释器的游戏脚本系统 28 HALT：停机指令 SETFUNCTION：将当前函数压入 funcStack 中（出错信息相关） SETLINE：设置 gDebugLine 全局变量（出错信息相关） 虽然某些 Opcode 可以通过其他 Opcode 来实现，例如 PUSHLOCAL1 等价 于 PUSHLOCAL （空格）1。尽管二者作用是一样的，但前者仅需要一次栈操 作。这样做的目的是提高代码密度和解释的速度。 （在 JVM 中，同样的压入 1 可以用 5 条不同的指令25） .4 虚拟机的内存结构虚拟机的内存结构 正文段：正文段：存放解释器生成的字节码。用一个数组实现，并规定了数组的最 大长度，指针 basepc 指向生成的第一条字节码，指针 pc 指向最后生成的字节 码。 #define MAXCODE 1024 static long mainbufferMAXCODE; static Byte *maincode = (Byte *)mainbuffer; static Byte *basepc; static Byte *pc; 堆栈段：堆栈段：存放上下文环境。同样用数组来实现，数组的每个元素均为 Object 类型。Stack 指向整个堆栈的底部，top 指向当前栈的顶部，而 base 则指 向当前调用栈的底部。 static Object stackMAXSTACK = T_MARK, NULL ; static Object *top = stack + 1, *base = stack + 1; 静态数据段：静态数据段：存放数值、函数地址等。实现为数组，每个数组元素为 Symbol 类型包含符号名以及值。其中，初始化时就已将 type、tonumber、next、nextvar、print、istable 作为注册函数，将字符串以及函 数指针保存起来。 typedef struct Symbol 第三章 GSS VM 的实现 29 char *name; Object object; Symbol; static Symbol tableBufferMAXSYMBOL = /*symbol type function */ “type“, T_CFUNCTION, GetType , “tonumber“, T_CFUNCTION, ObjToNum , “next“, T_CFUNCTION, Next , “nextvar“, T_CFUNCTION, NextVar , “print“, T_CFUNCTION, Print , “istable“, T_CFUNCTION, LibIsTable , ; Symbol *table = tableBuffer; Word nTable = 6; GSS 语句 data=6.3 则会添加一条记录：“data”, T_NUMBER, 6.3 堆：堆：堆的实现被分为两个部分，分别为 string 堆、array 堆，针对不同的堆， 其具体的 GC 处理亦有所不同。以下为堆声明的代码范例： static Hash *arrayBufferMAXARRAY; Hash *array = arrayBuffer; Word nArray = 0; static char *stringBufferMAXSTRING; char *string = stringBuffer; Word nString = 0; .5 实现虚拟机指令集的执行实现虚拟机指令集的执行 虚拟机的执行依赖于解释器将文件读入并正确译码。解释器以指向正文段 的 PC 指针为参数，调用虚拟机的 Excute 指令。 Excute 不可避免的用 switchcase结构进行实现，针对不同的操作码采取的 基于虚拟机和解释器的游戏脚本系统 30 策略也不相同。下面本文将针对几组典型的 Opcode 进行详细说明： NOP：nop 作用是空指令，故不作处理，直接 break 掉。 PUSHSTRING：将字符串类型压入到栈中，其结构形如：opcode index。 当 PC 指针读取到 PUSHSTRING 的 Opcode 时，则自动加 1，此时 PC 指针所指 的为 string 的地址（该地址非内存地址，为在 constant 表中的偏移位置） 。 int w = *(Word *)(pc); pc += sizeof(Word); Tag(top) = T_STRING; SValue(top+) = constantw; PUSHLOCAL：将栈底第 N 个元素压入栈中，结构为：opcode index。在 调用函数的时候，参数首先入栈，故参数位处于栈底。 *top+ = *(base + (*pc+); PUSHINDEXED：将 ARRAY 中的元素入栈。在该 OPCODE 之前，必定 存在两组 PUSH，即将 array 先入栈，再将 array 的 ref 值入栈，方才调用 PUSHINDEXED。具体的流程如下： -top; if (Tag(top - 1) != T_ARRAY) ReportBug(“indexed expression not a table“); return 1; Object *h = HashDefine(AValue(top - 1), top); if (h = NULL) return 1; *(top - 1) = *h; ADJUST: 因 GSS 为动态类型绑定，且 function 无返回类型的说明，顾需 第三章 GSS VM 的实现 31 要根据 return 值情况以及传参进来的实际数量，对栈进行修正。具体修正：若 return 数量要求数量，则只取要求数量；若 return 数量要求数量，则用 NIL 进行补足返回。 Object *newtop = base + *(pc+); if (top != newtop) while (top newtop) Tag(top+) = T_NIL; top = newtop; 、 LTOP：小于判断，满足条件则往堆栈中压入数值 1，否则压入 T_NIL 类 型。 Object *l = top - 2; Object *r = top - 1; -top; if (Tag(l) = T_NUMBER else if (ToString(l) | ToString(r) return 1; Tag(top - 1) = (strcmp(SValue(l), SValue(r) 0) ? T_NUMBER : T_NIL; NValue(top - 1) = 1; 基于虚拟机和解释器的游戏脚本系统 32 .6 GC 模块模块 GC 模块设计成标记清理算法，该模块并不会一直运行，只有当堆空间即 将发生溢出的时候，才进行清理。 事实上，对于所有堆中产生的空间，相应的全局 string、array 表中必有一 份指针指向它们，但真正需要保留的仅为在全局 table 以及 stack 中正在使用的。 所以思路便是将清理掉堆中不是当前 table、stack 所使用的元素。 结合 GSS 系统，垃圾回收具体的算法如图 3-3 所示。 遍遍历历全全局局符符号号 表表、栈栈空空间间，针针 对对在在其其中中的的字字符符 串串、ARRAY类类型型 标标记记为为1 遍遍历历堆堆空空间间 每每个个元元素素 该该元元素素是是否否已已 经经被被标标记记为为1 释释放放该该元元素素 占占据据空空间间 清清理理结结束束，将将堆堆中中的的 所所有有元元素素重重置置为为0 结结束束 开开始始 是是 否否 第三章 GSS VM 的实现 33 图图 3-3 标志清理算法框架标志清理算法框架 其中，array 为 Hash Table 类型，在前面已经介绍过，它的结构中包含了 mark 位；string 在 GSS VM 中实现如图 3-4 所示，为一个 mark 位与串内容的组 合。 0 mark位位 C风风格格String . C风风格格String尾尾(0) 图图 3-4 GSS VM 的的 String 形式形式 在虚拟机内部，产生 string 串的唯一接口为：StrDup，其实现为 char *s = calloc(strlen(l) + 2, sizeof(char); /* 创建标记位, 并拷贝字符串 */ *s+ = 0; return strcpy(s, l); GC 模块的主函数实现为 Dtable.c 中的 pack 函数（array 的压缩成类似，故 不进行重复演示）： MarkStack(); MarkTable(); /* 字符串压缩 */ int i, j; for (i = j = 0; i nString; i+) if (MarkString(stringi) = 1) stringj+ = stringi; MarkString(stringi) = 0; else 基于虚拟机和解释器的游戏脚本系统 34 /* 不在使用中的变量，则释放 */ free(stringi - 1); /* 更新现有的字符串总数 */ nString = j; .7 库函数库函数 库函数是库中存放函数的名称和对应的目标代码，以及连接过程中所需的 重定位信息。用户也可以根据自己的需要建立自己的用户函数库。库函数具有 明确的功能、入口调用参数和返回值。在 GSS 系统中，库函数机制如图 3-5 所 表明。 实实现现流流程程 实实现现函函数数: 调调用用GetParam获获得得参参数数 C语语言言对对其其处处理理 调调用用PushObject方方法法返返回回值值 调调用用Register(函函数数名名，函函 数数指指针针) 注注册册为为虚虚拟拟机机的的库库函函数数 虚虚拟拟机机内内部部处处 理理流流程程 参参数数全全部部入入栈栈， 保保存存栈栈的的上上下下文文 信信息息 通通过过函函数数调调 用用 恢恢复复栈栈的的上上下下 文文信信息息 图图 3-5 GSS 中库函数机制中库函数机制 第三章 GSS VM 的实现 35 我们库函数实现为一组通过 Register 注册的函数，且必须遵循调用： GetParam 获得参数，调用 PushNumber、PushString、PushObject 等方法返回结 果。 其中，Register 机制的实质是将函数指针压入全局符号表中。 #define Register(symbol, function) (PushCFunction(function), StoreGlobal(symbol) 调用库函数作为 Opcode 中 CALLFUNC 的实现，过程为先通过栈操作保存 上下文环境，再执行具体的操作，最后将操作返回的值入栈并还原上下文环境。 例如，对于查找子串在父串中的位置。先实现一组函数用于完成该功能： static void StrFind(void) int n; char *pos; char *s1, *s2; PObject o1 = GetParam(1); PObject o2 = GetParam(2); if (! IsString(o1) | ! IsString(o2) Error(“incorrect arguments to function strfind“); return; s1 = GetString(o1); s2 = GetString(o2); if (pos = strstr(s1, s2) = NULL) PushNumber(-1); else 基于虚拟机和解释器的游戏脚本系统 36 n = pos- s1 + 1; PushNumber(n); 将该函数注册为虚拟机的库函数： Register(“strfind“, StrFind) 则在 GSS 中，可以直接支持 s=strfind(string, subString)。 3.4 系统运行结果系统运行结果 基于需求以及上面的技术分析，我们实现各自的模块并进行集成为统一的 GSS 系统。下面将用几组程序对 GSS 最后实现的情况进行演示，在给出每个例 子的同时，会细致的进行分析，从而达到展示、集成测试的目的。 .1 生成工程生成工程 在 Linux 平台下，使用 GNU make 工具建立工程，在相应目录下，输入 make 命令可生成可执行文件。项目中使用的 makefile 文件如图 3-6 所示(如果要 在 Windows 平台下运行，只要将其中的 rm 命令改为 del 命令)。 第三章 GSS VM 的实现 37 图图 3-6 GSS 工程的工程的 makefile 文件文件 运行 make 的结果如图 3-7 所示。 图图 3-7 编译工程结果编译工程结果 结论分析：ANSI C 的语法保证了 GSS 项目在各个平台编辑环境下的通用 性，测试包括有 Linux GCC、Windows GCC(mingw 版)、VC 6.0，并分别在各 个平台下亦测试了程序运行正常。该实践证明，各个平台下的 GSS 编译没有具 体的差异，即实现了跨平台的目标。 .2 TableTable 结构演示结构演示 下面将对 table 结构进行验证，关注关联数组在游戏开发中的重要作用，例 子为针对游戏中的玩家，其中有“ilbe”玩家的血量为 480，魔法值为 360，且 该玩家加入了一个队伍，队伍的 leader 为“huzb” ，还有一个成员为“chenx” ， 该关系可用图 3-8 所示代码表示。 基于虚拟机和解释器的游戏脚本系统 38 图图 3-8 关联数组测试关联数组测试 其中，PrintTable 为一个递归调用的函数，主要负责执行对 table 结构的打 印。调用命令执行上述代码，其结果为如下图 3-9 所示。 图图 3-9 运行运行 table.ds 的结果的结果 结论分析：从语法上，关联数组显然提供了非常便捷的语法特性，因为关 联数组表现的更加接近于生活中的事物的描述特性。例如，想查询玩家 ilbe 所 处队伍的队长信息，则可以通过：data.ilbe.teamInfo.teamLeader 来访问。而且关 联数组的扩充被封装到具体虚拟机内部，可以对其进行任意的增加内容，程序 员不需要为其花费额外精力。当然，关联数组另外一个重要的特性是：mapping 中的元素是可以允许为 mapping，即嵌套是非常方便的，这也在上面的测试中 给与展示并验证。 .3 Hanoi 塔塔 Hannoi 塔是经典的回溯，问题描述为： 1.有三根杆子 A,B,C。A 杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从 A 杆全部移到 C 杆上 使用本研究中的脚本语言解决此问题的代码如图 3-10 所示。 第三章 GSS VM 的实现 39 图图 3-10 Hanoi 的的 GSS 实现实现 运行结果为下图 3-11 展示。 图图 3-11 hanoi 塔程序的运行结果塔程序的运行结果 结论分析：从 hanoi 塔程序的准确运行中，可以最终确定，虚拟机的堆栈 结构设计的正确性。因为 hanoi 塔本身是回溯的，回溯则是基于正确的入栈、 出栈方可以成功执行。在 GSS 中，入栈和出栈操作室由操作码进行直接支持， 故该模块的正确，也保证了程序之间互相调用的准确性。 .4 N 皇后问题皇后问题 问题描述：皇后问题是一个古老而著名的问题，是回溯算法的典型例题。 该问题是十九世纪著名的数学家高斯 1850 年提出：在 NXN 格的国际象棋上摆 基于虚拟机和解释器的游戏脚本系统 40 放 N 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列 或同一斜线上，问有多少种摆法。 使用本研究中的脚本语言解决此问题的主函数代码如图 3-12 所示。 图图 3-12 N 皇后问题的皇后问题的 GSS 解决方案主函数解决方案主函数 从上面可以看出，大部分语法跟 C 语言比较一致。N 皇后的算法也是基于 回溯的，即待放置的皇后满足在横、纵、左斜、右斜均不与已放置的皇后冲突， 在算法上通过不同的数组进行标记。如果可允许，则递归进行处理下一行皇后 放置。上述程序在 GSS 上的运行结果如下图 3-13 所示。 第三章 GSS VM 的实现 41 图图 3-13 N 皇后问题的运行结果皇后问题的运行结果 结论分析：N 皇后问题作为经典的题目，可以验证 GSS 性能。当测试 12 皇后时，输出到 9000 多组答案仍然在继续，由此可以分析出垃圾回收机制工作 顺畅。因为 GSS 设计的堆空间仅仅为 2048，在这样的堆空间中，9000 多组答 案必然引发内存管理。事实上，当 8 皇后的时候，在垃圾回收机制的主函数 pack 中插入调试语句 printf 可以发现，一共进行了 11 次内存整理。 同时，N 皇后问题的解决也反映了 GSS 的明显特征：有利于提高编程效率。 其简洁、高效的语法特性，在描述 N 皇后打印问题以及判定是否能置棋子的逻 辑时，提供了更为方便快速的实现。 .5 五子棋游戏五子棋游戏 五子棋是起源于中国古代的传统黑白棋种之一。它的棋文化源渊流长，具 有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。通过对五子 基于虚拟机和解释器的游戏脚本系统 42 棋游戏的实现，展示脚本系统在游戏开发中的框架。针对 GSS 系统开发的五子 棋游戏整体框架如图 3-14 所示。 脚脚本本文文件件 胜胜负负判判定定 电电脑脑AI 五五子子棋棋工工程程 MFC 游游戏戏主主框框架架 Call接口调 用 GSS脚脚本本系系统统 调调用用 载载入入执执行行 返返回回 图图 3-14 五子棋程序实现框架五子棋程序实现框架 该框架示意了 GSS 在游戏开发中的位置，即将整个脚本系统嵌入，并提供 接口作为桥梁实现外部.ds 脚本文件与游戏核心的交互。在五子棋中，我们将单 独的判断逻辑、电脑 AI 抽离出写入专门的脚本 Gobang.ds 中，并将需求固定部 分用 MFC 实现。在 MFC 程序初始化时由 GSS 通过 DoFile 进行载入，并在各 个执行步骤中，通过接口 Call 来负责逻辑的调用返回。采用该方式，当我们需 要更改逻辑判断（因需求变更或者更好的实现） ，则可以不需要更改到源文件， 而只需要修改.ds 外部脚本。该过程不需编译。 游戏系统采用 Visual Studio 2008 开发，具体的工程结构如图 3-15 所示。 第三章 GSS VM 的实现 43 图图 3-15 GSS 应用于五子棋工程应用于五子棋工程 编译运行五子棋工程，得到如图 3-16 所示的游戏界面。 图图 3-16 五子棋运行展示五子棋运行展示 基于虚拟机和解释器的游戏脚本系统 44 结论分析：作为一个小型游戏，我们将其与 GSS 进行结合，从而实现对系 统的展示。在上面的五子棋程序中，当我们需要修改判断规则或者 AI 的逻辑时， 直接对 Gobang.ds 脚本文件进行修改，而源程序本身可以不用对其进行任何的 编译即可运行。这点在大型网络游戏中将格外的重要：游戏维护阶段的成本远 高于开发，而在后期游戏主流程基本不会发生变化，但是细节逻辑总是不停地 休整，任何的小改动都需要对工程进行编译的代价是巨大的。 3.5 小结小结 本章对整个项目虚拟机实现部分的技术细节详细阐述，并用几个例子对项 目最终可行性进行了验证、对整个系统进行了展示。然后，这还是只能提供一 个概括，更细节部分请参阅程序实现部分。 第四章 总结与展望 45 第四章第四章 总结与展望总结与展望 本文在对现有的脚本语言进行大量的学习与研究的基础上，实现了自己的 一套脚本语言机制 GSS 系统。本章将对本文及项目的主要工作内容进行总结， 并指出工作中的不足之处。最后，将对下一阶段的工作以及进一步改进内容进 行展望。 研究本课题的主要动机是对程序设计语言原理和翻译过程，虚拟机的执行 及相关算法进行深入透彻的研究，同时通过编码实现一个简单的解释器程序和 虚拟机程序，以期提高自己的理论水平和编码能力，同样在未来游戏行业开发 时通过对内部机制的熟悉，提高开发质量。 本研究主要包括以下工作： 1.介绍了动态脚本语言的研究背景和现状，对相关应用领域和作用进行 了说明。 2.介绍了 GSS 的系统框架，包括功能框架与技术架构，对各个功能模块 进行了描述。 3.具体介绍了 GSS VM 实现的细节，并利用简短的几个小程序进行展示 了系统的可行性、性能等。 当然，本系统亦存在一些不足，需要在下一阶段的开发中继续完善，具体 主要是以下两个方面： 1.加入调试模块。在解释器和虚拟机中加入程序调试支持，例如设置断 点等，以增加程序开发效率和质量。 2.线程概念的引入。从 VM 底层对提供对线程的直接支持，因为游戏的 世界中对象是复杂的，例如对怪物 AI 的控制，可以通过各种不同的线 程表现不同怪物的 AI。 参考文献 46 参考文献参考文献 1 Alex Varanese.陈洪,罗颖民,李华杰翻译. 游戏脚本高级编程M. 北京:清华大学出版社,2006. 2 Andre LaMothe. Windows 游戏编程大师技巧（原书第二版）M. 北京：中国电力出版社,2004. 3 冀振燕,程虎. java 编译系统的研究J. 计算机科学 1996，36（1）. 4 周程,陈代进.游戏脚本语言的研究J.电脑知识与技术,2008. 5 徐正超,喻成. Java 虚拟机中内存管理机制研究D. 中南民族大学硕博士论文. 6 Tom Gutschmidt. Game Programming with Python, Lua, and RubyM. US:Premier Press, 2003. 7 Bruce Dawson. Adding Languages to Game EngineJ. Game Developer Magazin, 1997. 8 邓际锋. 一颗璀璨的月光宝石 LuaM. 程序员-2006 年 6 期. 9 TH.Rorner, Dennis Lee. The Structure and Performance of InterpretersZ. Washington: Department of Computer Science, 1998. 10 吴作顺,窦文化. 几个常用解释器的性能分析J.计算机工程与科学,2002. 11 Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffrey D.Ullman. 编译原理（原书第二版）M. 北京： 机械工业出版社, 2009. 12 Andrew W.Apple. 赵克佳,黄春,沈志宇. 现代编译原理-C 语言描述M. 北京：人民邮电出版社,2006. 13 Jeremy Singer. JVM Versus CLR:A Comparative StudyM. US:Computer Science Press, 2003. 14 E. Miranda, BrouHa. A Portable Smalltalk InterpreterJ. ACM SIGPLAN Notices, 1987. 15 李巍. 虚拟机机制研究D. 电子科技大学硕博士论文. 16 USENIX: The Advanced Computing Systems Association. OL. 17 Bill Blundent. Virtual Machine Design and ImplementationM. Shanghai: China Machine Press 2003. 18 R. W. Sebesta. Concepts of Programming LanguageM. 北京:机械工业出版社,2008. 19 Bruce Eckel. Thinking in Java. Third EditionM. 北京:机械工业出版社,2004. 20 维基百科 红黑树 /wiki/%E4%BA%8C%E5%8F%89%E6%A0%91OL. 21 侯捷. STL 源码剖析M. 武昌:华中科技大学出版社. 2009. 22 王晓东. 计算机算法设计与分析（原书第 3 版）M. 北京：电子工业出版社,2007. 23 Thomsa H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein. 算法导论（原书第二 版）M. 北京：机械工业出版社,2006. 24 汤韬. 动态语言，隔岸观“火”M. 程序员-2004 年 5 期. 25 James E.Smith, Ravi Nair. 安虹, 张昱, 吴俊敏翻译. 虚拟机系统与进程的通用平台M. 北京:机械 工业出版社M, 2009. 致谢 47 致谢致谢 临近毕业之际，望着完成的论文，心中有无限的感慨，也充斥着很多的感激。 在这里，我由衷地感谢在我成长道路中给与我无私帮助的长辈和朋友。 首先感谢我的导师：和。他们一丝不苟的工作作风、扎实的理论基础深深的 影响着我，并指导我众多的意见，在这里向两位导师表示我最真挚的感谢。 其次，非常感谢同组的另一位同学李小