2009年8月24日 星期一

Dirty Coding Tricks

Dirty Coding Tricks by Brandon Sheffield

================================================

今天在Gamasutra上看到的一篇文章。

遊戲開發有時程壓力,而當我們發現一個很難解的Bug,時間又已經來不及的時候,我們該怎麼辦? 這篇文章就舉出了幾個偷吃步的故事。

頭一個故事就很慘了。

在一個PS2遊戲即將要發行的時候,測試團隊發現,在第一個關卡裡,玩家只是靜靜的站著就偶而會造成crash,而且更不幸的是,是在燒成光碟之後,這個問題才會出現。

於是開發團隊為了解決問題,不斷的修改程式,燒成光碟,然後測試,弄了十幾個小時( 為了等程式 crash,只好拿 World of Warcraft 打發時間.... )。

後來奇蹟出現了。有人發現,一開始攝影機向右轉個90度的話,程式就不會出問題,於是乎,PS2的版本,就在攝影機轉個角度之後,順利通過測試而發片。而已經上架的另外兩個平台的版本,攝影機角度還是維持原先的設計。

我的結論是:寫程式,也需要奇蹟。

第二個故事,真的就是偷吃步了。

遊戲程式中所用到的資源,例如一大堆的檔案,在檔案系統中通常會想些編碼的方式當作索引來存取這些檔案。這個故事裡的團隊很倒楣,他們將檔案的檔名CRC32編碼,同時也將檔案內容做CRC32編碼,用這兩個值組成64位元的索引來存取檔案內容。

開發了兩年,處理了幾萬個檔案,從來沒有發生索引值衝突到的狀況。

可是,它真的發生了。兩個不同內容的檔案,卻有完全相同的檔名(也不知道為什麼要這樣設計....),而且檔案內容在編碼之後也得到相同的CRC32編碼--這下子事情大條。

改檔案系統,改索引方式,都是個大工程,而且誰知道改了之後會不會發生同樣的狀況? 這時候,再怎麼完美的編碼方式,都沒辦法給人信心了。

沒時間了,只好用一個最簡單的偷吃步解決這個問題 -- 把其中一個文字檔案打開,在最後面加一個空格,然後存檔。

於是乎,遊戲如期發行。

 

當然啦,這些方法都不是好的解決方式,而且會帶來後續的問題,不管是程式穩定度還是程式維護上的問題。

不過,對我們老是在有限時間跟疑難雜症打仗的人來說,這些故事是會讓人會心一笑的。

2009年8月18日 星期二

Design Patterns for Game Programming -- Reference Count

這是提供入行的新人教育訓練用,我們自己整理的Game Programming中的Design Patterns。我們所想到的第一個項目,就是Reference Count。所以就先將它整理出來了。

既然是寫設計模式,自然必須依照設計模式經典的編排方式來做。

以下進入正題。

 

Design Patterns for Game Programming -- Reference Count

使用時機

遊戲程式中充滿了使用記憶體資源的物件,其中有些物件的特性是,佔用大量的記憶體,又常常重複出現在遊戲中。例如,3D遊戲中的模型、貼圖,2D遊戲中的圖片資源等等。

clip_image002

(場景中重複出現的樹木就包括了重複使用的模型與貼圖) ( Screen-Shot from World of Warcraft )

針對這種物件,我們會將它設計成共享的資源物件,以節省記憶體的使用量。同時,我們也在共享資源物件中,加入參照計數(Reference Count),以便記錄每個共享資源所被參照的數量。

目的

將共用的資源做有效的管理。改善資源與記憶體的使用。

設計實作

clip_image003

架構上主要有三種物件。

Shared Resource :

也就是共享的資源物件,像是貼圖、模型、圖片等。成員變數m_iReferenceCount記錄的就是參照計數,而IncRefCount與DecRefCount則是用來對Reference Count遞增與遞減之用。每個Resource有一個唯一的Key值(例如,資源檔案名稱或是某種編碼後的整數)。

Resource Table :

存放Shared Resource的地方,通常會使用Hash Map、Binary Tree或是其他能夠快速的從Resource Key值搜尋物件的資料結構。

Resource Manager :

做為與應用程式溝通的介面物件。提供兩個最主要的成員函式 : Query Resource 與 Release Resource。

clip_image005

應用程式透過呼叫Resource Manager的Query Resource函式,來取得共享資源。

