【摘要】“连连看”是一款比较流行的小游戏,无论是网络版还是单机版,都具有容易上手、娱乐性强的特点,很受网民朋友们的欢迎。笔者在工作之余写了一个外挂程序仅用作娱乐测试,感觉对锻炼思维很有帮助,特写此篇文章,从分析入手,结合解决途径、部分编程细节给大家做一个介绍,但对边缘情况的特殊处理未作说明,仅供参考。
【关键字】外挂,图像识别,像素矩阵,位图,链表,图块
之所以写这篇文章,笔者的目的不是为了鼓励大家去开发各式各样的外挂程序,只是想把自己的思路作一个剖析,把解决问题的过程给大家做一个汇报,对于初涉编程的人员来讲,也可能会有一些启发作用,仅此而已。
首先必须说明的是什么是外挂程序,所谓外挂程序,是在主程序运行时的一种辅助工具,它截获主程序的消息,或者向主程序发送消息,亦或者操纵输入设备(如鼠标、键盘等)在系统或窗口作标空间模仿输入(如点击)动作,以达到人工操作的目的。本文介绍的便是最后一种方式。
编写这种程序,首先需要确定设计的目的、程序执行的方式等最基本的问题,并要逐步解决一系列的细节问题,如:图像的对比识别、执行速度的优化、执行过程监测、地图的现场制作、时间控制等等。下面介绍该程序的设计过程。
一、程序执行的目标及方式
设计之初,我把该程序要完成的任务归结为:模仿手工操作,点击相同的图块,通过系统计算和操作,达到快速“消块”的目的。
程序执行时,首先完成对全局形势的分析,并在以后的变化中随时修改内存中存储的数据结构,不断计算出可以相连的图块,并模拟鼠标的动作循环点击,直至最后“消”完。具体步骤如下:
1、确定目标程序的主窗口,以及第一个图块儿位置的相对坐标;
2、按照当前当前布局的地图初始化相应的数据结构,为程序准备数据;
3、使用图像识别技术,扫描全局相同的图块儿并进行分类;
4、在第3步的基础上,在每一类相同的图块儿中,寻找可以“消”的图块对;
5、把当前所有能“消”的图块对完全消除,并在“消”的过程中实时改变关键数据,为程序继续扫描作准备;
6、继续重复步骤4~5,直到最后结束。
二、程序设计过程
在这部分内容中,笔者将比较详细的介绍该程序设计的过程,以及一系列细节问题的解决思路。
(一)确定目标程序的主窗口,以及第一个图块儿位置的相对坐标
在以像素为单位的屏幕坐标系中,每一个窗口都有自己的相对坐标空间,这为外挂程序的实现提供了方便,那就是,只要我们找到了窗口在屏幕坐标系中的绝对位置,那么该窗口内任何一点就都可以通过屏幕的绝对坐标来定位了。
首先使用VisualC++的程序工具SPY查找程序主窗口的相关信息,这主要是为了在外挂程序中定位目标程序的主窗口,以便操纵输入。
使用SPY工具,可以取得当前可见窗口的任何信息,比如窗口标题、类、窗口大小、绝对坐标位置等等,这可以为外挂程序的编写提供重要的参数。对于新浪提供的网络版连连看游戏如图1所示,通过SPY工具,可以找出程序主窗口的窗口标题和大小以及坐标位置信息,如图2所示。
图1 新浪连连看游戏主界面
图2 SPY抓取窗口信息
在图2中,通过SPY工具抓取的窗口标题为“连连看Ver1.51 - [自由频道02]”。由此可见,主界面窗口的窗口标题与游戏用户进入的具体房间有关系,因此在程序中,定义一个专门的字符串对象m_strRoomName保存窗口标题信息。在编写外挂的代码时,可先取得游戏的主窗口句柄,并将之赋给一个全局变量m_pWnd。代码如下:
m_pWnd =CWnd::FindWindow(NULL,m_strRoomName);
在取得了主界面的窗口句柄后,下一步首先需要解决的便是首图快位置的确定,即需要找出最左上角图块[0,0]的相对坐标。可是现在仍然不知道每一个图块的像素大小,需要使用专用工具计算出每一个图块长和高的像素大小,在目前的情况下,没有合适的工具能直接取得所需的数据,笔者在这里把自己编写的工具作一个简单介绍,并将给出具体结果值。
在主界面内,任意选定一个坐标位置(x,y),并任意选定一个大小合适的像素方块用作图像识别,初步设定为20*20的像素矩阵,在窗口内循环比较,会找出一组四个相同的方框。如果找出大于四组数字,则需要把方框大小调大,如果找出小于四组数字,则需要把方框大小调小。前面给出的20*20的像素矩阵式经过测试比较合适的。
在选定像素矩阵大小后,运行程序,得到第一组四个坐标位置A(170,35)、B(170,195)、C(590,195)、D(646,115)。将上述四个位置的横纵座标分别按照从小到大的顺序排列,会发现它们的出现是有一定的规律性的。如图3所示。
图3 第一组相同图块的位置分布
根据实际情况,我们完全可以看出来这四个图快的相对位置,按照X座标的顺序它们的位置分别是:[1,0]、[1,4]、[15,4]、[17,2],如图3中所标记。计算得出它们的相对坐标(以像素为单位)分别为:(170,35)、(170,195)、(590,195)、(646,115)。为了更清楚的表示两组数据之间的关系,并从中找出规律,可以把这几组数据作一个简单的线性关系分析。因为所有图块的大小都是一样的,那么这四组数据必然具备下面的关系:
设图快的宽和高分别为w、h,A.x表示图块A的X轴坐标,单位均为像素;A[x]表示图块A在X轴上的的位置坐标。
B.x=A.x+(B[x]-A[x])*w
C.x=A.x+(C[x]-A[x])*w
D.x=A.x+(D[x]-A[x])*w
B.y=A.y+(B[y]-A[y])*h
C.y=A.y+(C[y]-A[y])*h
D.y=A.y+(D[y]-A[y])*h
从上面任何一组数据都可以计算出:w=28,h=40,单位为像素,即图块大小为28像素单位宽,40像素单位高。
得到了图块的大小,我们就可以把进行图像识别的像素矩阵设置为28*40,这样就可以得[0,0]图块在主界面内以像素为单位的起始坐标,经过计算可以得出图块[0,0]的起始坐标为(140,30)。
上面得到的这两个数据(图块大小、起始坐标)将是后续开发的关键数据。
(二)按照当前当前布局的地图初始化相应的数据结构,为程序准备数据
如果要使程序能够高效运行,那就必须设计高效合理的数据结构,这部分将着重介绍笔者设计的四个重要数据结构。
1、定义WORD类型数据按位表示地图。
因为新浪网提供的连连看游戏是按照既定地图进行变换的,图1所示为“蜈蚣”地图,其实每个“蜈蚣”的开局都是不一样的,但是它们的宏观布局却都是相同的,利用这个特点,就可以把部分地图进行初始化,为图像的进一步识别准备部分数据,以提高执行效率。如何构造保存地图的数据结构呢?我们首先对地图进行分析,找出地图的关键数据信息有哪些?
仍以图1为例,它的地图布局如图4所示。
图4 “蜈蚣”地图的布局
其实,游戏主界面最多可容纳的图块数为:11*19,我们使用19个WORD类型的数据来表示整个界面,每一列组成一个WORD,称为位图。在初始化时,根据实际情况在相应的位(bit)上置0或者置1(有真实图块的位置为1,空位置为0),这样就得到了19个表示地图图块分布的位图数据,以“蜈蚣”为例,19个位图数据初始化如下:
从左向右,用数组squarebitmap[0]~squarebitmap[18]表示
squarebitmap[0] = 0x0; squarebitmap[1] = 0x7ff;; squarebitmap[2] = 0x1fc;
squarebitmap[3] = 0x7ff; squarebitmap[4]= 0x1fc; squarebitmap[5] = 0x7ff;
squarebitmap[6] = 0x1fc;squarebitmap[7] = 0x7ff; squarebitmap[8] = 0x1fc;
squarebitmap[9] = 0x7ff;squarebitmap[10] = 0x1fc; squarebitmap[11] = 0x7ff;
squarebitmap[12] = 0x1fc;squarebitmap[13] = 0x7ff; squarebitmap[14] = 0x1fc;
squarebitmap[15] = 0x7ff;squarebitmap[16] = 0x1fc; squarebitmap[17] = 0x1fc;
squarebitmap[18] = 0x20;
这组数据不仅决定了游戏开始时的布局,随着图块的不断消失,相应位(bit)的值也会实时的从1变为0。所有的计算都是基于这个组位图进行的。
光有了地图的数据还远远不够,还需要记录每一个图块的信息,这里笔者采用了下面的方法进行。
2、定义数组squarend保存每一个图块的信息,因此该数组必然是一个二位数组。定义如下:
squarenode squarend[11][19];
结构体squarenode的定义为:
struct squarenode {
CPoint internaldot;//图块内点
short x;//该图块儿的x坐标值
short y;//该图块儿的y坐标值
short top;//该图块上方的空块数
short bottom; //该图块下方的空块数
short left; //该图块左方的空块数
short right; //该图块右方的空块数
BOOL bExist;//该图块是否已经消除的标志
int nodetype;//该图块的类型
struct squarenode * prev;//构成相同类型的图块链表
struct squarenode * next;// 构成相同类型的图块链表
};
3、定义数组squaretp保存界面内所有图块的类型,根据实际情况设定该数组的大小为105。这也是一个结构体,定义如下:
struct squaretype {
COLORREF c[20][20];//设定20*20的像素矩阵进行图像对比识别
int nodetype;//该种类型的序号
int totaltype;//识别出来的总的类型数
struct squarenode * firstnode;//该类型的第一个图块
};
4、定义数组squarecl保存当前可“消”的图块对,根据实际情况设定该数组的大小为105,初始值全为空(NULL)。这同样是一个结构体,定义如下:
struct squarecanlink {
struct squarenode *p;
struct squarenode *q;
};
上面定义的四个数组为程序的运行提供实时地图信息、图块信息、图块类型信息和可“消”图块对的信息。
(三)使用图像识别技术,扫描全局,找出相同的图块儿并进行分类
设置嵌套循环分别从X、Y方向扫描每一个图块,填充squarend数组。在填充该数组的时候,有四个元素需要特别注意,那就是top、bottom、left、right值。在计算一个图块周围的空块数时,需要借助当前地图的数据信息。下面以图1中[2,2]位置上的图块举例说明。
(1)读取squarebitmap[2] = 0x1fc,二进制表示为0000000111111100。
(2)[2,2]图块所表示的位置为
图5 图块[2,2]所代表的bit位置
从该位图可以看出,2-bit位置的前面有两个位置均为0,这表示该图快上方有两个空块,因此其top值为2。图块bottom值的计算方法与此类似,只是方向相反,不再赘述。
(3)遍历squarebitmap[0]~ squarebitmap[18],在所有位图的2-bit位上进行比较,找出相邻位置上的空块。如下图所示。
图6 所有位图2-bit位上的比较
从比较可以看出图块[2,2]的左右边均有图块存在,因此其left、right值均为0。相反,从图中,我们也可以看出图块[15,1]的left值为1,right值为3。
在扫描的同时,使用20*20的像素矩阵在图块与图块之间进行比较。发现不同的图块,则在变量squaretp数组生成一个新的类型,并把该图块作为该种类型的第一个图块进行保存;发现相同类型的图块,则把该图块的位置信息记录到相应类型链表的后面,如图7中所示。
循环结束后,扫描、识别、分类的工作也宣告完成。这时候,squarend、squaretp数组已经填充完毕。如果代码不出错的话,根据实际情况,每一种类型应该具有若干个图块(至少两个且为偶数,具体跟游戏的初始化有关)。
图7所示的是扫描识别结束后,类型数组中存储内容的示意图。
图7 全部图块扫描后的存储结果
(四)在每一类相同的图块儿中,寻找可“消”的图块对
前面已经得到了全部类型的图块并进行了分类,因此可以开始后面的工作了,也就是判断相同类型的图块是否可以“消”。
首先,必须弄清楚什么样的情况才可以“消”。下图表示的是几种典型的可“消”的模式(为了说明问题,没有列出所有情况)。为了简单的说明问题,使用示意图的形式表示,图中黑色表示相同的图块,空白处表示没有图块,格状处表示有不同的图块障碍。
图8 可“消”图块的多种情况
针对每种情况,都有不同的判断方法,下面举例说明三种情况下的判断方法。假设p、q是两个指向黑色图块的指针。
第一种情况,p、q图块在同一行,如果二者中间在水平方向上没有其他图块,如(a),即满足下面的条件:
(p->y == q->y) && (p->x+ p->right + 1) == q->x
那么这两个图块就能够点击消除。
如果不满足上面的条件,如(b),那么就要通过其他行去判断二者是否能“消”,即需要遍历0~p.y-1行以及p.y+1~10行,比较这些行上p.x和q.x列上的图块的left和right值。
第二种情况,p、q图块在同一列,如果二者中间在垂直方向上没有其他图块,如(c),即满足面的条件:
(p->x == q->x) && (q->y+ q->bottom + 1) == p->y
那么这两个图块就能够消除。
如果不满足上面的条件,如(d),那么就要通过其他列去判断二者是否能“消”,,即需要遍历0~p.x-1列以及p.x+1~18列,比较这些列上p.y和q.y行上的图块的top和bottom值。
第三种情况,p、q既不在同一行业不在同一列,如(e)(f)所示,这种情况就需要在相关的行和列上进行比较了,具体的实现细节不再赘述。
遍历squarend数组中所有的元素(即每一个图块),把能够“消”的图块对保存在squarecl数组中。
(五)把当前所有能“消”的图块对完全消除,并在“消”的过程中实时改变关键数据,为程序继续扫描作准备
经过第四步的遍历,squarecl数组中保存了当前形势下所有可“消”的图块对。设置一个循环,取出squarecl数组中所有的图块对,假设p、q可“消”,则模拟鼠标点击操作的代码如下:
//point1、point2为计算出的两个屏幕坐标点,分别位于p、q图块上。
m_pWnd->ClientToScreen(&point1);
m_pWnd->ClientToScreen(&point2);
SetCursorPos(point1.x,point1.y);
mouse_event(MOUSEEVENTF_LEFTDOWN,0,0,0,0);
mouse_event(MOUSEEVENTF_LEFTUP,0,0,0,0);
Sleep(500);
SetCursorPos(point2.x,point2.y);
mouse_event(MOUSEEVENTF_LEFTDOWN,0,0,0,0);
mouse_event(MOUSEEVENTF_LEFTUP,0,0,0,0);
通过模拟两次点击,这个图块对就从屏幕中消失了,所以当前地图需要实时更新数据,同时相邻图块的top、bottom、left、right等值都需要重新计算。下面通过分析部分代码说明这个实时更新过程,代码中i、j均为临时变量控制循环使用。
(1)首先需要改变p、q两个图块所在的squarebitmap数组中的位图值
cp = 0x0001;//cp是临时定义的WORD变量
cp = cp < (squarecl[i].p-="">y);
squarebitmap[squarecl[i].p->x] =squarebitmap[squarecl[i].p->x] ^ cp;
cp = cp < (squarecl[i].q-="">y);
squarebitmap[squarecl[i].q->x] =squarebitmap[squarecl[i].q->x] ^ cp;
(2)地图信息实时更新以后,部分图块的top、bottom、left、right值会发生变化,需要同时改变。下面的代码分别说明了p指向的图块消失后,有关图块的变化情况。
cp = 0x0001;
cp = cp < (squarecl[i].p-="">y);
for (j = squarecl[i].p->x - 1;j >= 0;j--)
if ( (squarebitmap[j] & cp) != 0 )
break;
if (j >= 0)
squarend[squarecl[i].p->y][j].right +=squarecl[i].p->right + 1;
for (j = squarecl[i].p->x + 1;j <>
if ( (squarebitmap[j] & cp) != 0 )
break;
if (j <>
squarend[squarecl[i].p->y][j].left +=squarecl[i].p->left + 1;
cp = 0x0001;
for (j = squarecl[i].p->y - 1;j >= 0;j--)
if ( (squarebitmap[squarecl[i].p->x] &(cp < j)="" )="" !="0">
break;
if (j >= 0)
squarend[j][squarecl[i].p->x].bottom +=squarecl[i].p->bottom + 1;
for (j = squarecl[i].p->y + 1;j <>
if ( (squarebitmap[squarecl[i].p->x] &(cp < j)="" )="" !="0">
break;
if (j <>
squarend[j][squarecl[i].p->x].top +=squarecl[i].p->top + 1;
在“消”完了squarecl数组中现存的所有数据后,地图信息同时进行了更新,所有相关图块的top、bottom、left、right值都发生了变化。这时候,就进入了下一轮循环,即在所有相同类型的图块链表中重新计算寻找可“消”的图块对,存入squarecl数组……直到找不到可“消”的图块对为止,程序结束。
三、程序优化的方法及辅助工具的制作
从上面的分析我们不难看出,影响程序执行效率的几个关键因素:图块扫描、像素矩阵比较、鼠标点击时间间隔等。
所有的图块必须一个一个的扫描,因为在初始化的时候任何一个位置上的图块都是随机出现的,不可能错过任何一个图块,因此图块扫描速度的提高是非常有限的。
在实际的游戏中,我们可以看到,当鼠标点击两个图块进行消除时,系统并不是马上删掉这两个图块,图块总是伴随着声音渐进消亡的过程,因此外挂程序在处理这个时间间隔时不能特别快,否则会出现“消不了”的情况,这是笔者在实践中验证的结论。
但是通过人为设定鼠标点击的时间间隔,可以使程序更加灵活,可以人为的控制“消”的速度不至于太快,不至于在房间内被“踢”出。
那么像素矩阵比较的速度能提高吗?答案是肯定的,却也是有限的。诚然,减小像素矩阵的大小可以大大减少比较的次数,但也可能会降低识别的正确率,造成严重后果,这需要在实践中不断摸索,找出能保证正确率的最小像素矩阵。笔者推荐16*16或者10*10的像素矩阵,若再继续减小矩阵恐怕会出现比较差的效果。
另外还有一个问题,那就是地图千变万化,不可能都在程序设计的时候写进代码里去,因此还需要一个地图制作的工具,否则这个外挂程序就不可能具有实用性。下面简要介绍一下笔者写的一个地图制作工具。
设计一个简单的对话框,将主窗口分为11*9的画面结构,如图9所示。
图9 地图制作工具主界面
在程序中,笔者采用了下面的方法:使用鼠标点击每一个单元格便出现一个图块,再次点击则图块消失,也可按住鼠标进行拉动。如图8种所示的青色单元格。地图输入完毕以后,点击确定保存结果,同时完成对squarebitmap位图数组的初始化。
其他的辅助工具如过程监测等,可以根据需要自行编写,笔者不再一一介绍。
此外,计算机的配置、系统性能是决定程序执行速度的重要指标和因素,因此如果想进一步提高效率,还可以考虑提高硬件的性能。
四、程序通用程度分析
其实,对于新浪网的连连看游戏,笔者还想到了另外一种外挂的方法,那就是预先存储所有类型的图块数据,如图10所示。这样在进行像素矩阵比较的时候就可以大大降低循环的次数,达到提高速度的目的。
图10 部分图块图案
但是这样做也有其弊端,在新浪网提供的连连看游戏中,系统本身提供了几套不同的牌形状可供用户选择,图9表示的只是其中一类,还有扑克牌、数字、交通标志等不同的类型,而且以后还有可能出现更多的形状,外挂程序一经开发不可能覆盖所有图案形状,采用本文介绍的方法就可以不考虑图案的种类,这也是牺牲速度换取程序通用性的一个策略。
经过十几天的不断调试,程序编译成功并通过测试,在实际运行中取得了较好的效果,无论是速度、稳定性方面都有较好的表现。笔者随后把该程序进行了扩展,使之可以挂在单机版的连连看游戏中(以“连连看3完全版”为蓝本),由于网络版与单机版连连看的变化方式完全不同,因此在设计方式及细节处理上也大不相同,但最基本的如全局图块的扫描、像素矩阵的比较等方面都可以做到代码的复用。
联系客服