很讚的遊戲編輯器

很多人都有使用 source control system(SCM) 的好習慣，不過我也發現到有些人在使用SCM時的壞習慣，以致於把使用SCM的好處給抵消掉不少，有時候甚至還得到反效果。其實我自己在初期剛使用SCM時，也是犯了同樣的壞習慣，一直到後來才意識到。因為這個壞習慣是那麼的不明顯，以致於大多數人都很自然而然的犯而不自知。 這個壞習慣是什麼呢？ 那就是把SCM當作是純粹的source code database來使用。為什麼我會說這是一個壞習慣(或錯誤)？雖然說source code database原本也是SCM的功能之一，但我認為並不是最重要的功能，最重要的功能應該是在control這個字的功能上面才對。SCM讓我們對source所作的修改、內容增減作記錄，每一筆記錄就是一個版本，每一個版本的所有變動都匯入到database裡。我們可以透過SCM client介面對這些版本作檢視，隨時可以更新到任意版本，隨時復原所作的變動回到指定版本。 在軟體開發過程中，有一大半都是在對原有的程式作修改，尤其是在大型的系統來說，有更多的小修改、錯誤修正等等。想想看，假如某一個版本的修改(bugfix或功能增減)僅在一個版本裡面就包含了十項、數十項或甚至數百項或更多的修改會是什麼樣的情況？ 當開發的軟體一切都正常的時候，把SCM當作source備份的database沒什麼問題，事實上也很合適。但是軟體的開發並不那麼簡單順利，尤其是大型系統的開發過程中，絕對會產生大大小小的bug。這些bug有時候很容易就可以解決修正，在一些複雜系統裡面，有些bug需要利用復原回朔(revert)的功能，將修改的內容還原到舊版本，一個一個版本往上回朔檢查問題是從那一個版本開始發生的。利用這個雖然辛苦但有效的土方法來找到問題發生點的版本，再去比對所作的修改是那裡產生的問題再去修正。 想想看當你用回朔法找到你想要解決的問題發生的某個版本，而在這個版本裡面有一堆的修改，裡面混雜了多個bug修正、功能增減等等會是什麼樣的情況？這一定會增加debug的難度。如果在這個版本裡面只包含對一件事情的修改，無論是bugfix或是功能增減，要回朔到上一個版本一定是件相對容易多的事情。一個版本只作一件事情，同時對於review也會是一件單純的事情。 所以對於SCM的使用，我永遠都秉持底下幾個...

如果拿程式執行速度和code size二者來比的話，我個人會先偏好較小的code size，而不會特別先去關注較快的執行速度，除非效能問題是個問題。很多時候，較小的code size，也意謂著較快的速度。C++程式最讓人經常誤解的一點是，會產生較大的code size，較慢的執行速度是另一個常見的迷思。不過事實上，在使用STL之類的template library或template class時，的確使用不當的話是特別容易產生較大的code size。下面提供幾個簡單的要點，可以幫忙稍減code size。 使用compiler的最佳化選項。一般分為針對執行速度最佳化或code size最佳化。以Visual Studio為例，/O1是minimize size對code size最佳化，/O2是maximize speed對執行速度作最佳化。 避免重複。把common code抽出來，作成function，library或之類的東西。減少source size也減少code size，也減少bug發生的可能性。 砍掉沒用的code。整支程式裡面若是包含了大量的無用程式，除了增加code size外，也可能會隱藏潛在的bug。花點時間，整理一個你的程式把無用的程式碼，短期內或可見的未來內用不到的程式碼清一清。不要過早加入用不到的功能，減少code size也減少bug。 不要include <iostream> ，假如你沒有用使用cin/cout/cerr/clog之類的內建物件。用include < iosfwd> 來取代 ，避免包含使用不到的物件來減少code size。 避免類似型別參數的template類。例如：vector<int> ，vector <unsigned int> 等，這些類別的參數可以替換成同一種型別，例如vector<unsigned int> 。使用同一類別的template容器，也能減少code size。 減少使用exception及RTTI。沒必要的話，減少使用exception及RTTI也能減少code size。 以上是幾個大方向上，如何減少code size的要點。當然還有一些手法，但都是較細節的小技巧，不一定有什麼幫助。就好像在作最佳...

