零、前言
大概是11年左右，我正上高二，家里买了电脑，当时最喜欢玩的是就是CF（穿越火线），不过自己技不如人，在游戏中总是被人虐，后来慢慢了解到了外挂，也使用了一些免费的外挂，常见的自瞄、透视、无后、无限子弹等功能都用过。
体会了使用外挂的爽感之后，便再也无法忍受不开挂情况下被人虐的感觉了。但免费的外挂大多都不可靠，要么有病毒，要么功能不可用。因此便萌生了自己学习写外挂的念头，由此跨入了学编程的大门。
到如今差不多已经过了十年，自己写外挂的热情早已不再，如今自己工作研究的方向更是和外挂没一点关系。但之前还是研究了一些外挂实现的原理，因此这里对之前研究了解过的内容做一个总结，也算是“圆”一个自己的外挂梦。
一、概述
百度百科上对外挂的定义如下。
外挂（wài guà），又叫开挂、开外挂、辅助、第三方辅助软件，综合某些修改器的功能进行编程出的游戏修改器。一般指通过修改游戏数据而为玩家谋取利益的作弊程序或软件，即利用电脑技术针对一个或多个软件进行非原设操作，篡改游戏原本正常的设定和规则，大幅增强游戏角色的技能和超越常规的能力，从而达到轻松获取胜利、奖励和快感的好处，通过改变软件的部分程序制作而成的作弊程序。
个人理解，常见的外挂一般是读取、修改数据包或是内存中的数据，来实现各种“强大”功能的，对不懂的人来说，都会认为外挂很神秘，很强大。这里会尝试实现两个外挂，来展示外挂的基本原理。
首先会实现QQ连连看这个游戏的外挂，这个外挂的原理比较简单，可以作为入门练手，自己当年也是基于这个外挂入得门。之后会实现UE4的Demo游戏ShooterGame的外挂，基于这个外挂可以了解FPS外挂的基本原理。最后，基于这两个外挂的实现过程以及原理，给出一些对抗外挂的一些思考。
接下来，我们先了解下QQ连连看外挂的实现。
二、QQ连连看外挂
QQ连连看是腾讯游戏大厅中的一个休闲游戏，界面如下。
游戏规则比较简单，玩家可以将2个相同图案的棋子连接起来，连接线不多于 3 根直线，就可以成功将棋子消除，多人游戏时，谁先将所有的棋子消除完毕，谁就获胜。
这个游戏的难点在于如何快速的找到两个可以消除的棋子，一般流程是，先找到2个一模一样的棋子，然后再判断这两个棋子是否可以符合消除规则，这个过程对于不是很熟练的人来说还是比较耗费时间的。
但对程序来说，这个过程非常快速，程序能够快速的遍历所有的棋子，并基于算法找到两个可以消除的棋子。若使用程序与别人比赛，那将必胜。
下面我们来看下如何实现这个程序。大部分的程序都遵循以下3个流程，我们这个外挂程序也不例外。
- 输入。
- 数据处理。
- 输出。
对于我们这个外挂来说，输入就是获取棋盘数据，数据处理就是根据棋盘数据判断哪两个棋子可以消除，输出就是自动点击这两个可以消的棋子。就个人来说，这里的难点是判断哪两个棋子可以删除，也即数据处理部分的算法逻辑。
下面拆解这3个步骤，一个个进行处理。
2.1 获取棋盘数据
程序的数据是都在内存中存储着的，如果想获取程序的数据，那么我们只需要拿到数据的地址并读取即可。这里的关键就在于如何获取到这个地址？对于游戏开发者来说，这个地址可以很容易的通过编译后的PDB拿到。而我们自然没有源码，因此只能够祭出神器CheatEngine。CheatEngine的介绍详见官网说明，这里不做过多的介绍，网上相关的教程也非常的多，可以自行查找学习。CheatEngine的界面如下。
使用CheatEngine直接打开QQ连连看的进程，根据经验（这里需要去猜，如果自己是游戏的开发者，那么这个程序该怎么去写，如果猜不对可能需要逆向调试看汇编代码），棋盘应该是一个二维数组，我们需要获取到这个数组的基地址，这样基于行数以及列数就可以获取任意行列的棋子数据了。按照习惯，我们倾向于认为棋盘的左上角是二维数组的第一个元素，那么我们通过CheatEngine不断的测试这个位置的棋子就可以得到它的地址。
我们已经使用CheatEngine打开了游戏进程，游戏中随便进入一个无人的房间，然后进入训练模式，每点击一下训练按钮，棋盘就会更新，配合棋盘的更新以及CheatEngine上的过滤逻辑，重复这个操作，我们就可以快速的拿到这个左上角位置棋子的地址。按照习惯，如果左上角没有棋子，那么这个值就是0，如果有棋子，那么就不为0。
除了数值规则外，还有一个问题是，棋子数据的宽度是多少？显然，这个游戏的棋子数量不会超过256，那么理论上我们是有单字节类型就可以表示所有的棋子，本着省内存的想法，这里我们先尝试使用单字节类型的数据宽度。
左上角棋子为空时，我们查找数据选择Exact value 0，如果棋子不为空，那么这里我们选择Bigger than 0。按照这个规则，我们通过CheatEngine的不断的对内存进行扫描。
最终我们得到了下面几个地址，无论怎么测试，这几个地址的值都会符合我们的规则。虽然这几个地址的值在变化，但是他们的值都不一样，因此肯定只有某个地址是正确的。
这里我们直接打开CheatEngine的内存查看器，一个个看每个地址的数据是否与棋盘上的棋子数据吻合，这里我们发现只有0x199F86这个地址的内存值与棋盘数据是一致的。
虽然找到了地址，但这个地址只针对当前进程有效，如果我们把游戏进程关掉，重新打开一个新的进程，这个地址就不一定正确了。
幸运的是，这个游戏足够简单，我们重新打开游戏后，发现这个地址依旧是棋盘的基址，这样我们读取游戏进程的这个地址就能够获取整个棋盘的所有数据了。
知道了地址，我们就需要通过编程实现获取棋盘的数据。获取棋盘数据有2个关键的步骤：
- 获取到QQ连连看游戏的进程ID，拿到进程句柄。
- 基于进程句柄，读取进程数据。
执行这两个步骤需要几个关键的win32 API，如下。
1
2
3
4
5
|
// 获取指定窗口的句柄
FindProHWND FindWindow(
LPCSTR lpClassName, // 窗口类名
LPCSTR lpWindowName // 窗口标题名
);
|
1
2
3
4
5
|
// 基于窗口句柄获取窗口进程的进程ID
DWORD GetWindowThreadProcessId(
HWND hWnd, // 窗口句柄，FindWindow方法的返回值
LPDWORD lpdwProcessId // 指向进程ID变量的指针，执行成功后，会通过该指针将进程ID传递出来
);
|
1
2
3
4
5
6
|
// 打开进程，成功后，将会返回打开的进程句柄对象
HANDLE OpenProcess(
DWORD dwDesiredAccess, // 打开进程时的权限，使用PROCESS_ALL_ACCESS即可
BOOL bInheritHandle, // 如果为真，此进程创建的进程将继承句柄。否则，进程不会继承这个句柄。使用FALSE即可
DWORD dwProcessId // 进程ID
);
|
1
2
3
4
5
6
7
8
|
// 读取指定进程的内存数据
BOOL ReadProcessMemory(
HANDLE hProcess, // 进程句柄，OpenProcee函数返回的句柄对象
LPCVOID lpBaseAddress, // 读取目标进程的地址
LPVOID lpbuffer_, // 存储数据的缓冲区
SIZE_T nSize, // 读取数据的长度
SIZE_T *lpNumberOfBytesRead // 指向实际读取数据的长度变量的指针
);
|
一个简单的代码示例如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 获取连连看窗口的句柄
HWND hnd = FindWindow(NULL, L"QQ游戏 - 连连看角色版");
// 基于窗口句柄获取进程ID
DWORD pid;
GetWindowThreadProcessId(hnd, &pid);
// 打开进程获取进程句柄
HANDLE handle = OpenProcess(PROCESS_ALL_ACCESS, false, pid);
// 读取连连看游戏内存数据
DWORD num_of_read;
ReadProcessMemory(handle, LPCVOID(0x00199F5C), LPVOID(&buffer_), 209, &num_of_read);
// 关闭进程句柄
CloseHandle(handle);
|
通过上述方式，我们就可以获取到棋盘的数据了。
但这里有个问题，棋盘的基址会随着游戏版本的变化而变化，如果游戏更新，那么上述流程需要重新操作一遍，才能拿到地址。
那么有没有其他方法，可以避免这个问题？是有的，可以使用图像识别的方式，截取整个棋盘的图像，之后对棋盘图像按照棋子的大小进行切割，切割完毕后，识别每个棋子的形状，进而获取棋盘的数据。只要游戏玩法不变，无论游戏版本怎么变更，都可以正确的获取到棋盘的信息。
这种方式自己还没有研究过，网上有见使用python实现的，可以参考下。
2.2 消子算法实现
有了棋盘数据后，接下来就需要实现消子算法了。有算法经验的话，会发现这是一个寻路算法，只是路径变化需要限制在3条线内。
而自己最早写这个外挂时是在高中的时候，那个时候还没有经验，想了好久，想了下面这样的算法。
2.2.1 普通算法
首先对消子逻辑进行归纳，可以发现消子大概有这2种情况。
第一种情况
在这种情况中，分别对两个一模一样的两个棋子（下图中画圈处）画条竖线，如下图中的线1和线2，基于这两条竖线，我们可以发现一条横线3，它可以无阻碍的连接线1和线2，同时线3与线1、线2的交点到两个棋子上也没有阻碍，那么这两个子便可以消掉。
第二种情况
在这种情况中，分别对两个一模一样的两个子（下图中画圈处）画条横线，如下图中的线1和线2，基于这两条横线，我们可以发现一条竖线3，它可以无阻碍的连接线1和线2，同时线3与线1、线2的交点那么这两个子便可以消掉。
至于两个子可以通过一条直线直接相连，或是通过两条直线相连的情况，是上面的一种特例，即某一条或是某两条直线的长度为0。
基于上述流程，那么我们便可以实现算法了，算法流程如下。
- 双重循环遍历棋盘中的任意两个有效棋子，如果发现两个棋子一样，那么执行第2步。
- 对这两个棋子分别画一条竖的虚拟线，然后从上到下，依次画一条横的虚拟线，判断这两条竖线以及横线所在的路径是否为空，如果为空，说明可消除，否则不能消除，继续执行下一步。
- 对这两个棋子分别画一条横的虚拟线，然后从左到右，依次画一条竖的虚拟线，判断这两条横线以及竖线所在的路径是否为空，如果为空，说明可消除，否则不能消除，回到第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
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
|
// 判断两个棋子之间是否可连通（即都为空的）
bool is_connected(POINT pt1, POINT pt2)
{
POINT tmp_pt1 = pt1;
POINT tmp_pt2 = pt2;
if (tmp_pt1.x == tmp_pt2.x)
{
auto min_y = min(tmp_pt1.y, tmp_pt2.y);
auto max_y = max(tmp_pt1.y, tmp_pt2.y);
for (int i = 0; i < max_y - min_y + 1; i++)
{
if (buffer_[min_y + i][tmp_pt1.x] != 0)
return false;
}
return true;
}
else if (tmp_pt1.y == tmp_pt2.y)
{
auto min_x = min(tmp_pt1.x, tmp_pt2.x);
auto max_x = max(tmp_pt1.x, tmp_pt2.x);
for (int i = 0; i < max_x - min_x + 1; i++)
{
if (buffer_[tmp_pt1.y][min_x + i] != 0)
return false;
}
return true;
}
return false;
}
// 横向检查
bool horizontal_check(POINT pt1, POINT pt2)
{
POINT tmp_pt1 = pt1;
POINT bianpt2 = pt2;
for (int i = 0; i < 11; i++)
{
bianpt2.y = i;
tmp_pt1.y = i;
if (is_connected(tmp_pt1, pt1) &&
is_connected(tmp_pt1, bianpt2) &&
is_connected(bianpt2, pt2))
{
return true;
}
}
return false;
}
// 竖向检查
bool vertical_check(POINT pt1, POINT pt2)
{
POINT tmp_pt1 = pt1;
POINT tmp_pt2 = pt2;
for (int i = 0; i < 19; i++)
{
tmp_pt2.x = i;
tmp_pt1.x = i;
if (is_connected(tmp_pt1, pt1) &&
is_connected(tmp_pt1, tmp_pt2) &&
is_connected(tmp_pt2, pt2))
{
return true;
}
}
return false;
}
// 判断两个棋子是否可以消除
bool is_eliminate(POINT pt1, POINT pt2)
{
// 这里先将两个棋子的值置为空，方便后面判断
auto pt1_value = buffer_[pt1.y][pt1.x];
auto pt2_value = buffer_[pt2.y][pt2.x];
buffer_[pt1.y][pt1.x] = 0;
buffer_[pt2.y][pt2.x] = 0;
// 横向和竖向判断
bool ret = (horizontal_check(pt1, pt2) || vertical_check(pt1, pt2));
// 将两个棋子的值还原
buffer_[pt1.y][pt1.x] = pt1_value;
buffer_[pt2.y][pt2.x] = pt2_value;
return ret;
}
|
2.2.2 广度优先寻路算法
除了上面的一种算法外，自己也参考《编程之美》上的讲解使用广度优先算法实现了一遍，大致思路如下。
- 遍历棋盘，找到一个有效棋子，之后基于该棋子向上下左右四个方向探索，如果棋子为空，那么先记录下坐标，如果不为空，判断与当前棋子相同，如果相同，那么说明目标棋子与当前棋子通过一条直线即可消除。如果不相同继续下一步。
- 遍历第一步保存起来的为空的坐标，以这些坐标为基准，再向其上下左右四个方向探索，探索的路径注意不要与第一步记录的为空的坐标重复。如果棋子为空，那么依旧记录下来，如果不为空，那么判断目标棋子与第一步中的有效棋子比对是否相同，如果相同，说明目标棋子与有效棋子可以通过两条直线连接起来，如果不同，那么继续下一步。
- 继续遍历第二步保存起来的为空的坐标，以这些坐标为基准，再向其上下左右四个方向探索，注意不要与1、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
|
// 一个通用往4周探索的函数
bool sub_find(POINT org, POINT &p, std::set<std::pair<long, long>>& m, std::queue<POINT> &q, long *v, long border, int seq)
{
// 如果为空，那么一直往前探索，同时将坐标记录下来，用于下一次遍历，同时避免再次遍历到
*v += seq;
while (*v >= 0 && *v < border && buffer_[p.y][p.x] == 0)
{
if (m.find({ p.x, p.y }) == m.end())
{
m.emplace(p.x, p.y);
q.push(p);
}
*v += seq;
}
// 当碰到不为空，且与原始有效棋子一致的棋子后，说明该坐标的棋子可以与有效棋子一块消除
if (*v >= 0 && *v < border &&
!(org.y == p.y && org.x == p.x) &&
buffer_[org.y][org.x] == buffer_[p.y][p.x])
{
return true;
}
return false;
}
// org为有效棋子的坐标
// q用来保存那些为基准的坐标位置，广度优先遍历需要
// m用来记录那些之前已经访问过的坐标
// count用来限制递归深度，因为最多是3条直线，那么递归到2之后就可以停止递归了
bool find_way(POINT org, std::queue<POINT> &q, std::set<std::pair<long, long>> &m, int count)
{
// 最多遍历3层
if (count > 2)
{
return false;
}
std::queue<POINT> tmp_q;
while (!q.empty())
{
POINT p = q.front();
// 依次从右左上下4个方向探索
if (sub_find(org, p, m, tmp_q, &p.x, 19, 1)) return true;
p = q.front();
if (sub_find(org, p, m, tmp_q, &p.x, 19, -1)) return true;
p = q.front();
if (sub_find(org, p, m, tmp_q, &p.y, 11, 1)) return true;
p = q.front();
if (sub_find(org, p, m, tmp_q, &p.y, 11, -1)) return true;
q.pop();
}
// 继续遍历下一层
return find_way(org, tmp_q, m , count + 1);
}
// 判断某个棋子是否有可以与之消除的另一个棋子
int main()
{
POINT pt;
std::queue<POINT> q;
q.push(pt);
std::set<std::pair<long, long>> m;
m.emplace( x, y );
if (find_way(pt, q, m, 0))
{
return true;
}
}
|
2.3 实现点击操作
当确定哪两个棋子可以消除后，接下来就需要执行消除操作了，消除操作很简单，只需要连续点击这两个棋子就行了。
程序实现鼠标点击一般来说主要有两种方法，一种是硬模拟，即真的模拟鼠标点击操作，鼠标会随着这个函数的调用而移动。另一种是软模拟，在windows中，鼠标点击后，系统会将鼠标点击的这个事件发送给目标程序，事件包含鼠标点击的坐标信息，目标程序基于这个事件做相应的处理。如果我们直接模拟发送鼠标点击的事件，那么就也实现了鼠标的点击。
这里我们采用第2种方式，即软模拟的方式，好处是鼠标不用像硬模拟那样真的移动，这种方式中主要需要使用SendMessage这个函数，其定义如下。
1
2
3
4
5
6
|
LRESULT SendMessage(
[in] HWND hWnd, // 目标窗口句柄
[in] UINT Msg, // 消息类型，这里使用WM_LBUTTONDOWN和WM_LBUTTONUP
[in] WPARAM wParam, // 额外信息1，这里为空
[in] LPARAM lParam // 额外信息2，指定鼠标点击的坐标，它是一个32位的整数，高16为y轴坐标，低16为x轴坐标
);
|
点击时，需要知道每个棋子的坐标。连连看游戏的界面可以由一个二维坐标系来表示，坐标系的原点在左上角，向右为x轴，向下为y轴。基于这个坐标轴，我们首先需要知道棋盘左上角第一个棋子中心点的坐标值，之后，我们还需要知道每个棋子的宽度和高度，这样就可以计算出任意一个棋子的中心坐标。
可以使用QQ的截图工具获取棋子的坐标，在截图时，截图工具会显示当前坐标点的坐标值，但这个坐标值是基于桌面的，因此若想获取棋子相对于游戏窗口的坐标值，就需要换算一下。自己量的左上角第一个棋子的坐标是30,198，棋子的宽度是31，高度是35，这样，假设坐标轴为(x,y)的棋子的横坐标就是30 + 31 * x，纵坐标就是198 + 35 * y。
有了坐标，我们就可以实现完整的模拟点击代码。鼠标点击这个操作，需要鼠标按下和鼠标抬起这两个事件配合完成，一个完整的点击操作代码如下。
1
2
3
4
5
6
7
8
9
|
// 两个棋子的坐标
POINT pt, p2;
LPARAM lparam1 = ((pt1.y * 35 + 198) << 16) + (pt1.x * 31 + 30);
LPARAM lparam2 = ((pt2.y * 35 + 198) << 16) + (pt2.x * 31 + 30);
// hnd是连连看窗口的句柄
SendMessage(hnd, WM_LBUTTONDOWN, 0, lparam1);
SendMessage(hnd, WM_LBUTTONUP, 0, lparam1);
SendMessage(hnd, WM_LBUTTONDOWN, 0, lparam2);
SendMessage(hnd, WM_LBUTTONUP, 0, lparam2);
|
2.4 效果
最终实现的连连看外挂效果如下。
三、小结
通过连连看外挂， 我们大致了解了编写外挂的基本流程，整体看下来，会发现连连看外挂的实现并不复杂，一方面，棋盘数据的获取比较简单，其次，数据处理逻辑也不复杂。
下一篇文章我们会基于UE4引擎的Demo游戏ShooterGame，实现一个自瞄透视外挂，相较于连连看外挂，自瞄透视外挂会更有一些难度，敬请期待。