記憶體配置:Pooled Allocation技術評比與效能測試

從剛進入遊戲業界開始,我就一直對於「記憶體配置」(Memory Allocation) 的系統架構與相關議題很感興趣。後來隨著閱讀書籍量的增加與工作經驗上的累積,逐漸接觸到各種不同設計架構與實作方法的記憶體管理機制,現在終於能夠將一些初步的心得整理出來了。

在遊戲程式設計的領域中,程式設計者經常需要即時且動態地產生出大量的小型物件,例如怪物、特效、場景物乃至於低階的節點物件等等。如果遊戲程式設計者只是天真爛漫地使用著單純無害的 operator new 以及 operator delete 程序,在經過遊戲執行中不斷反覆地配置與歸還記憶體的行為之後,很快就會使得完整的記憶體區段面臨嚴重的「記憶體破碎」(Memory Fragmentation) 問題。更糟的是,記憶體破碎的問題往往很難被偵測出來,而容易被開發者所忽略。

為了盡可能降低記憶體破碎的狀況,並且得到高效的物件配置程序,除了從高階層面利用資源管理 (Resource Management) 機制減少遊戲物件的生成與毀滅行為之外,同時也需要從比較低階的層面,也就是屬於記憶體配置的功能面向著手改善。在使用者每次進行 operator new 操作向作業系統索取記憶體空間時,C 語言的函式庫除了配置所要求的區塊大小以外,還會另外生成一小塊額外的區塊以簿記相關的資訊。對於經常進行生成與毀滅程序的小型物件來說,這樣的行為模式就顯得十分浪費而不具效率。如果能夠一次性的配置出一大塊記憶體,然後再依使用者的需求傳回部分區塊,可望就能夠改善 operator new 程序所產生的額外負擔。

為了能夠妥善管理一大塊的記憶體空間,程式設計者發展出了「Free List」這個用來處理動態配置記憶體的特殊資料結構。Free List 通常是以鏈結串列 (Linked List) 做為基底結構,將目前可使用以及使用中的記憶體空間紀錄並且連結起來。一般常聽到的「記憶體池」(Memory Pool) 或者「池式配置」(Pooled Allocation),就是利用 Free List 資料結構實作出來的記憶體管理機制,也是遊戲程式設計者不可不知的記憶體系統管理技巧。而應該如何實作出高效能的 Free List 結構,使創建物件與刪除物件時的負擔減至最小,更是池式配置記憶體機制中最關鍵的要點。

Continue reading

Database Hot Loader 最終曲:Tuning and Measuring Performance

歷經了漫長的 DHL 系統一二三部曲後,終於來到了這一系列文章的最終曲。

本篇的重點在於對 DHL 系統進行效能的優化以及量測。首先,對於 LuaDatabaseManager 類別提出幾項效能優化的可能性。以資料庫系統的作用來說,一般使用者會期望在索取資料的程序中,得到最佳化的執行效能,才不會因為對於資料庫的頻繁讀取而拖累了遊戲系統的整體效能表現。在二部曲中曾經提過,為了取得資料庫中的數值,使用者需要利用 LuaDatabaseManager 類別中的 GetData() 函式:

void LuaDatabaseManager::GetData(std::string& sheetName, std::string& fieldName, unsigned int id, std::string& value)
{
	int oldTop = lua_gettop(m_DBState);

	lua_getglobal(m_DBState, sheetName.c_str());
	lua_pushstring(m_DBState, fieldName.c_str());
	lua_gettable(m_DBState, LUA_GETTABLE_INDEX);
	lua_pushnumber(m_DBState, id);
	lua_gettable(m_DBState, LUA_GETTABLE_INDEX);
	value = luaL_checkstring(m_DBState, lua_gettop(m_DBState));

	lua_settop(m_DBState, oldTop);
}

在 GetData() 函式中,必須進行三次取出 table 結構的步驟;首先以 lua_getglobal() 函式取得最上層的 table,然後傳入欄位名稱以 lua_gettable() 函式取得第二層 table,最後再傳入資料 ID 以 lua_gettable() 函式以取得使用者要求的資料值。

