用游戲串起程序員的基本功之四

2019-11-17 05:06:33

字體：大中小

來源：轉載

供稿：網友

　　對于麻將牌的玩法來說,重要的就是要有吃、碰、杠、胡等四種功能.那么在游戲中怎樣編碼實現呢?

　　吃牌,就是比較對方打出的牌,和自家的牌是否可以連成一串.而碰牌就是比較對方打出的牌和自家的牌是否有2張相同的.假如有三張牌和對方打出的牌相同,就可以杠.胡牌則是至少要有一對相同的牌,除此之外,也可以有三張三張的相同的牌或連成串的牌.

　　所以對于吃、碰、杠、胡，我們可以分解為，查找兩張連續的牌，查找兩張相同的牌，查找三張相同的牌，對于胡牌，還要確定有且只能有一對相同的牌，其他的可以是三種相同的牌，或三張連續的牌。可見在此查找是算法的要害。

　　我們先來看一下有關查找的知識。

　　第一種查找的方法叫“線性查找法”，是從數據中的第一個數值開始查找比較，假如找到就返回該值或該值所在的位置。

　　示例如下：

　　13 25 16 23 57 66 為一個整型數組。

　　假如要在這樣一個數組中找到57，

　　步驟1：得到第一個數13，不相等，取得下一個數

　　步驟2：得到第二個數25，不相等，取得下一個數

　　步驟3：得到第三個數16，不相等，取得下一個數

　　步驟4：得到第三個數23，不相等，取得下一個數

　　步驟5：得到第三個數57，相等，返回所在位置5

　　代碼如下：

int chazhao(int key)//用線性查找法 ,key表示要查找的數值

{

int i=0; //指示在數組中的位置

while(i<14) // 直到結尾

{

if (key==apai[i]) //假如找到，

return i; //返回所在位置

i++; //沒找到，繼續向后搜索

}

return -1; //沒找，返回失敗

}
　　可以看到這種方法，不管數據是否有順序，也不管數據的多少，都是按順序挨個的搜索，直到找到或搜索完成，當數據很多時,尤其是要查找的數據排的比較靠后,就會很費時間。所以，對于已經排好順序的數據，假如還用線性查找法來查找的話，一定是很浪費時間的。有什么好的方法呢？

　　大家一定都查過英語詞典吧，當你要查一個以S開頭的單詞時，誰都不會從頭一頁一頁的向后翻,而是跳躍式的向后翻,假如我們先翻到了P開頭的一頁，我們一定會繼續向后翻，而不必再查前面的頁碼。再翻一次,到達T開頭的一頁,我們就會又先前翻,找P和T之間的頁.我們可以把這種查找的方法叫“折半查找法”。

　　它的原理是：先用欲查找的數值和該組數據的中間位置上的數值比較，當小于中間值時，再向前查詢，大于中間值時向后查詢，繼續取前面（或后面）一半數據的中間值進行比較，假如小于再向前查詢，大于就向后查詢，一直到找到或查詢完畢為止。

　　示例如下：

5 7 12 25 34 37 43 46 58 //是要查找的數據段，其中要查找46，

　　步驟一：中間值34<46,向后查找

　　步驟二：得到后半部分的中間值43<46,再向后查找

　　步驟三: 得到剩余部分的中間值46,返回

　　可見,這種方法明顯的減少了比較的次數.

　　下面是源代碼:

void chaxun(int key)//用折半查詢法,key表示要查詢的數值

{

int left=o; //待查詢數據段的左邊界

int right=12; //待查詢數據段的右邊界

int mid; //待查詢數據段的中間值

while(left<=right) //只要沒查詢完

{

mid=(right+left)/2; //取得待查詢數據段的中間值

if(key<apai[mid]) //中間值大于待查詢的數值

right=mid-1; //再查找前半段

else if (key>apai[mid]) //中間值小于待查詢的數值

left=mid+1; //再查找后半段

else if(key= = apai[mid]) //中間值等于待查詢的數值

return mid; //返回位置

}//end while

return –1;

}//end

　　查詢數據是數據結構中的又一重要知識,在實際應用中也很重要,假如有愛好可再深入的研究.我們只能到此為止.

　　回過頭來,我們再來看一看,這樣判定吃,碰,杠,胡.在此我們只以萬牌為例.

　　下面是數和牌對應關系:

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

一二三四五六七八九（萬）東

　　很明顯同一張牌是在小于40的數據段中,并且個位相同的數.并且它還對應著牌上的數.

　　所以判定是否為同一張牌的方法,我們可以這樣寫:

tempa=apai[i]%10;
tempb=apai[i+1]%10;
if(tempa==tempb)
　shi tong yi zhang pai
(注重這種牌和數得對應關系,在排序時,一定要以個位為準,而不是以實際的數值大小)
　　判定是否可碰,則可以這樣:

tempa=apai[i]%10;
tempb=apai[i+1]%10;
tempc=apai[i+2]%10;
if(tempa==tempb && tempb==tempc)

　　判定是否可杠,可以這樣:

tempa=apai[i]%10;
tempb=apai[i+1]%10;
tempc=apai[i+2]%10;
tempd=apai[i+3]%10;
if(tempa==tempb && tempb==tempc && tempc==tempd)
　　是否為順,則可以這樣判定:

tempa=apai[i]%10;
tempb=apai[i+1]%10;
tempc=apai[i+2]%10;
if(tempa==tempb+1 && tempb==tempc+1)
　　很簡單吧,相信你應該也會判定對方出的牌,自己是否可以碰,杠,吃了吧.在此我們就不多羅嗦了.

　　胡牌稍麻煩些,要判定各種副牌的方式,這里我們一起看看一條龍的胡法.

　　下面是源程序:

void yitiaolong ()
{ int wan,bing,tiao;//wan,bing,tiao 分別代表三種牌
　int temp;
　for(int I=0;I<13;I++)
　{
　　temp=apai[I];
　　if(0<temp<40)
　　　wan++;
　　if(40<temp<80)
　　　bing++;
　　if(80<temp<120)
　　　tiao++;
　　if(wan=8)//萬牌一條龍
　　for(int I=1;I<9;I++) //比較這8張牌
　　　 if(apai[I]%10=api[I+1]%10)
　　　　 //是否後一張等于前一張,相等,說明已經有將牌了
　　　　for(int a=1;a<40;a++)
　　　　　if (chaxun(a)!==-1) //找到所缺的牌
　　　　　　if (I=duifangchupai)比較是否和對家大的牌相等
　　　　　　　 ……..//胡了
　　　　　　 else
　　　　　　　//表示8張牌沒有相同的,也就是又8個串
　　　　　　　//查找所缺的牌,
　　　　　　　//與對方出的牌比較,
　　　　　　　//相等胡牌
　　　　　　　 ……….
　　　　　　 if(wan=9)
　　　　　　　　……….
　}
　if(bing>=8)
　　…..//餅牌一條龍
　if(tiao>=8)
　　…… //條牌的一條龍
　}
}
　　由于篇幅所限而且文章的重點不在于此,這僅給出一個框架,聰明的讀者,可以發揮自己的才智,將他補充完整.

　　下面我們簡單談一下人工智能,究竟我們在游戲中還需要一個對手.

　　作為程序員,我們不可能做出一個具有高超聰明的對手,而且我們也不可能將游戲中種種可能的打牌方法都寫入程序.那么就需要一種可操作的方法,使你的對手不至于太傻.

　　對于給策略性的游戲添加人工智能主要有這么幾步:

　　(1) 要找出所有獲勝的可能性

　　(2) 建立獲勝表,

　　(3) 每一步的玩法給出一個恰當的評價分值,其中包括給對手制造的麻煩所得的分,和給自己帶來的獲勝機會所帶來的分

　　(4) 根據所給的分值,確定其中所有可能的玩法中,分值最高的一種玩法,也就是最好的一步走法.

　　具體到麻將游戲下面是具體的分析:

　　假設a1,a2,... an 是手上當前牌序列,其中包括吃碰杠后的牌,

　　步驟1: 計算玩家離胡牌還有幾步. 假如玩家已經聽牌, 它離胡牌的步數是 1, 假如是一上一聽, 步數是 2, 以此類推;

　　步驟2: 假如步數是 m , 計算所有能使玩家到達胡牌的序列也就是所有胡牌的可能玩法 {b11,b12,....b1m}, {b21,b22,...b2m}, ....,{BT1,bt2,....,btm}

　　步驟3: 對于每個一個 {bt1,bt2,...,btm}, 計算胡牌的點數, 以及到達胡牌時要打出去的牌: {ci1,ci2,....,cim}

　　步驟4: 對于每一個 {bt1,bt2,...,btm} 計算胡牌的點數;

　　步驟5: 選取收益最大的方案 {bji,bj2,....bjm}

　　步驟6: 從{cj1,cj2,....cjm} 中按照跟熟原則打一張

　　動動腦筋相信你會做出更智能化的得對手。