译注
星际争霸 这个游戏对我而言非常重要.
不仅仅是从小玩到大(我出生前我爹: 我买个电脑给他学习. 实际上: 玩星际).
也不单纯因为星际一到星际二, 国服美服充了双份的钱(双份的快乐!)
更多的这个游戏一来把我拉进了科幻的(天)坑; 另一方面和终结者一起把我拉到了计算机的(另一个)坑(双份的头秃!).
我大约在一年半以前看到Patrick Wyatt的文章, 一系列四篇都是在讲他在90年代写 星际争霸 的故事的. 从游戏性, 寻路, 算法各个角度都有写到, 读后收获颇丰. 遗憾在当时没有留下Patrick的个人网址, 最要命的是我当时还忘了Patrick的大名, 无论如何Google都没能找回来, 懊悔至极 .
上周的时候点开浏览器输入网址的时候typo了一下, 把auth输入成了author, 结果居然Google提示出了他的个人主页. 遂浏览之, 找到这篇文章, 决定翻译一下转发到自己这里.
至于后续几篇会不会翻译, 啥时候鸽完, emmmm看本砖工啥时候有空, 先放出链接供有兴趣的去读.
- 星际争霸 的艰辛之路:为什么开发时游戏总在崩溃?(Tough times on the road to Starcraft: Why StarCraft crashed frequently during development)
- 躲开常见的链表导致的崩溃: 为什么我们本可以修复一些常见错误(Avoiding game crashes related to linked lists: How we could have fixed the most common causes)
- 星际争霸 的寻路补丁(The StarCraft path-finding hack)
- 星际争霸: 分崩离析的"太空魔兽"(StarCraft: Orcs in space go down in flames)
另外, 翻译时保留了全部链接和人名未作改动, 公司,游戏,术语我则尽可能翻译成了中文. 写完睡觉!
以下是正文
2012年7月, 由Patrick Wyatt, 161 评论.
我一直在写_魔兽争霸_ 早期开发的故事,但是我最近读的一篇文章激励我开始疯狂写_星际争霸_ 的故事. 最后就变成了这个分三个部分,长二十多页的文章,来讲讲_星际争霸_ 的开发历史,以及我关于如何开发更加可靠的游戏代码的思考. 我会在接下来几天发布后面的部分.
- 本篇: 为什么开发时游戏总在崩溃
- 第二部分: 为什么我们本可以修复一些常见错误
- 第三部分: 一些修复的实现细节
星际争霸 的起源
星际争霸 开发了大约两年半,其中发布前一年多都非常紧张. 在开发期间,这个游戏里的bug多的就和白蚁巢一样. 尽管它的先驱(魔兽争霸 I和II)比他们的竞品都要稳定的多,星际争霸 崩溃的如此频繁以至于游戏测试都很难进行,而这个状况一直持续到了发布前. 即便如此,这个游戏还是在发布后进行了许多修补工作.
为啥?有太太太太太多理由了.
太空魔兽
星际争霸 最早有一个颇为合理的一年开发周期,这样就可以在1996年圣诞节期间发布.
领导这个项目的和发起破碎国度(Shattered Nations)(视频)的是一伙人. 破碎国度 是个回合制的策略游戏,作为 X-Com 这个世界观下面的一个游戏, 本来是暴雪(Blizzard)1995年5月宣布的但是几个月后就取消了.
团队就这样被重新组建起来,打造一款能快速上市的游戏,这样暴雪就不会在游戏发布之间有太大的间隔.
- 1994 第4季度 – 魔兽争霸
- 1995 第4季度 – 魔兽争霸 II
- 1996 第4季度 – 计划的_星际争霸_ 发行日期
- 1998 第2季度 – 实际发行日期
现在回想起来想急忙赶工出一个游戏这种决定挺可笑的,但是公司总裁Allen Adham承受着压力要增长收入. 因为尽管暴雪早期的游戏都比预计中要成功的多,这也提高了人们对未来增长的预期.
鉴于有限的时间和人力,星际争霸 团队的目标是实现一个差不多的游戏: 最多也就是"太空魔兽"那种样子. 从这张照片可以看出来游戏团队当时想走的路, 这张照片截取自1996年第二季度的E3游戏展.

