圖形除錯設備

今年 GDC 給我的一個大震撼，就是，Game Engine / Graphic Engine 裡，要加上圖形除錯功能。

回頭翻了一本 3D Game Engine Architecture 的書，才發現人家早早就有說了。

這些功能的用處很大，做了絕對有好處。

然後發現，啊，Engine 裡頭那個顯示 Bounding Box 的物件，不就是其中一個圖形除錯物件麼?

Bungie 在開發 HALO 時，連網路封包的數據與優先權都用即時圖形顯示。

我們真的該把圖形除錯的功能加到 Engine 裡。

我叫它做「圖形除錯設備」。 ( Graphic Debugging Facilities )

首先，我把 Game Timer 做了修改。加上加速、放慢、暫停、甚至每個 Frame 更新固定時間的功能。這些在我們做 Animation 的除錯時，應該會很有幫助。另外，我還加了一個 Real Life 的 Timer，我們總還是會需要知道真實時間的吧?

然後， Engine 裡面加了一整組的 Debug Drawing API，包括畫線、畫圓、畫顆 Wireframe 的球、畫個十字、畫個座標軸、顯示字串訊息在 3D 場景裡，還有一個很有用的，畫個 Frustum 出來。

最後一個組件呢，就是弄了一組除錯用的 Camera 跟 Frustum。遊戲場景的攝影機，是場景管理中很重要的運算基礎，但是我們怎麼知道這些運算有沒有問題? 例如，Frustum 的 Culling 運算、遠方物件的 LOD 選擇，有了除錯 Camera 的模式，我們就可以很簡單的做檢查。

Hmm... 看來 Frustum 的 Culling 並沒有算得很乾淨...

引擎中不可或缺的事件訊息系統

嗯...對...

很久沒有發文了...

「懶」是唯一的解釋...

前一陣子看到一個引擎中的訊息系統架構，突然間，對整個引擎的架構設計有了新的想法。或者該說，解決了我心中長久以來的難題。

說穿了，不過就是事件訊息驅動式 ( Event Driven ) 的架構設計。

這東西被我晾在一旁太久，已經完全忘記它的存在了。

簡單舉個例子說吧...

遊戲中有很多系統，會受到攝影機的位置方向的影響，例如，天空盒子 ( Sky box ) 必須隨著攝影機的位置變動位置，動態讀取的無接縫地圖系統也必須檢查攝影機的位置來決定是否讀取地圖或是釋放地圖。如果在一個單純的程序式的架構中，我們會在攝影機位置變動的時候，呼叫這兩個物件系統來做相應的更新檢查。

像是這樣:

CameraManager::UpdatePosition(Camera* camera, Vector3 pos)
{
  camera->UpdatePosition(pos);
  skybox->UpdatePosition(pos);
  seamless_world->CheckLoading(pos);
}

只不過，這麼一來，我們可以非常確定的是， Camera Manager 這個物件已經跟 Skybox 、 Seamless World 分不開了。三個物件綁在一起的結果是，物件的再利用性大大降低。( 想想如果我們需要將 sky box 改為 sky doom, 又或者我們不再需要無接縫地圖的時候... )

這還只是其中一個問題。

另外一個問題是，在我們遊戲越做越大，引擎越寫越深入的時候，我們發現， LOD ( Level of Detail ) 的計算也需要隨著攝影機變動而更新，水面倒影效果也跟攝影機有關，粒子系統的繪製也需要攝影機的資料...

於是乎，我們又把 LOD 系統、水面倒影、粒子系統全綁到了攝影機物件裡。

更甚至於，第三人稱視角的遊戲裡，攝影機是跟著主角走的，所以，又把攝影機綁到了主角身上，跟著主角更新。

最後的結果就是，整個引擎裡各式各樣的系統物件，因為彼此之間相互影響的關係，全部混成一團。

現在換個角度，改用事件驅動來做。

攝影機變動的時候，我們不管 Skybox 、 Seamless World，只送個訊息給事件系統。

像是這樣:

CameraManager::UpdatePosition(Camera* camera, Vector3 pos)
{
  camera->UpdatePosition(pos);
  event_system->Send(idCameraPositionUpdated, camera);
}

而對於 Skybox, Seamless World 來說，必須有函式負責來接收這個事件，同時，在物件的初始化的時候，必須先把這個函式登記到事件系統裡。

Sky Box 的接收函式大概會長得像這樣:

Skybox::OnCameraPositionUpdated(Camera* camera)
{
  UpdatePosition(camera->GetPosition());
}

其他的，需要隨著攝影機更新而更新的物件，也都會有相類似的函式，同時也都需要將函式登記到事件系統中，事件系統在收到攝影機送來的事件後，就會分發事件，一一呼叫每個需要的事件處理函式。

這樣子，事件系統將我們的各個物件獨立開來，減少了很多錯綜複雜的關連。

更進一步來，我們可以在玩家主角的位置更新的時候，發送一個事件出來，然後在攝影機系統裡，寫個這樣的函式:

CameraManager::OnPlayerPositionUpdate(Player* player)
{
  UpdatePosition(player->GetPosition());
}

當然了，這樣的事件驅動架構不是沒有缺點的。缺點就是，為了遵循這個架構模式，我們必須多寫很多 code ，例如，本來可以直接在攝影機裡呼叫的函式，現在必須寫一個事件處理函式來呼叫它，而且還必須要把事件處理函式登記到系統裡，有點煩...

但是多花這些工絕對是值得的...

3dsMax Exporter Plug-in (3)

Well, 我們的Exporter還沒做完。

我們在MyExporter1::DoExport設定中斷點，會發現，這個函式會在我們選定了輸出檔，按下存檔之後才被呼叫。這時候，就開始了輸出工作。

首先會看到一個對話盒。

DoExport的程式碼裡，也就呼叫這個對話盒而已，實際輸出工作的呼叫，還是得要我們自己來。

這個對話盒是project wizard幫我們建立的，專案裡面有一個rc檔，我們可以打開來自己改。

例如，改成這樣，

我們可以將輸出時候需要的設定與選項，放在這對話盒裡頭，使用者按下了OK，實際的輸出工作就會開始進行了。

接下來，我們真的要開始從Max抓資料了。

Max有SDK，SDK也有Help文件。但是我們看習慣了MSDN, DirectX SDK文件之後，會發現Max SDK的文件真的是弄得很糟糕。但是我們還是得看。

有總比沒有好。

為了讓程式碼結構清晰些，我們建立一個ExporterPipeline物件來做這一堆苦工。

class CExporterPipeline
{
public:
    CExporterPipeline();
    ~CExporterPipeline();
    HRESULT Create(const char* model_name,const ExporterParameters& param);
    void SyncData();
    HRESULT Destroy();
private:
    void BeginSync();
    void EndSync();
    void SyncScene();
    void SyncGameNodeTree(int level,IGameNode* node,IGameNode* parent_node);
    void SyncGameNode(int level, IGameNode* node,IGameNode* parent_node);
    void SyncGameNodeGameObject(IGameNode* node, IGameObject* go);
    void SyncGameNodeMesh(IGameNode* node, IGameMesh* gm);
    void SyncGameNodeMaterial(IGameNode* node);
    void SyncGeometryData(IGameNode* node,IGameMesh* gm);
    void SyncMaterial(IGameNode* node, int matid, Mtl* mtl);
    void UpdateMeshSkinVertex(IGameNode* node,IGameMesh* gm);
    void UpdateNodeFrameAnimation(IGameNode* node);
private:
    Interface* m_MaxCore;
    IGameScene* m_Scene;
    IGameConversionManager* m_ConversionMgr;
    FILE* m_fpExportFile;
    ExporterParameters m_ExportParameters;
    int m_nTotalNodeCount;
    int m_nProgressNodeCount;
    std::vector<int> m_GameNodeIDArray;
};
extern CExporterPipeline g_ExporterPipeline;

ExporterPipeline只有幾個public函式: Create, SyncData, Destroy。其餘的苦工全部寫在private函式裡。

我們在MyExporter1::DoExport裡面這樣呼叫 :

int    MyExporter1::DoExport(const TCHAR *name,ExpInterface *ei,Interface *i, BOOL suppressPrompts, DWORD options)
{
    #pragma message(TODO("Implement the actual file Export here and"))
    if(!suppressPrompts)
        DialogBoxParam(hInstance,
                MAKEINTRESOURCE(IDD_PANEL),
                GetActiveWindow(),
                MyExporter1OptionsDlgProc, (LPARAM)this);
    ExporterParameters params;
    g_ExporterPipeline.Create(name,params);
    g_ExporterPipeline.SyncData();
    g_ExporterPipeline.Destroy();
    #pragma message(TODO("return TRUE If the file is exported properly"))
    return FALSE;
}

Create建立需要的物件與檔案，SyncData處理資料輸出，Destroy清除物件以及關閉檔案。

大致上外部的步驟就這樣。細節都藏在Exporter Pipeline裡，下回再繼續吧...

3dsMax Exporter Plug-in (2)

在實際執行之前，要先改一些程式碼。

打開專案程式的主檔案MyExporter1.cpp。

這個就是我們的Exporter主物件。從SceneExport繼承而來。

DoExport函式是實際進行輸出工作的入口函式。其他還有一些設定的函式，不過只有設定輸出檔副檔名的Ext函式比較重要。

int MyExporter1::ExtCount()
{
    #pragma message(TODO("Returns the number of file name extensions supported by the plug-in."))
    return 1;
}

const TCHAR *MyExporter1::Ext(int n)
{       
    #pragma message(TODO("Return the 'i-th' file name extension (i.e. \"3DS\")."))
    return _T("me1");
}