首先會在Resource Table中搜尋是否有對應Key值的資源存在,如果存在,就將資源的參照計數遞增之後,傳回給應用程式。如果不存在,就產生一個新的資源( 此時新資源的參照計數為1 ),插入Resource Table中,然後傳回給應用程式。

clip_image007

另外,應用程式也透過Resource Manager的Release Resource函式來釋放資源。

首先Manager會先將Resource的參照計數遞減,並且取得結果。如果參照計數小於或等於0,表示已經不再需要這個共享資源,就先從Resource Table中將資源移除,然後,刪除這個資源。

多緒環境下的設計實作

有兩項必須做到Thread-Safe,一是Resource Table的存取,避免多個執行緒同時修改Table內容以及相關的索引資料,另一個則是Reference Count的遞增與遞減計算,避免多個執行緒同時修改,造成資料錯誤。

使用設計上的限制

1. 在這個機制下,共享資源的生成與銷毀都必須是透過Manager的Query / Release來負責,應用程式要避免直接使用new / delete來生成 / 銷毀共享資源。一個可用的設計方式是,將資源物件的建構子與解構子封裝起來不公開,封鎖應用程式對共享資源的new / delete權限,同時宣告Manager為friend class,把權限讓給Manager。

2. 共享資源的Inc / Dec Reference Count操作必須是成對的,否則容易出現Memory Leak ( 當 Inc Reference Count次數大於 Dec Reference Count時 ) 或是使用到無效的指標 ( 當 Inc Reference Count次數小於 Dec Reference Count時 )。這項限制,可以透過Smart Pointer的設計來改善。

2009年7月31日 星期五

Code Review

前幾天在想有關Code Review的事情的時候,網路上瀏覽到這麼一張圖。

wtfm

哇哈,一張圖片,勝過千言萬語啊......

2009年7月10日 星期五

遊戲程式的設計模式

前幾天,老闆找我討論一個問題:要給程式新人怎麼樣的訓練,才能讓他們在專案開發上發揮該有的戰力?

我把這個問題繞了兩個彎,換成:有什麼東西是新人不懂,卻深植在老手腦子裡的?

於是我找到了幾個重點,其中一個就是遊戲程式的設計模式。

四人幫的書裡面所寫的設計模式,我稱它做一般化的設計模式。當然,在遊戲程式裡,也是多多少少會用到個幾種模式的,像是Singleton、Factory、State之類。

而我們要再進一步做整理的,是在遊戲程式裡常用的設計。

例如,在遊戲資源或是繪圖資源的管理上,運用Reference Count很常見,但是對剛跨入這一行的程式新人來說,Reference Count可是連聽都沒聽說過。而另外一個極端的資源管理方式,Garbage Collection,又是怎麼回事?

程式老手會說,拜託! 這是基本觀念好不好?

不過,要讓新手程式自己搞懂這是什麼,可是一個不算低的門檻。

以往,我們用的是,師父領進門,然後自己修行,從數十萬行的程式碼裡頭,自己把這些所謂的「基本觀念」搞懂的方式來訓練新人,訓練期不但太長,也未必人人都有辦法自己「頓悟」出來。而且,如果急就章似的就這樣把新人丟上線去打仗,那是很容易出問題的。例如,Reference Count一旦用錯了,小則memory leak,大則crash。

反正都不是好結果。

然後我們為了減少出錯的機率,將Reference Count的機制,套上了Share Pointer的Template來使用....

這又是新手程式要跨過的另一個門檻。

老手知道Reference Count的使用時機、使用方式,以及設計上所要考慮的點,也知道Share Pointer究竟要防範什麼樣的錯誤,以及會帶來什麼麻煩。但對新手程式來說,這是:千頭萬緒,治絲益棼。

所以我們要拉出一條可以當作起點的線頭,將這些遊戲程式中的設計模式,從複雜的程式碼裡頭整理簡化出來,降低新手程式的進入門檻。

也許哪一天我可以把某些個整理出來的模式Po出來也說不定......

2009年6月19日 星期五

Material Script and Technique

我想,大概沒有什麼繪圖或遊戲引擎不在引擎裡頭使用Material Script。

不過今天的重點不是 Material 怎麼設計 ( DirectX 裡頭的 Effect file 已經算是一個不錯的設計了 ),而是在使用 Material Script 所遇到的問題。

