2010年6月11日 星期五

一個「偽」亂數的演算法

這是前一陣子從 "Game Code Complete" 裡看到的演算法。

說是「偽」亂數,因為它並不夠亂。但是它非常節省效能。

 

需求是這樣:

有某個數量的獎品,我們希望每次亂數取出一個來,不能重複,而且每個都要取到。

演算法是這樣:

假設獎品數量為 member,比 member 大的一個質數為 prime,

首先先取三個亂數 RandomA, RandomB, RandomC

計算

Skip = RandomA * member * member + RandomB * member + RandomC

取得 Skip 數值後,在每次需要取亂數數值時,

nextNumber += Skip

nextNumber %= prime

也就是,每次計算時,把前一次的數值加上 Skip, 然後用這個質數來取餘數, 這樣算出來的 nextNumber 就絕對不會重複。當然餘數可能會比 member 數量還大,那就再計算一次,取下一個。

 

看完之後,霎時間覺得很神奇,一時半刻還想不透,於是用試算表建公式來算,果然,產生了一個不會重複數字的序列。

但是,從這序列也發現了缺點。就是取出來的數值是有某種規律的,而且規律很明顯。不過如果不把數列排出來,也不容易發現就是了。

效能是這個演算法最大的優點,每次取亂數只需要一個加法跟一個取餘數的運算。

 

再深入去看,這演算法還可以多做一些簡化。

Skip 這個數值,只要取小於 prime,大於 0 ( 最好也不要等於 1 ) 的數值就可以,不需要取三個亂數再去加減乘除。

取出的數值的規律是,從第一個取出的 nextNumber 開始,每次遞增 Skip 指定的數量,超過 prime 的時候,再回到 0 繼續算,而之所以會全部都選取到的原因,就是因為質數的特性 -- 只能被 1 與自己整除。

 

這個演算法可以用在什麼地方呢?

分配掉寶當然是不能用啦,這個數列太過規律了。但是任務物品的掉落倒是可以用得上,怪物的重生也可以用,適用的場合應該還不少。

2010年4月29日 星期四

Activision 把金雞母 Infinity Ward 送給 EA 的事件

今天看到了這樣一篇新聞。

38 Infinity Wards employees and ex-employees file class action lawsuit

霎時間,還搞不清楚這到底是什麼,為什麼沸沸揚揚。

於是開始Google搜索。

原來 Infinity Ward 是製作 "決勝時刻:現代戰爭2"的研發公司,母公司是遊戲發行商 Activision Blizzard。

現代戰爭2是2009年非常風光的一款遊戲,怎麼現在鬧出權利金跟獎金的糾紛來了?

 

故事要從今年三月說起。

三月初, Activision 以違約與不服從命令為由,強迫兩個 Infinity Ward 高高層離職。

總裁 Jason West 與執行長 Vince Zampella。

到底這兩人不服從什麼命令,沒人知道,但是猜測是說,Activision 希望他們繼續把現代戰爭繼續製作下去,做個沒完沒了。研發單位當然不肯。

沒想到重演當年在 EA 的 2015工作室一樣的不爽事件。

據說,那時候 2015工作室做了個很賣錢的"榮譽勳章",EA 龍心大悅,希望他們一直做下去,把這個招牌賣到不能再賣為止。結果自然也是不太愉快,帶了幾個人,兩人投靠 Activision。

只不過這次 Activision 更惡劣, 連該給的權利金與獎金,也一直扣著沒發放。

大概是鬧得非常非常不高興,這兩人就離職了。

然後,事件就一發不可收拾。

四月中,同樣也是遊戲發行商的 EA,宣布成立了一個新的工作室,叫做 "Respawn Entertainment",重生。並且由 Jason 與 Vince 兩位來帶領。

隔天,報導說,首席設計師 Mackey McCandlish 與程式設計師 Jon Shiring 從 IW 離職,當時雖未明講,但猜也猜得到,去 Respawn 了,後來也得到了證實。

這兩三週以來, IW 持續失血,老員工成雙成對的離職。人才流失就像潰堤一般,止都止不住。而且流失的人才還大部分都是菁英。首席軟體工程師 Francesco Gigliotti,首席動畫師 Mark Grigsby,首席角色動畫 John Paul Messerly,首席環境美術設計 Chris Cherubini,軟體工程師 Rayme C. Vinson,一堆的『首席』全都跑去了『重生』。

