基于像素识别的连连看辅助

这个算是除了课程设计之外我的第一个小工具，这里重点分析一下思路，有基础的读者应该可以通过参考本文章写出自己的程序。

注:此文章仅用于学习参考

一、 需要的知识：

  • C++基础
  • WinAPI的使用

二、 程序实现原理步骤：

  1. 获取游戏及图片信息
  2. 分析图片及定位将其转化为矩阵(二维数组)
  3. 通过BFS算法计算消除顺序
  4. 发送对应鼠标信息进行消除。

三、 分步说明

1. 使用的结构体与参数说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//点坐标带方向与当前步数
struct PointDir
{
	int x;
	int y;
	int step;//bfs中距离起点的距离
	int dir;//bfs中当前拓展的方向
};

//RGB颜色
class Color
{
  public:
	unsigned char R; //红色的亮度
	unsigned char G; //绿色的亮度
	unsigned char B; //蓝色的亮度
	Color(); //初始化参数为0
	Color(int r, int g, int b); //以rgb值初始化参数
	void operator=(COLORREF c); //以COLORREF对象赋值
	bool operator==(Color &c);
	bool operator!=(Color &c);
	void displayRGBInfo();
};

//一个方块
class Block
{
  public:
	Color rect[blockSizeY][blockSizeX];//一个方块内的所有像素点信息
	Block();// 初始化0
	bool operator==(Block &b);
};

//精度值，影响截取速度（单位 像素）
static const int radious;
//窗口 在屏幕内 的位置（单位 像素）
static const int windowX;
static const int windowY;
//窗口内 到地图 的偏移量（单位 像素）
static const int raceX = xx + radious;
static const int raceY = xx + radious;
//地图棋盘大小（单位 行列）
static const int sizeX;
static const int sizeY;
//方块大小（单位 像素）
static const int blockSizeX = xx - radious * 2;
static const int blockSizeY = xx - +radious * 2;
//每个方块之间的间隔（单位 像素）
static const int blank = xx + radious * 2;

2. 对图像的截取：

  • 使用的主要WinAPI函数：
1
2
3
4
5
6
7
8
9
10
//以字符串匹配查找窗口
HWND FindWindow(LPCSTR lpClassName, LPCSTR lpWindowName);
//改变窗口的大小位置以及窗口级别
BOOL WINAPI SetWindowPos(HWND,HWND hWndInsertAfter,int X,int Y,int cx,_In_ int cy, UINT uFlags);
//获取设备句柄
HDC GetDC(HWND);
//获取对应（x,y）坐标的像素点信息
COLORREF GetPixel(HDC hdc, int X, int Y);
// 激活窗口
SetForegroundWindow(hwnd);
  • 过程：

以窗口名称查找游戏窗口得到对应句柄，激活窗口，设置窗口位置(可省，仅便于计算像素点位置)。手动计算得出牌面上每个方块的像素位置，对每个方块截取像素并保存在相应结构体数组内。

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//查找并设置窗口
HWND hwnd=NULL //初始化窗口句柄
cout << "正在查找窗口 <<游戏窗口名称>>..." << endl;
while (hwnd == NULL)
{
	hwnd = FindWindow(NULL, TEXT("游戏窗口名称"));
}
cout << "窗口已找到" << endl;
cout << "设置窗口位置" << endl;
SetWindowPos(hwnd, HWND_TOP, windowX, windowY, 0, 0, SWP_NOSIZE);// 设置窗口位置但不改变大小
SetForegroundWindow(hwnd);// 激活窗口
}

//截取并保存每个方块信息
cout << "获取方块信息..." << endl;
//保存每个方块的rgb值
HDC hdc = GetDC(hwnd);
Block block[sizeY][sizeX];

//棋盘上的每个方块
for (int row = 0; row < sizeY; row++)
{
	for (int col = 0; col < sizeX; col++)
	{
		cout << "正在获取block[" << row << "][" << col << "]方块信息..." << endl;
		//每个方块内的每个像素点
		for (int i = 0; i < blockSizeY; i++)
		{
			for (int j = 0; j < blockSizeX; j++)
			{
				//分别保存每个方块的每个像素点信息
				block[row][col].rect[i][j] = GetPixel(hdc, raceX + col * (blockSizeX + blank) + j, raceY + row * (blockSizeY + blank) + i);
			}
		}
	}
}

3. 将截取的图像转化为矩阵(二维数组)：

  • 过程：

对保存的每个方块的像素信息进行比对，相同方块(截取的像素点信息相同)使用同一个数字编号，保存在一个二维数组内

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Block space;
for (int i = 0; i < blockSizeY; i++)
{
	for (int j = 0; j < blockSizeX; j++)
	{
		//设置空白方块的rgb值
		space.rect[i][j].R = xx;
		space.rect[i][j].G = xx;
		space.rect[i][j].B = xx;
	}
}

int cnt = 1;//起始编号为1,0表示为空地
Block pblock[50];//临时变量，保存已经出现过的牌形种类
pblock[0] = space;

for (int i = 0; i < sizeY; i++)
{
	for (int j = 0; j < sizeX; j++)
	{
		bool flag = false;// 标记当前坐标方块此前是否出现过，k为该方块对应编号
		for (int k = 0; k < cnt; k++)
		{
			//越界处理提示，一般不会出现
			if (k == 49)
			{
				cout << "error！牌面数量太多！" << endl;
				exit(1);
			}
			if (block[i][j] == pblock[k])
			{
				map[i][j] = k;
				flag = true;
				break;
			}
		}
		//如果此前都没有出现过该方块，给予新编号并保存当前方块
		if (!flag)
		{
			pblock[cnt] = block[i][j];
			map[i][j] = cnt;
			cnt++;
		}
	}
}