const TCHAR *MyExporter1::LongDesc()
{
    #pragma message(TODO("Return long ASCII description (i.e. \"Targa 2.0 Image File\")"))
    return _T("My Exporter Sample 1");
}
const TCHAR *MyExporter1::ShortDesc()
{           
    #pragma message(TODO("Return short ASCII description (i.e. \"Targa\")"))
    return _T("My Exporter 1");
}

我們把 ExtCount, Ext, LongDesc, ShortDesc 函式簡單實做之後，重新編譯一次。

然後，從 Visual Studio Debug 執行它。

跑不起來是正常的。

打開專案的 Property 設定，在 Debugging –> Command 那一項，把 3ds max 的執行檔設定進去。

然後我們可以 Start Debugging。

Visual Studio 會啟動 3ds max，而 max 會將我們的 plug-in load 進去。

我們的 exporter 是在 export 檔案時才會用到的，所以，先 export 看看。

我們會在存檔類型那裏，找到我們的輸出檔格式。

到這裏，我們的 exporter 算是可以掛上 max 系統裡了。

3dsMax Exporter Plug-in (1)

序言

Exporter 是我們在製作 3D 遊戲時，非常常用的一項工具程式。由於美術所製作的 3dsMax 模型，對於 3D 引擎來說，資料過多且複雜，所以我們需要借助 Exporter 將模型資料轉出成我們所需要的資料格式。DirectX X-File 即為其中一種格式。

3dsMax 利用了抽象介面的概念，定義了非常多的 Interface，Plug-in 設計者可以繼承這些 Interface 來實做，3dsMax 便可以透過抽象介面虛擬函式的動態連結，在需要的時候呼叫 Plug-in 所提供的實作物件。

Step by Step

第一步，當然是先把 3dsMax 安裝起來，同時，要安裝 3dsMax SDK，是的，Max 也有 SDK。

接著，為了自己的便利，最好把 "3ds max Plugin Wizard" 安裝起來。通常 SDK 的目錄文件裡都有，如果沒有，就花點時間請 Google 大神幫忙。

安裝完畢，Visual Studio的專案裡，會多了一種專案。

建立一個新專案 ( MyExporter1 )，當然，要選取3ds max Plugin Wizard。

然後Wizard會出現以下的選擇畫面。

看到麼? 沒在騙人，真的有很多種類型的 Plug-in。

我們這次需要的是 File Exporter 。

選擇以後，後面兩個步驟就照著需要，填寫裡面內容。

然後，Wizard 就會協助建立一個 Plug-in 專案。

有了專案，編譯看看。

如果，我們前面的設定沒有問題，編譯通常就沒問題。我們會得到一個附檔名是 dle 的檔案，直接輸出在 3dsMax 的 plugin 目錄下。

dle 檔案實際上就是一個 dll ，改成 dle 只是表示這是一個 exporter 。

Unreal Development Kit

Unreal把它的開發工具，很完整的開放出來了。免費授權。如果你自己做了個遊戲拿出來賣的話，只要收入不超過5000美金，是不用抽稅的。

據說Unreal在大陸的授權金已經是低到很離譜了，完全是為了打開市場考量，所以現在把這個開發工具免費授權也就真的沒什麼好驚訝的了。

下載網址在這裡:

Unreal Development Kit

昨天很快的用我的「光世代」下載了。

不過為什麼會變成簡體中文的咧?

 

而且說真的，打開程式以後完全不知道要怎麼開始編輯一個關卡或場景，有沒有什麼 Quick Start  或是 Tutorial 之類的文件可以看看啊?

Design Patterns for Game Programming -- Reference Count

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

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

以下進入正題。

 

Design Patterns for Game Programming -- Reference Count

使用時機

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

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

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

目的

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

設計實作

架構上主要有三種物件。

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。

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

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

另外，應用程式也透過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的設計來改善。

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 都加進去，也是不小的工程。

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

執行緒函式的設計

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

一開始是一個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;
}

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

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

Scene Graph Traveler

這一篇，就當做給我自己的記錄吧。

Scene Graph Traveler是我自己取的物件名字，是一個獲准在Scene Graph的樹狀結構中逛大街的物件。之所以會設計這樣的物件，主要是要從一個最近冒出來的需求，來調整整個引擎在Scene Graph中的架構。

原本，我在引擎中有一個Frustum Culler物件，負責將Scene Graph中所有可被Frustum見到的節點蒐集起來，然後一一交給Renderer做繪製。Culler會以遞迴呼叫的方式，跑一遍Scene Graph的樹狀結構，檢查與節點的碰撞關係，如果節點已經被Culler剔除了，那麼節點的Sub-Tree就可以不必再計算。

Scene Graph的遞迴方式，就類似以下的Code

er_code CNode::OnGetVisibleSet(CCuller* culler)
{
    if (node in frustum)
    {
        culler->Insert(this);
     }
     else return ER_OK;

    if (m_ChildList.size()==0) return ER_OK;
    er_code er=ER_OK;
    ChildList::iterator iter=m_ChildList.begin();
    while (iter!=m_ChildList.end())
    {
        er=(*iter)->OnGetVisibleSet(culler);
        if (er) return er; 
        ++iter;
    }
    return ER_OK;
}

 

