用游戏串起程序员的基本功之四

　2008-03-08 21:33:44　来源：WEB开发网　　　

核心提示：对于麻将牌的玩法来说,重要的就是要有吃、碰、杠、胡等四种功能.那么在游戏中怎样编码实现呢? 吃牌,就是比较对方打出的牌,和自家的牌是否可以

　　对于麻将牌的玩法来说,重要的就是要有吃、碰、杠、胡等四种功能.那么在游戏中怎样编码实现呢?

　　吃牌,就是比较对方打出的牌,和自家的牌是否可以连成一串.而碰牌就是比较对方打出的牌和自家的牌是否有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} 中按照跟熟原则打一张

　　动动脑筋相信你会做出更智能化的得对手。