4. 消除路径分析：

  • 过程：

算法使用BFS广度优先搜索，对每个未消除方块展开搜索，此处注意连连看限制条件（拐点不超过2个）将待消除方块信息(鼠标点击的坐标)保存在一个队列中。

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//该bfs仅判断单个方块是否有对应可达终点方块
//inX,inY为起点方块,ansX,ansY为找到的可连接的终点方块
bool bfs(int inX, int inY, int &ansX, int &ansY)
{
	PointDir inp, curp, nextp;//起点，当前访问点，下一访问点
	//初始化起点
	inp.x = inX;
	inp.y = inY;
	inp.step = -1;// 由起点开始的点出发时step必定+1变为0
	inp.dir = -1;// 起点不设置有效方向，便于step计数

	//q保存bfs待访问队列
	queue<PointDir> q;
	curp = inp;
	q.push(curp);
	bool isFind = false;//是否找到可连接的对应方块
	//当队列不空并且没有找到对应终点方块时继续循环
	while (!q.empty() && isFind == false)
	{
		curp = q.front();
		q.pop();
		//上下左右四个方向，dirs[][]数组为四个方向的向量数组
		for (int k = 0; k < 4; k++)
		{
			nextp.x = curp.x + dirs[k][0];
			nextp.y = curp.y + dirs[k][1];
			nextp.dir = k;
			nextp.step = curp.step;
			//当当前访问点方向与上一点方向不相同，判定为拐点，step++
			if (curp.dir != k)
			{
				nextp.step++;
			}
			//当拐点大于2个(不符合连连看消除条件路径)跳过当前次循环
			if (nextp.step > 2)
			{
				continue;
			}
			//当当前点为起点时跳过当前次循环
			//因为连连看可消除路径数小于可到达路径数，故不判定当前点是否曾经被走过即用一个bool visited[][]保存访问状态，若有更好解决办法欢迎讨论。
			if (nextp.x == inp.x && nextp.y == inp.y)
			{
				continue;
			}
			//边界检查
			if ((nextp.x >= 0) && (nextp.x < sizeX) && (nextp.y >= 0) && (nextp.y < sizeY))
			{
				//若是空地加入待访问队列
				if (map[nextp.y][nextp.x] == 0)
				{
					q.push(nextp);
				}
				//若与起点方块相同，则判定找到对应终点方块，记录坐标并退出循环
				if (map[nextp.y][nextp.x] == map[inp.y][inp.x])
				{
					map[inp.y][inp.x] = 0;
					map[nextp.y][nextp.x] = 0;
					ansX = nextp.x;
					ansY = nextp.y;
					isFind = true;
					break;
				}
			}
		}
	}
	return isFind;
}

//计算点击顺序并保存在待点击队列qClick
void caculate()
{
	//一次遍历并不能把整个棋盘消除完全，经过实验一般10*20的棋盘在不考虑 无牌可消 的情况下可以在3-4次循环内消除完整。
	//！注意此代码中的方法并不好，更好的方法应该是无限循环，当无牌可消的情况下加入重列动作，直到消除完整。
	//将待点击队列qClick改为优先队列（以起终点距离step排序，近的优先）在连连看生成代码较完善的情况下，可以极大的减少 无牌可消 的情况。
	for (int k = 0; k < 5; k++)
	{
		//bool checkOver()函数 检查当前棋盘是否已经消除完毕
		if (checkOver())
		{
			break;
		}
		for (int i = 0; i < sizeY; i++)
		{
			for (int j = 0; j < sizeX; j++)
			{
				//对每一个点bfs展开
				if (map[i][j] != 0) //0是空地
				{
					PointDir p1;
					p1.x = j;
					p1.y = i;
					PointDir p2;
					if (bfs(j, i, p2.x, p2.y))
					{
						//若找到可连接终点，将起点终点推入待点击队列
						qClick.push(p1);
						qClick.push(p2);
					}
				}
			}
		}
	}
}

5.消除的实现：

  • 主要WinAPI函数：
1
2
3
4
//设置鼠标位置
BOOL SetCursorPos(int X, int Y);
//鼠标事件(模拟鼠标点击行为)
void mouse_event(DWORD dwFlags, DWORD dx, DWORD dy, DWORD dwData, ULONG_PTR dwExtraInfo);
  • 过程：

按照待消除队列依次模拟鼠标移动点击消除便是。

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
while (!qClick.empty())
{
	PointDir p;
	p = qClick.front();
	//设置鼠标位置
	SetCursorPos(windowX + raceX + p.x * (blockSizeX + blank), windowY + raceY + p.y * (blockSizeY + blank));
	//模拟鼠标点击，先按下(LEFTDOWN)再放开(LEFTUP)
	mouse_event(MOUSEEVENTF_LEFTDOWN, 0, 0, 0, 0);
	Sleep(10); //要留给某些应用的反应时间
	mouse_event(MOUSEEVENTF_LEFTUP, 0, 0, 0, 0);
	qClick.pop();
}
程序
#cpp #程序 #代码
基于像素识别的连连看辅助
https://maoxianck.github.io/程序/基于像素识别的连连看辅助/
作者
MaoxianCk
发布于
2020年3月4日
许可协议