连连看外挂消去算法分析

 很久之前发布了一个小外挂，是我自己捣鼓出来的QQ游戏连连看外挂。
   见：http://www.cnblogs.com/G_Weber/archive/2009/06/02/1494871.html
在做这个外挂的时候，还是有一点点基于对象的思想的，小弟才疏学浅，还不敢说自己是做到面向对象。说基于对象，就是对其中最核心的消去算法做了封装，有一个跟其它因素无关的功能。今天，想把连连看外挂中核心的消去算法做一个分析。

一、何谓我所谓的“核心消去算法”
连连看的游戏规则就不用说了吧，不知道的人也不会看到这里来的。
“核心消去算法”就是在游戏中利用高效的算法找出符合连连看游戏规则，可以消去的两个点。

二、连连看的数据数据结构表示
    请注意，我现在分析的我这个算法不局限于某种连连看游戏。这里仅仅是使用QQ连连看举例而已。连连看是一个平面游戏，游戏界面是一个矩形，而且这个矩形可以细分为一个个小格子，每一个小格子就是一个游戏单元，我们需要数据结构来保存游戏数据，那么二维数组便是最佳的数据结构了。例如，对于下面的游戏截图：
 
经过我的处理后，我使用这样一个二维数组来保存游戏数据。
在我的程序中，最后得到的二维数组是这个样子的： （为调试方便，输出到文件）

我用0代表空格子，然后1---N代表不同的方块，相同的方块用相同的数字来表示。
那么连连看核心消去算法就简化为：如何从这样的一个二维数组里面找出可以消去的一对了~

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

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

五、确定图搜索的扩展单元
   既然使用图搜索方法，那么必然就会有一个扩展新的图节点的过程，宽度思想最基本的方法就是扩展在当前点的周围的点，然后在每次循环的时候判断新扩展的点是否规则。
 
例如，红色点位当前点，那么在一次图扩展的时候就会把蓝色的点加入考虑集合，然后不断判断集合的点是否符合规则。那么我们还需要另外编写算法，判断一个点是否符合规则，这样效率肯定不够高，所以我们在扩展的时候应该在扩展的过程中就利用游戏规则。游戏中可以消去的一对只有三种情况：
 
情况1：一条线直接连接两个相同的方块；
情况2：经过一个拐点连接两个相同的方块；
情况3：经过两个拐点连接两个相同的方块；
因此，充分利用游戏规则，在扩展图节点的时候，扩展单元应该是一条线条，而不是一个个方格。采用线条作为拓展单元的好处在于：
1.根据游戏规则，线条的拐点最多就两个，所以搜索的时候最大的深度不会超过3；
2.线条扫描到的点一定是符合游戏规则的点，那么就不用额外编写算法判断是否符合配对了，只要方格更初始方格相同，那就是可以组成消去对了。

所以扩展过程应该是这样：
从初始点开始，往四个方向检测：

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

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

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

view source

print?

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>有了方向的概念，然后就可以定义线条了：

view source

print?

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>

代表算法的类：

view source

print?

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);

七、重点实现代码：
这里再重点介绍下
// 给定一个点，在地图中搜索另一个能够消去的点

view source

print?

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);这方法就直接返回两个配对的点，因为我在这函数还根据连连看的实际玩法做了小小优化。玩过连连看的人都知道，如果我现在消去了一对点，那么下一次消除的时候在上一次消去的点附近总能找到解。所以我们可以第一次任意指定一个点开始搜索，以后都在上一次消去的点附近开始搜索！

view source

print?

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

