2010年12月23日 星期四

展開 min(min(4,2), 3) ?

我們可以在C/C++裡面定義巨集(macro),例如:

#define min(a,b) (a) < (b) ? (a) : (b)

在程式裡使用巨集,編譯時前置處理器(preprocessor)會將巨集展開之後,編譯器再對展開後的程式碼作編譯。例如:

min(4,2)

展會後會變成

(4) < (2) ? (4) : (2)

那麼 min(min(4,2), 3) 展開後會是什麼呢?為了查看展開後的程式碼,我們可以在VC的設定裡加上/P參數,然後重新編譯程式,編譯後會產生一個.i檔案,打開.i檔後搜尋到如下巨集展開後的程式碼。

((4) < (2) ? (4) : (2)) < (3) ? ((4) < (2) ? (4) : (2)) : (3)

觀察上面的程式後可以發現到,巨集的展開是先由參數,由內往外層展開。也可以發現到巨集展開的方式,和我們一般的函式呼叫是不同的,如果一個不小心沒有注意到的話,常常會得到預期以外的結果,這點是要特別注意的。

2010年10月24日 星期日

Symbian S60 5th v1.0 + Carbide.c++ v2.3

Symbian是我最早接觸的行動平台,同時也是我接觸過的平台裡面,最最不喜歡的平台。我不喜歡Symbian主要有二個原因。1、開發工具不穏定且不可靠。2、系統設計複雜學習曲線高。

撇開第二點不管,第一點還真是個嚴重問題。想像一下,當你寫好程式,編譯完成,然後按下Run啟動模擬器來執行或偵錯程式,模擬器花個幾分鐘啟動,在最後關頭卻給你當掉了,你說這東西能用嗎?每次按下Run啟動模擬器的動作,你都要祈禱啟動成功,這樣子的開發過程一點都不有趣。所以我非常非常的不喜歡Symbian~~

不過沒辨法,有時候我還是得用一下。最近因為又有需要所以更新開發環境,把Carbide.c++由v1.3更新到v2.3,同時把SDK由S60_3rd_FP2_v1.1更新為S60_5th_v1.0。更新完成試用之後,我不得不讚賞它一下。現在穏定度大大的提升了,原本三不五時就給你模擬器當掉的問題可以說已經沒有了,使用到目前為止雖然還有一、二次當掉的情況,但整體來說,這個問題可以當成是偶發的小問題,已經不會對開發造成不好的影響。除此之外,模擬器的啟動速度也有明顯的提升。光是這二點就大大的值得給它鼓勵勵,說聲讚!

不過話又說回來,雖然嚴重問題解決了,我還是不會變得對Symbian得感興趣,能不碰的話儘量不去碰。

2010年10月6日 星期三

非同步的寶石方塊

我一直很喜歡這類型的小遊戲。這類方塊遊戲的一個主要的特點是在於它可以在不中斷的情況下,不斷的接受你的輸入,不斷的去消去方塊,這讓整個遊戲變的非常有節奏感。有些同類型的遊戲就少了這樣的設計設計,當有方塊在消除時,一定要等這些方塊全部消除完畢,才能再繼續接受你的輸入,這等於硬生生的把遊戲給中斷,玩起來非常的不舒服,整個就遜掉了。

最近因為我的N73電池似乎有點問題(有陣子沒用後又拿出來用),所以又再換回A3100。為了紀念又換回A3100,所以就順便把寫好的一支寶石方塊小遊戲移植上去(完全GDI),看看效果。



等改天有空再改版到Good裡當作新的範例。

不過話說回來,換回A3100沒多久我就換成野火機。從某種角度來看,我也算是另一種全機制霸了(主要,幾乎)...不管如何,有空時又可以再多玩些不一樣的東西了...

2010年9月6日 星期一

Good Game Editor 1.2 Beta

* 新增Good.KillAllChild
* 關卡編輯器(Level Editor)支援按住Alt鍵以滑鼠拖曳物件作複製。
* 修正在關卡編輯器中拖曳物件過程中按ESC鍵的處理錯誤。
* AboutBox中,zlib及yardparser文字位置對調。
* 關卡編輯器新增使用方向鍵移動物件。
* 關卡編輯器中(Name|Visible|Rot|Scale|Repeat|Script)等屬性可以undo/redo。
* 關卡編輯器支援按住Shift鍵以方向鍵作色塊及貼圖物件縮放。
* 關卡編輯器支援以Tab鍵切換選取物件。
* 修正Good模組API傳入物件Id(0)的錯誤。
* 去掉Good模組中物件類別常數的前綴詞TYPES_。
* 去掉Input模組中按鍵常數的前綴詞KEYS_。
* 以Good.SetBgColor設定關卡物件BgColor等同於設定關卡背景清除顏色(ClearColor)。
* 新增範例lvlbg。
* 新增範例動態選單(menu)。
* 工具列新增一個可以開關ResourceView及一個開關OutputView的按鈕。
* AboutBox的連結(又)改成按鈕型式。
* 修正一個新增關卡的小問題,將HasClearColor初始為false。
* 將範例程式中使用的一些BMP圖形格式轉為PNG。
* 新增單人撲克牌遊戲:蒙地卡羅。
* AboutBox添加Wiki連結。
* 編輯器(Editors)的縮放比例最大可到800%。
* 修正一個新件貼圖物件大小計算錯誤的問題。
* 新增Good.GetTexId/SetMapId/SetTexId API。
* 新增檢查是否有新版本編輯器的功能(Help\Check for Update...)。
* 新增一個sample,簡單的示範縮放及旋轉(scalerot)。
* 移除AboutBox裡的waync's smallworld連結。
* 修正Good.GetDim在讀取貼圖物件時沒有正確回傳寬高的問題。
* 修正時間控制的問題,這樣在某些電腦上不會一執行遊戲時就失速。
* 新版本也能在iPhone上通過編譯執行。
* 增加對物件作縮放(xScale,yScale)及旋轉(Rotate)的支援。
* 把25940m改版一下支援iPhone,當作測試。
* 除了可以在Dependency指定外部資源(zip或good檔)外,新增可以加入搜尋路徑的功能。
* 以yardparser取代Boost Spirit作stge parser。
* AboutBox的Libs頁面裡的Spirit-1.8.5宣告變更為yardparser-1.5。

(下載)

2010年8月4日 星期三

25940p for PSP

自從上次更新過DevkitPSP之後,PSP版的25940p就無法編譯,其實是環境設定問題,不過當時沒有仔細去看是怎麼回事,直接就丟著不管。直到前天又突然想到,把DevkitPSP更新到目前R14後,試編譯一下,結果又可以編譯了,只不過這次是編譯問題,編譯不成功。既然可以編譯,所以花了點時間修正一下,順便作一些修正。下載

2010年7月26日 星期一

新增範例 :動態選單

新增一個範例:動態選單(menu)。下載

這是範例samples的另一個版本,主要作的示範是:
  • 如何動態顯示文字(英數字,中文也能以同樣原理製作只是較麻煩)
  • 示範簡單的選單動態效果
  • 示範觸碰檢定

