本文共 6136 字,大约阅读时间需要 20 分钟。
原文地址:http://www.cnblogs.com/hsapphire/archive/2011/03/14/1983447.html
在做这个外挂的时候,还是有一点点基于对象的思想的,小弟才疏学浅,还不敢说自己是做到面向对象。说基于对象,就是对其中最核心的消去算法做了封装,有一个跟其它因素无关的功能。今天,想把连连看外挂中核心的消去算法做一个分析。
一、何谓我所谓的“核心消去算法”
连连看的游戏规则就不用说了吧,不知道的人也不会看到这里来的。
“核心消去算法”就是在游戏中利用高效的算法找出符合连连看游戏规则,可以消去的两个点。
二、连连看的数据数据结构表示
请注意,我现在分析的我这个算法不局限于某种连连看游戏。这里仅仅是使用QQ连连看举例而已。连连看是一个平面游戏,游戏界面是一个矩形,而且这个矩形可以细分为一个个小格子,每一个小格子就是一个游戏单元,我们需要数据结构来保存游戏数据,那么二维数组便是最佳的数据结构了。例如,对于下面的游戏截图:
经过我的处理后,我使用这样一个二维数组来保存游戏数据。
在我的程序中,最后得到的二维数组是这个样子的: (为调试方便,输出到文件)
我用0代表空格子,然后1---N代表不同的方块,相同的方块用相同的数字来表示。
那么连连看核心消去算法就简化为:如何从这样的一个二维数组里面找出可以消去的一对了~
三、再次简化问题
从二维数组里面找出一对可以消去的方格,而连连看游戏只要求能消去就行了,消去对的顺序并没有做任何要求,所以我们可以这样看待问题。任意给定一个方格,要求找出能消去的另一个方格。而消去一对以后,再按照某种方式指定下一个方格,搜索出可以配对的另一个方格。
四、确定处理数据结构的思想
对于保存游戏数据的二维数组,我把每一个数组元素看成一个图节点,然后用图的宽度优先搜索方法搜索该图,找出一个配对。用深度优先也是差不多的,效率区别不大。
五、确定图搜索的扩展单元
既然使用图搜索方法,那么必然就会有一个扩展新的图节点的过程,宽度思想最基本的方法就是扩展在当前点的周围的点,然后在每次循环的时候判断新扩展的点是否规则。
例如,红色点位当前点,那么在一次图扩展的时候就会把蓝色的点加入考虑集合,然后不断判断集合的点是否符合规则。那么我们还需要另外编写算法,判断一个点是否符合规则,这样效率肯定不够高,所以我们在扩展的时候应该在扩展的过程中就利用游戏规则。游戏中可以消去的一对只有三种情况:
情况1:一条线直接连接两个相同的方块;
情况2:经过一个拐点连接两个相同的方块;
情况3:经过两个拐点连接两个相同的方块;
因此,充分利用游戏规则,在扩展图节点的时候,扩展单元应该是一条线条,而不是一个个方格。采用线条作为拓展单元的好处在于:
1.根据游戏规则,线条的拐点最多就两个,所以搜索的时候最大的深度不会超过3;
2.线条扫描到的点一定是符合游戏规则的点,那么就不用额外编写算法判断是否符合配对了,只要方格更初始方格相同,那就是可以组成消去对了。
所以扩展过程应该是这样:
从初始点开始,往四个方向检测:
如果不行,再从第一次检测到的格子出发,再进行扩展。线条最多可以有三次拓展,下面是第二次和第三次,只画出了其中一种情况:
浅蓝色这一行便是从初始化点经过三次扩展后能检测的点了,如果这些点中再也没有跟初始化点相同的方格,那么这一排就直接淘汰了。
六、数据结构代码表示
算法的重点就是上面提到的“线”了。定义线的数据结构之前,还需定义一个新的类型:方向;因为我们可以看到在图中,线的方向有四个: 向左、向右、向上、向下。我们用几个常量表示:
1 | // 方向 |
2 | const int X_Pos = 0; |
3 | const int Y_Neg = 1; |
4 | const int X_Neg = 2; |
5 | const int Y_Pos = 3; |
6 | typedef int OrientationType;<BR><BR><BR><BR>有了方向的概念,然后就可以定义线条了: |
01 | // 射线 |
02 | class Line |
03 | { |
04 | public : |
05 | |
06 | int mBeginRow; //射线的起点,不包括该点 |
07 | int mBeginCol; |
08 | |
09 | OrientationType |
10 | mOrientation; //射线的方向 |
11 | |
12 | int mCorner; // 还可使用的拐角 |
13 | };<BR> |
代表算法的类:
01 | //查找结果 |
02 | enum FindPathResult{FP_OK,FP_FAIL,FP_FINISH}; |
03 | |
04 | class CLLKCoreAlg |
05 | { |
06 | public : |
07 | //二维数组 |
08 | typedef vector<vector< int > > Int2Array; |
09 | |
10 | public : |
11 | // public methods ------------------------ |
12 | |
13 | CLLKCoreAlg(); |
14 | |
15 | //重新设置地图 |
16 | void SetMap(Int2Array &map); |
17 | |
18 | inline bool IsReady(){ return m_bEnable;} //算法准备好了么? |
19 | |
20 | // 寻找一个解,返回值代表成功或者失败 |
21 | FindPathResult FindPath( int &beginRow, int &beginCol, int &endRow, int &endCol); |
22 | |
23 | private : |
24 | // private methods --------------------- |
25 | |
26 | // 返回值为 true 的时候 resultRow,resultCol 为找到的点 |
27 | // 返回值为 false的时候 resultRow,resultCol 为终止点 即组成开区间(begin,result) |
28 | // 开区间(begin,result)为可扩展的格子 |
29 | bool _FindAloneXPos( int beginRow, int beginCol, int Value, int &resultRow, int &resultCol); |
30 | bool _FindAloneXNeg( int beginRow, int beginCol, int Value, int &resultRow, int &resultCol); |
31 | bool _FindAloneYPos( int beginRow, int beginCol, int Value, int &resultRow, int &resultCol); |
32 | bool _FindAloneYNeg( int beginRow, int beginCol, int Value, int &resultRow, int &resultCol); |
33 | bool _FindAloneLine(Line &L, int Value, int &resultRow, int &resultCol); |
34 | |
35 | // 给定一个点,在地图中搜索另一个能够消去的点 |
36 | bool _Match( int beginRow, int beginCol, int &endX, int &endY); |
37 | |
38 | // 扩展该线条 |
39 | void _ExpandLine(Line &L, int endx, int endy,deque<Line> & queue); |
40 | private : |
41 | // private attributes ------------------- |
42 | bool m_bEnable; |
43 | Int2Array m_Map; //二维地图 |
44 | int m_iRow; //行 |
45 | int m_iCol; //列 |
46 | |
47 | int m_iLastSuccRow; //上一次成功消去的地方 |
48 | int m_iLastSuccCol; |
49 | }; |
其中对外的接口非常简单:
void SetMap(Int2Array &map); //传入二维数组表示的连连看数据
inline bool IsReady(){return m_bEnable;}//算法准备好了么?
然后用户便可以不断调用下面的方法得到两个点(beginRow,beginCol),(endRow,endCol)
FindPathResult FindPath(int &beginRow,int &beginCol,int &endRow,int &endCol);
七、重点实现代码:
这里再重点介绍下
// 给定一个点,在地图中搜索另一个能够消去的点
01 | bool CLLKCoreAlg::_Match( int beginRow, int beginCol, int &endRow, int &endCol) |
02 | { |
03 | //宽度优先搜索使用队列作为辅助数据结构 |
04 | deque<Line> LineQueue; |
05 | |
06 | //记录初始化方格 |
07 | int MatchValue = m_Map[beginRow][beginCol]; |
08 | |
09 | //生成不同方向的四条线 |
10 | Line l; |
11 | l.mBeginRow = beginRow; |
12 | l.mBeginCol = beginCol; |
13 | l.mCorner = 2; //最多可以两个拐角 |
14 | |
15 | //压入四个方向的射线 |
16 | l.mOrientation = X_Pos; |
17 | LineQueue.push_back(l); |
18 | |
19 | l.mOrientation = X_Neg; |
20 | LineQueue.push_back(l); |
21 | |
22 | l.mOrientation = Y_Pos; |
23 | LineQueue.push_back(l); |
24 | |
25 | l.mOrientation = Y_Neg; |
26 | LineQueue.push_back(l); |
27 | |
28 | //用来存储临时结果 |
29 | int resultRow,resultCol; |
30 | |
31 | while (!LineQueue.empty()) |
32 | { |
33 | //每次循环处理一条线条 |
34 | Line l = LineQueue.front(); |
35 | LineQueue.pop_front(); |
36 | |
37 | //在当期射线上查找是否有配对的方格 |
38 | if (_FindAloneLine(l,MatchValue,resultRow,resultCol)) |
39 | { |
40 | //成功,返回查找结果,中断搜索 |
41 | endRow = resultRow; |
42 | endCol = resultCol; |
43 | return true ; |
44 | } |
45 | else |
46 | { |
47 | //失败 |
48 | //判断当期线条是否能继续扩展 |
49 | if (l.mCorner) |
50 | { |
51 | _ExpandLine(l,resultRow,resultCol,LineQueue); |
52 | } |
53 | //如果不能再扩展,就淘汰 |
54 | } |
55 | } |
56 | return false ; |
57 | } |
该函数使用到的辅助函数_FindAloneLine、_ExpandLine比较简单,请看源码。
八、改进优化
_Match 要求用户输入一个点,然后查找出配对的另一个点,但是我最终开放的接口为:FindPath(int &beginRow,int &beginCol,int &endRow,int &endCol);这方法就直接返回两个配对的点,因为我在这函数还根据连连看的实际玩法做了小小优化。玩过连连看的人都知道,如果我现在消去了一对点,那么下一次消除的时候在上一次消去的点附近总能找到解。所以我们可以第一次任意指定一个点开始搜索,以后都在上一次消去的点附近开始搜索!
01 | FindPathResult CLLKCoreAlg::FindPath( int &beginRow, int &beginCol, int &endRow, int &endCol) |
02 | { |
03 | unsigned int count = (m_iRow +1 )* (m_iCol+1); //最多尝试次数 |
04 | |
05 | int currRow = m_iLastSuccRow; |
06 | int currCol = m_iLastSuccCol; |
07 | |
08 | bool hasGrid = false ; //是否有未消去的格子 |
09 | |
10 | for ( int i=0;i<count;i++) |
11 | { |
12 | if (m_Map[currRow][currCol]) |
13 | { |
14 | //不是空的格子 |
15 | hasGrid = true ; |
16 | |
17 | if (_Match(currRow,currCol,endRow,endCol)) |
18 | { |
19 | //找到成功 |
20 | m_iLastSuccRow = currRow; |
21 | m_iLastSuccCol = currCol; |
22 | |
23 | beginRow = currRow; |
24 | beginCol = currCol; |
25 | |
26 | //更新地图 |
27 | if (beginRow == endRow && beginCol == endCol) |
28 | throw std::exception( "不可能!!!" ); |
29 | m_Map[beginRow][beginCol] = m_Map[endRow][endCol] = 0; |
30 | return FP_OK; |
31 | } |
32 | } |
33 | |
34 | currCol++; |
35 | if (currCol > m_iCol) //一列完,下一列 |
36 | { |
37 | currCol=0; |
38 | currRow++; |
39 | |
40 | if (currRow > m_iRow) |
41 | { |
42 | currRow = 0; |
43 | //到了最后一行完,从最上面的行开始 |
44 | } |
45 | } |
46 | } |
47 | //遍历完,全部无法匹配 |
48 | m_bEnable = false ; |
49 | //如果都没有未消去的格子,那就是成功了 |
50 | return hasGrid ? FP_FAIL:FP_FINISH; |
51 | } |
九、最后
这个搜索算法在QQ游戏中实现秒杀完全没问题!
这篇东东只是讨论了连连看外挂中消去这个步骤,在实际应用中还要涉及到如何获取游戏数据,就是上面提到的二维数组;最终得到的两个点的索引,即逻辑坐标转换为具体游戏的实际坐标,然后再具体怎么操作实现点击,自动玩游戏,这些就见人见智了,已经超过这里的范畴了。
给出我最终完成的源码
转载地址:https://blog.csdn.net/kuloveyouwei/article/details/12885691 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!