Programming

[2012] StarCraft 的開發歷史


作者: onelife (旺來) 看板: GameDesign
標題: Fw: [新聞] StarCraft 的開發歷史
時間: Wed Sep 12 21:32:27 2012

※ [本文轉錄自 StarCraft 看板 #1GJVm97_ ]

作者: zabiak (zabiak) 看板: StarCraft
標題: Re: [新聞] StarCraft 的開發歷史
時間: Mon Sep 10 22:41:10 2012

首先感謝LCamel分享這篇有趣的文章,我嘗試翻譯了這包含星海爭霸的由來、開發

過程、軟體工程及程式開發等面向的故事,與大家分享,其中的翻譯錯誤,也請大家不吝

指正,謝謝

原文連結:

Tough times on the road to Starcraft

原文及翻譯:

Tough times on the road to Starcraft

那段邁向"星海爭霸之道"的艱苦時光

by Patrick Wyatt

I’ve been writing about the early development of Warcraft, but a recent blog
post I read prompted me to start scribbling furiously, and the result is this
three-part, twenty-plus page article about the development of StarCraft, along
with my thoughts about writing more reliable game code. I’ll be posting the
latter parts over the next several days.

This post: Why StarCraft crashed frequently during development
Part 2: How we could have fixed the most common causes
Part 3: Explaining the implementation details of the fix

我已經寫了一些關於魔獸爭霸早期開發的相關文章,但是最近我讀到一篇部落格文章,促
使我振筆疾書,結果就是這分成三部分、二十多頁關於開發星海爭霸的文章,並包含一些
我對於撰寫可靠遊戲程式碼的想法。我將在接下來的幾天發表其餘的部分

此篇文章:為什麼星海爭霸在開發階段頻繁的死當
第二部分:我們如何修正時常造成死當的原因
第三部分:詳述關於修正的實作細節

The beginnings of StarCraft

During the development of StarCraft, a two and a half year slog with over a
year of crunch time prior to launch, the game was as buggy as a termite nest.
While its predecessors (Warcraft I and II) were far more reliable games than
their industry peers, StarCraft crashed frequently enough that play-testing
was difficult right up until release, and the game continued to require ongoing
patching efforts post-launch.

Why? There were sooooo many reasons.

星海爭霸之始

在星海爭霸推出前的開發階段(包含兩年半長時間的艱苦工作以及超過一年的收尾),遊戲
中的臭蟲多到像是白蟻巢穴一樣。相比於運作穩定度剩過其他同業的前作(魔獸爭霸及魔獸
爭霸二),星海爭霸實在太常死當,甚至直到釋出前的試玩測試都難以進行,在推出後更需
要持續不斷的補丁修正。

為什麼?有太太太太太多原因了。

Orcs in space

StarCraft was originally envisioned as a game with modest goals that could fit
into a one-year development cycle so that it could be released for Christmas,
1996.

The project leadership was comprised of the same folks who had started
Shattered Nations (video), a turn-based strategy game along the lines of X-COM
that Blizzard announced in May 1995 but canceled some months later.

The team members were regrouped to build something that could reach market
quickly so Blizzard wouldn’t have a long gap between game launches.

Q4 1994 – Warcraft
Q4 1995 – Warcraft II
Q4 1996 – planned ship date for StarCraft
Q2 1998 – actual ship date for StarCraft

The decision to rush the game’s development seems ludicrous in retrospect, but
Allen Adham, the company’s president, was under pressure to grow revenue.
While Blizzard’s early games had been far more successful than expected, that
just raised expectations for future growth.

Given a short timeframe and limited staff, the StarCraft team’s goal was to
implement a modest game – something that could best be described as “Orcs in
space". A picture from around the time of the E3 game show in Q2 1996 shows the
path the game team originally chose:

But a higher priority project overshadowed StarCraft and stole its developers
one by one. Diablo, a role-playing game being developed by Condor Studios in
Redwood City California, was in need of additional help. Condor, a company
formed by Dave Brevik along with Max Schaefer and his brother Erich Schaefer,
was given a budget of only $1.2 million – ridiculously small even in those
days.

The Condor team had no hope of making the game they aspired to build, but
they did such ground-breaking work in developing something fun that it made
sense for Blizzard to acquire Condor, rename it Blizzard North, and start
pouring in the money and staff the game really deserved.

Initially Collin Murray, a programmer on StarCraft, and I flew to Redwood City
to help, while other developers at Blizzard “HQ" in Irvine California worked on
network “providers" for battle.net, modem and LAN games as well as the
user-interface screens (known as “glue screens" at Blizzard) that performed
character creation, game joining, and other meta-game functions.

As Diablo grew in scope eventually everyone at Blizzard HQ – artists,
programmers, designers, sound engineers, testers – worked on the game until
StarCraft had no one left working on the project. Even the project lead was
co-opted to finish the game installer that I had half-written but was too busy
to complete.

After the launch of Diablo at the end of 1996, StarCraft development was
restarted, and everyone got a chance to see where the game was headed, and it
wasn’t pretty. The game was dated, and not even remotely impressive,
particularly compared to projects like Dominion Storm, which looked great in
demos at E3 six months before.

The massive success of Diablo reset expectations about what Blizzard should
strive for: StarCraft became the game that defined Blizzard’s strategy of
not releasing games until they were ready. But a lot of pain had to occur along
the way to prove out this strategy.

太空獸族

星海爭霸的初始預想是相當簡單的,符合一年的開發週期,並可在1996年的聖誕檔期推出

專案負責人是由"破碎的國度(影片)"團隊成員組成, 破碎的國度是暴雪在1995年5月發表
的回合制戰略遊戲,此專案在幾個月之後被腰斬。

團隊成員則進行重組,預計可在短時間內作出些什麼並推出,使得暴雪不會在各遊戲的上
市日期之間有太大的空窗期。

1994年第4季 – 魔獸爭霸
1995年第4季 – 魔獸爭霸2
1996年第4季 – 預計的星海爭霸出貨日期
1998年第2季 – 實際的星海爭霸出貨日期

現在回想起來,加快遊戲的開發腳步似乎荒唐可笑,但是公司總裁Allen adham承受著增
加公司營收的壓力,尤其是當暴雪早先推出的遊戲出乎預期的成功,更加深了對於公司未
來成長的期待。

在緊湊的時間表以及有限的人力下,星海爭霸團隊的目標是實作出一個簡單的遊戲 – 一
個稱之為"太空獸族"的遊戲。一張於1996年第2季左右的E3展覽會發布圖片可以看出遊戲
團隊最初決定的走向。

但是一個更高優先權的專案凌駕於星海爭霸之上,並把開發成員一個接一個"偷"走了。暗
黑破壞神,一個由位於加州Redwood市Condor Studio所開發的角色扮演遊戲,正處於需要
額外幫助的狀態。Condor,一家由Dave Brevik、Max Shaefer以及Erich Schaefer兄弟創
立的公司,僅編列120萬美元的預算 – 即使在那時候,也可以說是少得可憐。

Condor團隊並沒有辦法作出他們想要作出的遊戲,但是他們仍作出一些具開創性且有趣的
東西,促使暴雪收購它,更名為Blizzard North,並開始投入開發此遊戲實際上需要的資
金及人力。

最初,我跟Collin Murray(星海爭霸的程式設計師)飛到Redwood市去幫忙,後來,包括
加州Irvine暴雪總部的battle.net網路服務提供人員,數據機及區域網路遊戲人員,以及
圖型使用者介面(在暴雪稱之為"glue-screen")人員(包括創造角色,加入遊戲以及其他
meta-game的功能),都投入到這個遊戲的開發行列。

暗黑破壞神的開發規模越來越大,最後暴雪總部的每一個人 – 美術人員、程式設計師、
設計師、音效工程師、測試人員,都陸續投入暗黑破壞神的開發工作,最後,沒有任何人
在進行星海爭霸專案的開發工作。甚至連專案負責人都被指派來完成我已經寫到一半,但
忙到無法完成的遊戲安裝程式。

在暗黑破壞神於1996年末推出後,星海爭霸的開發工作才重啟,每一個人得到機會檢視遊
戲的走向,結論是相當糟糕。這遊戲已經過時,甚至無法留下深刻印象,尤其是與像是
Dominion Storm等專案進行比較,其於六個月前的E3進行展示,看起來相當棒。

因為暗黑破壞神的巨大成功,暴雪重新訂定他們所追求的目標:暴雪的策略是,星海爭霸
不應該在沒有準備好的情況下發行。為了達到這個目標,我們可是吃足了苦頭。

Something to prove

With everyone looking critically at StarCraft, it was clear that the project
needed to be vastly more ambitious than our previous ground-breaking efforts
in defining the future of the real-time strategy (RTS) genre with the first two
Warcraft games.

At the time of the StarCraft reboot, according to Johnny Wilson, then Editor
in Chief of Computer Gaming World, the largest-distribution gaming magazine
of that time, there were over eighty (80!!) RTS games in development. With so
many competitors on our heels, including Westwood Studios, the company that
originated the modern RTS play-style, we needed to make something that kicked
ass.

And we were no longer an underdog; with the successes of Warcraft and Diablo
continuing to fill the news we sure wouldn’t be getting any slack from
players or the gaming press. In the gaming world you’re only ever as good as
your last game. We needed to go far beyond what we’d done previously, and that
required taking risks.

需要證明的東西

在每一個人嚴苛地檢視下,很明顯星海爭霸專案需要有更大的雄心壯志,即超過我們之前
兩款魔獸爭霸遊戲(其定義了即時戰略遊戲未來)的開創性成就。

在星海爭霸專案重啟的當下,根據Computer Gaming World(當時發行量最大的遊戲雜誌)
總編Johnny Wilson所言,當時有超過80款即時戰略遊戲正在進行開發,有這麼多的競爭
者,包括Westwood Studios(首創即時戰略遊戲類型的公司),我們需要作出些什麼對對手
迎頭痛擊。

我們已非昔日的無名小卒;我們確信我們並未因報章雜誌充斥著魔獸爭霸及暗黑破壞神的
成功,而怠慢了玩家及遊戲媒體。在遊戲產業,你的評價只來自於你上一個推出的遊戲,
我們需要遠遠超過之前所作,而這代表我們需要冒險。

New faces

Warcraft II had only six core programmers and two support programmers; that
was too few for the larger scope of StarCraft, so the dev team grew to include
a cadre of new and untested game programmers who needed to learn how to write
game code without much mentoring.

Our programming leadership was weak: we hadn’t yet learned how essential it is
to provide guidance to less experienced developers early in the project so they
learn much-needed lessons before the game launches, so it was very much a
sink-or-swim proposition for new Padawans. A big part of the problem was just
how thin we were on the ground – every programmer was coding like mad to meet
goals, with no time for reviews, code-audits, or training.

And not only were there inexperienced junior members on the team, the leader of
the StarCraft programming effort had never architected a shipping game engine.
Bob Fitch had been programming games for several years with great results but
his previous efforts were game ports, where he worked within an existing
engine, and feature programming for Warcraft I and II, which didn’t require
large-scale engine design. And while he had experience as the tech lead for
Shattered Nations, that project was canceled, therefore no validation of its
architectural decisions was possible.

The team was incredibly invested in the project, and put in unheard of efforts
to complete the project while sacrificing personal health and family life. I’ve
never been on a project where every member worked so fiercely. But several key
coding decisions in the project, which I’ll detail presently, would haunt the
programming team for the remainder of the project.

新面孔

魔獸爭霸2只有6個核心程式設計師以及2個支援程式設計師;對於星海爭霸較大的規模來
說,實在是太少了,所以開發團隊增加了新的且未經試用的遊戲程式設計師,這些程式設
計師需要在得不到太多指導的情況下,學習如何寫出遊戲程式碼。

我們的程式設計領導環節相當薄弱:在專案早期,我們還不知道提供缺乏經驗的開發者開
發指南是必需的,導致他們在遊戲推出前的這段時間,學到大量的教訓,就像是對於新的
帕達瓦接受溺水或學會游泳的課題一樣。很大一部分的問題出在時程緊迫 – 導致每一個
程式設計師瘋狂地撰寫程式碼好達到目標,根本沒時間進行檢視、程式碼稽核或是教育訓
練。

不只是團隊中具有沒有經驗的新成員,星海爭霸專案的負責人也沒有商用遊戲引擎架構設
計的經驗。Bob Fitch有多年遊戲程式設計經驗,並伴隨著成功的結果,但是他之前的經
驗為遊戲移植,使用已存在的遊戲引擎,進行魔獸爭霸及魔獸爭霸2的功能程式撰寫,這些
都不需要大型的引擎設計經驗。當他作為破碎的國度主程式設計師時,這個專案後來被腰
斬了,因此並沒有機會驗證他對於架構的決策是否正確。

團隊為這個專案投入令人難以置信,甚至為了完成專案犧牲了個人健康及家庭生活。我從
來沒經歷過一個專案,其中的成員如此的鞠躬盡瘁。但是專案中的幾個主要的程式設計決
策,卻在專案的餘下部分,困擾著程式設計團隊。

Some things have changed

After spending months working to launch Diablo, and further months of cleanup
effort and patching afterwards, I returned to help with the reboot of
StarCraft. I wasn’t looking forward to diving into another bug-fest, but that’s
exactly what happened.

I thought it would be easy to jump back into the project because I knew the
Warcraft code so well – I’d literally worked on every component. I was instead
terrified to discover that many components of the engine had been thrown away
and partially rewritten.

The game’s unit classes were in the process of being rewritten from scratch,
and the unit dispatcher had been thrown out. The dispatcher is the mechanism I
created to ensure that each game unit gets time to plan what it wants to do.
Each unit periodically asks: “what should I do now that I finished my current
behavior?", “should I re-evaluate the path to get where I’m going?", “is there
a better unit to attack instead of the one that I’m targeting now?", “did the
user give me a new command?", “I’m dead, how do I clean up after myself?, and
so forth.

There are good reasons code needs to be rewritten, but excising old code comes
with risks as well. Joel Spolsky said it most eloquently in Things You Should
Never Do, Part I:

It’s important to remember that when you start from scratch there is absolutely
no reason to believe that you are going to do a better job than you did the
first time. First of all, you probably don’t even have the same programming
team that worked on version one, so you don’t actually have “more experience".
You’re just going to make most of the old mistakes again, and introduce some
new problems that weren’t in the original version.

The Warcraft engine had taken months of programming effort to get right, and
while it needed rework for new gameplay features, a fresh programming team
was now going to spend a great deal of time relearning lessons about how and
why the engine was architected the way it was in the first place.

那些改變的事情

在為了暗黑破壞神上市工作了幾個月,以及之後幾個月的收尾及後來的補丁,我重返崗位
回到星海爭霸重啟的計畫。我沒有預料到我會掉入另一個臭蟲宴會,但它就是發生了。

我以為回到專案工作是容易的,因為我對於魔獸爭霸的程式碼的理解相當透徹 – 事實上
,我可以對每一個元件進行開發工作。取而代之的是,我嚇了一大跳,因為許多遊戲引擎
的元件已經被棄之如屣或經過部分改寫。

遊戲的單位類別被重新改寫,而單位調度機制則已被丟棄。調度機制是由我創造,使得每
一個遊戲單位取得時間並計畫它想要作什麼。每一單位週期性地詢問:"我已經完成我現在
的行為,現在該作些什麼?","我需要重新評估路徑以到達我要去的地方嗎?","有比目
前我瞄準的單位更好的攻擊目標嗎?","玩家有給我新的命令嗎?""我已經死了,我該怎
麼把自己清除呢?" 等等

有合理的理由說明程式碼需要被改寫,但是除去舊的程式碼同樣具有風險。Joel Spolsky
在"你絕對不應該作的事之一"文章中大聲疾呼:

“你一定要記住,想要從頭開始時,請不要抱著這次會做得比第一次好的想法。首先,你
的程式團隊根本不可能和當初相同,所以並不會真的有"更多的經驗"。其實只會把大部分
的舊錯誤重新再犯一次,並且再多增加一些舊版本所沒有的新問題。" (註)

註:摘錄自"約爾趣談軟體(Joel On Software)    Joel Spolsky 著    梅普華 譯
悅之文化 出版

魔獸爭霸引擎花了幾個月的工作量才使得它正常運作,並需要額外的工作增加嶄新的遊戲
功能。現在,新的程式設計團隊需要先花好大一番功夫重新瞭解,遊戲引擎如何及為什麼
如此的建構。

Game engine architecture

I wrote the original Warcraft engine for Microsoft DOS in C using the Watcom
Compiler. With the switch to releasing on Microsoft Windows, Bob chose to use
the Visual Studio compiler and re-architected the game engine in C++. Both were
reasonable choices but for the fact that – at that point – few developers on
the team had experience with the language and more especially with its many
pitfalls.

Though C++ has strengths it is easy to misuse. As Bjarne Stroustrup, the
language’s creator, so famously said: “C makes it easy to shoot yourself in
the foot; C++ makes it harder, but when you do it blows your whole leg off."

History tells us that programmers feel compelled to try every feature of their
new language during the first project, and so it was with class inheritance in
StarCraft. Experienced programmers will shudder when seeing the inheritance
chain that was designed for the game’s units:

CUnit < CDoodad < CFlingy < CThingy

CThingy objects were sprites that could appear anywhere on the game map, but
didn’t move or have behaviors, while CFlingys were used for creating particles;
when an explosion occurred several of them would spin off in random directions.
CDoodad – after 14 years I think this is the class name – was an uninstantiated
class that nevertheless had important behaviors required for proper functioning
of derived classes. And CUnit was layered on top of that. The behavior of units
was scattered all throughout these various modules, and it required an
understanding of each class to be able to accomplish anything.

And beyond the horror of the class hierarchy, the CUnit class itself was an
unholy mess defined across multiple header files:

class CUnit … {
#include “header_1.h"
#include “header_2.h"
#include “header_3.h"
#include “header_4.h"
};
Each of those headers was several hundred lines, leading to an overall class
definition that could at best be called amusing.

It wasn’t until many years later that the mantra “favor composition over
inheritance" gained credence among programmer-kind, but those who worked on
StarCraft learned the hard way much earlier.

遊戲引擎架構

我使用微軟DOS平台、C語言及Watcom編譯器來撰寫原本的魔獸世界引擎。為了釋出到到微
軟視窗作業系統的轉變,Bob選擇使用Visual Studio編憶器,並使用C++重新架構遊戲引擎
。這兩者皆是合理的選擇,但在那個時候,事實上,團隊中只有少數的開發者具有使用此
種語言進行開發的經驗,更遑論此語言中蘊含的許多陷阱。

C++有其長處,但也容易被誤用。就像C++之父Bjarne Stroustrup的名言:
“使用C語言,很容易就搬起石頭砸自己的腳;使用C++,變得沒這麼容易,但是一旦你這
麼作,你整條腿都要報銷"

歷史告訴我們,程式設計師在使用新的語言進行第一個專案開發時,覺得有必要嘗試新語
言的每一個特徵,這體現在星海爭霸的類別繼承。有經驗的程式設計師在看到為了遊戲單
位設計的繼承鍊時,會感到不寒而慄。

CUnit < CDoodad < CFlingy < CThingy

CThingy物件在遊戲地圖中無所不在,但並不移動或具有行為。CFlingy用在創造微粒,當
爆炸發生時,許多CFlingy以隨機方向分散開來。CDoodad – 在過了14年之後,我想這是
一個類別名稱 – 是一個未具現化類別。CUnit則是最高層級的類別。單位的行為被分散在
這些各種不同的模祖中,這需要對每一個類別都有深刻的瞭解,才能夠完成任何事情。

除了這恐怖的類別階層,CUnit類別本身簡直是亂七八糟,搞得天怒人怨,其定義包含了
多個標頭檔:

class CUnit … {
#include “header_1.h"
#include “header_2.h"
#include “header_3.h"
#include “header_4.h"
};
其中的每一個標頭檔都有好幾百行,導致整個類別定義就像是整人大爆笑。

在多年之後,有一句在程式設計師間口耳相傳的口訣如是說"優先使用組合而非繼承",但
對於在暴雪工作的程式設計師來說,早就已經體驗過"震撼教育"的洗禮了。

We’re only two months from launch

With its troubled early history, after the reboot the development team was
pressured to finish up, and so schedules were bandied about that showed the
game could be launched in two months.

Given the number of game units and behaviors that needed to be added, the
changes necessary to switch from top-down to isometric artwork, a completely
new map editor, and the addition of Internet play over battle.net, it was
inconceivable that the game actually could ship in that time, even assuming
that the art team, designers, sound engineers, game-balancers and testers
could finish their end of the bargain. But the programming team continually
worked towards shipping in only two months for the next fourteen months!

The entire team worked long hours, with Bob working stretches of 40 hours, 42
hours, even 48 hours programming. As I recall no one else attempted these sorts
of masochistic endeavors, though everyone was putting in massive, ridiculous
hours.

My experiences developing Warcraft, with frequent all-nighters coding, and
later Diablo, where I coded fourteen-plus hour days seven days a week for
weeks at a time, suffered me to learn that there wasn’t any point in
all-nighters. Any code submissions [ha! what an appropriate word] written
after a certain point in the evening would only be regretted and rewritten in
the clear light of following days.

Working these long hours made people groggy, and that’s bad when trying to
accomplish knowledge-based tasks requiring an excess of creativity, so there
should have been no surprises about the number of mistakes, misfeatures and
outright bugs.

Incidentally, these sorts of crazy hours weren’t mandated – it was just the
kind of stuff we did because we wanted to make great games. In retrospect it
was foolish – we could have done better work with more reasonable efforts.

One of my proudest accomplishments was to ship four Guild Wars campaigns in a
two-year window without leading the development team down that dark path.

離推出只有兩個月

其多災多難的早期歷史,以及自計畫重啟後開發團隊就面臨早日完工的壓力,所以時程規
劃也是急就章,要在兩個月內讓遊戲上市。

增加大量的遊戲單位及其行為,需要從鳥瞰圖變成立體投影圖,全新的地圖編輯器,可以
透過battle.net進行網路對戰,在在都凸顯準時上市是不可能的任務,這還是在沒有把跟
美術團隊、設計師、音效工程師、遊戲平衡制定人員以及測試人員的"吵架大會"列入考慮
的情況下。但是程式設計團隊仍持續不斷地工作,想要在短短的兩個月內推出這款遊戲,
但最終我們花了14個月才達到這個目標。

整個團隊工時過長,Bob不間斷地撰寫程式整整40小時、40小時,甚至48小時。在我的回
憶裡,沒有其他人像他如此地燃燒小宇宙,但是每一個人的工時都長得離譜。

在我開發魔獸爭霸以及暗黑破壞神的經驗裡(頻繁的通宵達旦地撰寫程式,每天工作超過
14小時,每週工作7天),讓我知道徹夜工作是毫無意義的。所有在深夜完成的"鬼斧神工"
,在接下來的日子裡都會現出原形,而需要砍掉重練。

長時間的工作會使人們腦筋不清楚,這對於需仰賴大量創造力的腦力密集型工作來說,簡
直是糟糕透頂,所以產生大量錯誤,功能缺失,以及顯而易見的臭蟲,也就不令人意外了

順帶一提,這種瘋狂的工時是不必要的,之所以這麼作的原因,是因為我們想要作出好遊
戲。回顧過去,我們當時真是犯傻,只有在合理的工時下,才可以完成品質更好的作品。

我一生最驕傲的事,就是激戰在推出遊戲及三款資料片這為期兩年的時間中,我沒有引領
開發團隊再次走上那充滿荊棘的道路。

The most common cause of StarCraft game crashes

While I implemented some important features in StarCraft, including fog-of-war,
line-of-sight, flying unit pathing-repulsion, voice-chat, AI reinforcement
points, and others, my primary job gravitated to fixing bugs.

Wait: voice-chat! In 1998?!? Yeah: I had it all working in December 1997. I
used a 3rd-party voice-to-phoneme compressor, and wrote the code to send the
phonemes across the network, decompress them, and then play them back on the
other seven players’ computers.

But every single sound-card in our offices required a driver upgrade to make
it work, if the sound card was even capable of full-duplex sound (simultaneous
recording and playback of sounds), so I regretfully made the recommendation to
scrap the idea. The tech-support burden would have been so high that we would
have spent more money on game support than we would have made selling the game.

So anyway I fixed lots of bugs. Some of my own, sure, but mostly the elusive
bugs written by other tired programmers. One of the best compliments I’ve
received came just a few months ago, when Brian Fitzgerald, one of two best
programmers I’ve had occasion to work with, mentioned a code-review of
StarCraft; they were blown away by how many changes and fixes I had made over
the entire code-base. At least I got some credit for the effort, if only well
after the fact!

Given all the issues working against the team, you might think it was hard to
identify a single large source of bugs, but based on my experiences the
biggest problems in StarCraft related to the use of doubly-linked linked
lists.

Linked lists were used extensively in the engine to track units with shared
behavior. With twice the number of units of its predecessor – StarCraft had
a maximum of 1600, up from 800 in Warcraft 2 – it became essential to optimize
the search for units of specific types by keeping them linked together in
lists.

Recalling from distant memory, there were lists for each player’s units and
buildings, lists for each player’s “power-generating" buildings, a list for
each Carrier’s fighter drones, and many many others.

All of these lists were doubly-linked to make it possible to add and remove
elements from the list in constant time – O(1) – without the necessity to
traverse the list looking for the element to remove – O(N).

Unfortunately, each list was “hand-maintained" – there were no shared
functions to link and unlink elements from these lists; programmers just
manually inlined the link and unlink behavior anywhere it was required. And
hand-rolled code is far more error-prone than simply using a routine that’s
already been debugged.

Some of the link fields were shared among several lists, so it was necessary
to know exactly which list an object was linked into in order to safely
unlink. And some link fields were even stored in C unions with other data
types to keep memory utilization to a minimum.

So the game would blow up all the time. All the time.

造成星海爭霸死當的原兇

我實作星海爭霸中一些重要的功能,包括視野範圍限制、視野、飛行單位的路徑互斥、語
音聊天、人工智能集節點,以及其他功能,但我最主要的工作其實是修正臭蟲。

等一下,在1988年實作語音聊天功能?沒錯,一切都在1997年12月大功告成。我使用第三
方開發的聲音-音素轉換壓縮工具,並撰寫了在網路上傳輸音素的程式碼,以及解
壓縮功能,接著在其他七位玩家的電腦播放。

但是我們辦公室的每一張支援全雙工(同時錄音並播放聲音)的音效卡,都需要更新驅動程
式才可以使用這項功能,只能說遺憾,這點子只得被束之高閣。因為提供技術支援的金錢
負擔將會相當巨大,超過我們賣出遊戲的營收所得。

我修正了相當多的臭蟲,一些當然是我造成的,但是大部分難以發現的臭蟲是由其他疲憊
不堪的程式設計師所撰寫的。幾個月前,Brian Fitzgerald(他是我合作過的程式設計師中
最好的兩位其中之一)對星海爭霸進行程式碼檢視後,給予我極高的讚譽,可以說是我這輩
子所得到最好的。我對整個程式碼經過許多變更及修正,臭蟲被一網打盡。至少我的努力
得到肯定,而事實也是如此!

由於橫亙在開發團隊面前的所有問題,你可能認為在龐大的程式碼中很難找出臭蟲,但是
根據我的經驗,星海爭霸最大的問題其實來自於使用了雙向鏈結串列。

鏈結串列在引擎中被廣泛地始用,用來記錄單位及其共享行為。魔獸爭霸2的單位數目有
800個,但星海爭霸最多有1600個,整整增加了一倍。這使得我們必需對尋找特定類型的單
位這件事進行優化,方法是將他們鏈結在一起存放於串列中。

回顧遙遠的記憶,有很多用來儲存玩家的單位及建築的串列,很多用來儲存每個玩家"發
電"建築的串列,一個儲存每一架航空母艦無人戰鬥機的串列,以及其他很多很多其他的串
列。

所有的串列都是雙向鏈結的,使得我們可以在常數時間(O(1))裡新增及移除節點,而不需
要搜尋整個串列找到欲移除的節點(O(N))。

不幸的是,每個串列都是"手工維護"的 – 沒有共用的函式去鏈結及取消鏈結這些串列,程
式設計師全憑手動在需要鏈結及取消鏈結的地方加入行內函式。手工程式碼遠比使用已經
過除錯的常式來的容易出錯。

有些鏈結欄位是由多個串列共享,所以必須要確切知道這個物件被哪些串列鏈結,好安全
地移除鏈結。一些鏈結欄位使用C語言的union型別儲存,可以最小化記憶體的使用。

總的來說,這個遊戲總是死當,履試不爽。

But why did you do it that way?

Tragically, there was no need for these linked-list problems to exist. Mike
O’Brien, who, along with Jeff Strain, cofounded ArenaNet with me, wrote a
library called Storm.DLL, which shipped with Diablo. Among its many features,
storm contained an excellent implementation of doubly-linked lists using
templates in C++.

During the initial development of StarCraft, that library was used. But early
in the development the team ripped out the code and hand-rolled the linked-lists
, specifically to make writing save-game files easier.

Let me talk about save games for a second to make this all clearer.

但是為什麼你們要這麼作呢?

一切都是悲劇阿!其實這些鏈結串列問題根本就不該存在。我跟Mike O’Brien及Jeff
Strain(後來共同成立ArenaNet公司)撰寫了一個叫作Storm.DLL的函式庫,與暗黑破壞神一
起出貨。在Storm眾多的功能中,有一個卓越的雙向鏈結串列的實作,是我們使用C++中的
範本功能撰寫出來的。

在星海爭霸最初的開發階段,我們使用這個函式庫。但是在早期開發階段,開發團隊將這
程式碼刪去,並手工處理鏈結串列,為的是讓遊戲存檔時的寫檔比較容易。

讓我們接著談談遊戲存檔好讓一切明朗。

Save games

Many games that I played before developing Warcraft had crappy save-game
functionality. Gamers who played any game created by Origin will remember how
looooooong it took to write save-game files. I mean sure, they were written
by slow microprocessors onto hard-drives that – by today’s standards – are
as different as tricycles and race cars. But there was no reason for them to
suck, and I was determined that Warcraft wouldn’t have those problems.

So Warcraft did some tricks to enable it to write large memory blocks to disk
in one chunk instead of meandering through memory writing a bit here and
there. The entire unit array (600 units times a few hundred bytes per unit)
could be written to disk in one chunk. And all non-pointer-based global
variables could similarly be written in one chunk, as could each of the
game-terrain and fog-of-war maps.

But oddly enough, this ability to write the units to disk in one chunk wasn’t
essential to the speed of writing save game files, though it did drastically
simplify the code. But it worked primarily because Warcraft units didn’t
contain “pointer" data.

StarCraft units, which as mentioned previously contained scads of pointers in
the fields for linked lists, was an entirely different beast. It was necessary
to fixup all the link pointers (taking special care of unioned pointer fields)
so that all 1600 units could be written at once. And then unfixup the link
pointers to keep playing. Yuck.

儲存遊戲

在我開發魔獸爭霸之前,我玩過許多遊戲,他們的遊戲存檔功能都很糟糕。玩家玩任何由
Origin出品的遊戲,都會記得他們需要花費多久的時間存檔。我的意思是,他們使用速度
慢的微處理器對硬碟進行寫入的動作,以現在的標準來看,就像是拿三輪車與賽車作比較
。但是,仍然沒有理由會爛成這樣,所以我暗自決定,這些問題絕不會出現在魔獸爭霸裡

魔獸爭霸使用了一些小技巧,讓他可以一次將一大塊記憶體區塊寫入硬碟,而不是緩慢地
透過記憶體一個bit一個bit的進行寫入。整個單位陣列(600個單位乘上幾百個byte),可以
一次寫入硬碟。所有非指標的全域變數,像是每一個遊戲地形及視野範圍限制地圖,可以
用類似的方法一次寫入。

奇怪的是,這個將單位一次寫入硬碟的能力,並不是提升遊戲存檔寫檔速度的決定性因素
,但仍顯著地簡化了程式碼。而魔獸爭霸單位並不包含指標資料,透過一次寫入,效果則
相當明顯。

如前所述,星海爭霸單位儲存於具有指標的鏈結串列欄位中,完全是不同的挑戰。必須要
修復所有的鏈結指標(使用特別手法處理union類型指標欄位),使得所有1600單位可以一次
寫入。接著反修復這些鏈結指標,使得可以繼續進行遊戲。啐!

Change back!

So after fixing many, many linked list bugs, I argued vehemently that we should
switch back to using Storm’s linked lists, even if that made the save-game code
more complicated. When I say “argued vehemently", I should mention that was
more or less the only way we knew how to argue at Blizzard – with our youthful
brashness and arrogant hubris, there was no argument that wasn’t vehement
unless it was what was for lunch that day, which no one much wanted to decide.

I didn’t win that argument. Since we were only “two months" from shipping,
making changes to the engine for the better was regularly passed over for
band-aiding existing but sub-optimal solutions, which led to many months of
suffering, so much that it affected my approach to coding (for the better) ever
since, which is what I’ll discuss in part two of this article.

給我改回來!

在修正了相當多的鏈結串列臭蟲後,我激烈地爭論我們應該回頭使用Storm的鏈結串列,
縱使這會讓遊戲儲存的程式碼更加複雜。當我說"激烈地爭論",我應該或多或少提一下,
在暴雪裡進行爭論的唯一已知方法,就是憑藉著年輕人的自以為是以及傲慢自大。唯一不
激烈的爭論是,討論當天午餐該吃些什麼,因為沒人想作決定。

我並沒有贏得這場爭論。因為我們距離出貨只剩"兩個月",對引擎進行變更比較好的方法
是,經常對現有但並不完美的解決方案貼OK蹦,這導致多個月的水深火熱,並造就我使用
更好的方法來撰寫程式,我將在本文的第二部分進行討論。

More Band-Aids: path-finding in StarCraft

I wanted to mention one more example of patching over bugs instead of fixing
the underlying problem: when StarCraft switched from top-down artwork to
isometric artwork, the background tile-graphics rendering engine, which dated
back to code I had written in 1993/4, was left unchanged.

Rendering isometric-looking tiles using a square tile engine isn’t hard, though
there are difficulties in getting things like map-editors to work properly
because laying down one map tile on another requires many “edge fixups" since
the map editor is trying to place diagonally-shaped images drawn in square
tiles.

While rendering isn’t so bad, isometric path-finding on square tiles was very
difficult. Instead of large (32×32 pixel) diagonal tiles that were either
passable or impassable, the map had to be broken into tiny 8×8 pixel tiles –
multiplying the amount of path-searching by a factor of 16 as well as creating
difficulties for larger units that couldn’t squeeze down a narrow path.

Had Brian Fitzgerald not been a stellar programmer, the path-finding problem
would have prevented the game from launching indefinitely. As it was pathing
was one of the problems that was only finalized at the end of the project. I
plan to write more about path-finding in StarCraft because there are lots
interesting technical and design bits.

更多的OK蹦: 星海爭霸的路徑搜尋

我想再舉一個例子關於寧可使用補丁修正臭蟲,也不要嘗試去修正底下的問題。當星海爭
霸從鳥瞰圖喘變成立體投影圖,背景的砌塊式圖像繪圖引擎可追溯至我在1993/1994年撰
寫的程式碼,分毫未改。

使用方型砌塊繪出立體投影的砌塊並不困難,但要讓地圖編輯器正常運作仍有相當的難度
,因為將一地圖砌塊放在另一個砌塊上面,需要大量的"邊緣修復",因為地圖編輯器嘗試
將對角線形狀的圖像繪於方型砌塊上。

繪圖沒那麼糟糕,在方型砌塊上的立體投影路徑搜尋非常困難。不使用分成可通過及不可
通過大的(32×32像素)對角線砌塊,地圖是以小的8×8像素組成 – 使得路徑搜尋以16倍的
數量級成長,而且造成較大的單位沒有辦法擠進狹窄的路徑。

要不是Brian Fitzgerald是一位一流的程式設計師,本來路徑搜尋的問題將使得這款遊戲
永遠無法上市,路徑問題直到專案收尾階段才解決。我計畫寫更多有關星海爭霸的路徑搜
尋的內容,因為在技術上或設計上都相當有趣。

End of part 1
So you’ve heard me whine a bit about how difficult it was to make StarCraft,
largely through poor choices made at every level of the company about the
game’s direction, technology and design.

We were fortunate to be a foolhardy but valiant crew, and our perspicacity
carried the day. In the end we buckled down and stopped adding features long
enough to ship the game, and players never saw the horror show underneath.
Perhaps that’s another benefit of compiled languages over scripted ones like
JavaScript – end users never see the train wreck!

In part two of this article I’m going to get even more technical and talk
about why most programmers get linked lists wrong, then propose an alternative
solution that was used successfully for Diablo, battle.net and Guild Wars.

And even if you don’t use linked-lists, the same solutions carry over to more
complex data structures like hash tables, B-trees and priority queues.
Moreover, I believe the underlying ideas generalize well to all programming.
But let’s not get ahead of ourselves; that’s another article.

Thanks for reading this far, and sorry I haven’t yet discovered how to write
concisely.

filed under: game design, programming tagged with: starcraft

第一部分的結尾

關於製作星海爭霸有多困難這件事,你已經聽我大吐苦水,很大一部分是因為公司的每一
個層級對於遊戲方向、科技以及設計,作了錯誤的選擇。

我們很幸運我們是一支鐵頭又強悍的團隊,且我們的洞察力讓我們贏得最後的勝利。在收
尾階段,我們繼續埋頭苦幹,並停止增加新功能,確定遊戲時間夠長,可以推出了。玩家
絕不會發現底下發生的恐怖事情,或許這是編譯式語言另一個勝過像是Javascript這種腳
本語言的地方 – 終端使用者絕不會看見火車失事!

在這篇文章的第二部分,我將會談論更多技術性的話題,並講述為什麼大部份的程式設計
師總是把鏈結串列搞砸了,接著提出成功使用於暗黑破壞神、battle.net以及激戰的另一
種解決方案。

即使你不使用鏈結串列,相同的解決方案甚至會使用更複雜的資料結構,像是雜湊表、
B樹以及優先佇列。我相信基本思想足以概括所有的程式設計面向。但讓我們慢慢來,那屬
於另一篇文章的內容。

謝謝你讀到這裡,很抱歉我還不知道如何寫得簡單扼要。


※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.232.70
※ 編輯: zabiak          來自: 111.251.232.70       (09/10 22:42)
推 dl4303:推                                                       09/10 22:42
推 std94003:推推                                                   09/10 22:47
推 doom3:END推                                                     09/10 22:50
推 KYPKYPKYP:學過程式推  好猛阿~                                   09/10 22:51
推 justastupid:好神 英文也太好了                                   09/10 22:53
推 Vett:看到linked list的死當   真是妙到一個不行                   09/10 22:54
推 huggie:讚讚讚!!                                               09/10 22:55
推 suwilliam:人家是這樣堅持品質(燒錢)反觀國內……難怪被韓國超車  09/10 22:56
推 OSDim:樓上那是員工自主賣命阿,哪有燒錢                          09/10 22:59
→ OSDim:感動                                                      09/10 22:59
推 bbyan:所以在世界末日之前玩不到蟲心了嗎 QQ                       09/10 23:01
推 moongloaming:不解釋了~                                         09/10 23:03
推 derswarm:推 翻得真好                                            09/10 23:05
→ dakkon:蟲心也才剛beta,就算不用六個月.四個月也總是要的           09/10 23:06
推 cji4284503:這麼認真翻譯只能推了QQ 大感謝!!!                     09/10 23:07
推 ck321:好強喔 真想看他們寫的程式 TAT                             09/10 23:07
推 Sechslee:不推不行                                               09/10 23:09
推 crazymagic00:英文推推推推推推推推推推!!!                        09/10 23:09
推 PTTco:CS的只能推了                                              09/10 23:10
推 imunknown:                                                      09/10 23:10
推 VenceYen:同為RD只能淚推…                                      09/10 23:12
推 MaySnow2010:寫得很好,翻譯也很棒!!值得鼓勵,大推!!              09/10 23:13
→ VenceYen:不過現在開發應該會更容易                               09/10 23:13
推 Sechslee:"只有在合理的工時下,才可以完成品質更好的作品。"       09/10 23:18
推 hahahaha5438:星海爭霸之始—>  穩定度"剩"過其他同業的前作       09/10 23:19
推 zseineo:推                                                      09/10 23:19
推 nilson847552:"只有在合理的工時下,才可以完成品質更好的作品。"   09/10 23:20
推 oscarss07:這麼長的翻譯只能推了                                  09/10 23:20
推 Puser:                                                          09/10 23:20
推 jhunfong:推翻譯!!!!                                             09/10 23:23
推 wtao: 原來Diablo 太成功 讓SC1完整了才敢上架@_@                  09/10 23:27
→ wtao:  果真成也Diablo  敗也Diablo                               09/10 23:27
推 Lioli:大推翻譯官                                                09/10 23:29
推 paul81611:推高品質翻譯!                                         09/10 23:35
推 CaTkinGG:推!看到錯誤的設計方向讓之後的臭蟲只能貼OK繃心有戚戚焉  09/10 23:41
推 always123x:專業推                                               09/10 23:43
推 FAlin:翻譯專業推!!                                              09/10 23:45
推 Infernity:超扯!!                                                09/11 00:01
推 aCCQ:推~                                                        09/11 00:05
推 bobjohns:我覺得SC1做的比SC2好 光 音效跟圖 就贏了                09/11 00:19
推 only1032:感謝翻譯                                               09/11 00:22
→ wtao:    BZ 以往的音樂都很用心 幾乎都很有特色獨創               09/11 00:29
推 yuiweq1999:大推翻譯~翻得好好看噢QQ                              09/11 00:39
推 Emerson158:"想要從頭開始時,請不要抱著這次會做得比第一次好的想  09/11 01:30
→ Emerson158:法。"  …有深刻體會過                               09/11 01:31
→ Emerson158:話說這才是有料的工程師阿…                          09/11 01:32
推 jackalin2002:讓我一直想起八掛那篇 講德國人精神跟台灣人精神…   09/11 01:42
推 rssai:SC1真是難以跨越的巨牆~~SC2目前也難以超越                  09/11 04:23
→ photopanda:裡面提到的兩家遊戲公司/工作室都被EA吃掉了,回不來了  09/11 04:52
→ photopanda:萬惡EA還我Origin跟西木頭啊!                         09/11 04:52
推 LZong:原來SC1的程式設計上是這麼可怕的東西…                    09/11 07:43
推 PanXPan:推!                                                     09/11 10:02
推 oceanocean:太不簡單啦~推推                                      09/11 13:44
推 little76d:推翻譯                                                09/11 14:00
推 carlk:推翻譯太強大了= =                                         09/11 14:37
→ OpenSolaris:同是RD幫推,雖然有些還不是看得懂。                  09/11 15:57
推 onelife:好文推~ 原po願不願意也轉錄到GameDesign版?               09/11 19:55
→ zabiak:忘了說  大家可以隨意轉錄  進行交流  但這篇文章應該會被   09/11 21:05
→ zabiak:瘋狂吐槽  因為我沒有任何開發遊戲的經驗  對於電腦繪圖理   09/11 21:06
→ zabiak:論也是一竅不通  XD                                       09/11 21:07
推 losesong:很詳實的心路歷程 推!                                   09/12 11:40
推 Falldog:推                                                      09/12 16:00
推 onelife:感謝同意轉錄~                                           09/12 21:32

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: onelife (114.44.144.207), 時間: 09/12/2012 21:32:27
推 tsl3333:推                                                      09/12 22:55
推 changyin:推                                                     09/12 23:15
推 skyhawkptt:推!!專業翻譯精彩好文                                 09/13 02:03
推 k387259:推哦 原來心路歷程這麼…~~可以讓我轉貼嗎                09/13 03:03
推 Bencrie:原來 Origin 有遊戲存檔很久的特色 XD                     09/13 09:24
→ Bencrie:難怪 Ultima VIII – Pagan 剛出的時候被罵翻了             09/13 09:25
→ Bencrie:Avatar 常常被機關整死,搞得玩家走一小段路就得存檔       09/13 09:26
→ Bencrie:偏偏存檔以當時的硬體來說又存超慢,讓人超不爽 XD         09/13 09:28
推 chenglap:「僅編排 120 元的預算」這句真是令人心痛.               09/13 11:30
→ chenglap:「僅編列 120 萬元預算」                                09/13 11:30
推 tobygameac:他的blog好棒!                                        09/13 11:32
推 chenglap:「甚至犧牲個人的家庭和健康」在我們這邊是基本要求…    09/13 11:34
→ chenglap:就算如此, 我們這邊大規模的企劃預算還不及別人 1/3.      09/13 11:40
推 Ebergies:樓上拍拍 XD                                            09/13 11:55
推 alsh:SC的路徑搜尋居然到上市前才作完 這功能超強的…             09/13 12:07
→ alsh:SC的尋路效果比之後的AOE AOC還好很多                        09/13 12:08
推 dragoni:大推啊!!!!                                          09/13 12:38
推 lf21201:看完推 翻譯推                                           09/13 13:31
推 bachi95:好文推!                                                 09/13 14:31
推 silveriii:push                                                  09/13 16:11
推 a83a83cjcj:推 T^T                                               09/14 15:45
推 lc85301:太厲害了…                                              09/15 22:13

廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s