但是一个更要紧的项目压制了_星际争霸_ ,把开发者一个接一个的拉走了: 暗黑破坏神(Diablo)需要额外的帮助. 暗黑破坏神一个角色扮演游戏, 由当时位于加州红木城(Reedwood City)的神鹰工作室(Condor Studios)开发. 神鹰最早是Dave Brevik, Max Schaefer和他兄弟Erich Schaefer组建的公司,当时只有120万美元的预算: 即使是那个年代也是少的可怜的数目.
神鹰团队毫无希望能完成他们想做的游戏,但是他们做的前期开发工作实在是太有趣了. 对于暴雪来说将神鹰收入囊中是合情合理的, 遂收购之,改名北方暴雪(Blizzard North),并开始往这个急需帮助的游戏里投钱投人.
最早是一个_星际争霸_ 的程序员Collin Murray和我飞到红木城帮忙, 其他人在暴雪总部尔湾(Irvine)开发战网(battle.net)支持. 包括互联网,局域网,以及UI界面(在公司内叫"胶水屏")来支持角色选择,加入游戏和其他游戏前的准备功能.
随着暗黑破坏神的增长,最终所有在暴雪总部的人: 美工, 程序员, 设计师, 音效, 测试都来干活了,直到压根没人在干_星际争霸_ . 甚至_星际争霸_ 的项目领导也开始兼职写暗黑的游戏安装器: 一个我写了一半但是太忙了没空完成的部分.
在暗黑破坏神在1996年底发布之后, 星际争霸 的开发才重启. 所有人都有了机会来重新看看这个游戏的未来, 而且未来并不好. 这个游戏已经逾期了,而且和让人眼前一亮没有半毛钱关系,尤其是和像 多米诺风暴(Dominion Storm)这样的项目比起来,后者在六个月前E3展的预演就看起来非常振奋人心了.
暗黑破坏神的巨大成功重设了我们对暴雪的价值观的期望: 星际争霸 后来定下了"暴雪出品必属精品"的基调 但是为了证明这个基调我们走过了太多的痛苦.
去证明一些东西
每个人都用审慎的目光看着_星际争霸_ . 显然这个项目需要比先前的工作更加有野心,来重新定义即时战略游戏(RTS)的未来. 而_魔兽争霸_ I和II都是RTS的一种.
在_星际争霸_ 重启期间,有超过80(80!!)个RTS游戏在开发. 这是Johnny Wilson, 电子游戏世界(Computer Gaming World) 的首席编辑告诉我们的, 后者是当时世界上最大的游戏杂志. 这么多竞争对手中甚至包括西木工作室(Westwood Studios), 这家公司最早发明了现代RTS游戏机制. 我们需要做点真的让人耳目一新的东西出来.
我们并没有处于劣势,魔兽争霸 和暗黑破坏神的成功充斥的新闻报道, 我们不至于受玩家和媒体的不待见. 但是在游戏领域你最多只和上一部作品一样好. 我们得做的比上一部作品好得多,而这要求我们承担更多的风险.
新面孔
魔兽争霸 II只有六个核心程序员和两个支援程序员; 对于规模更大的_星际争霸_ 而言这完全不够,所以开发团队新添了一帮年轻且没啥经验的游戏程序员. 他们自己还需要学习怎么写游戏代码,却得不到多少指导.
我们项目的领导层也没有很强的领导力. 我们应该给没什么经验的程序员在项目早期提供指导所以他们可以在游戏发布前学到一些必要知识, 但那时我们尚不知道这件事有多重要. 所以对这帮绝地学徒而言,他们基本是自生自灭. 我们问题的很大一部分就是我们如履薄冰: 每个程序员都在疯狂写代码完成目标,却没有时间做代码审查,审计或者训练.
问题不仅仅是团队里没什么经验的年轻成员,星际争霸 代码团队的精英也从没有构架过一个完整的游戏引擎. Bob Fitch写过好几年的游戏,也有不少很棒的成果,但是他之前的经验都是在游戏端,他和已有的引擎打交道就可以写出_魔兽争霸_ I和II,完全不需要大规模的引擎设计. 尽管他也有 破碎国度 的领导经验,那个项目毕竟是被取消了,所以完全没法知道他在那边做架构的时候的一些决定是否合理.
整个团队在项目上花了非常多的时间精力,这些闻所未闻的投入牺牲了团队成员的个人健康和家庭生活. 我从来没在哪个项目里发现每个人都这么拼命三郎. 但是项目中有一些关键的代码决策,我下面会讲的几个,会在整个开发周期里一直萦绕着代码团队,挥之不去.
有些事变了
在暗黑破坏神发布前干了几个月,以及之后又有些清理,补丁的几个月之后,我回去帮忙重启_星际争霸_ . 我没打算再来一场Bug盛宴,但是事情就是这么发生了.
我以为我可以轻而易举的融入项目中, 毕竟我对_魔兽争霸_ 的代码太了解了: 每个部件的开发我都有参与过. 然而我却有点惊恐的发现引擎的很多部分都已经被扔掉或者部分重写了.
游戏中的单位类正在准备从零开始重写,并且单位调度器被扔掉了. 调度器是我在游戏中创建的一个机制,来确保每个单位都能有时间决定它要做什么. 每个单位都会周期性的询问:“当前动作执行完了,我应该干什么?”, “我应该重新寻路去到我要去的地方吗?”, “和我现在正在攻击的单位比起来有没有更好的单位可以攻击?”, “玩家是不是给我一个新的命令了?”, “我死了, 怎么清理我的尸体?”, 这类的问题.
即使有风险, 也有很多理由去重写代码; 退一步讲, 现有代码也是有风险的. (There are good reasons code needs to be rewritten, but excising old code comes with risks as well.) Joel Spolsky在 你永远不该做的事, 第一卷(Things You Should Never Do, Part I) 里说的最不容置喙(eloquently):
你得记住, 当你重新开始的时候, 完完全全没有理由相信你会比第一次做的更好. 首先, 你的工程团队可能和原来的不一样, 所以你并不见得"更有经验". 事实上, 你只是会犯更多的老错误, 顺便引入第一版里本不存在的问题.
魔兽争霸 的引擎花了几个月才编写好, 为了加入_星际争霸_ 特有的新的游戏特性现在要重做. 我们新组建的这个团队之后得花很多时间重新学习: 第一版的引擎为什么, 又是怎么编码才变成当时的构架的?
游戏引擎架构
我以前用C给微软DOS写过魔兽世界的游戏引擎,用的Watcom编译器. 现在我们转移到Windows了, Bob选择用Visual Studio编译器, 并且用C++重构游戏引擎. 编译器和C++都是合情合理的选择, 只有一个问题: 在那时团队里只有很少的人有C++的经验, 更别提C++的各种坑.
尽管C++很强, 它很容易被误用. 人尽皆知的C++语言的创造者, Bjarne Stroustrup说过: “用C很容易打到自己的脚, C++很难; 不过你如果一不小心打到了, 你的整条腿都得废掉.”
历史的进程告诉我们程序员总是喜欢用在第一个项目里用上新语言的每一个特性, 所以写_星际争霸_ 的时候我们就滥用了类(class)和继承(inheritance). 代码老手看到我们给游戏单位设计的继承链的时候怕是不寒而栗:
CUnit < CDoodad < CFlingy < CThingy
CThingy 是精灵图(sprites), 他会在地图的任何地方出现, 但是不会移动没什么行为.
CFlingys 则是创造粒子(particles)用的, 当游戏里什么东西炸了的时候会有一些粒子随机的四散开来.
CDoodad… 我寻思我们14年前当时是这么命名的.
这个类不能实例化, 只是对继承他的类封装了一些必要的方法.
最后CUnit 是最顶上一层.
每个单位的行为都分散在各种模组里面, 你得对每个类都有深入的理解才能真正的写代码.
除了糟糕透顶的继承关系, CUnit类本身也是一坨屎山, 其定义甚至像下面这样横跨了好几个头文件.
class CUnit ... {
#include "header_1.h"
#include "header_2.h"
#include "header_3.h"
#include "header_4.h"
};
每个头文件都有好几百行, 最终的类定义只能说是可笑至极.
直到很多年以后"要组合不要继承"的观念才在程序员中流行起来, 不过那些在_星际争霸_ 中写过代码的人则用更辛苦的方法亲身体悟到了.
只剩两个月就要发布了!
有这么一个混乱的起步, 重启团队要完成开发的压力很大. 在盘根错节的日程安排中却可以发现游戏还有两个月就要发布了.
考虑到游戏单位的数量庞大, 他们的行为更加浩如烟海; 游戏视角从俯视变成了斜视, 绘制工作也非常庞杂; 我们还要一个全新的地图编辑器; 得加上战网来支持在线游戏. 总而言之我们不太相信游戏能在两个月内做完 – 即使艺术团队, 设计师, 音效师, 平衡组和测试组都如期交付也不行. 开发团队则总处在"还有两个月就要发布了"的压力下忙了14个月.
整个团队都在加班. Bob那时一周工作80个小时, 然后是82, 88小时. 尽管每个人都加班很夸张, 但是我也不记得有谁像Bob那样努力到近乎自虐.
我在_魔兽争霸_ 开的夜车, 以及在暗黑破坏神上几乎007的经验告诉我, 开夜车是完全没必要的. 所有在夜里某个时间点以后提交[哈!提交这个词太合适了]的代码都只会在悔恨中和接下来几天的白天重写.
这么加班让人迷幻, 这对做需要大量知识的工作来说很糟糕, 因为我们的工作要很多创造力. 所以我们搞出一大堆错误, 不合时宜的特性和漏洞也不奇怪.
无独有偶的是, 我们加的班不是强制的: 只是我们想做出很棒的游戏而已. 但是回头来看这又很蠢, 我们本可以用合理的精力做出更好的产品.
我最引以为傲的成就就是我在两年的时间里领导了4个 激战(Guild Wars) 的战役, 而没有把我的团队带下_星际争霸_ 那条道.
星际争霸 游戏崩溃的最常见原因
尽管我实现了_星际争霸_ 的很多特性: 战争迷雾, 视野, 飞行单位路径分离, 语音聊天, 加强AI还有些别的, 我的工作却被吸引到了修bug上.
等下: 语音聊天! 1998年?!? 是: 我1997年12月就全干好了. 我用了一个第三方语音转音素的压缩器, 写了代码把这些音素传过网络, 解压, 然后在其他七个玩家的电脑上播放.
但是我们办公室的每一个声卡都要升级一个驱动才能工作… 前提是这个声卡还得支持同时录音和播放. 所以我非常懊悔的建议团队还是别加这个功能. 要不然的话技术支持的压力会大到我们雇游戏客服的钱都比我们卖游戏来的多.
所以总之啦, 我修复了好多bug. 有些bug是我的, 但是大部分是其他精疲力尽的程序员写的捉摸不透的一些bug. Brian Fitzgerald是和我合作过的最好的两个程序员之一. 有一次他审计_星际争霸_ 的代码的时候, 惊异于我在整个代码库里做的修改, 给了我我收到过的高的赞扬. 尽管已经过去很久了, 但是至少我还是收了表扬的吗!
考虑到所有我们遇到的困难, 你可能会觉得很难找到一个大范围的漏洞. 但是就我的经验来看_星际争霸_ 当时最大的漏洞是用双链表(doubly-linked linked list).
链表用来追踪有相同行为的单位, 这在引擎里用的很多, 魔兽争霸 一局游戏最多只能有800个单位, 星际争霸 翻了一倍. 1600这个数字使得用链表把特定类型的单位放在一起加速搜索至关重要.
我依稀记得每个玩家的单位和建筑都有一个链表, 生产建筑也有链表, 航母也有链表记录战斗机的数量, 还有好些其他的东西都用链表.
所以这些链表都是双向链表, 所以添加和删除元素都是O(1)的时间复杂度; 否则的话得走遍整个列表去找要删除的对象, 那就是O(N)的复杂度了.
很不幸的是, 每个链表都是手动维护的: 没有一个共享的函数来链接或者打断链接; 程序员在任何需要的地方手动把链接,断链接写到程序里. 而手动重写要比用一个早已修复过的函数更容易产生bug.
有些链表元素还被链接在了其他链表里面, 所以很有必要知道一个对象到底被链接在那些链表里了才能安全的断链. 还有一些元素甚至被存在了C的union里面来减少内存开销.
所有游戏总是崩溃. 总是.
但你为啥要这么做啊?
很不幸的是, 这种链表问题根本不应该存在. 我和Mike O’Brien还有Jeff Strain一起创建的ArenaNet. 我们写了一个库叫Storm.DLL, 这个库和暗黑破坏神一起发布的. 除了其他许许多多的特性, Storm包括了一个用模板(template)实现的非常好的双链表.
星际争霸 最早开发的时候这个库是用了的. 但是游戏开发早期我们把整个代码都掀了重写了一份链表, 主要是为了让保存游戏的文件更好些.
我来说说保存游戏你就懂了.
保存游戏
我在开发_魔兽争霸_ 之前玩的很多游戏中保存游戏的功能都很糟糕.
所有玩过Origin家的游戏的人都记得写一个保存游戏的文件要多多多多多久. 我的意思是, 没错他们是在微处理器和机械硬盘上工作. 如果用现在的标准的话大概相当于三轮车对赛车. 但是他们也不应该做的这么糟啊, 所以我决定_魔兽争霸_ 一定不能有这种问题.
魔兽争霸 用了一些小技巧来把大块的内存写到硬盘里去, 而不是在内存里弯弯绕绕的找要存储的字节. 一整个单位列表(600个单位乘上每个单位几百个字节) 可以一整块的写进硬盘. 所有不基于指针的全局变量, 游戏内地表和战争迷雾也都可以用类似的方法
但是很奇怪的是, 把这些单位一整块的写进硬盘并没有很大效率的提高写进保存游戏文件的时间, 尽管这极大的简化了我们代码. 这个方法有用主要是因为单位不包含"指针"数据.
之前提到过, 星际争霸 的单位中包含了大量的用链表存起来的成员. 这就导致_星际争霸_ 和_魔兽争霸_ 保存游戏的功能完全不一样了. 我们得把所有链表的指针都整理好(还得特别小心缠在一起的指针), 这样1600个单位的数据才能一次性被写入. 然后你还得把链表重整放回内存才能恢复游戏. 啊呀.
改回去!
所以修正了好多好多链表bug后, 我言辞激烈的辩驳说我们应该改回Storm的链表,即使保存游戏会变得很复杂. 我说"言辞激烈"的时候, 我应该提一下我们那时在暴雪唯一知道的争辩方式就是这样. 一帮年轻, 傲慢的年轻人, 所有争论都是"言辞激烈"的 – 除了讨论那天午饭吃啥, 没人想点单.
我输了那场争论. 既然我们只有"两个月"就要发布了, 往好的方向修改引擎这种动议经常被否决, 取而代之的是一些像创可贴一样现成但不是很好的解决方案. 这导致了很多个月的折磨, 如此痛苦以至于我写(好)代码的能力都受到了影响, 这件事我在第二部分再讨论.
再加点创可贴: 星际争霸 的寻路算法
我还想提另一件事情, 也是我们如何修补漏洞而不是从根本上解决问题的. 当_星际争霸_ 从俯视视角改到斜视视角的时候, 背景渲染引擎从来没变过 – 后者是我在93年四月写的.
用方形渲染引擎渲染斜视纹理也不是那么难, 不过会让地图编辑器这种东西变得难做. 因为在地图上把一层纹理放在另一层上的时候你得把"边缘"修补好, 因为地图编辑器会试着去摆放横平竖直的图片, 但你的内容却是斜的.
总的来说渲染也不是很糟糕, 寻路则变得非常困难. 以前我们有大块的纹理(32 x 32像素), 这些纹理亦或是能经过或是不能经过. 但是现在地图要被划分成8x8像素的小纹理块, 寻路的压力就大了16倍. 另外大型单位如果不能挤进一条小路的话也给寻路造成了麻烦.
Brian Fitzgerald是个优秀的程序员, 若不是他我们的游戏可能无限期跳票. 毕竟寻路问题才是整个项目最后一个完成的部分. 我打算另写一些_星际争霸_ 的寻路问题, 因为这里面有很多有趣的技术和设计细节.
第一部分结语
你已经听我抱怨了好多关于做_星际争霸_ 有多难的事情了. 搞这么复杂主要是因为游戏的方向也好, 技术和设计也好, 每个层面, 每个方向决策都很糟糕.
很幸运我们的团队经常蛮干但不受挫折, 而最终带我们走向成功的是我么你的洞察力. 最后我们停了下来, 游戏能发布的时候就不在添加新的特性, 玩家也没看到游戏内部糟糕的代码运行. 也许这是编译型语言比JavaScript这种解释型语言的好处吧: 用户根本不知道内部已经乱成一坨了.
在这篇文章的第二部分我回去讲一些更加技术的部分. 我会聊聊为什么大部分程序员都搞不定链表, 举出一个在暗黑破坏神, 战网和激战里用的成功方案.
而即使你不用链表, 同样的思路也能用到更复杂的数据结构离去, 诸如哈希表, B树, 优先队列这类的. 更进一步的是, 我相信底层的思维方法可以泛化到所有编程工作中. 但是先别高兴的太早, 那是另一篇文章了.
感谢你能读到现在, 抱歉我还没搞明白怎么写的简明扼要.