colaghost

前言

当初做这个东东只是想参加学校的科研立项，最初的设想是供儿童随意在画板上涂鸦，然后让儿童涂鸦的图案动起来，就例如说画一个球就会滚动，画一辆飞机就会飞起来。

前期

当初的设想很美好很强大，但真正构思时却发现这远远超出了我们的水平，光是基本图形，如直线，多边形，圆等的识别就已经让我们纠结了好久。

但既然选择了，无论做成什么样，还是要继续下去的。我们团队几个人开始研究关于基本图形的识别，记得大概好像耗费了一个月的时间吧。当时首先解决的是关于直线的识别，其实说起来也很简单，就是计算首末两点的距离，和整条直线点与点之间距离的和，前者除以后者，当结果大于某一个常数时就认为是直线。经过测试也认为这是可行的，识别率在经过不断调整那个常数后可以达到很高了，差不多90%以上了。

后来圆、多边形以及波浪线跟弧线的识别也都一一被攻破，当时还用MFC做了一个很简陋的画板来测试这些方法，可惜那个画板好像后来删掉了。

但光识别基本图形还不够，毕竟不可能只画这几样东西。我们做了一个设想，就是认定所有的图形，无论多复杂，都是由这些基本图形构成，只要我们能够统计出一幅图案由多少种基本图形构成，以及各种基本形的个数和它们的相对位置，即可以认定为它是或接近于哪幅图案。当然图案都由我们收集好，目前我们做不到说儿童想要画什么就出现什么样的动画，只能通过播放接近的flash来实现这个目的。图案也就是flash，我们收集了几百种flash，并统计他们的特征，也就是上面说的那几个值，并以特定的方式编写好一个配置脚本，识别时就是根据这个配置脚本来判定的（基本图形除外）。

正式版本

这个版本的界面就是上图，很简单，只有几个按钮，如清除画面，识别画图，截图和退出等。因为这是面向儿童的，觉得不应该有太多操作，应该尽可能简单，涂鸦时也不可选定画线大小和颜色等，这不是普通的画板！

下面两张图片是一个简单的示例：

涂鸦

识别后

其实这里有一个问题，就是基本图形只能一笔画完，不然就会被认定为其它基本元素。组合识别有时候也不是尽善人意，会出来一些令你摸不着头脑的动画。

最后

这里做得比较成功的还是关于基本图形的识别吧，至少可以保证很高的识别率，大都在90%以上。组合识别却有待改进，或者我们应该改变整个识别的思路，但至于怎么做，我们现在却都没有时间去考虑了，接下去都是要工作了，也许将来有时间和有能力来改善这个版本，我相信会是一个很好的东东。至少，它让你的构思动起来了，这不是很好玩吗？

这些天的一些开发涉及到mediastreamer等几个开源包，之前一直是用跑在虚拟机上的redhat。无奈问题多多，测试程序音质很差，两台机之间的音频通信更是无法忍耐，延时很严重，还老是有杂音，一说快就完全听不清楚了。心想可能是系统跑在虚拟机上的关系吧，记得程序总会爆出警告。加上也想换到ubuntu10.04过下瘾，就直接安装上了。

满怀期待地换上了，把几个包都编译好。试了下用ring_start来播放*.wav文件，倒也没有延时了。再试下开源包自带的echo这个例子，无奈问题来了，貌似采集不到声卡的数据，没有音频输出。看了一下程序的输出报告，只有OSS，却没有ALSA。怪了啊，UBUNTU默认应该只有ALSA的啊，怎么会只有OSS的呢？

不管那么多了，升级下声卡驱动吧，看看问题能不能解决！折腾了半天把驱动更新完，并用gnome-alsamixer做了一些改动，好，以失败告终，除了杂音大点外无任何副作用！

最后跑到群上问，有一大牛才相告程序找到的oss是pulse-oss-plugin，而且所有音频输出由pulseaudio接管，但底层还是基于alsa的。以为是mediastreamer2这个开源包不支持pulseaudio，可是搜了下人家明明白白写着是支持的。阅读了一下关于这点的源代码，也确实有提供了pulseaudio的支持。既然这样的话应该还有pulseaudio的才对啊，怎么会只有OSS呢？再次试着configure整个开源包，突然看到了一句，“checking for LIBPULSE… no”！一切问题出来了，少了个pulse的静态开发库。上新立德搜了个，安装后，运行echo时手动指定声卡为pulseaudio。出声了，折腾了一天的问题竟然就出在这个小点上。可能是mediastreamer2依赖于这个库的一些调用，当缺少这个库时，开发包预编译时就会认定没有pulseaudio而直接把相关源码略过。

人机对战版：某一方一次性消去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!

考完试后就总是会不自觉得登上学校的选课系统去查询成绩，可是老是要打开浏览器去登陆系统也是比较麻烦的事，就思索着自己写一个脚本来查询成绩。刚好这些天在看python，用它来实现这方面的应用还是比较简单的。

其实总的说来就是要获取到查看成绩的那个页面，然后再分析得到里面的相关数据并显示出来。

抓取页面涉及到登陆跟cookie的问题，这里用的是urllib2和cookie这两个模块。

由于要保存登陆后的cookie，所以需要先提取出来。

1
2
3

cookie = cookielib.CookieJar()
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cookie))
urllib2.install_opener(opener)

这样通过urllib2来模仿登陆后就能获得相应的cookie了，这时才能接着下一步去获取对应的成绩页面。

因为我们需要登陆后才能获得相应的页面。这时候就用到urllib2模块了，用它可以实现向url发送一些数据，其实在网站上登陆也就是把相应的数据发送到服务器上，然后通过验证后再获得对应的cookie，这样下次发出请求时服务器就能通过cookie识别出用户并做出应答。

1
2
3
4
5
6
7
8
9

url = 'http://www.someserver.com/cgi-bin/register.cgi'
values = {'name' : 'Michael Foord',
'location' : 'Northampton',
'language' : 'Python' }
 
data = urllib.urlencode(values)
req = urllib2.Request(url, data)
response = urllib2.urlopen(req)
the_page = response.read()

上面代码就是向服务器发送数据的代码。values这个字典变量保存了我们所填取的数据，如你所知都是一些键值对，键值就是所填的表单的名字，然后发送时要经过标准方式编码，这是由urllib.urlencode()完成的。

接下去用urllib2获取相关页面时就会自动替换头部中cookie的值，这样就能够得到应答了。

获取到成绩页面后，其实得到的也就是一个HTML文档，这时候还得通过分析来提取出我们相要的那些数据。

为了从HTML文档中提取数据，要将SGMLParser类进行子类化，然后对想要捕捉的标记或实体定义方法。

1
2
3
4
5
6
7
8
9
10
11
12

class URLLister1(SGMLParser):
     def reset(self):
         SGMLParser.reset(self)
         self.result = []
         self.open = False
     def start_tr(self, attrs):
         id = [v for k, v in attrs if k=='class']
         if 'alt' in id:
             self.open = True
     def handle_data(self, text):
         if self.open:
             self.result.append(text)

经过分析提取后，最后得到的才是我们想要的那些成绩的数据。

这是查询成绩的显示，没有经过格式化，懒得去搞了，能看就行了。

其实整个过程并不顺利，因为在抓取页面时一些网站会分析协议包的头部，要是Referer的值不是指向它的网站的URL时，就不会做出应答。我们学校的网站就是这样，就因为这个小小的问题不断地在试，有好几次还因为忘了替换User-Agent的值，被学校的服务器误以为是在对它做IPC$攻击，还把我的IP给封掉了(=_=!幸好过些时间就解封了）。