撲克牌遊戲設計類的程式設計是對初學者非常好的程式練習,若架構沒設計好程式碼寫起來的確會很麻煩,但設計好的話真的沒有什麼大問題。

不當之架構

每份 poker 遊戲設計的架構不應完全相等,但初學的人大多會想,因 poker 是 13 個數字 * 4 個花色,所以會宣告成 int poker[13][4] 或 int poker[4][13],我認為非常不適合!雖顯示上較為方便,但這樣產生一副 poker 在洗牌時、發牌時,分析上也較為麻煩,故不這麼做。

吾人建議:「處理歸處理,顯示歸顯示,把這二個分開來!」

洗牌 (shuttle,使用之架構)

產生 low~up 不重覆亂數很有名的一個演算法即是 shuttle ,不知是否有正式名稱,吾人通稱為  poker algorithm。它的精神流程大致如下

(1) 產生一個 low~up 的陣列 (有 up - low + 1 個元素)。
      for(i=0; i!=up-low+1; ++i) array[i] = i;
(2) 開始洗牌
     (2.1) 用隨機亂數產生 low~up 之整數 pos  : 
              pos = rand() % (up-low+1);
     (2.2) 將第 i 張牌與第 pos 張牌交換 : 
              tmp = array[pos]; 
              array[i] = array[pos];
              array[pos] = tmp;
     (2.3) 重覆 2.1 與 2.2,重覆 up-low+1 次,確保每張牌都有被換過。
(3) 洗好後,取出前 m 張,就產生了 m 個 low~up 不重覆之亂數。

在洗牌流程 (2) 上有許多的方式可修正,其特性等這裡並不探討。第二個方式是,先抽第 pos1 張,再抽第 pos2 張,接著再交換這二張牌,這樣的確有可能有些牌沒被交換過。另執行次數也不一,最常見是 n 張牌就交換 n 張,也有人認為多換幾次無所謂,所以洗了 2n 次;也有人認為洗了 n/2 次便可得到最佳亂數排列,這些於此均不探討。

綜合以上說明,洗牌的程式碼便出來了

#define N 52
#define SWAP(a, b){int t; t=a; a=b; b=t;}

// ====================================
// shuttle
void shuttle(int *array, int Size)
{
    int i, pos;
    srand((unsigned)time(NULL));
    rand(); // 先抽掉一個亂數

    for(i=0; i!=Size; ++i){
       // 取出第 pos 張牌
       // pos = rand()%52; // worst
       pos = (int) (N*(double)rand()/RAND_MAX); // better
       // 將第 i 張牌與第 pos 張牌交換
       SWAP(array[i], array[pos]); 
    }
}
 

顯示花色與數字

上面產生了52張牌,數字是 0~51, 但這和撲克牌似乎有點不一樣!因撲克牌數字是 A 2 3 4.... 10 J Q K (轉換後分別對應至 0~12),而花色是 ♠ ♥ ♦ ♣ (轉換分別對應至 0~3),接下來說明怎麼將這52個數字 (0~51) 轉換成撲克牌的花色及點數。這裡提出二種轉換方式,分別以二張圖做說明

EdisonX-079.png

吾人比較傾向上面這張圖的編碼方式。它的公式為

for (i = 0; i!=52; ++i){
    flower = i % 4; // 花色, 0~3
    number = i / 4; // 數字, 0~12
}

EdisonX-081.png    

上面這組對照也不錯 ,重點是一副新的撲克牌買來應就是這樣排列,所以用這組編碼的人很多!建議二組都要知道,因不同遊戲較適合的編碼可能不盡相同。這組的轉換如下

for(i=0; i!=52; ++i){
    flower = i /13; // 花色, 0~3
    number = i %13 ; // 數字, 0~12
}

但目前只能將數字 0~51 轉換成花色 (0~3) 及點數 (0~12),都沒講到顯示部份,接著就是顯示之部份。

顯示撲克牌之花色與數字

直接先提,是用 mapping table 的概念。經驗不多的人這方面比較薄弱 (老手也請不吝評論指導),接下來這段會是該思考的地方。上一點已提到,0~51 轉換成牌的花色與點數都是用公式去轉,但轉出來都是數字。

花色為 0: 梅花, 1:方塊, 2: 紅心, 3:黑桃
數字為 0: A, 1: 2, 2:3, ...., 8: 9, 9:10, 10:J, 11:Q, 12:K