舉個例子,我們在遊戲裡,點選一個物品或怪物的時候,物品會有特殊的標示,像是加個邊框或是變得比較亮什麼的。因為Render的方式不同,所以我們必須更換不同的Render State或是Shader。

直覺的方法是,把Material Script換掉。直接換成加邊框的Material。

不過這樣會衍生一些問題。

第一個問題是,我們在遊戲裡有很多種Material,是不是每種Material都要再加一套加邊框的格式? 而且呢,更換 Material Script 意謂著我們需要重新編譯 Script,重新編譯 Shader,重新設定 Script 中的參數。同時,我們必須訂出一套 Material Script 檔案的命名規則,否則我們怎麼找到正確適合的 Material Script ?

另外一個問題。在我們的設計裡,Material Script 是屬於共用的檔案資源,同一個 Material 可以因為模型的不同而指定使用不同的貼圖,甚至於同一個模型都可以任意的更換貼圖。所以這麼一來,貼圖成了額外設定的一個變數,而這個變數,必須在更換 Material Script 時保持不變。

所以我沒有採用這種方法。

我的 Material Script 是直接使用 DirectX Effect file 的,Effect 裡頭有支援 Multi-Technique 的結構,所以我就修改了引擎中的 Effect Material 系統,將 Multi-Technique 的架構加了進去。

於是呢,我的 Material Script 中,除了預設的Technique之外,又加了一個加邊框的 Technique,需要更換 Render 方法或 Shader 的時候,就切換指定的 Technique,這麼一來,不但可以快速切換,不需要特別的檔案命名規則,而且,像是光源、貼圖等等在 Render 時所需要的參數,也不需要重新再連結設定一次。

不過,壞處是,我必須在每一個有需要更換 Technique 的 Material Script 中,把這樣的 Technique 都加進去,也是不小的工程。

還是說,誰有更簡潔的解決方法?

2009年5月18日 星期一

BattleStar Galactica看完了

  image

image

(圖片來自BattleStar官網)

終於,把BattleStar給看完了。

每次看完一季的BattleStar,都會想把EVE Online的帳號再去開起來玩玩,這次也不例外。

雖然說,這最後一季第四季的劇情有點扯(其實從第三季開始就感覺編劇在掰了),中間還碰到一次美國編劇罷工,造成劇情中間有一個段落,不過,還是很好看的啊!

小時候看過所謂的青少年版的BattleStar,那時候最崇拜的角色就是Starbuck,技術最好,最帥的飛行員。現在長大啦,看的又是比較晦暗,成熟版的BattleStar,可是最喜歡的角色還是這裡頭的Starbuck--雖然在這個版本裡被改成了女的。

BattleStar的背景設定是很有趣的,撇開那個被自己製作的機器人追殺不談,就說這個太空艦隊吧。艦隊不光是有軍艦跟戰鬥機而已,還有一大堆平民所搭乘的太空船,提煉燃料的船、運輸囚犯用的船、殖民地流亡政府的殖民地一號、上頭有五星級飯店跟賭場的星雲九號、還有很重要的一艘資源回收垃圾船....

比起其他的太空科幻片,這樣的艦隊設定才是合理又完整。

哪一天我們要設計這類型科幻遊戲的時候,一定要有這樣的設定啊。

話說,第四季劇情走到一半,Starbuck帶隊找到了地球,不過,這個地球已經是一片殘破,只留下核戰之後的廢墟。然後就看美國的編劇們要罷工多久了。

幸好,第四季又拍了後面十集。

整個艦隊放棄了這個核戰廢墟,繼續找另外一個可以居住的星球。經過一場沒成功的軍事政變,死的死,傷的傷,在大結局的時候,找到了一顆有生命可以居住的星球,也就是十五萬年前的我們這顆星球,艾達瑪指揮官就稱它做「地球」。

哈。

所以我們的文明是Starbuck他們帶來的,我們的血統裡頭有一部分是Cylon複製人....

2009年5月6日 星期三

執行緒函式的設計

我在引擎的設計裡,修修改改的弄出了幾種執行緒函式的架構。

一開始是一個thread loop,執行緒函式中有一個無窮迴圈,像是我在Render Thread做的這樣,