現在，需求來了。

我要用滑鼠指標點選場景裡面的一個物件，所以我將滑鼠的座標，轉換成場景空間中的一條射線。我叫它做Picker。

Picker搜尋物件的方式跟Culler很類似，也是需要跑一遍Scene Graph中的樹狀結構，檢查射線與節點的碰撞關係，如果射線與節點有碰撞，就繼續搜尋Sub-Tree，否則就可以不必再計算。

簡單的做法呢，就是Scene Graph中，再增加一個讓Picker遞迴的函式。不過這麼一來，我就讓Picker與Scene Graph綁在了一起。

所以這絕對不是好設計。

Culler與Picker在Scene Graph中的行為幾乎是相同的，所差別只在判斷是否要繼續搜尋Sub-Tree的方式。至於在樹狀結構中遞迴的方式則是完全相同。所以我將這行為抽離出來，變成了Scene Graph Traveler。

class CSceneTraveler
{
public:
    enum TravelResult
    {
        Travel_InterruptAll=0,
        Travel_Interrupt,
        Travel_SubTree,
    };
public:
    CSceneTraveler() {};
    virtual ~CSceneTraveler() {};
    virtual TravelResult TravelTo(CNode* ) =0;
};

這是一個抽象物件，需要在Scene Graph中逛大街的物件，都可以繼承它來取得在Scene Graph中遞迴的許可。所以，Culler以及Picker就從這個類別繼承出來，並且各自實作所需要的TravelTo函式。

而Scene Graph Node本身的函式，則是做了這樣的修改

CSceneTraveler::TravelResult CNode::VisitBy(CSceneTraveler* rpTraveler)
{
    if (!rpTraveler) return CSceneTraveler::Travel_InterruptAll;
    CSceneTraveler::TravelResult res=rpTraveler->TravelTo(this);
    if (res!=CSceneTraveler::Travel_SubTree) return res;  // don't go sub-tree
    if (m_ChildList.size()==0) return CSceneTraveler::Travel_Interrupt;
    ChildList::iterator iter=m_ChildList.begin();
    while (iter!=m_ChildList.end())
    {
        res=(*iter)->VisitBy(rpTraveler);
        if (res=CSceneTraveler::Travel_InterruptAll) return res;
        ++iter;
    }
    return res;
}

 

其實會這樣修改設計，還有一個原因。我的Scene Graph以及Culler是放在繪圖核心的模組裡，而Picker是在遊戲層的物件，為了保持物件之間關係的乾淨清爽，所以我並沒有直接用簡單的方法，把Picker綁在Scene Graph裡，而是將這個Traveler抽離了出來。

未來還會不會有其他的物件可以繼承這個相同的行為，我也不知道。

DirectX Shader 材質

最近拿起了3ds max，玩一玩裡頭的DirectX Shader 材質。發現它其實還挺好用的。

首先先將材質換成DirectX Shader

然後材質的參數就會換成這樣的介面

第一個，DirectX Shader的欄位，可以讓我們指定使用的Fx檔案，第二個Parameters的欄位，裡面所有的參數，都是從Fx檔案裡定義的。只要照著標準的規則寫，參數便能夠列在這上面，讓製作人員去調整。同時在做模型輸出的時候，也同樣可以取得這些設定的值。

至於這些個參數是怎麼定義的，可以打開default.fx來看。


// light direction (view space)
float3 lightDir : Direction < 
    string UIName = "Light Direction";
    string Object = "TargetLight";
    > = {-0.577, -0.577, 0.577};
// material reflectivity
float4 k_a  <
    string UIName = "Ambient";
    > = float4( 0.47f, 0.47f, 0.47f, 1.0f );    // ambient
float4 k_d  <
    string UIName = "Diffuse";
    > = float4( 0.47f, 0.47f, 0.47f, 1.0f );    // diffuse
float4 k_s  <
    string UIName = "Specular";
    > = float4( 1.0f, 1.0f, 1.0f, 1.0f );    // specular
int n<
    string UIName = "Specular Power";
    string UIType = "IntSpinner";
    float UIMin = 0.0f;
    float UIMax = 50.0f;   
    >  = 15;

這個程式的語法，稱做 DirectX Standard Annotations and  Semantics，角括號裡面的字串以及其它變數的宣告，在Effect Fx中是沒有作用的，但是，在max中，就定義了Parameters的參數介面。

除了在DirectX SDK中有文件說明，max的網站上也可以下載到相關的文件(不過版本很舊了)。

用DirectX Shader材質有兩個好處，一是這個Effect Fx的檔案我們可以直接在遊戲程式中使用。第二是，這個材質能夠所見即所得的顯示出來材質效果。

所以，我很認真的在考慮，也許就直接把Effect Fx檔案拿來當做引擎中的材質使用好了。

Intelligent Mistakes

Intelligent Mistakes: How to Incorporate Stupidity Into Your AI Code