2010年7月4日 星期日

單人撲克牌遊戲 - 蒙地卡羅

新增一個簡單的單人撲克牌遊戲:蒙地卡羅,簡單介紹一下玩法。下載

  1. 事先排列好5x5張牌。
  2. 每次移動一張可以配對的牌,並消除這對牌。在上下、左右及斜向相隣的二張牌,只要擁有同樣數字(不計花色),即可配對。
  3. 消除二張配對的牌後,剩餘的牌以往左往上的方式補滿空隙,接著在發新牌補滿後面的空格。
  4. 重覆步驟2~3,直到沒有牌可以配對及發完所有牌為止。
  5. 結果有二種。一個是勝利,成功的消除掉所有牌。另一個是Gameover沒有牌可以再作配對。

2010年6月17日 星期四

以Boost.Spirit實作算式計算機

Spirit是開源碼C++程式庫Boost裡的一個項目,大量使用了C++ Template Meta-Programming實作技術。它提供了一個用來實作語言剖析器的框架,就好像lex/yacc一樣是專門用來製作語言剖析器的工具。但是Spirit因為應用了C++ Template Meta-Programming的技術,使得我們可以在C++程式碼中寫出相當於EBNF 的描述且可直接編譯並執行,也因為如此Spirit是一套既神奇又威力強大的工具程式庫。

按照慣例,前面我們已經以手工的方法,以及lex/yacc的方式實作了算式計算機,這次我們要使用Spirit來作個簡單的算式計算機。

EBNF表示式

雖然前面我們已經提到過Spirit的神奇的能力,也就是可以直接把EBNF式直接以程式碼的形式寫在C++程式碼內,但是因為受限於C++程式語言的語言,有些表式法需要作些調動,這裡面主要有幾個地方的語法需要注意。

A B

上面是原EBNF表示式的寫法,用來表示一個序列,A之後會有個B。而在Spirit裡需改寫成如下的形式。

A >> B

看起來沒有什麼太大的不同,也可以很容易的理解這是表示在A之後跟著B的序列。再來是*號的用法。

A*

在EBNF內,在符號A之後加個*號,表示A的數量是可重複的,可以是0個以上的A所構成的序列。而在Spirit中需改寫成如下形式。

*A

正好相反,需要把*號擺到符號的前面,因為在C++裡面並沒有任何後序式的*號運算元。不過就算改成前置式也不會影響到原來所代表的意義,並不會造成什麼衝突,容易理解。

A?

這是表示符號A是可有可無,也就是A的數量可以是0個或一個。以下改成以Spirit的寫法。

!A

如你所見到的,問號變成驚嘆號,同時也提到前面變成前置式。那麼一個以上的表示式呢?一樣使用加號,也一樣改成前置式即可,如下所示。

+A

現在來看一個簡單的範例,如下所示是EBNF式,用來表示以逗號分隔的數字的EBNF表示式。
S := INTEGER (',' INTEGER)*

改成Spirit的形式。
S = INTEGER >> *(',' INTEGER);

很直接,也不需要再多作說明。不過上面的式子還不是最終可用的版本,底下還會再陸續交待清楚。

Parser

在上面我們所看到的EBNF表示S式中的INTEGER以及逗號是終端符號。根據我們在lex及yacc的教學中知道,這些終端符號是由lex或具有lex功能,也就是字彙剖析器所解析出來再傳遞給語法剖析器的。在Spirit中對應於yacc工具的語法剖析器功能就是在上一小節中,可以直接在C++程式碼中寫下EBNF表示式的功能,而對應lex的字彙剖析器的功能就是這一小節要介紹的內容。

在Spirit中提供了許多的Parser,這裡的Parser指的是字彙剖析器,像是整數的剖析器,浮點數的剖析器,字串的剖析器,或字元的剖析器等等,這些Parser可以和上面的EBNF表示式一樣混合在一起直接寫在程式碼內。例如上例的INTEGER就可以使用整數Parser來代換,而逗號就用字元的Parser來代換。

以下列出常用的Parser。
int_p             整數
real_p            浮點數
ch_p              字元
str_p             字串
range_p           字元範圍
chseq_p           字元集
anychar_p         任何字元
alnum_p           英數字元
alpha_p           英文字母
space_p           空白字元
底下舉幾個簡單的範例來作說明如何使用這些parser。左邊是常規表示式,而右邊是Spirit的寫法。
abc               ch_p('a') >> ch_p('b') >> ch_p('c')
abc*              ch_p('a') >> ch_p('b') >> *ch_p('c')
abc+              ch_p('a') >> ch_p('b') >> +ch_p('c')
a(bc)+            ch_p('a') >> +(ch_p('b') >> ch_p('c'))
a(bc)?            ch_p('a') >> !(ch_p('b') >> ch_p('c'))
[abc]             chseq_p("abc")
[a-z]             range_p('a','z')
看過以上幾個簡單的範例之後,相信對於Spirit的Parser有了基本的了解。現在我們可以把S寫成完整的Spirit式EBNF表示式了,如下所示。
S = int_p >> *(ch_p(',') >> int_p);
Spirit可以讓我們直接在C++程式裡面使用EBNF表示式,我們要怎麼在程式裡面使用S呢?S在程式裡面代表什麼?

在Spirit中S代表的是一個Rule,它的型別是rule<>,這是一般的表示式類型,事實上在Spirit裡一個rule<>已經是一個可以工作的Parser了。S完整的定義如下。
rule<> S = int_p >> *(ch_p(',') >> int_p);
在Spirit中有一個parse函數,使用parse函數我們就可以使用S來解析資料,使用方法如下。
bool parse_number(char const* str)
{
  return parse(str, S, space_p).full;
}
parse的第一個參數是文字串流來源,第二個參數就是我們提供的rule(parse),而第三個參數也是個Rule,是專門使用來過濾空白字元的,一般我們直接拿space_p來使用就足夠了,如果還有更複雜的過濾需求的話再另外提供即可。

最後parse函數的回傳值是一個叫作parse_info的結構,我們在上例裡面只拿它的full欄位來使用。full可以告訴我們解析的動作是否正常完成,即從資料來源的開頭一直解析到資料結尾都沒有任何錯誤發生。

動作程式碼

現在我們已經知道怎麼使用Spirit來實作一個Parser了,不過這個Parser還不怎麼有用,因為它還只能夠檢查文字資料是不是符合我們的語法。至少還得像lex/yacc一樣還能插入我們自己的動作程式碼到Parser裡面,這樣這個Parser才能真正為我們作點什麼。

繼續拿上面的例子來作說明。
S = int_p >> *(',' >> int_p);
假如每當我們的Parser解析出一個數字時,我們的程式想要獲得通知以便把這個數字儲存起來或者直接拿它來作點運算。在yacc裡面我們會在二個int_p後面插入一段動作程式碼,而在Spirit中也是一樣的作法,而且也很直覺。
S = int_p[&f] >> *(',' >> int_p[&f]);
在二個int_p的後面我們各加了一對方括號,而在方括號中是個&f。f是個函數,我們使用這樣的語法告訴Spirit當解析到一個int時呼叫我們的動作程式碼f函數。f函數有一個int的參數,我們可以直接使用這個參數,如果我們現在是使用ch_p則參數變為char,依此類推。