於是先把要顯示的字串都先寫成一個 table

#define BUF_SIZE 3
const char flower_table[4] = {'\5','\4','\3','\6'}; // 4個花色
const char number_table[13][BUF_SIZE] = {
    " A", " 2", " 3", " 4", " 5", " 6",
    " 7", " 8", " 9", "10", " J", " Q", " K"};

 

問: 花色初值為什麼是{'\5','\4','\3','\6'}; ??
答: 去查 ascii code, 5 4 3 6 分別代表梅花、方塊、紅心、黑桃

問:為什麼要再設這二個 table ?
答:因到時算出 flower_index 後,就 putchar(flower_table[flow_index]); 算出點數 number_index後,就 printf("%s",number_table[number_index]);

問:為什麼還要那麼麻煩,一開始就直接設 poker[4][13] 就好了不是嗎?
答:不好洗牌、不好派牌、不好顯示,除了容易比較牌的大小 (也未必比較好比較) 之外,我想不到還有其它優點。

好了,假設我們使用的是第一個轉換方式,也就是

for (i = 0; i!=52; ++i){
    flower_index = i % 4; // 花色, 0~3
    number_index = i / 4; // 數字, 0~12
}

那麼「洗好一副牌,並顯示這副函的順序」便可寫成這樣

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 52
#define SWAP(a, b){int t; t=a; a=b; b=t;}


#define BUF_SIZE 3
const char flower[4] = {'\5','\4','\3','\6'}; // 4個花色
const char number[13][BUF_SIZE] = {
    " A", " 2", " 3", " 4", " 5", " 6",
    " 7", " 8", " 9", "10", " J", " Q", " K"};

// ====================================
// shuttle
void shuttle(int *array, int Size)
{
    int i, pos;
    srand((unsigned)time(NULL));
    rand(); // 先抽掉一個亂數

    for(i=0; i!=Size; ++i){
       // 取出第 pos 張牌
       // pos = rand()%52; // worst
       pos = (int) (N*(double)rand()/(RAND_MAX+1.0)); // better
       // 將第 i 張牌與第 pos 張牌交換
       SWAP(array[i], array[pos]); 
    }
}

// ====================================
// display
void display_poker(int *poker, int Size)
{
    int i;
    for(i=0; i!=Size; ++i) {
       // 顯示花色, flower_index = poker[i] % 4
       putchar(flower[ poker[i] % 4 ]); 
       // 顯示點數, number_index = poker[i] / 4
       // printf("%s ", number[ poker[i]/4 ]);
       printf("%s", number[ poker[i] >> 2 ]); // faster
       if(i%13==12) putchar('\n');
    }
}

int main()
{
    int i, poker[N];
    for(i=0; i!=N; ++i) poker[i] = i;
    shuttle(poker, N);
    display_poker(poker, N);
    return 0;
}

 

執行結果如下圖 (應沒發現有重覆的牌吧?)

EdisonX-082.png  

抽大小遊戲

現假設要玩的遊戲是抽大小,玩家一張、電腦一張比較大小,點數 A 最大,接著為 K Q J 10 9... 2;點數相同時比花色。這時用第一種轉換就方便很多!第一種對應等於是 (3>2>1>0) > (51>50>49>....>4),我們用一種「偷機」的方式!如果判斷出那張牌(0~51) 的點數小於 4 時( 一定是 A),就將那張牌的點數 +52 ,到時比較時將會變成 (55>54>53>52) > (51>50>...>4),這樣可以省一些 if-else 之判斷。副函式參考如下

// ====================================
// 比較單張大小, a>b 傳回 1, a<b 傳回 0
int compare_single(int a, int b)
{
    a+= (a<4)*N,b+= (b<4)*N;
    return a>b;
}

※  約瑟夫問題

這些遊戲最大可討論的地方在於:(1) 派牌時,玩家/電腦 是否可指定要第幾張牌 (2) 一局結束後,該撲克牌若還沒用玩就繼續用。基本上,上面這二個問題就是約瑟夫問題(Josephus Problem,有 n 個人圍成一個圈,每數 k 個就殺掉被數到的那人;再繼續從下一個人開始數 k 個,再殺掉被數到的人;推斷最後站在哪個位置會生存下來)之變型。

於是,這裡簡單說明一下約瑟夫問題怎麼解,有興趣請自行  coding