by Mick West

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

每天看Gamasutra，偶爾會看到一些好東西。

這個主題叫做「有智慧的錯誤」。

人都是會出錯的，所謂「人有失手，馬有亂蹄」，但是電腦AI不會出錯，只有計算夠不夠完整的問題。

但是這樣的遊戲，玩起來就死板板的，也喪失了一些趣味。

作者舉了他自己做的撞球遊戲當做例子，撞球遊戲的AI不難，就是簡單物理碰撞計算而已，對電腦來說，出桿可以非常非常的精準，但是「人」就不行了，要不就打歪，要不就力道不對，總之是不可能精準的像電腦一樣。

所以，這樣的遊戲玩起來，就是跟一個精準得要命的電腦對手在玩。不但每顆球都打得很「千」，連不小心放的「嗆斯」都沒有。

這就很無趣了。

AI is “too good”.

所以，要做一些精心設計的錯誤，讓玩家覺得他佔到便宜，好比說，偶爾故意放個「嗆斯」、偶爾「突槌」一下、偶爾不小心把母球打進洞....

這樣就有趣多了，人生本來就是充滿了不確定啊....

Finding Oriented Bounding Box

前一陣子發現計算OBB的演算法，研究了幾天，本以為大致都了解了，但深入去思考推導之後，卻才發現，原來我是錯得離譜，Totally Wrong!! (翻譯叫做 "一整個錯!!")

於是又從頭開始，一步一步從數學的角度來看。

觀念還是一樣，把美術模型的每一個頂點，都當做是取樣點，然後用Least Square Fit的方法，找出OBB需要的中心點以及三個軸向。

OBB的中心點取得，根據的是偏微分取極值的方法，三個軸向呢，則是用Principal Axis的概念，從Eigen vector來取得。

底下是兩個參考資料。

http://mathworld.wolfram.com/LeastSquaresFitting.html

http://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf

這個推導，背後的數學有點小複雜，不過，大概都是些矩陣向量的運算概念。

最後呢，得到一個取得OBB的步驟。

1. 先建立一個可以解出Eigen value, Eigen vector的函式庫(或者去抄一個)

2. 把所有頂點座標加起來，找出平均值，就是OBB的中心。

3. 對於每一個頂點，計算與中心點在 x,y,z 三個方向的誤差值 X,Y,Z ，取得兩兩相乘的值，XX, XY, XZ, YY, YZ, ZZ，把每個頂點所算出來的這六個值，全部加起來平均。然後塞到一個3x3的矩陣內。

4. 把這個矩陣丟給Eigen System求解，拿回三個Eigen vector。

5. 用這三個Eigen vector得到的座標系統，轉換原來的頂點，找出在這個座標系統中的Box長寬高。

數學才是王道

話說，元旦連續假日，大家都放假了，我還要上班。

把Code拿出來看看，想說處理一下引擎裡Bounding Box的計算。

找了一些Open Source的參考Code來看，想看看有沒有什麼比較有效率的演算方式來計算Bounding Box。

然後，我就愣住了。

眼前的這個演算法，把所有頂點的資料拿去算一個covariance matrix，再用這個matrix求解eigen vector以及eigen value，然後....就算出了包圍所有頂點的最佳的Oriented Bounding Box。eigen vector是OBB的三個軸向。用找到的三個軸向，來計算OBB的軸半徑。

我傻眼了。

eigen vector有那麼神嗎? 連這個都能算。還有covariance matrix究竟是什麼東西啊?

開始研究了幾天，總算是比較清楚整個運算的來龍去脈。

有時間整理出來的話，再拿來分享好了。

簡單的說，covariance matrix計算(x,y,z)數據的變異量以及彼此之間的影響，例如，x軸方向的數據，在y軸數據變動時，所受到的影響，這東西可以從最小平方差的總和，以偏微分取極值的方式導出類似的計算。

接下來這樣想，假設我們已經知道了OBB的三個軸向，我們就可以將所有的頂點(x,y,z)，轉成在OBB座標系中的頂點(x',y',z')，而以(x',y',z')所計算得的covariance matrix，兩個不同的軸向(x'與y'或是 y'與z'等等...)之間的互相變異量應該是最小的，滿足這樣條件的三個軸向，就是最佳的OBB軸向。

這些計算一直演算下來，就出現了eigen value problem，所以最後eigen vector又出來幫忙，解決了問題。

好，結論。

結論就是....

數學才是王道啊!!

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

Update: 原來還是看錯了，對應eigen vector的eigen value並不是軸半徑，covariance matrix只用來取得OBB的軸向。

遊戲中的特效系統

在過去，我們將遊戲中的特效，分為兩種類型。一種我們稱之為「模型特效」，基本上它就是個美術製作出來的3D模型，只是我們將它用為特效物件上。另外一種，就是「粒子系統」所呈現出來的特效。

