實作Lua Closure二合一洗牌發牌機

dice-triangle

(圖片來源:maniacworld.com)

亂數 (Randomness),是每一位程式設計者們熟悉又親切的好朋友,無論我們開發製作的是哪一種類型的遊戲,亂數機制總是在遊戲設計程序與撰寫程式碼的過程中,扮演著不可或缺的重要角色。亂數最重要的用途,就是提供遊戲世界中必要的「不確定性」,只要能夠將這份「不確定性」的設計機制運用得宜,就可以為玩家們帶來許多驚喜感與樂趣元素。

然而,有許多時候,亂數的產生並不只是使用 rand() 函式般單純容易而已。在某些遊戲機制裡,無邊無際的亂數數值,並不能滿足程式設計者或企畫設計者所想達到的目標——我們需要的是「亂中有序」——能夠在某個限定範圍之內產生亂數。

何謂「亂中有序」?撲克牌遊戲就是一個最好的實例。撲克牌由 4 種花色與 13 種數字,組合成 52 張「牌組」。而「洗牌」(Shuffle) 動作可以定義為:在一組有限的集合元素內,進行亂數排列的程序。只要將牌組洗完之後,就可以按照牌堆的排列順序,開始一張張地進行「發牌」動作了。

對於程式設計者來說,不論是使用哪一種程式語言,要實作出洗牌與發牌的功能都不是件太困難的事情。假設,我們可以使用 Lua 語言來實作洗牌發牌機,是否能夠創造出什麼樣有趣的變化?

Continue reading

快快樂樂學遊戲Threading程式設計

這是我在近期內對於 Threading 主題的學習整理文。如果你對於多執行緒程式設計沒有半點概念的話,建議可以先從我之前寫的「多核多緒多樂趣」開始閱讀,然後再視個人需求取用以下各項資源。

所謂的「多執行緒」程式設計,或者可簡稱為「多緒」程式設計,在英文中有許多相關的專業技術名詞,例如 Threading、Multithread、Concurrency、Parallel、Multicore 與 Multiprocessor 等等,在搜尋資料時可以嘗試不同的關鍵字,往往可以找到不少意料之外的好東西。而其中最常見的總括性簡稱,應該就是 Threading 了。

基礎定義

既然要學習 Threading 程式設計的知識,首先要瞭解的當然是 Threading 的基礎概念:

  • Thread:看看 Wikipedia 裡的定義,至少把最前頭那段 Thread 的基本定義,以及 Thread 與 Process 的不同之處搞懂。簡單來說,執行緒是用來執行電腦程式的執行環境;而多執行緒,就是能夠使程式系統同時執行多個不同程式碼區段的一種技術。
  • Thread Safety:雖然使用 Threading 技術能夠提升程式系統的執行效能,但伴隨而來的則是麻煩又難解的 Thread Safety 議題。大致上,我們可以使用 Re-entrancy、Mutual exclusion、Thread-local storage 以及 Atomic operations 這四種方法來達成安全使用多執行緒技術的目標。

Continue reading

MSVC與CRT的恩怨情仇

很久沒有寫程式設計入門知識的相關文章了,這篇文章要來談談程式庫 (Library) 連結,以及關於 MSVC 與 CRT 之間的種種恩怨情仇。

如果你使用的作業系統是 Linux、Mac 或其他非 Windows 平台,你可以忽略這篇文章;如果你使用的作業系統是 Windows 平台,但沒有用 Microsoft Visual Studio C++(以下簡稱為 MSVC)軟體撰寫 C++ 程式的話,這篇文章對你的幫助可能很有限;但如果你的作業系統是 Windows,而且你使用的程式整合開發環境是 MSVC 軟體撰寫 C++ 程式的話,這篇文章應該能夠幫助你釐清一些重要的基礎觀念。

身為程式設計者,在學習程式設計的過程中,你是否曾經遇過某些看起來不知所云的錯誤訊息,卻不知該如何解決?例如當你快快樂樂地寫完程式,並且確認所有的程式碼都能成功通過編譯之後,接著執行「建置方案」(Build Solution) 的步驟,結果卻跑出一堆莫名其妙的錯誤:

LIBCMTD.lib(mlock.obj) : error LNK2005: __lock 已在 MSVCRTD.lib(MSVCR80D.dll) 中定義過了
LIBCMTD.lib(mlock.obj) : error LNK2005: __unlock 已在 MSVCRTD.lib(MSVCR80D.dll) 中定義過了
LIBCMTD.lib(crt0.obj) : error LNK2005: _mainCRTStartup 已在 MSVCRTD.lib(crtexe.obj) 中定義過了

…………

LINK : warning LNK4098: 預設的程式庫 ‘MSVCRTD’ 與其他使用的程式庫衝突,請使用 /NODEFAULTLIB:library
LINK : warning LNK4098: 預設的程式庫 ‘LIBCMTD’ 與其他使用的程式庫衝突,請使用 /NODEFAULTLIB:library
D:\Workspace\CrtLibTest\Debug\CrtLibTest.exe : fatal error LNK1169: 找到有一或多個已定義的符號

以一般的情況來說,如果在你的程式專案中有使用某些由他人所撰寫的第三方程式庫或是開源專案的程式庫,比較容易會發生上述的錯誤狀況。從上述這些看似離奇而令人摸不著頭緒的錯誤訊息中,我們大概可以猜測問題點應該在於 LIBCMTD.lib 與 MSVCRTD.lib 這兩個程式庫身上。但到底什麼是 LIBCMTD.lib 和 MSVCRTD.lib?在我們的程式碼中有使用這些程式庫嗎?

Continue reading

Strategy & State:條件判斷式的消除者

strategy-pattern

Strategy Pattern

身為一位程式設計者,你是否曾面臨條件判斷式繁殖過盛的困擾?經常用折疊不完的 N 層 if-else 結構來考驗自己的腦力?或是只能瞪著超過 500 行的 switch-case 條件判斷式舉手投降?您的困擾我瞭解,請容許我向您引薦本篇文章的雙主打星——Strategy 與 State 範式,讓它們帶領我們一同邁向美妙動人的範式之道吧!

首先要瞭解的是,為什麼要將 Strategy 與 State 範式放在同一篇文章裡介紹?因為兩者雖然在設計層面的動機與出發點有所差異,但是在實際的應用面中非常地相近。根據《物件導向設計模式》(Design Patterns) 書中的定義,只要將右圖中的 Strategy、ConcreteStrategyA 與 ConcreteStrategyB 角色,更改為 State、ConcreteStateA 與 ConcreteStateB,就會變成 State 範式的結構圖,可以說兩者就像是孿生兄弟般密切相關。

如果真的要區分出 Strategy 與 State 範式之間的差異,可以參考《重構——向範式前進》中論述的內容:

State pattern 對「必須在一整族 state classes 的實體之間輕鬆轉換」的 class 有益,而 Strategy pattern 則是有助於讓 class 把演算法執行任務委託給「一整族 Strategy classes 的某一個實體」。

從我理解的角度來解釋,Strategy 範式比較著重於包裝相同派系的演算法,而 State 範式則特別注重在各狀態之間的轉換邏輯。所以只要瞭解 Strategy 或 State 範式兩者之一,就等於學會了兩種設計模式,真的是太划算太值得啦!雖然 Strategy 與 State 範式非常單純而且易於理解,但這兩項看似不起眼的小小範式,卻經常能夠在程式系統中發揮很好的應用效果,絕對是程式設計者不可不學的必備基礎知識。本文中將以 Strategy 範式為主,說明兩者在遊戲系統中的相關應用。

Continue reading

遊戲專案的目錄結構規劃

不知道各位如何規劃遊戲專案的目錄結構?各位所使用的是專案管理體系的正規方法,或者只是隨意地將檔案與資料夾散佈在電腦中的各處?在一個遊戲專案的開發過程裡,重要的資產除了程式碼檔案之外,還包括了設計文件、美術素材、音效檔案,以及最終的執行檔等等。該如何妥善管理這些不同類別的項目,以達到良好的成效?在此將以我個人目前使用的方法,提出一套目錄結構的規劃架構,與各位一同進行交流討論。