Activision 在這幾週來,悄悄的進行組織重整,也開始對留下來的還忠誠的 IW 員工發放積欠的獎金跟權利金,但終究是喚不回 IW 員工的信任了,失血非但沒止住,IW 員工還給了 Activision 一個暱稱 -- "shit"。

到今天,估計 IW 原先的員工已經有一半離職。Activision 調動了其他工作室的人到 IW 裡,希望維持住產品的開發運作,但想也知道,基本上起不了什麼作用。

Activision 的某個高層,前幾天也辭去了職務 ( 不過還是以類似顧問的身分留著 ),沒講理由,大概是辭職以示負責。有人毒舌的說,「不會也是要去Respawn吧?」

 

故事寫到這邊。

IW 的兩個頭子真正的離職原因是什麼很難說,也有人說是他們打算把現代戰爭這個招牌賣到別的發行商手上才被開除,但是會引發後面一連串的『首席』離職,Activision 也必有虧欠員工之處。我想權利金與獎金發放的太不乾脆,應該會是主因之一。

不管怎麼說,這一場風波下來, EA 這個風評也不甚好的發行商,光是躺著就能撿到一整隊的金雞母,還不只是一兩隻而已。

天上掉下來的會生金蛋的母雞,誰不帶回家?

現在, EA 說的很漂亮了,完全不會干涉他們開發的內容,未來也會盡全力去發行遊戲...

Activision 一個錯誤的決定,把白花花的美金平白的又還給了 EA。EA 應該是暗爽在心裡吧?

(Update : 又看到幾篇精彩的歷史,修改了一些...)

2010年4月2日 星期五

一年一度的愚人節歡樂日

愚人節是很歡樂的日子。

Blizzard 依照慣例出了好幾道搞笑的假新聞,國內的遊戲公司也有的開始玩起來了。

Google 照例還是玩很大。

MLB 也有一堆假新聞。

今天看到一個說法是,「愚人節是 IT 產業的國定假日」。

同事說,那我們應該放假一天的呀...

來轉貼個歡度愚人節總整理好了。

剛剛在 GameDev.net 上,看到 The Daily GameDev.net 編輯所寫的一段,算是最好的註解。

他寫,

If you're expecting news from today well, you can forget about it. I refuse to look at any headlines today because... well, if you don't know than you deserve what you get :P

他「拒絕」在今天看任何的頭條新聞...

2010年3月26日 星期五

My GDC 2010 (Day 5)

GDC 最後一天。下午上完課,晚上就要到機場去,很操...

Day 5

第一堂課,本來要參加一個滿有意思的課程,但是,由於出發得較晚,結果因為人數已滿而進不去。( 我又要抱怨這糟糕的課程安排了... )

跑去聽了一場比較另類的題目,"Paint-by-Gender: How to Add Pink Gameplay to Your 'Blue' Title (and Still Keep All the Boys Happy)"。

意思是,如何讓你的遊戲可以受女生歡迎,男生也不會太反感。

底下有Check-List

Female-Friendly Checklist

1. Detailed backstory for characters and the world

2. Major female character(s), non-stereotypical

3. In-game relationships, especially ones the player can affect

4. Emotional moments

5. Moral complexity in characters and situations

6. Opportunities for non-violent action

7. Gameplay variety that creates strategic options

8. Important choices

9. Meaningful victory condition

其實說穿了,就是要多一點的Fu,少一點暴力,女性角色不要只是花瓶...

第二堂課,去聽了模擬市民3,講述他們怎樣去模擬遊戲中的每個小人。

感覺上就是,這是一個很龐大的資料驅動式系統,每個小人有 motives, traits, long-term progression, production rules, …

還看到了一個2D Top-view,專門用來測試小人的生活狀況的測試工具...

今天下午,GDC 到 1600 就結束,下午課程只有兩場。

下午第一場去聽的是,"The Rendering Tools and Techniques of Splinter Cell: Conviction"。

內容主題好幾個,Occlusion Query, Cascaded Shadow Map ( 啊...又見到它了... ), SSAO…

他們用的Occlusion Query方法,是改良過的 Hierarchical Z buffer。效果還不錯。

Cascaded Shadow Map就不多說了。

SSAO的部分,偷吃偷得很兇。完完全全是事先算好,甚至美術修過圖的一張貼圖,然後用類似 lightmap 的方式,計算貼圖軸後貼上去。效果沒差多少,但是效能差很多...

( 我們來參加 GDC,簡直就是來觀摩各式各樣的偷吃步的... )

最後一場,本來並沒有期待很多,不過卻真的有些收穫。

"Uncharted 2: HDR Lighting"