而你也可以使用一般型的動作程式碼函數,它的原型如下。
template<typename Iterator>
void func(Iterator first, Iterator last);
Iterator對應資料流的類型,例如char*。這個函數帶有二個參數,分別是解析出來的token在資料流中的開始及結尾。

你也可以一次使用好幾個動作程式碼在同一個位置,像下面的例子一次呼叫三個函數。如果指定二個以上的動作程式碼的話,它們會以左至右的次序被呼叫。
S = int_p[&f1][&f2][&f3];
呼叫函式也能是個functor(仿函式),它的原型如下。
struct myfunctor
{
  template<typename Iterator>
  void operator()(Iterator first, Iterator last) const;
};
使用方法如下。
S = int_p[myfunctor()];

實作

到此為此,我們已經學習了如何使用Spirit來製作Parser的相關知識,現在我們可以正式拿Spirit來實作一個算式計算機。

根據前面的介紹,首先我們把表示算式計算機的EBNF表示式改成以Spirit形式的表示式,工作就已經算是完成一大半,如下所示。
rule<> group, factor, term, expression;

group = ch_p(',') >> expression >> ch_p(',');
factor = int_p | group;
term = factor >> *((ch_p('*') >> factor) | (ch_p('/') >> factor);
expression = term >> *((ch_p('+' >> term) | (ch_p('-') >> term)
接著再加上parse函式的使用,就已經是一個可以運作的算式計算機程式了,剩下的只要再補上動作程式碼,用來處理真正的數值運算,整個程式就可以完成。底下列出不包含動作程式碼,但可以實際動作的程式列表。
#include <iostream>
using namespace std;

#include "boost/spirit/core.hpp"
using namespace boost::spirit;

int main()
{
  rule<phrase_scanner_t> group, factor, term, expression;

  group = ch_p('(') >> expression >> ch_p(')');
  factor = int_p | group;
  term = factor >> *((ch_p('*') >> factor) | (ch_p('/') >> factor));
  expression = term >> *((ch_p('+') >> term) | (ch_p('-') >> term));

  string str;
  while (getline(cin, str))
  {
    if (str.empty() || str[0] == 'q' || str[0] == 'Q')
      break;

    if (parse(str.c_str(), expression, space_p).full)
    { // Parsing succeeded
      cout << "Parsing succeeded\n";
    }
    else
    { // Parsing failed
      break;
    }
  }
  return 0;
}
把這個程式拿來編譯後執行起來看看,它可以用來檢驗一個算式的正確性。接著,我們要加上動作程式碼,讓它可以作真正的運算,計算出最後的結果。

前面我們學過動作程式碼的形式及如何撰寫動作程式碼,底下我們就以前面所學寫下四個分別用來計算加減乘除以及一個用來儲存得到的數字的動作程式碼,另外再配合一個用來模擬堆疊的vector容器。
vector<int> v;

void push_int(int i)
{
  v.push_back(i);
}

void do_add(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b + a);
}

void do_sub(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b - a);
}

void do_mul(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b * a);
}

void do_div(char const* first, char const* last)
{
  int a, b;
  a = v.back(), v.pop_back();
  b = v.back(), v.pop_back();
  v.push_back(b / a);
}
這裡所使用的方法和我們在學習資料結構與演算法時用來處理算式的方法一樣,也就是將算式由中序式轉換為後序式,然後再配合堆疊,就可以很容易的把算式結果計算出來。這部份的原理就不再這裡再複述一次,有興趣的話自行參考相關資料。

最後我們再把動作程式碼插入到rule內,整個Parser就完成。如下所示。
group = '(' >> expression >> ')';
factor = int_p[&push_int] | group;
term = factor >> *(('*' >> factor)[&do_mul] | ('/' >> factor)[&do_div]);
expression = term >> *('+' >> term)[&do_add] | ('-' >> term)[&do_sub]);
另外補充一下。在上面這幾行的rule裡面就沒有再看到ch_p的使用,那是因為Spirit已經有對一些operator作針對字元參數的覆載(overload),所以我們就可以省略掉ch_p。不過在有些情況下,C++編譯器還是會找不到正確的operator函式,當這樣的情況發生時,我們只需明確的寫上ch_p即可。或者為了避免這樣的情況發生,你也可以一律都用統一的寫法加上ch_p。

2010年6月10日 星期四

malloc(0)的回傳值?

用VC寫個小程式作個實驗。

int *a = (int*)malloc(0);
if (a)
  cout << "not null\n";
else
  cout << "null\n";

程式執行的結果是,

'not null'

為什麼配置一塊大小為0的記憶體的回傳值不是NULL?

  • 有時候要配置的記憶體大小是計算得到的,這個大小有可能為0,為了和配置失敗回傳的NULL作區分,同時也能保持程式對任何大小記憶體的處理一致,所以就讓0大小的配置也回傳個有效的指標。

  • 不管是不是NULL,free都能接受。

  • ...

最後,根據C99標準

If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

所以,簡單的講,malloc(0)是沒有定義的行為。對於沒有定義的行為,去討論它是沒意義的...

2010年6月6日 星期日

2010/06/06 更新記錄

  • 新增檢查是否有新版本編輯器的功能(Help\Check for Update...)。
  • 新增一個sample,簡單的示範縮放及旋轉(scalerot)。
  • 移除AboutBox裡的waync's smallworld連結。
  • 修正Good.GetDim在讀取貼圖物件時沒有正確回傳寛高的問題。
  • 修正時間控制的問題,這樣在某些電腦上不會一執行遊戲時就失速。

2010年5月11日 星期二

虛擬檔案系統

大家都頃向於把自己遊戲所使用到的資源,以自己的檔案格式作加密打包。我也不例外,以前也和大家一樣設計了自己的檔案格式,可以將多個檔案加密壓縮打包起來,當然也還需要製作可以讀寫這種檔案格式的工具程式。實作出來後感覺還不錯,只不過其實這只是多此一舉的動作。

後來我改使用zip格式作資料包。想要加密?也沒有問題,加上密碼保護就可以了。工具也有一堆現成的,要用WinZip7-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++ FileStream或者是指向記憶體的StringStream。isFileExist和loadFile也很直覺,不必再多作說明。

這裡只需要對搜尋次序多作點解釋。

在實際應用時,如果整個遊戲會使用到的資源數量很多時,可以根據不同方法分類,區分成幾個子檔案系統,分別以addFileSystem加入。因為加入時會有次序關係,所以假如在不同的檔案系統內(如fs1.zip和fs2.zip)同時存在同樣名稱的檔案,則在呼叫loadFile時,只會回傳第一個找到的檔案。利用這個特性,我們可以用它來設計一個簡單的線上遊戲的檔案更新機制。

應用一