我現在要作一個實驗，模擬一個虛擬的世界，這個世界的構造很簡單，是一張10乘10的地圖，總共100個格子所組成。在這個世界裡面，會隨機產生金幣，機率是一半一半，也就是說大約在這100個格子裡面，平均會有50個金幣。還要模擬某種生物，這種生物的生存目的很簡單，就是儘可能的吃金幣，因為這個世界的食物只有金幣。能夠吃愈多金幣的生物就愈能夠生存下來並把它的基因繼續傳播下去。生活在這個世界的生物就把它命名為吃金幣的人...吃金幣的人在這個世界能作的事情很有限，除了吃金幣外，他只能作上下左右四種方向的移動，每次只能移動一個格子。 這個實驗的目的是想辨法找到一個最佳的路徑搜尋方法，讓吃金幣的人儘可能吃愈到愈多的金幣。為了評估吃金幣的人的路徑搜尋方法有多好，需要有一個可以量化的方法。所以就很簡單的設定，如果吃金幣的人每吃到一個金幣就能獲得10分，分數愈高就表示它的路徑搜尋方法愈好。當然也不能讓吃金幣的人任意的作無限次移動，因為這樣一來就沒有意義了，因為吃金幣的人一定可以吃光世界上所有金幣。所以我們要限制移動次數，比如說200次，每200次移動後再來作評分。 我們將會使用基因算法(genetic algorithm)，讓吃金幣的人自行進化，得到一個認為最棒的路徑搜尋方法。 基因算法的主要精神是，對於所要解決的問題以模擬生物界物競天擇適者生存的自然法則，讓所摸擬的人工生物自行進化出在模擬世界中的優勢物種，也就是得到所求的最佳解。不過這裡講到的進化這二個字有誤導的嫌疑，實際上這也是大多數人對於進化及演化之間的誤解。進化這二字裡面隱含了方向性，而事實上演化是沒有方向性的，演化是生物對生存環境的適應。生物會演化成什麼樣子，沒有任何的目的性和方向性，這裡面帶有隨機性，主要取決於環境變因。 自然選擇和變異再加上時間是演化的基本原則，所以我們將要模擬的程式也是使用到這幾個基本原則。雖然實際上的細節，和真實世界生物界的演化並不相同，但因為我們利用這幾個演化的基本原則來模擬我們的世界，結果也會得到類似的結果。我們可以看到我們所模擬的吃金幣的人果真在這個金幣世界裡面，慢慢的演化出愈來愈聰明的路徑搜尋方法。而同自然界的生物演化一樣，你甚至無法知道也無法分析它到底是怎麼辨到的。 前面提到這個世界是個10x10的地圖，共有100個格子，在這個世界面裡有會隨機產生的金幣。如果一個格子上...

在 猜數字遊戲 (電腦猜人) 這篇文章裡，最後提到怎麼從10個數字裡面挑出4個數字的組合的方法。 這個方法很簡單，0x3ff這個數字共有10個位元1(bit)，我們可以把這10個位元和0-9這10個數字作一一對應。用一個迴圈來找從1到0x3ff這些數字裡面，有那些數字是包含4個位元1，也就是要找的。例如0xf這個數字，2進制是0000 0000 0000 1111，最右邊4個bit都是1，根據1的位置轉換後變成3210這個數字。同理0x17這個數，2進制是0000 0000 0001 0111也是4個bits為1，轉換後為4210這個數字。依此類推。 這個方法用來選取小範圍數的組合還可以，可是一但數字大了，效能就太慘不忍睹了。例如以今彩539的可能組合為例，全部1-39共39個數字裡面挑出5個，全部共有575757種組合。雖然57萬多種組合看起來不大，但是以上面的方法來找，則要搜尋的迴圈範圍一下暴漲為2^39才能得到這57萬組結果，這是一個天文數字。所以這個方法就不可行了，勢必要使用更有效率的演算法才行。 稍微研究後，很幸運的不到10鐘就讓我找到了一個看來可行的演算法，很快的寫了一支小程式來測試。測試結果果然很理想，以C(39,5)作計算測試，不到1秒鐘的時間就得到正確結果！ ; 底下是演算法的概述，同樣以10個數字取組合為例： * 考慮最簡單的情況，作10取1組合 0 1 2 3 4 5 6 7 8 9 10個數字共有10個位置可以放入數字1，從最左邊的位置開始，共有10個位置可選擇，所以總共有10種可能。 用計算組合的公式驗算一下，C(10,1)=10!/1!(10-1)!=10!/1!9!=10 * 考慮10取2的情形 因為第一個1有0-9共10個位置可以選擇，如果第一個1選擇放入位置0，則第二個1有1-9共9種位置可以選擇放入。因為位置0的情況已經考慮過，所以接下來只要往後看不再往前看，需要排除掉已考慮過的位置。接著考慮如果第一個1選擇放入位置1，則第二個1排除位置0和1後還有2-9共8種選擇。依此類推，根據第一個1的位置選擇不同，則有9(p0), 8(p1), 7(p2), 6(p3), 5(p4), 4(p5), 3(p6), 2(p7), 1(p8), 0(p9)種選擇，小括號內的p0-9為第一個1的選擇位置...

