现在的位置: 首页 > 综合 > 正文

连连看外挂消去算法分析

2014年09月05日 ⁄ 综合 ⁄ 共 6809字 ⁄ 字号 小 中 大 ⁄ 评论关闭

原文地址：http://www.cnblogs.com/hsapphire/archive/2011/03/14/1983447.html

连连看外挂消去算法分析

 很久之前发布了一个小外挂，是我自己捣鼓出来的QQ游戏连连看外挂。 
  
见：http://www.cnblogs.com/G_Weber/archive/2009/06/02/1494871.html 

在做这个外挂的时候，还是有一点点基于对象的思想的，小弟才疏学浅，还不敢说自己是做到面向对象。说基于对象，就是对其中最核心的消去算法做了封装，有一个跟其它因素无关的功能。今天，想把连连看外挂中核心的消去算法做一个分析。

一、何谓我所谓的“核心消去算法” 

连连看的游戏规则就不用说了吧，不知道的人也不会看到这里来的。 

“核心消去算法”就是在游戏中利用高效的算法找出符合连连看游戏规则，可以消去的两个点。

二、连连看的数据数据结构表示 

    请注意，我现在分析的我这个算法不局限于某种连连看游戏。这里仅仅是使用QQ连连看举例而已。连连看是一个平面游戏，游戏界面是一个矩形，而且这个矩形可以细分为一个个小格子，每一个小格子就是一个游戏单元，我们需要数据结构来保存游戏数据，那么二维数组便是最佳的数据结构了。例如，对于下面的游戏截图： 
1  

经过我的处理后，我使用这样一个二维数组来保存游戏数据。 

在我的程序中，最后得到的二维数组是这个样子的： （为调试方便，输出到文件） 
2 

我用0代表空格子，然后1---N代表不同的方块，相同的方块用相同的数字来表示。 

那么连连看核心消去算法就简化为：如何从这样的一个二维数组里面找出可以消去的一对了~

三、再次简化问题 

    从二维数组里面找出一对可以消去的方格，而连连看游戏只要求能消去就行了，消去对的顺序并没有做任何要求，所以我们可以这样看待问题。任意给定一个方格，要求找出能消去的另一个方格。而消去一对以后，再按照某种方式指定下一个方格，搜索出可以配对的另一个方格。

四、确定处理数据结构的思想 

    对于保存游戏数据的二维数组，我把每一个数组元素看成一个图节点，然后用图的宽度优先搜索方法搜索该图，找出一个配对。用深度优先也是差不多的，效率区别不大。

五、确定图搜索的扩展单元 

   既然使用图搜索方法，那么必然就会有一个扩展新的图节点的过程，宽度思想最基本的方法就是扩展在当前点的周围的点，然后在每次循环的时候判断新扩展的点是否规则。 
5.1  

例如，红色点位当前点，那么在一次图扩展的时候就会把蓝色的点加入考虑集合，然后不断判断集合的点是否符合规则。那么我们还需要另外编写算法，判断一个点是否符合规则，这样效率肯定不够高，所以我们在扩展的时候应该在扩展的过程中就利用游戏规则。游戏中可以消去的一对只有三种情况： 
5.2  

情况1：一条线直接连接两个相同的方块； 

情况2：经过一个拐点连接两个相同的方块； 

情况3：经过两个拐点连接两个相同的方块； 

因此，充分利用游戏规则，在扩展图节点的时候，扩展单元应该是一条线条，而不是一个个方格。采用线条作为拓展单元的好处在于： 

1.根据游戏规则，线条的拐点最多就两个，所以搜索的时候最大的深度不会超过3； 

2.线条扫描到的点一定是符合游戏规则的点，那么就不用额外编写算法判断是否符合配对了，只要方格更初始方格相同，那就是可以组成消去对了。 


所以扩展过程应该是这样： 

从初始点开始，往四个方向检测： 
5.3 

如果不行，再从第一次检测到的格子出发，再进行扩展。线条最多可以有三次拓展，下面是第二次和第三次，只画出了其中一种情况： 
5.4 5.5 

浅蓝色这一行便是从初始化点经过三次扩展后能检测的点了，如果这些点中再也没有跟初始化点相同的方格，那么这一排就直接淘汰了。

六、数据结构代码表示 

算法的重点就是上面提到的“线”了。定义线的数据结构之前，还需定义一个新的类型：方向；因为我们可以看到在图中，线的方向有四个: 向左、向右、向上、向下。我们用几个常量表示：

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游戏中实现秒杀完全没问题！  

    这篇东东只是讨论了连连看外挂中消去这个步骤，在实际应用中还要涉及到如何获取游戏数据，就是上面提到的二维数组；最终得到的两个点的索引，即逻辑坐标转换为具体游戏的实际坐标，然后再具体怎么操作实现点击，自动玩游戏，这些就见人见智了，已经超过这里的范畴了。  

    给出我最终完成的源码 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