分享到： 自制 QQ游戏 连连看 外挂 ~~ | CPU各寄存器的作用 2011-03-14 11:42 浏览 1360 评论(0) 分类:Web前端 查看更多 相关推荐 连连看一种算法的实现、分析与思考（上） 《连连看游戏算法实现、分析与思考》 连连看，这款经典的休闲益智游戏，以其简单易懂的规则和挑战性的玩法深受玩家喜爱。在本文中，我们将深入探讨连连看的算法实现，对其进行分析，并引发一些思考。我们将不涉及... 连连看算法 连连看算法 连连看算法 连连看算法是連連看游戏中的一种核心算法，该算法主要解决了游戏中连通两个点的问题。该算法的要求主要有两个：一是要连接的两点上的图形相同，二是两点间存在一条没有障碍的路线，并且折点不超过两个。... C++实现的连连看算法 C++实现的连连看算法，一个例子可以明白C++语法和开发 的基础 小游戏连连看的详细算法 连连看是一款广受欢迎的休闲游戏，其核心玩法是通过消除...总的来说，连连看的算法设计涵盖了数据结构、搜索算法、游戏逻辑等多个方面，理解并实现这些算法能够帮助开发者更好地创建出趣味性和挑战性兼备的连连看游戏。 基于python图像识别实现的连连看外挂项目源码（仅供学习用途）.zip 基于python图像识别实现的连连看外挂项目源码（仅供学习用途）.zip 代码完整，仅供学习用途，违法使用需使用者自己承担后果。 基于python图像识别实现的连连看外挂项目源码（仅供学习用途）.zip 代码完整，仅供... 连连看java算法 连连看 java算法 基于安卓手机开发的游戏程序 连连看核心算法.rar 连连看是一款广受欢迎的休闲消除类游戏，其核心算法是实现游戏流畅运行和高效消除的关键。在本压缩包“连连看核心算法.rar”中，我们可以深入探讨连连看游戏的算法设计与实现。 连连看的基本规则是：玩家需要找出并... 连连看核心算法c++版本 在实现连连看游戏的过程中，算法扮演了至关重要的角色。本篇将深入探讨连连看的核心算法，特别是基于集合形式搜索路径的C++实现。 连连看的核心算法主要包含以下几个关键部分： 1. **游戏地图的表示**：首先，我们... 功能较全的连连看，经典算法 从给定的文件信息来看，我们正在探讨一个Java编写的连连看游戏的实现，其中包含了游戏界面设计、算法逻辑以及游戏控制的关键元素。下面将详细解析这个游戏中涉及的重要知识点。 ### 1. Java Swing GUI编程 游戏... 连连看 寻路算法 源码 本压缩包提供的源码着重展示了如何利用A*寻路算法来优化连连看的寻路过程。 A*（A-Star）寻路算法是一种启发式搜索算法，它结合了Dijkstra算法和最佳优先搜索，通过一个估价函数来指导搜索，寻找从起点到终点的最短... 基础入门连连看算法 在编程实现连连看算法时，我们主要关注以下几个关键知识点： 1. 图形表示与存储： 在连连看游戏中，我们需要用数据结构来表示游戏盘面。一种常见的方式是使用二维数组或矩阵，其中每个元素代表一个图案或者空白... Java 连连看 经典算法 本项目中，我们重点探讨的是“Java连连看”的经典算法，包括随机分布算法、遍历查找算法以及时间进度控制算法。这些算法的设计不仅保证了游戏的趣味性和挑战性，还使得代码实现更加简洁易懂。 首先，随机分布算法是... java 连连看算法 在IT领域，连连看是一款广受欢迎的休闲游戏，它的核心在于设计高效的算法来找到并消除一对对相同的元素。本文将详细探讨如何使用Java语言实现连连看的算法，特别是利用递归处理无限拐点的情况。 连连看游戏的基本... 一个连连看游戏的算法程序 在这个项目中，我们关注的是一个使用C++Builder编程语言实现的连连看游戏的算法程序。C++Builder是一种集成开发环境，它提供了C++语言的编译器和丰富的VCL（Visual Component Library）组件库，方便开发者构建桌面... 连连看消除算法 连连看消除算法是一种常见的休闲游戏玩法，其核心是通过寻找并消除两个相同图案的棋子，直至棋盘上没有可消除的对为止。在本文中，我们将深入探讨连连看消除算法的设计与实现，以及相关技术要点。 连连看游戏的基本... 连连看的具体算法.doc 连连看的具体算法.doc 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar FLASH连连看算法分析及源代码.docx 《FLASH连连看算法分析及源代码》 连连看是一款深受玩家喜爱的休闲游戏，其核心在于设计合理的算法以判断两个相同图案是否可以通过直线连接。本文将深入探讨FLASH平台下的连连看算法，并提供源代码示例。 首先，... MFC学习笔记\MFC学习笔记整理：002_腾讯游戏连连看外挂制作(一) 虽然MFC本身不包含这样的功能，但可以结合OpenCV或其他第三方库进行图像分析，识别连连看棋盘上的图案。 4. **定时器**：为了实现外挂的自动化操作，我们需要设置定时器，定期执行某些任务。MFC提供了CTimer类来... Global site tag (gtag.js) - Google Analytics