colaghost

前言

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

前期

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

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

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

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

正式版本

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

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

涂鸦

识别后

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

最后

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

何为placement new呢？placement new 是重载operator new的一个标准、全局的版本，它不能被自定义的版本代替（不像普通的operator new和operator delete能够被替换成用户自定义的版本）。

首先我们区分下几个容易混淆的关键词：new operator、operator new、placement new 。

对于new operator，其实它是语言内建的，我们是没有办法改变它的。当我们创建了一个new表达式时，会发生两件事。首先，使用operator new()分配内存，然后调用构造函数。现在明白了吧，new operator会去调用operator new()跟创建对象的构造函数，我们能控制的，只有内存的分配函数operator new()(对于operator delete()也是一样)。所谓控制，其实就是重载这个函数，编译器将用重载的operator new代替默认的版本去分配内存。

接下来就是要说的placement new了。其实它也是operator new重载的一个版本，只是很少人用到它。它有一个特点，就是允许你在已经分配好的内存上创建一个对象，也就是说，可以通过某种手段在指定的内存创建对象。

好了，说到这里，我们就可以利用它来做一些高效率的事情了。

当我们用new分配对象数组空间时，会自动调用对象的默认构造函数。可是如果数组只有一部分元素会被使用，或者元素立即被赋值，那刚刚自动调用对象的默认构造函数不就等于白做了吗？这时候placement new就发挥作用了，因为它可以在分配好的缓冲区上创建对象。采用这种方式，缓冲区占用的存储区的分配，可以避免被默认的构造函数初始化：

const size_t n = sizeof(string) * 30;
string *sbuf = static_cast(::operator new(n));/*这时候是直接调用operator new函数来分配内存的，也就是说，只会分配空间，类似于malloc。*/

下面是一个在分配好的内存空间上创建对象的函数：

void append(string buf[], int &size, const string &val)
{new (&buf[size++]) string(val);}//palcement new

这样的话，我们就可以在需要的情况下使用pacement new通过复制构造函数来初始化数组里的元素，在一些情况下能够提高程序的效率。
但这样的话我们就得自己来负责清理工作了，凡事有利必有弊吧。

这里得通过显式调用string的析构函数，如：

buf[size].~string();

并用operator delete来释放存储区：

::operator delete(buf);

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