熟悉 Lua 語言的讀者應該很清楚,除了使用 lua_gettable() 函式取得 table 結構中的數值以外,還有另外一項替代方案:使用 lua_rawget() 函式。預設情形下,在 lua_gettable() 函式中,會喚起 table 的 metamethod,而對於將 table 單純當成陣列結構處理的資料表格來說,其實並不需要這層額外的彈性,所以如果使用 lua_rawget() 函式取代原來的 lua_gettable() 函式,理論上應該能夠獲得某種程度的效能提升。

Continue reading

Database Hot Loader 三部曲:Implementing Observer Entity

Observer Entity

Observer Entity

在前篇文章裡,以 VSTO 與 Lua 實作了 DHL 系統中資料匯出、讀取以及管理的核心功能後,本文將以一個簡單的 3D 程式範例,介紹如何將 DHL 系統與遊戲物件相互結合,以實現真正能夠使用於遊戲專案中的預定目標。

藉由之前建立完成的 LuaDatabaseManager 類別,已經能夠幫助我們動態修改並且載入 Lua 格式的資料庫表格,但是該如何使遊戲中的物件對資料庫的變化產生自動化反應呢?只要利用設計模式中的 Observer 模式,就能夠使我們順利達成目標。

如圖所示,在範例程式中,以 OpenGL 繪製出一個基本的三角形物件以及一個矩形物件,同時在視窗裡不停地旋轉;而視窗程式的建立,則使用 GLUT 函式庫以簡化相關的程序。

首先,在程式碼中創建出 Triangle 與 Quad 類別,分別用來代表畫面中的三角形與矩形物件。而這兩個物件的頂點、顏色、位移、旋轉軸與旋轉速度數值,則由 Excel 工作表中的資料數據進行設定。在範例程式的 Excel 檔案中,共有以下三張工作表:

  • triangle
  • quad
  • speed

在 triangle 表格裡的 vertex1、vertex2、vertex3、color1、color2 與 color3 欄位,分別定義了三角形物件的三個頂點及顏色的資料,而最末的 translate 與 rotate 欄位則用來定義三角形物件的位移量與旋轉軸;quad 表格以此類推。在 speed 表格中,只有 triangle 與 quad 兩個欄位,分別定義了這兩個物件的旋轉速度。

Continue reading

Database Hot Loader 二部曲:Using VSTO and Lua

接續前篇文章的簡短介紹,本文將開始使用 VSTO 與 Lua 語言實作 DHL 系統。首先,定義 DHL 系統的開發環境以及執行環境:

Database Hot Loader 系統

  • 程式開發環境:Visual Studio 2005 Team Suite
  • 使用者執行環境:Office 2003

為了使 Office 2003 達成轉換資料格式的任務,必須仰賴 VSTO 所提供的擴充功能。Visual Studio Tools for Office (簡稱為 VSTO)的作用,簡單來說就是讓程式設計者能夠在 Office 應用程式中,使用 .NET 撰寫附加的擴充元件,使一般的文件檔案,也能夠具備客製化的特殊功能。另外,微軟 .NET 平台的優勢,就是能夠使用 .NET 家族中的任何一種語言來撰寫程式,在此我選擇 C# 做為開發 DHL 系統的語言。

只要使用 VSTO,幾乎就能夠達成一切 Winform 可以做到的事情。在活頁簿上放個按鈕元件?沒問題;另外產生一個全新的 Winform?小意思;在 Excel 的主選單上增加自訂項目?一片蛋糕。總是覺得 Office 應用程式某些地方用得不夠順手嗎?有了 VSTO 以後,就可以幫助我們達成自己動手撰寫擴充功能的願望。