在遊戲開發初期,我習慣不作資料打包,所有資源都放在資源資料夾裡(如media),當然這個資料夾裡根據規劃還可以有其它子結構。這樣一來,每當美術資料或企劃資料有任何更新,我可以直接Copy新的檔案蓋過去來更新,不必作什麼打包的動作,所以可以很快的完成一個測試動作。把測試程式交給美術或企劃也是一樣,他們可以用同樣方法很快的作修改和測試。

等到最後階段再把整個資源資料夾裡zip起來(或視情況分成幾包),然後在程式裡面多寫幾行addFileSystem,其它程式完全不必動。當然,對於資料包我可能改個副檔名,把zip改成dat什麼的,不過加上個密碼後要解開也不是容易的事。

應用二

底下介紹一個使用虛擬檔案系統建立的小型線上遊戲更新機制。

線上遊戲每隔一陣子都會有更新,每一次的更新都會有一個更新資料包,這個更新資料包其實就是一個zip包,裡面包含了所有這個版本需要更新的檔案。

首先Client程式更新時會先從Server下載一個List,這個List會列出從第一個版本開始到目前版本的所有更新資料包的檔名和CheckSum。下載下來後,Client就拿這個List裡的名單來檢查自己Local端資料包,如果CheckSum不對或不存在就把它下載到Local端。

完成更新後,把List名單裡的所有資料包以addFileSystem一個一個加入,因為這份名單是根據更新的版本次序建立的,所以在以addFileSystem加入後,當程式裡去loadFile時能夠確保可以從這一堆資料包裡取出最新版本的檔案。

2010年4月28日 星期三

good Game Editor 1.1 Beta Release!

  • 遊戲資源編輯
    • 貼圖 (Texture editor, Jpeg, PNG, BMP)
    • 聲音 (Audio, OGG, WAV)
    • 地圖編輯 (Map editor)
    • 精靈編輯 (Sprite editor)
    • 關卡編輯 (Level editor)
    • Script編輯 (Script editor)
  • 範例程式
    • 打磚塊/寶石方塊/踩地雷等16個小遊戲範例
  • 遊戲範例
    • 25940m
  • 輸出WIN32獨立可執行檔 (Stand-alone exe)


;

本來要等到加上文字物件後再釋出,不過這陣子比較沒時間更新,所以先把目前的版本作為1.1beta釋出...

這個版本作了許多小更新,主要在加強 particle的部份,應用方面可參考25940m,另外API reference也作了更新。

下載good Game Editor 1.1 Beta
API 參考手冊

2010年4月15日 星期四

猜數字遊戲 (電腦猜人)

前幾天午睡時突然被告知要參加公司內部的程式設計比賽,題目是用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};

  sort(myints, myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while (next_permutation(myints, myints+3));

  return 0;
}
執行結果如下:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
不過因為我們是要產生4位數字的組合,而這4個數字是由0~9裡選出來的,也就是要作m取n的排列,但是next_permutation只能作n位數排列,所以需要另想辨法。

稍微設計一下之後,把這個操作分為二部份。第一部份首先選擇4位數數組,例如1234或2345等,接著再以next_permutation產生這些數組的所有排列,最後把所有這些數組的排列合拼,就能得到所有可能答案的排列組合。

那麼要怎麼挑出數組?也就是作出10取4的組合。

首先我把每一個數字當作一個位元來看,0x3ff這個數由十個位元1組成,可以表示為0~9十個數字全選。我只需要簡單跑個迴圈,從0開始找到0x3ff,如果找到的數是包含4個為1的位元的話,那就表示找到了一個我要的數組,接著把對應位元為1的位置轉換為數字就可以了。然後再拿它來透過next_permutation產生所有排列。

例:

9876543210
----------
0000001111 ==> 3210
0000010111 ==> 4210
1001001100 ==> 9632
依此類推..

如此就能產生所有可能的排列組合,完成第一部份的工作。至於第二部份就沒什麼好說的了,重點是在於一開始如何想通怎麼作,實作就更簡單了。

2010年4月3日 星期六

以lex/yacc實作算式計算機

前面我們透過手工的方式實作了一個簡易的算式計算機,現在我們要開始使用工具來作同樣的事,比較看看手工和使用工具有什麼不同的差別。首先要介紹的就是lex&yacc。

lex & yacc

lex(Lexical Analyzar)及yacc(Yet Another Compiler Compiler)是用來輔助程式設計師製作語法剖析器的程式工具。lex的工作就是幫助我們將輸入的資料文字串流分解成一個個有意義的token,而yacc的工作就是幫我們分析這些token和我們定義的規則作匹配。下圖中所表示的是使用lex及yacc的一般工作流程。



首先看到yacc會讀入一個.y檔案,這裡.y檔案的內容就是我們使用類似(E)BNF語法定義的語法規則,yacc會分析這些語法規則後,幫我們產生可以用來解析這些規則的程式碼,而這個檔案一般名稱預設為y.tab.c,產生的程式碼裡面最重要的一個的函式叫作yyparse。

同yacc類似,lex也會讀入一個.l的檔案,這個檔案裡面定義的是如何從文字流裡解出token的規則,使用的方法是常規表示式(regular expression)。在圖的左側中間我們還可以看到有一個叫作y.tab.h的檔案從yacc產生出來並餵給lex作輸入,這個檔案是yacc根據在讀入的.y檔裡面所定義的token代號所產生出來的一個header,這樣yacc及lex產生出來的程式碼裡面就可以使用共通定義的代碼而不必各寫個的。lex分析過.l檔案後也會產生一個一般預設叫作lex.yy.c的原始碼檔案,裡頭最重要的一個函式叫作yylex。

最後,我們把yacc產生出來的y.tab.c還有lex產生出來的lex.yy.c,以及其它我們自己撰寫的原始碼檔案一起拿來編譯再作連結,最後產生出來的就是一個可以用來解析我們定義的語法的解析器工具。以上是整個lex及yacc的使用流程概觀。

常規表示式

在正式使用lex之前,我們首先來對常規表示法作一個基本的認識。常規表示法是一種用來表示字串樣式(pattern)的中繼語言,就好比前文所介紹的(E)BNF表示式一樣,都是用來描述其它語言的語言,只不過用途不太一樣罷了。

常規表示式使用一些中繼符號(meta-symbol)以及ASCII字元定義字串樣式,以下列出一些常規表示式所使用的符號。
 .   表示除了換行字元以外的所有其它字元。
\n 表示一個換行字元。
* 表示左方的字元或樣式可以是0個或多個。
+ 表示左方的字元或樣式可以是1個以上。
? 表示左方的字元或樣式可以是0個或1個(可有可無)。
^ 表示是在一行的開頭。或者在方括號內表示[不包含]。
$ 表示是在一行的最後。
a | b 表示為a或b二者選一。
(ab)+ 小括號裡表示為一個子樣式,表示為有1個以上的ab組合。
"a+b" 字串常量"a+b"。
[] 一組字元,表示為這組字元當中的任一個。
底下列出一些範例。範例的左邊是樣式,右邊是符合樣式的字串。
 abc   abc