故事背景:

羅馬人佔領喬塔帕特後,39 個猶太人與歷史學家Josephus 及朋友躲到一個洞中,39 個猶太人決定寧願死也不要被敵人抓到,於是決定了一個自殺方式,41 (n) 個人排成一個圓圈,由1、2、3 連續報數,每逢報第3 (m)人就必須自殺,直到所有人都自殺身亡為止。然而Josephus 和他的朋友並不想遵從,將朋友與自己安排在第16 個與第31 個位置,逃過了這場死亡遊戲。

(1) 用 circle link 解

直接先建立 n 個資料 (內容假定為 1~n) 之 circle link,從頭開始數,每數 m 個之後就將該 link release 掉,再繼續數 m 個;直到剩下的 link 只為一個。

(2) 用 array 解

直接設定大小為 n 的 array,內容為 1~n;從 index 0 開始數,每數 m 個就將該值設成 -1。於是要設一個 counter,再依序一直 polling  array 之內容,如果遇到 array 為 -1 ,counter 不增加;反之才增加 counter。這在解法上會比 circle link 慢很多,實做大致如下,跑得很慢 (只是 demo),可以有更多優化。 

#include <stdio.h>
#define M 3 
#define N 13

int main()
{
    int i,array[N];
    int pos=0; // 目前數到之位置
    int alive=N; // 存活人數
    int counter=0; // 計數器
    for(i=0; i!=N; ++i) array[i]=i+1;
    while(alive!=1){ // 只留一人
       // 人還活著, 繼續計數
       if(array[pos]!=-1) ++counter; 
       // 數到 M 
       if(counter==M) {
          printf("%d", array[pos]); // 印出原本編號
          array[pos]=-1; // 該員死亡
          --alive; // ��活人數少 1
          counter=0; // 將 counter 設 0
       }
       // 數完一輪又回到 0 
       (++pos==N)?pos=0:NULL;
    }
    // 查最後生還者
    for(i=0; i!=N && array[i]==-1; ++i);
    printf("\nalive pos:%d\n", array[i]);
    return 0;
}

 

用 array 另一種解法是
(2.1) 先產生一大小為 N 之陣列,初值全設 0 ;counter 初值設1
(2.2) 每數 M 個 (不包含非 0 的元素,那些已經自殺了),就填入計數器 counter,並把counter+1。
 
優缺留予讀者分析。

(3) 其它解法

這問題有變化題,目前最佳的解法「應」為 DP 式解法,不於此討論內,有興趣請再額外閱讀研究。

(4) 其它擴展問題

(4.1) 從第一個開始數,每數 M 個殺 K 個人,求最後留下來的人。
(4.2) 酋長問題:此 N 人裡面有一人為酋長,每數 M 個殺 K 個人,殺到酋長遊戲結束(也就是酋長要最後存活之意 )。

抽大小遊戲程式碼

說明完約瑟夫問題,也給了最簡單的解決方案 (程式碼沒拿到 acm 測過,估應會 TLE),接著可以正式開始玩簡單的抽牌遊戲。

遊戲說明:
(1) 遊戲初始有 52 張牌。
(2) 每輪玩家指定從剩下牌堆裡抽一張出來;電腦也隨機從剩下牌堆裡抽一張出來,比較大小。
(3) 一輪比完後,2張牌即棄牌,玩完52張牌後檢視玩家贏得場數。

 程式碼大致如下,「完完全全沒有優化」,可看到不少硬爆的痕跡

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define BUF_SIZE 5
#define USED -1 // 使用過之牌設成 -1
#define N 52
#define SWAP(a, b){int t; t=a; a=b; b=t;}
#define RANDOM(low, up)(int)(((up)-(low))*(double)(rand())/RAND_MAX +(low))
#define DRAW_LINE() puts("-------------------------")

const char flower[4] = {'\5','\4','\3','\6'}; // 4個花色
const char number[13][BUF_SIZE] = {
    " A", " 2", " 3", " 4", " 5", " 6",
    " 7", " 8", " 9", "10", " J", " Q", " K"};

// ====================================
// shuttle
void shuttle(int *array, int Size)
{
    int i, pos;
    srand((unsigned)time(NULL));
    rand(); // 先抽掉一個亂數

    for(i=0; i!=Size; ++i){
       // 取出第 pos 張牌
       // pos = rand()%52; // worst
       pos = RANDOM(0, N-1); // better
       // 將第 i 張牌與第 pos 張牌交換
       SWAP(array[i], array[pos]); 
    }
}