過去我們在設計的時候，「粒子系統特效」交給誰來設計製作，一直是一個很困擾的問題。粒子系統沒有一個固定的3D模型，只有一堆的運算參數。程式設計師根據這些參數，去計算每個粒子隨著時間的變化，所以裡面牽涉到不少的數學運算。

程式設計師非常清楚這些參數在數學上的意義，也明瞭調整這些參數對粒子系統的影響，所以，似乎交給我們來設計各式各樣的粒子特效是個不錯的主意。

但這樣一來，這個特效就很可能不好看。例如上面那張單調的煙火特效。畢竟，程式設計師並不是美術設計師。

可是交給美術設計師來製作設計的話，我們要做的第一件事，並不是設計一個很好用的粒子系統編輯器工具，而是 -- 教他們「數學」。

不要鬧了。

所以，有一段時間，我們的粒子系統特效一直是程式設計師在製作。不過，只是做些小特效，比較炫麗、華麗的魔法招式特效，還是交給美術設計，用模型特效來做。

最近我們發現，我們的美術設計師在3dsMax這些建模工具裡，也能夠把粒子系統摸索得很熟練，呵，這是個好機會，讓我們脫離設計難看的粒子特效的好機會。

於是我們做了一些研究，修改3dsMax exporter plugin，將美術在3dsMax中設計的粒子系統輸出，取得一些參數，然後運用這些參數，在遊戲中想辦法模擬出3dsMax的粒子運算。

這麼一來，所有的魔法招式特效，都可以交給美術設計師來製作設計，甚至於，還能夠設計一個華麗的模型特效，再搭配一些粒子特效做點綴。遊戲中的特效就會變得很吸引人。

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

其實，遊戲中還有第三種類型的特殊效果，是運用「Shader」所做出來的效果，例如場景光暈、光線的散射、折射、反射等等。還有像底下這張圖，在「魔獸世界」裡，掛點以後所看到的畫面。

這類型的特殊效果，就真的必須由程式設計師來設計了。

場景管理與通道

遊戲中，隨著劇情跟內容的進行，遊戲場景也會一場一場的變化。遊戲場景大大小小不同，龐大的遊戲場景，可能會有數千個物件在其中，而在網路遊戲的場景中，除了物件之外，可能還會有數百個玩家在其中。

但是我們視野所見的範圍，只是龐大場景中的一角，我們所見到的物件或是玩家，也只是附近的一小撮而已。數字上來說，可能只有十幾二十個物件、七八個玩家，相較於整個場景，只是一小部分。其他大部分場景中的物件與玩家，不管他們發生了什麼事，都是千里之外的事情，我們看不見，也不需要知道。

所以，我們需要場景管理(Scene Management)。

場景管理的最大用處，是能夠用很快的方式，找出視野範圍內的物件，也就是我們需要關心的物件。一般來說，會先將一個場景空間分割成小區塊，把每個物件放在它隸屬的小區塊中，然後再用一個樹狀結構將區塊組織起來，像是二元空間分割(Binary Space Partition, BSP)、四元樹、八元樹等等。

接下來的動作就是，我們可以知道視點在哪個區塊中，視野包括了哪些區塊，然後就只需要處理這些區塊中的物件就好。

通道(Portal)系統則是另一個在場景管理中的工具。

我們在場景裡有一棟房子，我們站在房子外的時候，房子內發生了什麼事，我們是不需要知道的，同樣的，在房子內的人，也看不到房子外。只有門打開的時候，透過大門，房子內外的人可以彼此看見。這個大門，就是所謂的「通道」。

房子是場景中的一個封閉空間，也是一個獨立的區塊，我們站在房子外，除非透過「通道」，否則看不見房子內部。也因為這樣，只有在「通道」進入我們的視野內的時候，我們才需要處理房子內的人和物。

這麼一來，繪圖效能與計算效率都可以提昇。

請看取自「魔獸世界」的這張圖。我站在旅館的外面，左邊站了一個衛兵，右邊有另一個女性NPC，當然旅館內的物件跟NPC是看不見的。這個旅館的造型設計也是完全為了通道而設計的，門口進去一點點，就橫著一道牆，所以我們就算是這樣面對著門口，也還是看不到裡面的狀況。

 

第二張圖，是在旅館內，身後站了兩個女NPC。我們看不到外面。

我在這兩個情形下，抓了兩張線框模式的圖。

線框模式下，看得很清楚，在旅館外面的時候，旅館內的NPC，完全沒處理。在旅館內的時候，更簡略了，連外面的場景都沒處理。

遊戲中的腳本語言

這幾年，越來越覺得遊戲內的腳本語言(Script Language)是一個必要的東西。尤其是遊戲越做越大，越做越複雜，沒有個理想的腳本語言實在是沒辦法應付這樣的需求。

在以前那個一切都還很美好的時代，遊戲也很美好，也很簡單，我們不需要太複雜的腳本語言。簡單的一個文字檔，寫下NPC的ID，起點的位置，終點的位置，然後我們就可以控制NPC，讓他在場景裡從這邊晃到那邊，再從那邊晃回來。