abc* ab abc abcc abccc ...
abc+ abc abcc abccc ...
a(bc)+ abc abcbc abcbcbc ...
a(bc)? a abc
[abc] a b c (三者其中之一)
[a-z] 任何a到z之間的字元
[a\-z] a - z (三者其中之一)
[-az] - a z (三者其中之一)
[A-Za-z0-9]+ 1個以上的大小寫英文字母及數字組成的字串
[ \t\n]+ 1個以上的空白字元 (包含空白,跳鍵及換行字元)
[^ab] 除了a及b以為的任何字元
[a^b] a ^ b (三者其中之一)
[a|b] a | b (三者其中之一)
a|b a或b其中一個
看過這幾個簡單的範例之後,相信對於常規表示式有了一個基本的認識。

lex

現在要開始使用lex來協助我們寫個簡單的字彙剖析器作練習,這個範例可以作簡單的計算字元數、字數及行數。在那之前我們先來看看前面提到過的要輸入給lex的定義檔案內容是長什麼樣子。如下所示,我們可以看到一份定義檔案內容以符號%%分為三大區塊。
%{
... 定義 ...
%}
%%
... 樣式 ...
%%
... 程式 ...
定義區塊裡面放的是我們的程式碼,我們可以把和應用程式相關的定義或宣告放在這個區塊裡面。lex載入定義檔為我們產生字彙剖析器的程式碼時,會原封不動的把這一區塊個的程式碼複製過去,而不會對這部份程式碼作任何處理。

樣式區塊是主要的重點區塊,裡面條列的是我們剛剛學習的使用常規表示式定義的樣式以及對應的動作程式碼,動作程式碼的作用等到稍後我們真正見到時再作說明。而程式碼區塊和定義區塊一樣,放置的也是我們自己的程式碼。lex在最後為我們產生字彙剖析器的程式碼時也會原封不動的複製過去,而不作任何處理。

接下來我們可以寫下計算字數行數範例所需要的定義檔。
%{
int nchar, nword, nline;
%}
%%
\n { nline++; nchar++; }
[^ \t\n]+ { nword++, nchar += yyleng; }
. { nchar++; }
%%
int main(void)
{
yylex();
printf("%d\t%d\t%d\n", nchar, nword, nline);
return 0;
}
在這份定義文件內,我們看到在定義區塊裡面有一行C語言的變數宣告,宣告了三個整數變數,nchar、nword及nline,分別用來代表接下來我們要計算的字元數、字數以及行數。

接著在樣式區塊裡面定義了三個樣式,根據我們在上一節裡面學到的對於常規表示式的知識,我們可以知道這三條樣式所代表的意義。
 \n   換行字元
[^ \t\n]+ 1個以上的非空白字元
. 換行字元之外的所有字元
我們現在要注意的是在樣式常規表示代的右邊以大括號括起來的程式碼,這就是前頭我們有提到過的動作程式碼。這是在字彙剖析器在分析字串樣式匹配時,若樣式符合且樣式有指定動作程式碼,也就是在樣式右側的程式碼,則這段程式碼就會被執行。

以\n這條樣式來說明,如果樣式匹配,則程式碼{ nline++; nchar++; }會被執行。注意到這裡的大括號,假如動作程式碼只有一行的話,則大括號是可有可無的,像是第三條樣式。但我們一律還是都寫上大括號以免有所遺漏,同時也要注意的是不管動作程式碼有幾條指令,全部都要寫在同一行裡面。

最後是程式碼區塊。這區塊裡有個main進入點,第一行指令呼叫了yylex這個函式。在前面的介紹中,我們知道yylex是由lex自動幫我們產生的函式,這個函式的工作就是幫我們作字彙剖析,一直到結束後才會返回。返回之後,我們再把計算的字元數、字數以及行數列印到畫面上。

看過這個簡單的範例之後,是不是對於lex是如何運作以及怎麼使用lex有點概念了。

yacc

yacc必須搭配lex一起使用,因為yacc主要的工作是作語法分析,而構成語法句子的token是由lex負責分析比對。和上一節同樣,我們透過一個簡單的範例來學習如何使用yacc。這個範例我們要作的是,能從輸入串流中的每一行文字裡讀取0個或1個以上的數字,如果有超過1個以上的數字,則每個數字需以逗號分開,最後再把所有數字相加的結果列印到畫面上,直到結束輸入為止。

首先我們第一步驟是使用EBNF表示式把規則寫出來。
S := INTEGER (',' INTEGER)*
因為yacc的樣式區塊裡的樣式使用的是BNF表示式,所以我們要把上述的規則改寫為BNF表示式。
integers := INTEGER | INTEGER ',' integers
有了BNF表示式之後,我們就可以寫出用來給yacc看的定義檔了。定義檔的格式和lex定義檔的格式類似,底下我們列出這個範例的yacc定義。
%{ 
int yylex(void);
%}
%token INTEGER
%%
lines
:
| lines integers '\n' { printf(" = %d\n", $2); }
;

integers
: INTEGER { $$ = $1; }
| INTEGER ',' integers { $$ = $1 + $3; }
;
%%
int main(void)
{
yyparse();
return 0;
}
上表是yacc定義檔,我們直接看樣式區塊部份。列表中我們寫了二條樣式,第二條integers也就是我們前面寫下來的BNF表示式。除此外我們再另外加了一條規則lines,這條規則可以讓我們在執行測試的時候可以連續測試多行的資料,而不必每次測完一行資料就需要再重新執行程式。

我們現在要注意的是在樣式的右側的動作程式碼。和lex定義檔裡的動作程式碼一樣,我們統一使用大括號將動作指令括起來。在動作程式碼裡面我們可以看到像$1、$2還有$$這樣奇怪的東西。在動作程式碼裡的這幾個符號是對應到樣式裡面的符號值,從左邊開始算來,第一個符號叫作$1,第二個叫$2,依此類推。而樣式左側,也就是樣式冒號的左側值則以$$表示。

因此,我們在lines樣式裡的$2就對應integers。預設情形下,符號值的型別是整數,當然我們也可以使用其它型別的符號值,不過這不是我們要談的重點,有興趣的話請參考lex/yacc相關書籍資料。lex定義檔內容我們就不再表列出來,可以自行參考範例內容。

實作

了解lex及yacc的使用後,我們就可以使用lex及yacc來協助我們實作算式計算機了。以下表列出yacc的算式計算機實作定義檔內容。
%{
#define YYSTYPE double
extern int yylex();
%}

%token NUMBER

%%
lines
:
| lines expression '\n' { printf(" = %lf\n", $2); }
;

expression
: term { $$ = $1; }
| expression '+' term { $$ = $1 + $3; }
| expression '-' term { $$ = $1 - $3; }
;

term
: factor { $$ = $1; }
| term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
;

factor
: NUMBER { $$ = $1; }
| group { $$ = $1; }
;

group
: '(' expression ')' { $$ = $2; }
;

%%
int main(int argc, char** argv)
{
yyparse();
return 0;
}
下表是lex定義內容。
%{
#include "y.tab.h"
%}

%%
[0-9]+"."[0-9]+ { sscanf(yytext,"%lf",&yylval); return NUMBER; }
[0-9]+ { sscanf(yytext,"%lf",&yylval); return NUMBER; }