// ====================================
// display_card
void display_card(int card)
{
   putchar(flower[ card % 4 ]); 
   printf("%s", number[ card >> 2 ]); // faster
}

void display(int* array, int Size)
{
    int i, counter=0;
    for(i=0; i!=Size; ++i) {
       if(array[i]!=USED) display_card(array[i]), ++counter;
       if(counter==13) counter=0, putchar('\n');       
    }
    
}

// ====================================
// 比較單張大小, a>b 傳回 1, a<b 傳回 0
int compare_single(int a, int b)
{
    a+= (a<4)*N,b+= (b<4)*N;
    return a>b;
}

// ====================================
// 計算現有牌數之第 n 張牌之數值
int cal_n_pos(int *array, int Size, int n)
{
    int i=0,counter=0; 
    int number=0; // 點數
    // 找出第零張沒使用過的牌
    while(array[i]==USED) ++i;

    // 取得第 n 張沒使用過的牌
    for(; i!=Size && counter!=n; ++i){
       if(array[i]!=USED) ++counter;
       if(counter==n) break;
    }
    number = array[i];
    array[i]=USED;
    return number;
}

// ====================================
// 主函式
int main()
{    
    int i, poker[N];
    int card_cnt=N; // 剩下牌數
    int draw_pos=0; // 欲抽第幾張牌
    int draw_number=0; // 抽出之點數
    int win=0,lose=0; // 戰積
    int pc_pos, pc_number;
    for(i=0; i!=N; ++i) poker[i] = i;
    shuttle(poker, N);    
    
    while(card_cnt!=0){
       DRAW_LINE();
       // display(poker, N);
       printf("\n[the numbers of card: %2d]\n", card_cnt); // 顯示訊息
       
       // 提示欲抽哪張牌
       do{          
          printf("please input nth card to draw(1~%2d): ", card_cnt);
          scanf("%d", &draw_pos);
          if(draw_pos>card_cnt || draw_pos<=0) puts("input error!! input again");
       }while(draw_pos>card_cnt || draw_pos<=0);
       --draw_pos;       

       // 玩家抽出之點數
       draw_number = cal_n_pos(poker, N, draw_pos);
       printf("You draw:"), display_card(draw_number);
       --card_cnt;

       // 電腦抽出之點數
       pc_pos = RANDOM(0, card_cnt-1);      
       pc_number = cal_n_pos(poker, N, pc_pos);
       printf("\nPC draw:"), display_card(pc_number);
       --card_cnt, putchar('\n');
       if(compare_single(draw_number, pc_number)) {
          ++win;
          puts("you win!!");
       }
       else {
          ++lose;
          puts("pc wins!!");
       }
    }
    DRAW_LINE();
    printf("you win %d times!!\n", win);
    printf("you lose %d times!!\n", lose);
    printf("thank you for playing..");
    return 0;
}

 

撲克牌程式補充說明

(1) 上述的「使用者決定抽牌」,在紙牌遊戲並不常用,但該延伸之問題 (約瑟夫問題) 仍於其它地方常見。
(2) 上述之程式碼,可繼續進行延伸,如:切牌動作、依序派予四位玩家手牌等
(3) 可考慮加二張鬼牌進去,增加遊戲之種類與趣味 ( ASCII '\1', '\2')
(4) 在做 draw_card 時,可再加入繪牌之函式 (所以可能還要再畫牌的背面),這部份於此不贅述。
(5) 其它撲克類遊戲,可再考慮帳號登入、手上籌碼等,甚至可以做紀錄檔 ( 但建議要有加密,還要想辦法鎖單機 ),由於加密部份吾人亦為新手,只會使用「自己想」的簡單加密,於此便不再介紹。

其它紙牌遊戲

據吾人所知撲克遊戲大概有以下種類

(1)  牌組類:如大老二、十三支、ShowHand、德州撲克,這類型遊戲要為每份牌組寫要判斷函式,從大到小依序判別。
(2)  點數類:有名的像 十點半、Black Jack、橋牌類 (雙人~4人橋牌、拿破崙橋牌)等,這類型撲克遊戲較為簡單,新手可先從這裡下手。
(3)  其它類:水果盤、心臟病 是真人在玩速度,不是非常適合用電腦設計;吹牛 較麻煩是 AI 之設計。