一開場,講了很多 Gamma 曲線的東西,本來搞不懂是什麼,後來在朋友的 Blog 上看到 Gamma Correction 的觀念,才瞭解了。

簡單說,美術製作的貼圖素材,所有的顏色與亮度數值,都不是線性的,而我們在 Pixel Shader 裡,卻拿這些數值去做線性運算,這中間就有誤差了。

這就是人家比我們專業的地方,就是人家可以上台發表,我們只能在台下鴨子聽雷的差別。

故事還沒完,Gamma Correction 之外,他們還做了所謂 Filmic Tonemapping 的修正,修正掉過亮以及過暗的地方。

再來是SSAO。印象最深的,就是 "Who needs sphere? A box will do just as well"。

用個盒子算AO就好啦。 ( 怎樣? 又觀摩到一個偷吃步... )

最後呢,講述了他們的 Rendering Pass 架構,以及他們很自豪的最佳化的做法。不過,這部分完全是 PS3 硬體上的東西,真的是有看沒懂。

( 就在那一瞬間, 四個 Cascaded Shadow Map 畫在一張貼圖上的畫面,又閃過在我眼前... )

 

THE END

2010年3月22日 星期一

My GDC 2010 (Day 4)

GDC 的講題,分成幾類,程式、美術、設計、製作等等,參加 GDC 的人也算是各領域的人都有了。不過,有點要注意的是,可以的話,最好不要跑到別人的場子去。

例如昨天 Blizzard 的場子就是程式領域的,所以,當程式人聽到這麼重要的 Hotspot 分析工具, Designer 卻覺得 "not so valuable" 的時候,底下會響起一片 "你們真是不識貨啊" 的笑聲。

不過程式人在美術人的場子裡也好不到哪裡去。根據我們美術同事轉述,以下是演講人講述在他們公司裡的對話:

美術 : 「這個功能可以做嗎?」

程式 : 「不行」

美術 : (中指)

程式 : (當作沒看見)

美術 : (遞...)美鈔

程式 : (眼睛上全是Dollar Sign)

「兩天後,我們有了這個酷功能...」

( 類似的故事好像有發生在我跟我的美術好友 Louis 的身上,不過我當然是不記得的啦... )

Day 4

一大早參加的課程是由冰島的 CCP (做 EVE 的那家公司)演講的題目,"Code and Complexity: Managing EVE's Expanding Universe",演講人是個金髮正妹的程式設計師,大清早看見金髮正妹的同行,一整個讓人神清氣爽啊...

好吧,內容。

內容是,EVE Online 營運了七年下來,他們怎麼去控制程式的各種版本,各種狀況。版本控制方面,用了四條 Stream—Dev, Stage, Release, Hotfix,沒有很多的分支。程式碼方面,有幾個重要的點,

Think ahead – simple, clear, and clean

Follow a coding standard

Think big – optimize

Think carefully

Balance features vs. technical debt

很重要的就是,不要去標新立異,寫一堆別人很難看懂的 Code,也不要去做一些技術性很高,但沒什麼用途的東西。

接著下一場,全會場只有一堂課程,就是 Sid Meier 的演講。大製作人,所以逼著全部的人都要去聽。我就不多寫了,同行的 Designer 說,沒什麼新鮮的。

下午第一場,聽的是"Streaming Massive Environments from 0 to 200 MPH",講的是他們的賽車遊戲,如何將賽道 Streaming。

用了很多的技巧,似乎是能節省時間的技法全都用上了。LOD, 貼圖壓縮, 甚至連 Disk I/O Cache 都考慮進去了。因為有這樣的需求,所以他們自己發展了一套 Pipeline 工具。

也算是很猛的啦...

接著呢,不小心選到一場地雷課。聽了十分鐘就跑出來了。可是課程的安排很糟糕,又沒別的課好去,所以就又去微軟講 Windows Phone 7 的場子裡,看看還有沒有禮物可拿...

本日最後一場,走到了 Intel 的場子,聽聽有沒有什麼多緒的新概念。

不多。

新的 Windows 作業系統裡好像有個 Slim reader/writer locks 和 Condition variables,據說比 Critical sections 還要節省資源,可以找天來試試看到底是什麼東西。

2010年3月21日 星期日

My GDC 2010 (Day 3)

現在開始進入正式的 Main Conference。

Day 3

第一場重頭戲,就是 Blizzard 的 keynote 。鐵定會爆滿,所以我們早早就從飯店出發到會場去排隊。