沒有人會嫌這隻NPC很單調。

不過時代不同了。

大概在半年多一年以前，我們的遊戲有個需求，我們需要在人物技能的Tool tip上，顯示各種技能在攻擊與防禦上的影響，而這些影響會跟著人物屬性數值變化。遊戲企劃給了一些公式，大概都是把屬性數值拿來加減乘除算一算。

於是我們的程式設計師很認真的開始分析這些公式，希望可以找出規則，產生出個表格，然後用一個函式搞定所有技能影響的計算。

如果你也是這麼想，那就表示你對遊戲企劃的了解還不夠深。

這規則只有神仙才找得出來。

於是我們開始引入腳本語言。

過去我們曾經研究過lua。lua名氣不小，而且自從「魔獸世界」的UI系統與它結合並且利用它發展出一整套的Addons之後，名氣更大。不過，我們選擇的是Squirrel。

Squirrel，松鼠。不知道作者為什麼要取這個名字，它的Script檔案，附檔名是nut，就是給松鼠吃的堅果。很幽默。

Squirrel的作者據說是Far Cry這個遊戲的程式設計師，他們在Far Cry這個遊戲中原本是使用lua，所以骨子裡的程式碼是跟lua很像的。

好，回到我們的技能Tool tip。

舉個例子，有一個攻擊技能，會根據人物的力量屬性計算傷害加成，公式是這樣:

傷害加成 = (力量數值) x (技能等級+5) / 100

遊戲程式可以很簡單的把這個公式寫進程式中。但是隔沒幾天，任性的遊戲企劃來改公式了，於是程式設計師把這一小段程式改寫。又過了幾天，覺得這個技能太強了，又改公式，程式設計師又動了一次刀....

然後是無窮迴圈。

把這些公式的計算，開放在腳本語言中做計算，讓企劃可以自行修改，我們就能夠擺脫任性企劃的糾纏。

程式中的寫法當然不同了。

上面的傷害加成公式，是寫在Script中，腳本語言提供一個函式給遊戲程式呼叫，傳回傷害加成計算的結果。

function GetDamageModify()
{
  return PlayerStr() * ( SkillLv() + 5 ) / 100;
}

PlayerStr(), SkillLv()是兩個由遊戲程式提供給腳本語言呼叫的函式，分別會傳回力量屬性數值以及技能等級。

這兩個函式是額外寫的，腳本語言沒有強大到可以直接呼叫遊戲程式中的函式。我們必須將提供給腳本語言呼叫的C/C++函式，用腳本語言所能理解的方式再包裝一次，腳本語言才能使用它們。

這個包裝的過程，lua跟Squirrel叫做Bind。包裝的方法很繁瑣，也不容易理解。所以，有人利用Template寫出一整套的Binding工具程式庫。lua有luabind, Squirrel有sqplus。

RegisterGlobal(SquirrelVM::GetVMPtr(),&GetPlayerStr,_T("PlayerStr"));
RegisterGlobal(SquirrelVM::GetVMPtr(),&GetSkillLevel,_T("SkillLv"));

這兩行是寫在C/C++遊戲程式中，利用sqplus工具，將 C/C++ 的 GetPlayerStr(), GetSkillLevel()兩個函式，登記給腳本語言呼叫，在腳本中的函式名稱分別是 PlayerStr() 與 SkillLv() 。

這樣套入之後，我們與遊戲企劃就開始分工了。程式設計師需要做的，就是定義與實做這些提供給腳本呼叫的函式，至於公式的內容，就讓遊戲企劃自己去處理。

============= 時間的分隔線 ===============

話說，幾個月之後，遊戲製作人決定要重新檢視一遍所有幾十個技能的設定，同時調整所有的計算公式....

程式設計師笑了....

Objects Streaming in Multi-Thread

這一篇，算是整理我自己的設計思路。

簡單來說，這功能是讀取資料流裡面的資料，然後產生相關的物件，包括遊戲中的物件，以及引擎核心的物件。當然免不了的，是必須放在多執行緒的環境中來進行，我們不能讓遊戲在進行中的時候，還要停下來等待讀取。

我做了個「不正式的」UML順序圖。

幾個主要的步驟是這樣：在讀取之前，先做一些清除物件列表的事情，然後一個一個物件讀取，讀取完了，再對於這些讀取到的物件，連結它們的從屬關係。物件的產生是由物件的Factory函式來負責，Stream讀取了物件的Type Info之後，根據物件的類別呼叫對應的Factory函式。

物件的Factory函式要做幾個工作：產生新物件、將物件加入到Stream的物件列表中、讀取物件的內容資料。

在多執行緒的環境下，這樣的流程是沒有太大問題的，只要負責讀取的Stream不是各個執行緒共用的就好，而實際上也沒有必要這麼做。

但是遊戲中有幾種物件，資料量很大，很佔用記憶體空間，在設計上，我們必須讓這些資料變成共享的資料以節省不必要的記憶體浪費。而這些物件，在上面的流程裡，就會出問題了。

