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;
}
Related Posts Plugin for WordPress, Blogger...