題目是 "Designing for Performance, Scalability & Reliability: StarCraft II's Approach"

一開場,先講幾個 Blizzard 的 Core Value。

Gameplay first – the “invisible” tech. ( 這個尤其重要,所以放在第一個... )

Think globally – games are global

Commit to quality – we are all QA

接下來,展示了 StarCraft II 的 Performance 分析工具。是的,這一場演講的最主要主題,就是 Blizzard "自己做" 的效能分析工具。雖然是自己做的,但是功能絕不輸專業的分析工具。

( 後來想到,你們就是因為自己做這個工具,才會讓遊戲 Delay 這麼久吧? )

B社抱持的想法其實也不是沒道理,因為第三方的效能分析工具很難做到即時的分析,換句話說,即使有很多分析的資料,但是依然沒辦法跟遊戲畫面或狀況結合起來,對於分析效能來講,效果總是打了折扣。

所以我們就看見了,在 StarCraft II 的遊戲畫面上又多了一層效能分析的 Layer ,所有的分析曲線都能夠顯示在上面。

程式團隊還另外做了一個分析地圖 Hotspot 的工具,可以讓 Designer 了解地圖的效能狀況。有人問,這東西 Designer 覺得怎樣,答案是 : "Not so valuable…"

接下來,就像我之前說的,因為課程時段安排的很糟糕,我又多出了很多時間。

於是跑去聽了一場主題是 "The AI of BioShock 2" ,內容是跟製作流程相關的演講。

幾個重點:

Less document, more prototype

Don’t over concept & over document

Prototype early

Prove features before enter production

Work iteratively as a group

下午,時間還是很多,所以到底下的展場晃了很久,看了一些有興趣的攤位。

下午的最後一場,跑到了戰神III的課程去聽。主題是戰神III的影子。

Cascade Shadow Map。

對,又是它。

也許是PS3的運算比較快,記憶體比較小的關係,這裡的 CSM 運算,跟PC上的運算有些不同,但基本理論跟演算是一樣的。

而戰神III也另外做了一些最佳化的處理,減少運算量,這部分,PC上倒是也可以應用的。

簡單講,兩個偷吃步。

看不見的不要算

看不清楚的也不要算

2010年3月18日 星期四

My GDC 2010 (Day 2)

今年的GDC是在 3/9 至 3/13 ,所以我現在寫的是回憶錄...XD

Day 2

早上還是待在微軟的場子裡,聽了兩堂關於 DirectCompute 以及 Tessellation 的課程。

DirectCompute 主要在介紹 Compute Shader 的使用( 對..今天也還是Tutorial.. ),重點在於,Compute Shader 本身就是為了做平行化計算而生的,所以各式各樣我們在做平行化、多執行緒的程式所需要考慮到的問題,例如Shared Memory, Atomic Operation...等等,都在這裡一一出現。

平行處理始終是個大課題啊...

在 HDR 計算時,可以將平均亮度的計算拉到 Compute Shader 來做,這算是很好的應用了。

DirectCompute 是 DX11 的規格,不過某些 DX10 顯卡已經有 Compute Shader 可用,DX10 也有函式可以呼叫來使用說。

Tessellation 課程的演講人是個華人,他說大部分的 DX SDK Sample 都是他寫的。

這個課程的主題,就是介紹幾個 Tessellation 的 Sample,每個 Sample就解說一下做法,然後把範例跑一跑,還不算太無聊。

範例咧,在 Dx11 的 SDK Sample 裡都有。

下午,微軟的課程就走到即將發表的 Windows Phone 7 作業系統上了,所以我就先到了 iPhone 的場子去。iPhone 有一場很有意思的講題 -- "如何讓你的 iPhone App 保持 Apple Store 的排名上"。

答案就是,跟我們的MMO要保持在遊戲社群網站排名的手法一樣...

持續的做更新

節慶的時候出個更新做 in-game 活動

網站上面弄點相關新聞

官方人員有事沒事在社群網站上放點消息,跟玩家溝通

...

MMO Game, Mobile Game, Social Game, ... 只要是在網路上玩、網路上營銷的遊戲,操作手法都極為相似啊...

下午最後一堂課,又回到了微軟的場子裡,聽聽 Windows Phone 7 這個系統。

微軟打算把這個系統跟 XBox Live, Windows Live Games 結合起來,然後把 Apple Store 的功能、Facebook 的社群功能全部包在這裡面...

換句話說,就是整碗捧去啦...

一天結束,有始有終,又填了一份問卷,又拿了一件微軟 T-Shirt