我用兩個不同的Stream，放在不同的執行緒裡，同時讀取一個共享的Object。由於物件的Factory函式中，並不會產生兩個獨立的Object，而是分享同一個Object，所以在讀取物件的內容資料時，就很容易發生資料打架的Race Condition。

為了解決這個問題，我又多開了一個執行緒。姑且叫做「共享資料專用執行緒」。這個執行緒的唯一工作，就是負責讀取這些共享物件的資料內容。執行緒會把工作存放在佇列中，一項一項的依序處理，這樣一來，資料打架的問題就不會再發生了。

當然，除了共享資料的物件之外，其他的物件也可以把讀取工作交辦給這個執行緒來做，不過我並不打算這麼做，因為這些物件並沒有資料打架的問題，沒有必要多花費一道手續跟時間，而且對這個專用執行緒來說，這麼多物件都交給它讀取，太操了...

繪圖執行緒的同步化

嗯...果然不出所料，一開始實做繪圖執行緒，就面臨了幾個問題。

第一個問題是資料的Race Condition，之前已經預期到會有這類問題發生，不過沒有防範完全，所以在一些共享物件的『參考計數』上出狀況。用了兩個函式 InterlockedIncrement 以及 InterlockedDecrement 改掉了這問題。

另一個問題就是當初沒有想到的，也算是對多緒的程式設計還瞭解的不夠透徹所致。把前面的這張圖拿回來看。一開始，我採用的設計是右邊的這個 Consumer thread 的架構，紅色的邏輯執行緒送指令到佇列，綠色的繪圖執行緒負責從佇列中取出指令來執行。

做法看起來還不錯，但是實際執行就有問題。

問題出在，邏輯執行緒是遊戲程式的主執行緒，而主執行緒會分到相對比較多的執行時間，於是，邏輯執行緒所送給佇列的指令，繪圖執行緒在分到的時間不夠多的狀況下，就沒有辦法及時的處理完。結果就是，邏輯執行緒的Frame rate很高，但是實際畫面的更新率卻非常非常低。

我試了幾個方法，將繪圖執行緒的優先權提高、讓邏輯執行緒Sleep()一下....最後使用了底下這張圖的方法，在邏輯執行緒與繪圖執行緒之間，建立一個同步的機制，讓邏輯執行緒在接到同步信號之後，才進行下一個Frame的運算。

把繪圖執行緒的優先權提高似乎沒什麼用處，執行緒分到的時間還是少得可憐。而用Sleep函式讓邏輯執行緒睡一下的方法，可以讓佇列中不要累積太多的指令，不過同步的效果並不好，兩個執行緒時快時慢，反而不好控制。

比較起來，同步信號的方式算是比較好的方法。

 

PS. 文章中的兩張圖片，取自Intel在GDC 2008發表的演講內容。

繪圖執行緒的設計

把繪圖功能分離成一個獨立的Rendering Thread一直是我想要做的一種設計，將遊戲程式的執行緒與繪圖的執行緒分開，理論上在多核心的電腦環境中，可以提高不少的運算效能。但在這裡面，還有個問題 -- Race Condition。

這是個很大的困擾。我要怎麼樣避免遊戲邏輯與繪圖功能存取到相同的繪圖資源物件？舉例來說，繪圖功能在讀取Vertex Buffer內容進行繪圖的時候，如何避免遊戲邏輯將資料寫入同一個Vertex Buffer？

不能將Vertex Buffer這些繪圖資源鎖在執行緒裡，繪圖物件很多，存取頻率又很高，這麼頻繁的上鎖解鎖動作，只會耗掉不必要的效能，沒有多少好處。想了很多，卻一直沒有好的方法。


一直到今年的Game Developer Conference，我看到了這張圖。

兩種模式差異並不大。紅色是遊戲邏輯的執行緒，綠色是繪圖執行緒，中間的藍色代表的是繪圖指令。邏輯執行緒將繪圖指令送到佇列中，繪圖執行緒從佇列中取出指令執行。

一個很簡單的架構，就將邏輯執行緒與繪圖執行緒切了開來。

繪圖執行緒擁有繪圖資源物件的存取權，邏輯執行緒不能直接存取繪圖資源物件，只能透過繪圖指令。這麼一來，就沒有兩個執行緒存取相同資源物件的問題，也就能夠避免Race Condition的發生。

當然了，這只是架構設計，實作層面也應該還有很多目前還沒看到與想到的問題，現在正準備寫個程式來實現這樣的架構，看看到底會面臨什麼樣的問題。

等實做程式出來以後，再來做個記錄吧...

PS. 文章中的圖片，取自Intel在GDC 2008發表的演講內容

Update 8/3 : 在Nebula Device這個引擎上，看到Rendering Thread是採用Proxy Pattern的方式來做，邏輯執行緒中用到的物件都只是Proxy物件，真正的繪圖工作是Proxy所指向的物件來實際執行。這方式也不錯，不過我還是 比較喜歡Command Queue的方式。