俄罗斯方块

人机对战版:某一方一次性消去N(N>=3)行以上时,另一方会增加N-1行。

这里放出下载地址:teris ai

前言

对于80后的人来说,大概都会玩过的游戏就是俄罗斯方块了,虽说现在可能很少会去玩这个了,但是经典永远都是经典。以前都是玩别人的,很早就想自己做一个,但由于某些原因一直搁着,上学期刚好看《编程之美》时又看到这个东东了,才开始动手。

前期

前期的工作只要考虑的是保存积木块的数据结构跟积木块移动、旋转跟消行之类的算法。

积木块是用二维数据来表示的,由于各种积木块的尺寸都不相同,而且旋转后的尺寸也可能发生变化,如果为不同的积木块设计不同尺寸的数组,则可能造成程序管理的混乱。因此就用统一尺寸的数组来容纳所有可能的积木块,4*4的数组就可以满足要求了。但相对来说会浪费一些空间,因为总共有7种积木,每种积木又有4种变形(有些可能只有一种或两种,这里是为了不在程序里加太多判断条件)。

至于积木块的碰撞检测,有一个最简单的算法,就是每下落一行,就判断积木块数组是否跟所在游戏区域有重合(有方块的值设为1,当两者相加为2即为重叠)。但这样效率比较低。因为每下落一行,很多区域都需要重复判断。

这里我采用的是《编程之美》里面提供的方法,对于每一个积木块,都会记录相应的初始数值,如下:

即计算每一个积木块所占区域的最小列minCol和最大列maxCol,以及最小行minRow和最大行maxRow。还有一个数组是用来保存游戏区域每一列最高高度的那一个方块(积木块是由数个方块组成)的位置。我们发现,可以下落到的最低高度取决于最先接触到已有方块那一列。由此,可以计算积木块每一列触底高度的最小值,这样根据这些最小值跟先前的数组即可进行碰撞检测(只需要判断积木块有方块的那列的触底高度是否大于或等于所在列最高高度的那一个方块的位置即可)。由于每次最多只需要进行四次加运算,故效率比较高。但空间开销比第一种方法大,而且每次积木块触底后需要更新保存游戏区域每列最高高度的那个方块位置的数组。

《编程之美》里的算法并不支持在下落过程中通过水平移动来“钻洞”,这里我做出的改进是:假设要进行左移,就把积木块在游戏区域里的位置的x值减1,然后判断积木块的每一列(只需判断(minCol, maxCol)这个区域的列即可)的触底高度是否比其所在游戏区域的那一列的最高高度的方块的位置值小,如果是的话则再根据每一种碰撞算法检测是否发生方块重合。

至于消行,我是先把消的行的位置记录在一个容器里,然后从最低的行开始移动,即假设要消的行为第三行跟第五行,即先把第五行以上的第三行以下的往下移动一行,再把第三行以上的往下移动两行,要消多行的话就以此循环下去,直至所有的要消的行都处理好,这样每一行只会被移动一次。

单人版

这个版本的跟其它的俄罗斯方块并无多大区别,鉴于前期工作做得比较彻底,故编码阶段也并无遇到多少问题。界面是用Win32 SDK编程来实现的,我不会MFC,故只能自己处理所有的消息,异常麻烦,导致界面代码也写了不少,唯一一个好处就是异常自由,封装好的东西总会多多少少让你觉得不爽。

人机对战版

其实初做这个游戏的AI时并不指望能达到多牛逼的地步,只是想试着玩一下而已。

做为一个人来说,我想大家都能明白玩俄罗斯方块时要一次性多消行,尽量不要摆太高,不要出现“洞”什么的。但计算机太弱智了,它没办法理解这些,故只能采用“计分制”,具体来讲就是如果积木的某种摆放达到了某要求就增加一定的分数,反之就扣除。

最开始的计分完全是自己弄着玩,玩个几千分就死掉了。后来在Pierre Dellacherie算法的基础上加上了自己的一些试验结果,看着它跑了两个多小时都没死掉,当时正值凌晨,就想着挂着它让它跑一晚上好了。没想到第二天起来还没死掉,呵呵!

其实这个AI版本让机器自己玩肯定所向无敌,当由于人机对战的话会把某一方消的行增加到另一方,而且实际上人在玩时往往会等待一次性消去3行、4行的机会。但这个AI算法注重的是不死,这时就需要做出改进了,也就是再根据下一个掉落的积木块来选出实际上最好的局势。其实具体实现也不难,不过就是剪枝,在根据当前下落积木块算出的最排前的N个局面,再根据它们和下一个掉落的积木块分别计算最好的N个局面,再从这N个局面中通过比较挑出最好的那一个。但问题就是N的选定,这又得通过一系列的试验。由于种种原因,一直没有进行这样的改进,可能是懒吧,也就一直放着了。

最后

其实这个东西还是做来自己玩的吧,没有多少实用性。毕竟界面比我做的炫、AI比我智能的网上一搜一大堆,但算是练练手吧,呵呵,just for fun!

标签: ,
文章分类 C/C++, Programming
2 comments on “俄罗斯方块
  1. 广林说道:

    你好我想知道Pierre Dellacherie算法的相关资料,能给我一份吗?

    [回复]

    colaghost 回复:

    呵呵,具体的资料我也没有,我当时参考的是这篇博文的,你可以参考下http://kb.cnblogs.com/a/1420682/

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*