DWORD WINAPI CRenderThread::RenderThreadFunc(LPVOID thread_obj)
{
    CRenderThread* thread_ptr=(CRenderThread*)(thread_obj);

    while (!s_bExitThread)
    {
        CRenderCommand* cmd=0;
        thread_ptr->m_CommandQueueLock.Lock();
        if (thread_ptr->m_CommandQueue.size())
        {
            cmd=thread_ptr->m_CommandQueue.front();
            thread_ptr->m_CommandQueue.pop_front();
        }
        thread_ptr->m_CommandQueueLock.Unlock();
        if (cmd)
        {
            cmd->Execute(thread_ptr->m_pRenderThreadState);
            medelete cmd;
        }

        Sleep(0);  // 這個很重要,如果不休息,主緒會忽快忽慢,而且可能兩次執行的速度差異幾十倍
    }
    return 1;
}

迴圈的最後,要讓執行緒睡一下下,因為如果不這麼做的話,在Windows的架構裡,這個執行緒可是會吃掉CPU不肯放出來的,也就會造成主緒所分配到的時間忽多忽少,跑得忽快忽慢。

另一種執行緒函式,是用在背景讀檔的執行緒,每個執行緒只執行一次。

DWORD WINAPI CThreadStream::LoadingThreadFunc(LPVOID thread_obj)
{
    CThreadStream* thread_ptr=(CThreadStream*)(thread_obj); 

    WaitForSingleObject(thread_ptr->m_BeginEvent,INFINITE);  // wait for begin 
    thread_ptr->Load(thread_ptr->m_szRequestFilename,
      thread_ptr->m_szRequestPathID);
    SetEvent(thread_ptr->m_EndEvent);  // loading done
    return 1;
}

執行緒建立之後,並不會馬上進行讀檔,而是會等待一個開始的事件,讀檔完成以後,再設定結束事件,讓主緒可以得知檔案已經讀完。

這個設計,有個問題。也就是每讀取一個檔案,我們就必須建立一個執行緒,讀完了,就刪除執行緒。這在系統資源的使用上,還有執行的效能上,都不是很好的設計方式。

我沒有用Thread Pool來改進,而是做了其他方向的修改。

最先是用了一個無窮迴圈來做。

DWORD WINAPI CThreadStream::LoadingThreadFunc(LPVOID thread_obj)
{
    CThreadStream* thread_ptr=(CThreadStream*)(thread_obj); 
    
    while (!s_bExitThread)
    {
        if (WaitForSingleObject(thread_ptr->m_BeginEvent,0)!=WAIT_OBJECT_0)
        {
            Sleep(0);
            continue;
        }
        thread_ptr->Load(thread_ptr->m_szRequestFilename,
                                      thread_ptr->m_szRequestPathID);

        SetEvent(thread_ptr->m_EndEvent);  // loading done
        ResetEvent(thread_ptr->m_BeginEvent);  // reset begin for next loop
    }
    return 1;
}

這個迴圈每次都檢查開始事件是否被設定,如果沒有,就讓執行緒睡一下下,然後繼續迴圈檢查。用這個方法,我可以讓背景讀檔的執行緒一直活著,有需要的時候,就幫忙讀個檔案。

但是這個執行緒的CPU負擔其實還是很重的,要一直looping檢查。而讀檔的工作,執行的頻率又不是很高。一直looping非常不划算。

所以我將開始事件改成了無限等待,同時加上一個離開執行緒的事件旗標。

DWORD WINAPI CThreadStream::LoadingThreadFunc(LPVOID thread_obj)
{
    CThreadStream* thread_ptr=(CThreadStream*)(thread_obj);

    HANDLE hWaitHandle[2]={ thread_ptr->m_BeginEvent,thread_ptr->m_QuitEvent };
    while (TRUE)
    {
        DWORD signal=WaitForMultipleObjects(2,hWaitHandle,FALSE,INFINITE);  // wait for begin or quit
        if (signal==WAIT_OBJECT_0+1) break;

        thread_ptr->Load(thread_ptr->m_szRequestFilename,
       thread_ptr->m_szRequestPathID);

        SetEvent(thread_ptr->m_EndEvent);  // loading done
        ResetEvent(thread_ptr->m_BeginEvent);  // reset begin for next loop
    }
    return 1;
}

這樣一來,這個執行緒只會在開始事件被設定時才會醒來工作,做完又會繼續等待。

雖然不算是最佳的設計,倒也符合我們現在的需求了。