在前篇文章中,曾特別提到需要使用 Visual Studio 2005 的 Team Suite 版本,原因在於 DHL 系統必須使用 VSTO 的「文件層級」(document-level) 擴充程式,而在 Visual Studio 的眾多版本中,只有 Team Suite 版本能夠開發文件層級的擴充程式,一般程式設計者常用的 Professional 版本則只能夠開發 VSTO 的「應用程式層級」(application-level) 擴充程式。關於文件層級與應用程式層級的介紹,請參考「Visual Studio Tools for Office 」中文線上文件裡的詳細說明。

Continue reading

Database Hot Loader 首部曲:Introduction

mana-energy-potion「我有一個夢想,期望有天我們能夠免於調校遊戲資料數據的苦痛。」馬丁路德博士夢想,是人人生而平等並且免於種族歧視的迫害。而我的夢想,沒有這麼崇高偉大,只是希望能夠幫助團隊成員改善遊戲的開發流程。

每次當我看到遊戲企畫者,為了調整遊戲中的各種數據,而必須不斷重複一連串繁瑣而且漫長的操作程序,就替他們感到很辛苦。為了測試資料數據的正確性,首先要在 Microsoft Office Excel 上輸入資料內容,存檔後匯出,接著以外部工具將文字檔轉換為遊戲自訂的檔案格式,把檔案置入遊戲目錄中,最後再開啟遊戲,等待遊戲程式以及遊戲資料載入完成,然後檢視執行的結果。

「咦,食人怪的偵察範圍太遠,而火球魔法的距離太近了些。」於是按下離開遊戲的快速鍵,然後在 Excel 表格中修改相對應的數據後,再次存檔匯出,再次以外部工具轉換為遊戲自訂的檔案格式,再次把檔案置入遊戲目錄中,然後再次開啟遊戲,再次等待遊戲程式與遊戲資料載入完成。

(圖片來源:www.play-gadgets.com)

除非企畫設計者擁有強大的靈動感知能力,能夠精準地預測出合適的遊戲數值,否則總是需要不斷地嘗試錯誤並且經歷許多修改程序,才能夠將遊戲數據調校到完美平衡的狀態。不停地、不停地、不停地重開遊戲,幾乎是每位遊戲企畫設計者都曾經歷過的處境。在遊戲專案開發初期時,可能還感受不到特別的困擾之處;然而當專案到了後期階段,遊戲中的美術素材動輒佔有成千上百 MB 的份量,所以每次開啟遊戲都必須要等待漫長的遊戲初始化載入時間,甚至只是修改單一一個欄位的數據,同樣難以免於遊戲重開的等待過程。

有沒有可能改善這種狀況,減少重新開啟遊戲程式的頻率?有沒有可能在不需要重新啟動遊戲程式的情況下,讓企畫設計者能夠即時調整遊戲的資料庫數據?

Continue reading

物件導向設計新思維:深入Policy-Based Class Design新大陸

自前一篇「物件導向設計新思維:探索Policy-Based Class Design新視界」發佈以來,已經過了很長的一段時間。在這篇千呼萬喚始出來的續集裡,將會進一步深入探索 Policy-Based Class Design 背後的設計概念與理論,以及在實作層面上經常會遭遇到的問題;最後,以一個遊戲系統中常見的音源引擎 (Audio Engine) 類別設計為範例,做為本文的片尾曲目。

記得曾經有人問過比爾蓋茲,如果有天他被迫一人獨自在荒島上生活,身旁只有一樣物品陪伴的話,最想要什麼東西?他的回答是:「一部電腦與編譯器。」許多程式設計者心裡所嚮往的美好世界,就是那種無拘無束、無邊無際的自由;好像只要手指還能夠活動、頭腦還能夠寫程式,天底下就沒有辦不到事情!只是,有時候這種無限度的自由,反而會對程式系統造成負面的影響。

《C++ 設計新思維》(Modern C++ Design) 書中的第一章,就對於程式系統的設計就開宗明義地闡述:

理想上,一個良好設計應該在編譯期強制表現出大部分 constraint(約束條件、規範)。