有些人喜歡將許多各式各樣不同用途的資料夾,直接放置在電腦的「桌面」上,最後經常會使得整個桌布,幾乎被各種不同圖示與資料夾所淹沒。這樣的作法,在一時的使用上或許非常方便,但是如果沒有善加整理歸檔,未來很容易會找不到想尋找的目標文件或檔案。不論是公司的正式專案,或是自己在工作之餘開發的個人專案,都能夠從良好的目錄結構規劃中,得到易於管理與變動的益處。

首先,我習慣在電腦硬碟的作業系統槽(通常是 C 槽)之外,選擇一個空間足夠的磁碟槽,在根目錄下開啟幾個資料夾進行專案的管理:

  • Codespace:專案區,只存放由 CVS 或 SVN 等版本控制系統取出的各項專案。
  • Workspace:工作區,存放各項測試中的程式、待完成的工作項目,以及各種經常需要查閱使用的文件及資源。
  • Temp:暫存區,存放各種暫時物件,包括從網路上下載的安裝檔,以及檔案解壓縮後的資料夾等等。

專案區中的資料,應該經常與版本控制系統保持同步化,盡可能減少修改後的版本存在於自己電腦中的時間。即使個人的工作硬碟不幸遭遇毀損的狀況,也能夠由版本控制系統的伺服器中,重新取回整個專案的資料。而工作區,則用來存放各項試驗中的專案;例如在剛開始接觸 Boost.Pool 函式庫時,我就會在工作區裡開設一個測試資料夾命名為 TestBoostPool 進行各項測試,等到成果達到一定程度後,再將專案提交至版本控制系統以及專案區中存放。最後,在暫存區中的資料,則只是便利暫時性的使用,可以隨時將全部的內容清空刪除。

Continue reading

記憶體配置: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

登泰山而小天下:Boost C++ Libraries 初體驗

說來有些慚愧,一直以 C++ 語言做為謀生工具的我,在使用了多年的 C++ 程式語言之後,最近終於與聞名遐邇的開源專案 Boost C++ Libraries(簡稱為 Boost)進行了第一次的親密接觸。在本文裡,將參照 Boost 官網的「Getting Started on Windows」文章,於 Windows 作業系統以及 Visual Studio 2005 程式編譯器的環境下,詳細介紹安裝及建置 Boost 的步驟,並且在最後使用 Boost.Thread 函式庫做為測試範例。

從前就常聽到其他人談論著 Boost 的優點,但是只要知道其中由上千個標頭檔以及數十個函式庫所組成,而且還需要以繁複的步驟手動建立函式庫的 .lib 檔案,很容易就會使初學者望而卻步。對於用慣了程式整合開發環境以及現成函式庫的我來說,Boost 簡直就像是一座美麗動人但又戒備森嚴的堡壘般令人不敢輕易接近。多年以後的現在,總算是鼓起了勇氣重新面對 Boost。花了些時間閱讀文件,然後按照指示一步步完成安裝建置之後,發現原來這些步驟比起從前已經簡化許多,函式庫的使用也不如想像中的困難!

One of the reasons for boost’s success has been the cross-pollination of ideas between diverse library projects.

Boost 是由一群功能獨立的函式庫所組合而成的集合體,其中涵蓋了許多熱門而經常使用的函式庫,以及比較冷門的特殊功能作用函式庫。所有的函式庫都包含在名為 boost 的 namespace 中,不僅能夠使各函式庫維持一致的使用風格,同時也得以避免命名衝突的問題。如官網中的 FAQ 所述,Boost 的成功正是由於不同功能函式庫之間的「交叉授粉」(cross-pollination) 作用所致;雖然其中多數函式庫都能夠分開獨立使用,但正是由於函式庫之間相互支援的功能以及介面,才使得 Boost 的開發者社群與使用者社群能夠蓬勃發展且欣欣向榮。

Continue reading