[ \t] ;
[\n] { return '\n'; }
. { return yytext[0]; }

%%
int yywrap()
{
return 1;
}

2010年3月22日 星期一

我的小遊戲

之前提過,我平均每年至少會作個一款小遊戲(不管是新開發或重製),這些小遊戲會開放免費下載。到目前為止已經推出12款了,其中7款Windows遊戲,2款Symbian遊戲,1款J2ME遊戲和1款WindowsMobile遊戲。

開發這些遊戲除了自己好玩外,也是練功的好題目。所以可以發現到,這幾個小遊戲裡面,有好幾款其實只是不同平台的移植(同平台上用不同方式實作練習就不提)。透過這種方式我能接觸並學習到不同平台的開發,同時也能加強跨平台的經驗也訓練小技巧,一舉數得。

會把它開放到網站上,只不過是基於獨樂樂不如眾樂樂的簡單想法,有沒有獲得迴響其實也沒所謂。至少每當看著首頁那一堆自己的作品,只有一個爽字能夠形容!

(PS:這些遊戲有差不多一半都是WindowsGDI程式...所以效能難免有時不理想,不過那不是重點)

;


25940m (by good)
25940p


實驗中國象棋 (WindowsMobile,240x320)
實驗中國象棋 (Symbian s60, 176x208)


單人撲克101


小香咪咪方塊
小香咪咪方塊(J2ME1.0)


867 (upup原型)


鋤草機 (說明)


拼吐 (說明)


傷心掃雷 (Symbian s60, 176x208)


Paint by Numbers 2005 (說明)

2010年3月19日 星期五

C++編譯時期靜態多型在遊戲中的應用

上次談到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,讓所有物件都能存取到它,也就能存取到所有資料。為了簡單起見,我們讓CGameApp同時作為這個singleton範理所有狀態。
; 範例3
class CGameApp
{
CGameApp();
public:
CGameDB mGameDB;
CGameMgr<CGameObj> mObjMgr;

static CGameApp& getInstance();
};
如範例3,我們加了一個getInstance的靜態方法用來取得CGameApp的唯一實體物件。這樣就解決了所有問題。

;;;

底下我要開始介紹我使用的方法,應用C++編譯期靜態多型的小技巧,同時也包含跨平台設計的基本架構思想。
; 範例4
template<class GameT>
class CGameApp
{
};

class CGameAppWin : public CGameApp<CGameAppWin>
{
CGameAppWin();
public:
static CGameApp& getInstance();
};
CGameApp<>是GamePlay主體,完全只和GamePlay有關,是可跨平台的部份,因為它完全沒有使用到任何和平台相關的功能。CGameAppWin繼承CGameApp<>,實作和平台相關的全部功能,如顯像,音樂音效,讀寫檔等等。要跨平台的時候,只需要提供不同平台的CGameApp<>繼承者即可。

以上就是我的遊戲架構主體慣用手法,非常簡單。

;;;

這個架構如何作到跨平台?舉個簡單的例子會很容易了解。
template<class GameT>
class CGameApp
{
void onEnterGameMenu()
{ // 進入遊戲選單畫面。
...
// 此時,需要改變背景音樂。
GameT* pGame = static_cast<GameT*>(this);
pGame->notifyChangeBgm(ID_BGM_GAMEMENU); // 由GameT實作,CGameApp只作呼叫。
...
}
};

class CGameAppWin : public CGameApp<CGameAppWin>
{
// 實作,播放指定背景音樂。idBgm由CGameApp<>定義。
bool notifyChangeBgm(int idBgm);
};
如上例中,CGameApp<>在進入遊戲選單時會呼叫onEnterGameMenu函式,而在onEnterGameMenu中會呼叫一個叫作notifyChangeBgm的函式來發出通知,改變播放背景音樂。notifyChangeBgm函式在CGameApp<>中沒有實作,而是由GameT也就是CGameAppWin來實作。這樣就完全把音樂音效的實作細節切離開來。其它的功能也能如法炮製達到GamePlay和平台相關實作分離。

;;;

下面再看一個例子。
template<class GameT>
class CGameApp
{
// 初始化遊戲,成功回傳true失敗回傳false。
bool init();
};

class CGameAppWin : public CGameApp<CGameAppWin>
{
typedef CGameApp<CGameAppWin> BaseT;

// 改寫CGameApp::<>init。
bool init()
{
if (!BaseT::init())
return false;

// 其它初始化動作。設定顯示模示,初始化音樂音效模組等等。
...
}
};
上例中CGameApp<>有個init的函式用來初始化和平台無關的GamePlay,而CGameAppWin因為和平台有關,還有其它和平台相關的初始化需求,如初始化顯示模式,音樂音效等。所以CGameAppWin改寫了CGameApp<>::init達到這個目的。

實際上,這個例子並沒有使用到C++編譯期靜態多型,它只是單純的函式改寫,只不過是在實作上的一個慣用手法..

2010年3月8日 星期一

最簡單的單元測試工具 - CppUnitLite

測試驅動開發(Test Driven Development, TDD)敏捷開發流程(Agile Process)中扮演了一個很重要的角色,不過本文的重點在於TDD,不談Agile,實際上我也不懂,不懂的東西我也不談。

第一次接觸TDD,是在開發JSR-184時。在你的JSR(Java Specification Requests)實作和VM整合之前,VM Vendor會要求你的實作至少要通過TCK(Technology Compatibility Kit)。TCK是透過JCP(Java Community Process)取得,目的是用來驗證某JSR的實作品是否符合規範。實際上TCK就是一組使用JavaTest harness的測試包,包含了各種用來測試JSR的單元測試(Unit Test)。

以TCK for JSR-184來說,總共包含了161個測試項目,每一個測試項目裡面又再包含了2至10個子測試項目,而每一個子測試項目裡面又有不定數量的更小的測試。JavaTest是個自動化測試的環境,只要載入JSR-184的測試包,設定好環境之後就可以執行自動測試,然後看看結果如何。

JavaTest的測試都是Java寫的,雖然是Java新手,但是當時在發開發的過程中也能感受到TDD的威力。舉個簡單的例子:對於像我這樣不懂3D的人來說,還可以開發3D引擎,你說利不利害。我只需要想盡辨法讓測試能過關就行了,很多細節其實也不懂。這樣說雖然是比較誇張點,但我想要表達的是,TDD果然是神。

;

話說回來,C/C++是我使用最多的程式語言,所以我如果也要使用TDD的話,就需要找一套支援C/C++的TDD程式工具。因為我沒那麼聰明,所以都只挑簡單易用的,最後終於讓我找到了CppUnitLite這個工具。實際上是在閱讀<修改代碼的藝術>這本書時,從中學到的,CppUnitLite是作者設計實作的一套短小精幹的UnitTest工具,簡單易用。

這本書的內容我全部忘光光了,但我學會了使用CppUnitLite就算是值回票價了。現在底下內容要作個簡單的介紹,看看如何撰寫單元測試。

;