身為一位程式設計者,或多或少都有把自己的程式碼交給其他程式設計者使用的經驗,相對於「程式撰寫者」來說,所謂的「程式使用者」,就是那些使用你所撰寫的程式碼的人。就像是遊戲程式中經常使用的 DirectX、OpenGL 或者 .NET Framework 以及遊戲函式庫與引擎等等,我們都是身為「程式使用者」的身份。

Continue reading

容器們,奮起吧!—以常整數映射型別改進 STL Containers 的介面類別

承續前篇「容器們,奮起吧!—實做 STL Containers 的包裝介面」的內容,本文將進一步改善容器 Wrapper Class 的實做設計。文中將利用《C++ 設計新思維》(Modern C++ Design) 書中,第二章第四節的常整數映射型別 (Mapping Integral Constants to Types) 技術,將原來程式碼重複性極高的 ValueDictionary 與 AutoPtrDictionary 類別合而為一。

所謂的常整數,就是一個整數型別 (Integer) 的編譯期常數值 (Constant)。而利用以下這個簡單的 template 結構就能夠將常整數映射成不同的型別 (Type):

template< int V >
struct Int2Type
{
    enum { value = V };
};

這個長相奇怪的 Int2Type template 結構,是如何將常整數映射成為不同的型別呢?根據書中的論述:

Int2Type 會根據引數所得的不同數值來產生不同型別。這是因為「不同的 template 具現體」本身便是「不同的型別」。

Continue reading

深入Lua-based GUI系統架構與實做細節

cpp-to-lua-architecture在前篇「使用Lua實做GUI系統的遊戲實例」中介紹了 Lua 於 GUI 系統的基本用法後,本文開始進入 GUI 的核心功能層面。

一般來說,有數種不同的架構方式能夠結合 Lua 與 C++ 實做 GUI 系統。其一是將 Lua Script 當作純粹資料描述用的程式碼,僅儲存 UI Layout 相關的資料(如前篇文章所示),而由 C++ Code 掌控核心功能並且讀取 Lua Script 進行資料的處理。其二則是於 C++ 端實做出一組完整的 UI Widget 類別,然後再將這組 Widget 的所有函式、甚至所有類別,註冊給 Lua 端自行呼叫使用。

另一種方法則是在 Lua Script 中包含資料描述以及核心功能,將 GUI 系統的全部相關功能全權交由 Lua 端處理。而 C++ 端程式,則負責發送鍵盤與滑鼠的輸入訊息給 Lua 端程式,供 GUI 系統判斷各種 UI 事件。最後再將測試的結果,傳回給 C++ 端程式進行後續判斷與處理。本文將使用這一種架構來實做 Lua-based GUI 系統

Continue reading

使用Lua實做GUI系統的遊戲實例

在這篇文章裡,將以國外一個非常著名的休閒遊戲 Diner Dash 2 的實例,探討 Lua 的應用功能之一:GUI 系統。自前篇「Scripting系統概論與Lua簡介」對 Lua 的 What(是什麼)Why(為什麼使用)有了初步的認識之後,接下來的重點就是瞭解 Lua 的 How(如何使用)

在進入 How 的主題之前,先補充一下 Where(在何處使用)的概念。Lua 的能力十分強大,似乎無所不能,可以完成任何的任務與功能。但是就實際應用層面的考量來說,哪些功能與系統才是真正適合使用 Lua 的部分呢?又要如何區分 C++ 語言與 Lua 語言所能達成的任務呢?

以兩者擅長處理的事項來分類:

  • C++:低階核心、記憶體管理、資源管理、繪圖底層、數學運算、訊息發送。
  • Lua:使用者介面、人工智慧、資料管理、遊戲邏輯、動態行為。

複雜的運算與低階的底層核心,適合使用 C++;而因應設計需求,經常會變動的各種功能系統,例如使用者介面、人工智慧、遊戲邏輯等等就適合使用 Lua 來完成。另外,有安全性考量的功能層面,也應該使用 C++ 撰寫比較合適。

Continue reading