另外,現今也有許多「桌遊」型遊戲,比較簡單的是地圖制(但麻煩就是在地圖的繪制),如大富翁、矮人礦坑;比較麻煩的是回合、屬性制,像三國殺、遊戲王 (不知道有沒有這種紙牌遊戲)。若上述這些遊戲 (地圖制 + 回合制) 都會寫的話,早期的遊戲開發架構大致也知道該怎麼,剩下的便是顯示 (GUI) 部份,這部份也是關鍵的部份,因它也是影響遊戲賣不賣的一個重要關鍵。

介紹至此,若真對遊戲設計有興趣,建議還是去找介紹遊戲設計的書好好一字一字慢慢 K ,這裡介紹的,只是最基楚、沒技巧的方式。

edisonx 發表在 痞客邦 PIXNET 留言(5) 人氣()


留言列表 (5)

發表留言
  • sayya
  • 筆者你好,看了你寫得東西非常感興趣,有些問題想請教您:
    // pos = rand()%52; // worst
    pos = (int) (N*(double)rand()/RAND_MAX); // better
    我不太懂為什麼你這段要用下面的code,不用上面的。其中的原理是什麼呢
  • 這屬一般亂數問題。問題簡化一下,假設 RAND_MAX = 7, 要進行
    rst = rand() % 5,會有什麼現象。
    rand()=0, 5 : rst=0
    rand()=1, 6 : rst=1
    rand()=2, 7 : rst=2
    rand()=3 : rst=3
    rand()=4 : rst=4

    結果後面的兩個結果會比前面的三個結果機率來得低,
    用第二種方法實質上不能完全避免這種情況,但可以將這種不均勻的狀況,
    打散到各結果去,可推一下用第二種寫法的話,上面不均勻的狀況會變哪幾個數的機率會較低。

    edisonx 於 2012/07/13 03:30 回覆

  • sayya
  • 您好,感謝你的回答,// pos = rand()%52; 不使用這個方式的原理我已經明白了,但是我還是看不懂pos = (int) (N*(double)rand()/RAND_MAX); 這個方式,怎麼將這種不均勻的狀況,打散到各結果去? 另外rand(); // 先抽掉一個亂數 =>這個目的是什麼@@,因為第一次看到亂數可以這樣用,問題可能有點多@@
  • 我仔細推一次後發現,那段碼有個地方寫錯了<已修正>
    應該是這樣才對

    double rndf = rand() / (RAND_MAX+1.0); //[0,1) 亂數
    int pos = (int)rndf() * N ; // [0, N-1] 整數亂數
    所以要合在一起寫的話就變..
    int pos = (int)(rand() / (RAND_MAX+1.0) * N);

    一些相關的議題可參考這篇。
    http://edisonx.pixnet.net/blog/post/72607067

    續上一個假設,RAND_MAX = 7, N = 5 (就是 %5)
    int rst = (int)(rand() / (RAND_MAX+1.0) * N);
    rst = (int)( rand() / 8.0 * 5 )

    rand() = 0, 1 , rst = 0
    rand() = 2, 3 , rst = 1
    rand() = 4, rst = 2
    rand() = 5, 6 rst = 3
    rand() = 7, rst = 4

    不均勻的情況一樣有兩種,rst=2, rst=4,
    但這種情況被「均勻打散」到 rand() = 4 , 7 ,
    不再集中於「某一個特別區段」的 rand() = 3, 4,
    為何強調至少要「均勻打散」?
    因為我們用的亂數產生器是希望至少能達到「機率隨機,且均勻」的目的。

    至於其他理由,可能與一些數論有關了,不再贅述。

    rand() 先抽掉一個原因有點難解釋,或說是我解釋不清楚,
    現在我也不會先做「抽掉」的動作就是 (原因是我改用其他亂數產生器),
    其中一項原因是,若你程式執行頻繁時,不先抽到一個,
    得到的亂數序列可能相仿。

    上面這些碼,我有空時再重整一下,順便再看一下有沒有其他錯誤的地方,像洗牌方式已經有比較好的洗牌法了。

    edisonx 於 2012/07/14 02:42 回覆

  • 悄悄話
  • 悄悄話
  • 悄悄話

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