下載後解開檔案,我們只需要將om/CppUnitLite裡的檔案加到我們自己的專案就可以了,om/CppUnitLite裡的Cpp和CppUnitLite資料夾不用管它。

接下來就可以開始撰寫測試了,底下示範一個超簡單的測試。
#include  "CppUnitLite/TestHarness.h" 

TEST(test, test1)
{
  int a = 1;
  int b = 1;
  int c = 2;
  CHECK(a == b);
  CHECK(a != c);
  CHECK(b == c);
}

int main()
{
  TestResult tr;
  TestRegistry::runAllTests(tr);
}
以上,我們寫了一個簡單的測試單元:TEST(test, test1)。每一個測試用TEST這個Macro指定,名稱由二部份組成。它作了三個小測試,二二比較變數。前二個測試內容為真,所以沒問題可以通過,不過第三個測試b==c就不為真了,所以測試到這裡就失敗了。輸出結果如下:

Failure: "b == c" line 12 in d:\vs.net\testc\main.cpp
There were 1 failures

如果把第三條測試改為CHECK(b != c),則測試就能夠通過,輸出結果如下:

There were no test failures

很簡單吧。完。

;

目前使用CppUnitLite在smallworld2的開發上。每次新增功能,我的步驟是先設計介面,然後撰寫測試,最後實作。使用CppUnitLite可以很簡單的撰寫單元測試,但真正困難的是如何撰寫出好的測試,這是另外一個課題了。最後要補充說明的是,測試單元也是代碼,所以不要以為測試代碼不會有Bug。

2010年3月6日 星期六

手工打造算式計算機

前面已經對(E)BNF表示式作過一個簡介,現在要來看看怎麼樣實作一個可以處理簡單的整數四則運算的Parser。因為我們的重點將放在Parser的語法器(syntax analyser)上,所以忽略字彙剖析器(lexical scanner)不談,雖然一個Parser是由這二部份構成。

;

許多Parser或Compiler相關的書籍資料上,都會拿簡單的算式計算機作為範例,可以找的到算式計算機的EBNF表示式,底下我們直接引用:

expression = term ('+' term | '-' term)*
term = factor ('*' factor | '/' factor)*
factor = integer | group
group = '(' expression ')'

上面的語法可以使用來解析如下的算式:

1+2-3*4
5*(6-(7+8)/9)

;

那麼要如何實作出能夠解析符合我們定義好的規則語法的資料的剖析器呢?

一個剖析器的轉換工作主要分成二個部份:將讀入的資料串流分解為有意義的小單位 token,及處理這些token間的關係。將資料串流分解成小單位 token的工作我們不多作說明。我們現在直接假設我們已經能夠得到分解完畢的 token了,接下來的工作就是分析這些 token之間的關係,檢查它們是否符合我們定義的規則語法。

作法相當的直接。首先,我們從資料串流中獲取一個token,接著檢查這個token是否符合我們正在檢查的語法的第一個符號,如果比對結果是符合的話,那麼我們就把當前的 token 給丟棄並再讀入下一個token,接著再繼續拿這個token和規則的下一個符號作比對。在比對規則時,如果中間遇到了非終端符號,則這個非終端符號會再展開。一直重複這個動作直到讀完所有資料為止,比對的程序才結束。

拿我們定義的group規則來作說明,以下為虛擬碼。
// 檢查當前的token是否是我們所期望匹配的符號
void match(token)
{
  if (current_token == token)
    current_token = get_next_token(); // 如果匹配成功則再讀入下一個符號
  else
    error(token + “ token expected); // 比對失敗報出錯誤
}

// group規則
void group()
{
  match('('); // 第一個符號需匹配 '(' 字元 (終端符號)
  expression(); // expression是另一條規則需在往下展開 (非終端符號)
  match(')'); // 最後一個符號需匹配 ')' 字元 (終端符號)
}
使用這樣的方法我們可以很容易的把(E)BNF描述句轉成程式碼實作出來。

;

我們已經知道要怎麼把我們的算式計算機給實作出來,所以接下將前面定義的EBNF表示式轉換成如下的C/C++程式碼。
// 規則:group := '(' expression ')'
float group()
{
  float val;
  match('('); // 第一個符號需匹配 '(' 字元
  val = expression(); // expression是另一條規則需要往下展開
  match(')'); // 最後一個符號需匹配 ')' 字元
  return val;
}
接著是factor。
// 規則:factor := integer | group
float factor()
{
  if ('(' == current_token) // 是group規則的開始符號嗎?
    return group(); // 以group規則展開
  else
    return get_number(); // 讀解出一個數字
}
factor這條規則是由integer或group這樣的規則組成,其中 integer是個終端符號而group是非終端符號,所以我們一開始先作一個檢查來判定目前讀到的 token是不是group規則的開始符號,如果是的話就再以group規則展開,否則就直接讀取出一個數字來。

接著來看term這條規則。
// 規則:term := factor (('*' factor) | ('/' factor))*
float term()
{
  float val = factor();
  while ('*' == current_token || '/' == current_token)
  {
    if ('*' == current_token)
    {
      match('*');
      val *= factor();
    }
    else
    {
      match('/');
      val /= factor();
    }
  }
  return val;
}
最後是expression。
// 規則:expression := term (('+' term) | ('-' term))*
float expression()
{
  float val = term();
  while ('+' == current_token || '-' == current_token)
  {
    if ('+' == current_token)
    {
      match('+');
      val += term();
    }
    else
    {
      match('-');
      val -= term();
    }
  }
  return val;
}
大功告成!

;

因為我們實作的是簡單的算式計算機,所以用的方法很直接,對於錯誤的處理是直接中斷跳出,在更複雜的Parser就必須再配合roll back的機制,這樣才能處理option的情況,基本概念如下的虛擬碼。
bool ab()
{
  char* save = p;
  if ('a' == *p ++ && 'b' == *p++)
    return true;

  p = save; // roll back
  return false;
}
這樣子的實作手法會更一般化。

p是輸入串流也是我們讀取token的來源,在進入點我們一律會先把目前串流的位置記錄下來,以便當這條規則不符合時可以回覆原來的狀態,讓上一層規則可以繼續嘗試其它規則。

2010年2月5日 星期五

WTL簡介

good Game Editor的視窗編輯器是以WTL作為框架實作的,因為WTL的資料非常稀少,本文就針對WTL作個簡單的入門介紹。

歷史背景

ATL(Active Template Library,或者ActiveX Template Library ) ,它本來的目的是為了要讓COM元件以及ActiveX元件的撰寫變得更容易。因為ATL是拿來寫COM元件的,所以它只有幾個非常基本的GUI類別,相當於MFC的CWnd和CDialog。 很幸運的是,這幾個 GUI類別有很足夠的彈性可以讓像WTL這樣的東西架構在它之上。

WTL實際上是ATL的一組擴充,它也和ATL一樣都是以C++ Template寫成。它擁有許多像MFC的強大GUI類別所提供的能力,同時還能編譯出更小的執行檔。如果你學習過 MFC的程式設計,那麼你會很習慣於像MFC那樣的元件包裝還有很彈性訊息處理機制,也就是說你會比較容易進入WTL的世界。