之前玩了一陣子的連連看小遊戲，不過一直沒有去想想這類型的遊戲的主要gameplay的原理。現在花了點時間思考一下，研究看它的模式，設計了一個簡單的演算法，寫了支小程式來試試，效果基本上還不錯。 基本玩法是這樣子的。地圖大小是NxM，填滿X種類的圖形，每一個圖形一定可以跟另一個同樣的圖形作配對。配對方法是找出一條二個同樣圖形之間的連線，就可以同時把這二個圖形消除。連線最多只允許二個轉折，中間必須暢通。 以下對基本判定原理作概述，如下圖。 現在要找出A點和B點之間的連線。r0和rn是上邊界及下邊界，c1-c2線在r0至rn之間滑動。只要確定A-c1及B-c2及c1-c2三條線是暢通，即找到連線。若找不到連線，再以同樣原理找垂直方向一次。 若水平或垂直方向都找不到，則連線不存在。

將小圖合併成大圖是最佳化的一種技巧，合併的時機可以是在程式編譯時期，透過工具或者是人工方式作到。或者也能在程式執行時期，由程式自動將小圖合併。這牽涉到怎麼將小圖合併成大圖的演算法，同時在繪圖時也需要支援怎麼從大圖裡抽取出原本是小圖的相關資訊等等。 這裡只對小圖合併大圖作簡介，提供一個簡單的演算法。 首先想到的是很直接的作法： 假設大圖是一張矩形，而小圖也都是矩形。一開始有張空白的大圖，當第一張小圖要擺進大圖時，先確認這張小圖是否可以放進這張空白的大圖裡，如果答案是可以的話，則將這張小圖擺進大圖的左上角位置。接著將空白大圖剩下來的空白區域切割成二塊空白矩形。切割的方法是，小圖以右及小圖以下作分界。 如圖所示，把1號小圖放進大圖後，剩下來的空白區域可以依小圖位置往右往下切成AB二塊較小的空白區塊。 接下來繼續同樣的步驟依序再擺入其它的小圖，如下圖所示。2號小圖可以擺的進去原來切出來的A號空白區塊，把2號小圖放進去後，剩下來的空白區域再以同樣的方法再切成AB二塊空白區塊。 依此累推，將各小圖一個一個塞進去，如果某張小圖找不到可以塞的進去的空白區塊，則再新開另一張空白大圖即可。 因為每次會把剩餘的空白區域切割成二塊，所以很自然的在實作上可以應用一個二元樹的結構，將每個節點分成左右二個子樹，底下列出主要的虛擬碼。 Node::Add(Image) {   if (NotImageAdded()) {     if (IsImageFit(Image)) {       AddImage(Image);       Left = new Node(BoundLeft + ImageWidth, BoundTop, BoundRight, BoundTop + ImageHeight);       Right = new Node(BoundLeft, BoundTop + ImageHeight, BoundRight, BoundBottom);       return true;     }     return false;  ...

花了二晚將前次發表的 KillSudoku 移植成Web版，這次利用HTML5的繪圖功能取代掉原來簡單的文字模式顯示，改良成更好的圖形顯示。 這個版本實作了簡單的編輯功能，可以很容易的輸入或創造謎題(滑鼠左鍵輸入再點一下取消輸入)。不過目前還沒有實作檢查輸入的題目是否有唯一解，所以如果嘗試去解沒有唯一解的題目時可能有會不可預期的結果。 這次增加了一個新的Pattern：XYZ Wings，不過現在懶的介紹了～ 目前只在Chrome及Safari上試過。 ( 試試看 )

使用INI格式，底下有幾個優點。 格式簡單易懂 、容易使用 編輯器隨處可得，編輯維護相對容易 實作一個INI Parser不難 在程式裡，無論是作為程式設定儲存格式，或是作為小型的資料庫格式，使用INI資料格式對於以上需求，綽綽有餘。Good Game Editor的 資料格式 就是現成的實例。 ; INI的格式內容非常結構化，一個INI是由Section組成，每一個Section裡面可以包含Item，每一個Item是由一對Key和Value組成。 一個Section由字元'['及']'所構成，括號所包圍起來的字串為Section的名稱。如[Player]。 Item由Key及Value成對以字元'='隔開組成。如Name=Waync Cheng。 所有在字元';'後面到行尾的文字都視為註解而被忽略。 底下是一個簡單的範例。 [Player] Name=Waync Cheng Windows提供了 GetPrivateProfileString 系列的API可以讀寫INI的資料內容，使用Windows API寫入INI檔案的方式如下。 char StrName[] = "Waync Cheng" WritePrivateProfileString("Player","Name",StrName,"c:\\test.ini"); 從INI檔案讀出的方法如下。 char StrName[MAX_LEN]; GetPrivateProfileString("Player","Name","DefaultName", StrName, MAX_LEN, "c:\\test.ini"); ; Windows API使用起來稍微不方便，同時也不具跨平台，底下使用C++語言設計一個新的INI讀寫類別，主要的設計考量是更方便的讀寫INI。 C++語言提供了operator  overloading 的機制，正好可以被我們利用來作為一個介面，讓我們可以更直覺的讀寫INI的內容。 ...

過早作最佳化是萬惡的根源 (Premature optimization is the root of all evil.) 最佳化守則 別作! (Don't do it!) 高手專用：先別作! (For experts only: Don't do it yet!)

大家都頃向於把自己遊戲所使用到的資源，以自己的檔案格式作加密打包。我也不例外，以前也和大家一樣設計了自己的檔案格式，可以將多個檔案加密壓縮打包起來，當然也還需要製作可以讀寫這種檔案格式的工具程式。實作出來後感覺還不錯，只不過其實這只是多此一舉的動作。 後來我改使用zip格式作資料包。想要加密？也沒有問題，加上密碼保護就可以了。工具也有一堆現成的，要用 WinZip 或 7-Zip 什麼的都可以，完全不必花費任何力氣就擁有工具可以讀寫資料包。所有我需要作的事就是設計一個程式庫，可以用來讀寫 Zip檔案格式 就行了。事實上 zlib 已經能夠滿足這個需求了，只需要再多作一點程式包裝。所以我多花了些功夫在程式介面的設計上，最後完成了虛擬檔案系統的設計( smallworld2 ::Archive)。 為什麼把它叫作虛擬檔案系統呢？因為它目前支援了二種檔案系統，一個是一般的路徑檔案系統，另一個就是剛剛提的zip檔案系統。不管你使用的是那一種檔案系統，對於呼叫者而言是抽象的。呼叫者只需要透過統一的介面只存取檔案，完全不必考慮這個檔案是在那個資料夾或那個zip檔內，或甚至是在那一塊記憶體內(這是第三種形式)。 class Archive { public:   bool addFileSystem(std::string const& path);   bool addFileSystem(std::istream& stream);   bool isFileExist(std::string const& name) const;   bool loadFile(std::string const& name, std::ostream& outs, std::string const& password=""); }; 如上是虛擬檔案系統的C++程式介面，很簡單。因為其中也使用了C++ stream作為資料交換介面，所以也能很容易的和 C++ IOstream 家族結合使用，變的很有彈性。 addFileSystem是用來增加一個路徑或zip檔案到搜尋路徑。而另一個stream的版本則是用來加入一個來自串流的檔案系統，這個串流可以指向C++ Fil...

前幾天午睡時突然被告知要參加公司內部的程式設計比賽，題目是用C寫一支文字模式的4位數字猜數字遊戲，由使用者來猜電腦的數字。在上星期時其實就已經有公佈了，但我沒有注意到所以是臨時加入，還好這是個簡單的題目，不用花多少時間就可以寫出來。 規則： - 這是一對一比賽，雙方各選擇一4位數字，不讓對方知道。 - 4位數字由數字0至9組成，每位數不得重複。 - 雙方輪流猜對方的數字，直到一方猜中為止。 - A方猜B方的數字後，B方根據A方的猜測回答幾A幾B。 - 一個A表示猜中一個數字且位置正確，一個B表示猜中一個數字但位置不正確。 - 當一方猜中4A0B時即表示猜中對方全部4個數字且位置正確，贏得比賽。 - 例：B的謎底是4208，底下箭頭左測是A的猜測，箭頭右測是B的回答。 　　　1234 ==> 1A1B 　　　5678 ==> 1A0B 　　　2406 ==> 1A2B 　　　... 　　　4208 ==> 4A0B ; 寫個程式讓玩家來猜電腦的數字不難，不過我從來沒有寫過讓電腦來猜玩家數字的版本，所以花了點時間想想怎麼寫。 研究後歸納出二個點。 1, 使用窮舉法將所有可能數字組合列出。 2, 每次猜測後根據結果排除不可能是答案的組合，重複這個動作直到猜中答案為止。 第1點只是實作問題，第2點概念也很簡單，但要過濾不是答案的組合根據的是什麼？乍看之下沒什麼頭緒，不過想通之後就非常簡單了。 它的基本原理如下：假如謎底是4561，如果猜1524則會得到1A2B。從相反的角度來看，如果謎底是1524，則猜4561時也會得到1A2B的回答。 利用這個方法，每一次猜測一個數字X後，再以這個數字當作答案，來和所有剩下來的候選答案作比對，如果得到的結果(幾A幾B)和數字X是一樣的話，就把這個數字保留下來繼續作為候選答案，否則就過把這個數字過濾掉。下一把，繼續從候選答案裡選一個出來猜，重複上面的動作，直到猜中為止。 ; C++ STL的algorithm裡有個叫作next_permutation的函數，可以用來生成排列。 #include <iostream> #include <algorithm> using namespace std; int main () {   int myints[] = {1,2,3};  ...

上次談到 C++編譯時期靜態多型 的原理，這次要介紹C++編譯期靜態多型要如何應用在遊戲中。雖然這篇文章主要是在談C++編譯期靜態多型的應用，不過其中也牽涉到跨平台的程式設計，所以也順便作點和跨平台程式設計的介紹。 跨平台程式本身不難，困難點在於如何把和平台有關的部份和平台無關的部份切割開，只要作到這點剩下來的就沒什麼難的了。至於要怎樣才能作的好跨平台程式設計並不是在這邊三言二語就能講的清楚。 總之記住儘可能的把平台有關和無關的部份分離，以及儘可能的使用標準的程式庫。例如std::string就是C++標準和平台無關，CreateWindow就是和Windows平台相關的API。 ;;; 如果我們是以C++物件導向來作遊戲程式設計，我們可能會有個上層的CGameApp類別，其它還有遊戲物件如CGameObj等類別。 ; 範例1 class CGameObj { }; class CGameApp { public: CGameMgr<CGameObj> mObjMgr; }; 在範例1中，CGameApp管理所有遊戲物件。這邊我們先不管CGameMgr<>是什麼東西，實際上在本例中我們也不需要去知道。 因為CGameApp是整個遊戲程式的核心，它除了管理所有遊戲物件(CGameObj)外，同時也管理所有其它和遊戲相關的物件或資源或者說狀態(State)。 ; 範例2 class CGameApp { public: CGameDB mGameDB; CGameMgr<CGameObj> mObjMgr; }; 如範例2中的mGameDB，是和遊戲會使用到的資料庫。現在問題來了，如果CGameObj的實體物件需要存取mGameDB怎麼辨。一個簡單的方法就是讓CGameObj內涵一個mGameDB的參考，我們可以在建立一個CGameObj物件時把它傳入CGameObj的constructor。 不過這樣作另一個問題又來了。在CGameApp內不一定只會有一個像mGameDB這樣的東西，通常還會有其它資料是其它物件需要存取的。如果全都傳到物件內，那肯定不是一個好辨法。 有一個更好的解決辨法，那就是把所有資料都集中在一起管理，把它變成一個 singleton ，讓所有物件都能存取到它，也就能存取到所有資料。為了簡單起見，我們讓...

smallworld是smallworld2網路架構的第三層(應用層)。 smallworld2網路架構分成四個階層，最底層是串流層(Stream)，負責提供最基本的TCP/IP串流封裝及連線管理。第二層為封包層(Network)，負責提供格式化的封包支援以及完整的斷線處理機制。第三層為應用層(Smallworld)，提供動態可擴展的分散式網路架構。第四層為遊戲應用層，提供和線上遊戲一般應用邏輯相關支援。 設計smallworld應用層最大的困難在於，必須讓使用者也就是應用程式的開發者，能夠以開發單一伺服器應用的單純方式，來開發一個分散式架構的多人連線應用程式，所有複雜的細節都需由底層處理掉。smallworld建立了二個概念來達成這個目標，分別是Scope及VirtualConnection。 對於伺服器S而言，所有訊息都是透過一條Connection傳送出去的。Connection的另一個端點可能是一個Client，也可能是另一個Server。而這個端點可能是與伺服器S有實際建立連線，也可能是間接和伺服器S建立連線。假如這個Connection與伺服器S間有實體連線，則伺服器S就能直接把訊息傳送給對方，否則就以間接的方式轉送過去。無論這個Connection是直接或間接的連線，對於伺服器S來說，是不必關心的事情，底層自動會想辨法把訊息傳送給這條Connection的對應的端點上去。所以對伺服器S而言，Connection是虛擬的。 Connection的取得一律透過定義Scope作為Filter來獲得。以線上遊戲為例。當一個玩家登入遊戲後，就會有許多個Scope和他建立關係，例如這個玩家的可見視野、玩家加入的組隊、公會、聊天室、P2P交易、商店等等。這些全都是Scope，概念一樣，只是定義不同。透過定義好的Scope，再拿這個定義作為Filter由可以到達的在線上的伺服器收集符合的Connection，之後就可以對這些Connection作操作。 以上是構成smallworld的二個重要Concept。 ------------------ 套用smalllworld的框架就可以很容易建立可以動態擴展的線上遊戲架構，不過在實際應用上還是會有其它問題。舉個例子說明：假如我以單一伺服器的方式實作了一支Server程式，這支程式可以處理完整的虛擬世界。伺服器執行起來後...

good::gx是負責繪圖的介面。它很簡單，至少目前來說還很簡單。只有二個介面：Image及Graphics。 Image介面對貼圖作一層薄薄的包裝，good執行的時候，所有使用到的貼圖的地方全都透過這一層介面作存取。下面是Image介面定義。 template<class ImgT> class Image { public: bool isValid() const; int getWidth() const; int getHeight() const; bool hasKeyColor() const; int getKeyColor() const; void setKeyColor(int keycolor); }; Graphics介面提供了很少的功能，目前只有貼圖和畫色塊二個功能，因為目前good的成像目前只需要這二個功能就足夠畫出所有東西。下面是Graphics介面定義。 template<class ImgT> class Graphics { public: bool drawImage(int x, int y, ImgT const& img, int srcx, int srcy, int srcw, int srch); bool drawImage(int x, int y, ImgT const& img) { return drawImage(x, y, img, 0, 0, img.getWidth(), img.getHeight()); } bool fillSolidColor(int left, int top, int width, int height, int color); }; + + + 實際應用的時候，只需要針對不同繪圖平台作不同實作品的提供，對於good內部而言，幾乎不必作任何修改。目前good::gx有四種實作品，GDI、SDL、imgp及OpenGL。