WTL有二個主要的修訂版本,版本3及7。版本的號碼對應到ATL的版本號碼,這也是為什麼不叫作版本1及2。一直到版本7.1之後微軟將WTL變成一個開源碼的專案,寄駐在Sourceforge上,而目前最新的版本已到8.1。

安裝

你可以在底下的位址下載到最新版本(http://sourceforge.net/projects/wtl/),目前最新的版本是8.1版,而good是使用8.0版本製作。在網站上提供了exe版的自解壓縮檔和zip格式的檔案。下載下來後,解壓縮到電腦上任意的位置。

解壓縮後,AppWiz、AppWizCE 和 AppWizMobile 三個資料夾,提供了以 Java Script撰寫成的針對不同版本Visual Studio的安裝程式。根據自己電腦上安裝的 VS.NET 版本,選擇對應的安裝程式來自動安裝 WTL 精靈到你的VS.NET資料夾。Samples資料夾裡有一些有趣的教學範例程式,有興趣的話可以自行研究看看。

因為WTL完全是以C++ Template實作,所以只有C++ Header檔,不需要任何Lib檔,所以我們只需要把include資料夾的位置加到自己專案的搜尋路徑裡就完成了安裝。因為 WTL可以是個通用的模組,所以一般來說我會選擇把它加入到全域的搜尋路徑裡,這樣就不必每個專案都新增一次搜尋路徑。

以 Visual Studio 2003 .NET 為例。選單〔Tools→Options〕叫出對話盒視窗,在左側選取〔Projects→VC++ Directories〕,在右側〔Show directories for:〕裡選擇 Include files,然後新增你的電腦裡WTL的include資料夾路徑。這樣就完成了整個安裝流程。

應用程式精靈

在VC新增一個專案,如圖所示,現在可以看到多了一個WTL精靈可以選擇,我們選擇了它來新增一個WTL專案。輸入專案名稱後,按下OK鍵進入應用程式精靈畫面。


首先看到的是精靈的第一頁介紹頁面,這個精靈主要的工作是協助我們設定視窗應用程式類型,以及視窗屬性。若是在此直接點擊Finish鈕則可立即以預設設定完成新建專案。


精靈的第二頁,可以看到左側的選項裡有許多不同種類的應用程式可以選擇,我們使用預設值,使用SDI(Single Document Interface)類型的應用程式。右邊的options項目也都保留預設值不動。


第三頁的選項和視窗使用者介面功能有關。和MFC一樣,WTL為我們提供了方便的ToolBar及StatusBar介面,也能夠根據應用程式的需求指定View視窗的類型。


按下Finish鈕,完成設定建立一個新專案。你可以看看WTL為你產生了那些檔案,接著按下編譯鈕編譯整個程式並執行看看。一行程式都不用寫,就可以生出一個漂亮的視窗程式來。你可以自己再使用精靈試試看不同的選項,產生不同類型的應用程式出來玩玩看。

下圖是WTL應用程式精靈產生出來的程式,編譯後並執行起來的畫面,不需要寫下任何一行程式就能輕鬆獲得。

2010年2月1日 星期一

(E)BNF表示式

BNF(Backus-Naur Form)是由John Backus所開發,可用來表示與上下文無關文法的語言,也就是一種用來描述語言的中繼語言(meta-language)。一個BNF表示式是由一個非終端符號(non-terminal)和它的產生式所組成,產生式可以是一個終端符號(terminal)和非終端符號組成的序列。(終端符號中的標點符號一般使用單引號括起來,而字串則使用雙引號)

底下為一個簡單的範例:

sent := subj verb '.'
subj := “Birds”
verb := “sing”

在上面的例子裡面,如Birds、sing及句點('.')表示終端符號。而sent及verb表示為非終端符號。這條BNF句子定義了一條文法,表示的意思為,一個sent是由subj及verb再以一個句點為結尾所構成。

BNF表示式有以下幾種主要表示形式:

(1) S := A B C
(2) S := A | B | C
(3) S := {A}

第一條表示說,S是由ABC三個符號所定義, 而ABC是以序列的形式依序出現,也就是說A之後一定跟著一個B,而B之後一定跟著一個C。第二條表示說,由S可推導出A或B或C其中之一。第三條表示說,由S可以推導出一個或多個A。

範例:

S := x A
A := y | z

(1) xy (O)
(2) xz (O)
(3) xx (X)
(4) yz (X)

以上4個範例中,只有(1)(2)是符合上面BNF文法定義的句子,因為x之後只能接y或z所以(3)不符合文法,因為S只能以x開頭為句子所以(4)也文法錯誤。

範例:

id := alpha {alpha}
alpha := a | b | c | d

(1) aabbbcdd (O)
(2) cabbbda (O)
(3) baccab (O)
(4) bdax (X)
(5) 5acd (X)

在上面的5個範例裡面,其中(1)(2)(3)項是正確符合上面BNF的文法定義。而(4)因為alpha裡不包含x符號所以語法不正確。而(5)因為alpha裡面不包含5所以也不正確。

範例:

S := '-' FN | FN
FN := DL | DL '.' DL
DL := D | D DL
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

這幾條規則可以用來描述如3.14這樣的浮點數或如-3.14具有負號的浮點數。在DL這條規則裡面我們看到了它的定義中還出現了自己,用自己來定義自己的情況,也就是說這是一種遞迴的定義形式。雖然還是勉強能夠看的懂這些定義,不過還是有點不是那麼直覺易用,所以後來又出現了BNF的擴展形式EBNF(Extended Backus Naur Form),EBNF引進了底下幾個新的符號改進了這些問題。

(1)?:表示符號左方的符號(或左方的括號中的一組符號)是可有可無 (optional)。
(2)*:表示符號左方的符號的數量可以出現0次以上。
(3)+:表示符號左方的符號的數量可以出現1次以上。

所以上面的浮點數範例使用EBNF可以重新改寫成如下的形式。

S := '-' D+ ('.' D+)?
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

這樣是不是變的簡單明瞭多了?當然EBNF並沒有比BFN強大到那裡,只不過和BFN比較起來在使用上更加方便而已,而所有的EBNF表示式都是可以轉換為BNF表示式的。

;

有了EBNF表示式的基本認識之後對實作parser會有幫助,之後再介紹如何使用不同工具實作parser。

2010年1月23日 星期六

特訓99稱號

以前在網站上擺過後來移除,現在再把它放在這。這是玩了N次收集到的,純脆是個人收藏,只是不知道還有沒有沒收錄到的...

2010年1月1日 星期五

實驗中國象棋 for WM/PPC

每一年不管是新作或改版我至少要製作一個小遊戲,放在我的網站上公開免費下載,一般都在元旦的時候釋出。


今年開放的是實驗中國象棋 WindowsMobile/PocketPC版,目前已公開過Symbian版,而這也是我第一次公開 WindowsMobile/PocketPC上的小遊戲。 下載


這個版本是使用我最新的PC版核心來作移植,不過PC版是只供個人使用,沒打算開放。放張圖看看就好。

Related Posts Plugin for WordPress, Blogger...