前几天想起了这个想法，然后最近两天开发了这个工具，就是用于 QQGame 中的连连看的辅助工具。本来是想把全部代码都公开的，但是我在调试程序的时候注意到腾讯在qqgame中宣传卖那些游戏道具。所以我的想法就改变了下，不想影响腾讯卖这些道具来赚钱，所以我把原来完整功能版的版本又加上了一些限制。
辅助工具实现的功能包括：全自动点击，自动重排（当方块无解时），显示可点击方块提示（相当于官方的指南针功能），模拟单步点击。
首先进入 QQGame，连连看，开始游戏后如下图所示：
启动工具后的界面如下图所示，点击任务栏按钮即可。具体用法参考任务栏的tooltip和压缩包中的简要说明。
最后我为这个版本加了以下限制，使他不至于惹上“影响别人赚钱”的嫌疑（虽然我一向非常鄙视腾讯）。主要限制如下：
（1）自动点击的速度限制在 1 秒一次点击，但可以暂时体验 500 ms 速度。更快的点击速度全部被禁用！
（2）提示数量超过16个（相当于道具中的指南针）时，每次需要输入验证码才能继续。
（3）快速连击“消掉一对方块”的次数如果超过10次，则需要输入验证码才能继续。此处快速连击是指两次点击时间间隔小于 1 秒。
作为兴趣，验证码对话框是我今天加上去的，显然这个手段也是我和腾讯学习来的，如下图所示：
这个对话框比较简单，我用代码动态生成一个图片显示在上面，当然题目也是动态生成的，题目主要是 100 以内的加减乘除法。图片中我放了随机的贝塞尔彩色线条作为干扰。问题里面的每个字符采用了位置和角度的轻微抖动，但是没有经过变形，因为我是用 GDI 函数绘制的文本。
下面介绍下这个辅助工具的一些内容，首先我寻找到游戏中的窗口后，需要确定的棋盘网格的内容，最早我的想法是用4到5个关键点采样来检测方块。但是后来我实际开发时发现，比较幸运的是，能选取特定的方块坐标，可以仅仅用一个采样点就能区分出所有方块。满足这样高区分度条件的采样点一共有四个，被我用代码寻找了出来。检测方块时，相比之前的“快速美女找茬”工具，这次我用了效率更高些的直接对位图数据块寻址来检测。当然，这要求对位图中的像素定位（即在内存数据块中定位到某个位置的某个通道）需要非常熟悉，我在自己的博客中介绍过多次，这里就不重复了。
确定了棋盘网格的内容后，就是这个工具的核心，即寻解的方法。从这点上来说，其实程序的寻解和人的寻解本质上并没有什么不同，只不过两者的侧重点稍有区别。在程序中，在确定棋盘网格的过程中，我就建立了对每一种方块都建立了一个双向链表（采用双向链表的原因是因为随着寻解的过程，需要频繁的进行节点脱链操作），去存储他们的坐标。这样的目的是不需要反复的盲目扫描棋盘，而是把精力集中到判断两个方块是否有通路就可以了。游戏中的方块多达 40 多种，所以我用一个指针数组来存储所有链表的 Head。取决于游戏的设计，链表数量较多，但长度较短（例如为 4 ）。所以尽管寻解算法的时间复杂度相对与链表长度为 O(n^2)，但整个求解过程依然是感觉很快，后台运算的线程感觉是瞬间就退出的，以至于我觉得哪怕是用户需要的时候再算时间都来得及，根本不需要另起一个线程来求解了。当完全不使用定时器延时时，令我感到吃惊的是，仿佛是就点了一下，然后所有方块就全部消失的无影无踪了，这根本违背了我们平时观看到的场景印象。由于方块消失的太快，整个游戏窗口都弥漫在一团烟雾效果中。
下面我给出的是连连看的“通路”判断方法，这是所有连连看的共同游戏规则。不管是什么连连看游戏，你都能在代码中看到这个函数，只不过可能形式有多种多样而已。由于分别在两个方向上检测，所以两部分的代码惊人的一致，这也可能让我这样有完美主义倾向的人感觉不爽，想把两部分代码合并成一个循环（我们把网格指针的偏移作为变量，分别存放到一个含有两个元素的数组中即可，例如如果我们要在水平方向上移动，偏移量是+-1，在垂直方向上移动，偏移量是+-行宽度），这当然是可以的，但我想可能会牺牲掉一部分代码可读性。下面的代码非常简洁，它的主题是来自我以前发表在 BCCN上 的 TC2.0版的连连看（DOS贴图版）中的代码：
//连连看游戏的核心算法
BOOL CanConnect(char map[11][19], int row1, int col1, int row2, int col2)
{
int path, i, j, left, right, top, bottom;
int min1, min2, max1, max2;
//-----------------查找水平方向----------------------------
min1 = max1 = col1;
min2 = max2 = col2;
while(min1 - 1 >= 0 && map[row1][min1 - 1] == 0) min1--;
while(min2 - 1 >= 0 && map[row2][min2 - 1] == 0) min2--;
left = __max(min1, min2);
while(max1 + 1 < 19 && map[row1][max1 + 1] == 0) max1++;
while(max2 + 1 < 19 && map[row2][max2 + 1] == 0) max2++;
right = __min(max1, max2);
//检查两条水平线之间是否有可连通的垂直线
for(i = left; i <= right; i++)
{
path = 0;
for(j = __min(row1, row2) + 1; j < __max(row1, row2); j++)
{
path += map[j][i];
if(path > 0) break;
}
if(path == 0)
return TRUE;
}
//-----------------查找垂直方向----------------------------
min1 = max1 = row1;
min2 = max2 = row2;
while(min1 - 1 >= 0 && map[min1 - 1][col1] == 0) min1--;
while(min2 - 1 >= 0 && map[min2 - 1][col2] == 0) min2--;
top = __max(min1, min2);
while(max1 + 1 < 11 && map[max1 + 1][col1] == 0) max1++;
while(max2 + 1 < 11 && map[max2 + 1][col2] == 0) max2++;
bottom = __min(max1, max2);
//检查两条垂直线之间是否有可连通的水平线
for(j = top; j <= bottom; j++)
{
path = 0;
for(i = __min(col1, col2) + 1; i < __max(col1, col2); i++)
{
path += map[j][i];
if(path > 0) break;
}
if(path == 0)
return TRUE;
}
return FALSE;
}
下面是后台线程的代码，调用了上面的方法，过程类似绘制“金刚石”图形（所有顶点彼此连线），和冒泡排序一类的时间复杂度相同。
//用于寻找可点击方块的后台线程，进入线程时，map 已经初始化好了
DWORD WINAPI MyThread(LPVOID lpParameter)
{
PMYTHREAD_PARAMS pMyParams = (PMYTHREAD_PARAMS)lpParameter;
int i;
HWND hwnd = pMyParams->hWndUI;
PCELLPOS pNode1, pNode2;
BOOL bAllListIsNull;
BOOL bFind_One_Solution; //是否找到了一个解
while( !bThreadStopSignal )
{
bAllListIsNull = TRUE;
bFind_One_Solution = FALSE;
//此处暴力的盲目搜索就是了~。~ 有时间的话需要让此处更“智能化”！
//pCellPos[0]就是代表空白位置的链表，永远为 NULL （浪费掉了）
for(i = 1; i < CELL_TYPE_COUNT; i++)
{
//在链表中搜索是否可点击类似金刚石画法，时间复杂度：O(n^2)
if(pCellPos[i] != NULL)
{
bAllListIsNull = FALSE; //存在链表不为空
pNode1 = pCellPos[i];
while(pNode1 != NULL)
{
pNode2 = pNode1->pNext;
while(pNode2 != NULL)
{
if(CanConnect(map, pNode1->row, pNode1->col, pNode2->row, pNode2->col))
{
//找到了一对可点击方块
map[pNode1->row][pNode1->col] = 0;
map[pNode2->row][pNode2->col] = 0;
CLICKINFO cInfo;
cInfo.row1 = pNode1->row;
cInfo.col1 = pNode1->col;
cInfo.row2 = pNode2->row;
cInfo.col2 = pNode2->col;
SendMessage(hwnd, WM_CLICKINFO_FIND, (WPARAM)pMyParams->bIsAutoClick, (LPARAM)(&cInfo));
RemoveNodeFromList(&pCellPos[i], pNode1);
RemoveNodeFromList(&pCellPos[i], pNode2);
bFind_One_Solution = TRUE;
break;
}
//由于两个Node都已经被释放了，所以必须立即结束对当前链表中的搜索。
if(bFind_One_Solution)
break;
pNode2 = pNode2->pNext;
}
if(bFind_One_Solution)
break;
pNode1 = pNode1->pNext;
}
}
}
//已经没有方块了？
if(bAllListIsNull)
{
//发送消息，所有解已经搜索完毕，游戏可以胜利清空所有方块
PostMessage(hwnd, WM_SOLUTION_COMPLETE, 0, 0);
break;
}
//对所有链表都搜索完毕了，但找不到解，需要重排！
else if(!bFind_One_Solution)
{
PostMessage(hwnd, WM_NEED_RERANGE, 0, 0);
break;
}
}
bThreadRunning = FALSE;
return 0;
}
最后这里的双向链表，还有队列等辅助数据结构当然都可以选用STL中的模板，而我没有用STL，此处全部是自写的。这样的好处可能就是非常直观吧，所有代码都在自己的眼皮底下，比较放心罢了。这里给出几个双向链表操作函数，实际上非常简单非常简短。
//释放某一个链表，最后把表头置为NULL
void FreeList(PCELLPOS* ppHead)
{
PCELLPOS pTmp = NULL;
PCELLPOS pNode = *ppHead;
while(pNode != NULL)
{
pTmp = pNode->pNext;
free(pNode);
pNode = pTmp;
}
(*ppHead) = NULL;
}
//把一个新节点挂接到指定链表上，如果链表为空，则会被创建！
void AddNodeToList(PCELLPOS* ppHead, int row, int col)
{
PCELLPOS pNewNode = (PCELLPOS)malloc(sizeof(CELLPOS));
pNewNode->row = row;
pNewNode->col = col;
pNewNode->pForward = NULL;
pNewNode->pNext = NULL;
if(*ppHead == NULL)
{
*ppHead = pNewNode;
return;
}
else
{
//找到tail节点，然后挂接上去！
PCELLPOS pCur = *ppHead;
while(pCur->pNext != NULL)
pCur = pCur->pNext;
pNewNode->pForward = pCur;
pCur->pNext = pNewNode;
}
}
//从链表中把指定的节点除去，如果是最后一个节点，则会导致该链表被置为 NULL
void RemoveNodeFromList(PCELLPOS* ppHead, PCELLPOS pNode)
{
//是表头吗
if(pNode == *ppHead)
{
*ppHead = pNode->pNext;
}
// [Forward] <--> [X] <--> [Next]
// [Forward] <-----------> [Next]
if(pNode->pForward != NULL)
pNode->pForward->pNext = pNode->pNext;
if(pNode->pNext != NULL)
pNode->pNext->pForward = pNode->pForward;
free(pNode);
}
其中，提示可点击方块时，没有直接用窗口 DC 或者屏幕 DC，我用的是 SetWindowRgn 方法（如果用 LayeredWindow 的 COLOR_KEY 会有闪烁，所以改为用 Window RGN）。
最后，暂时发布工具的可执行文件，该工具是采用VS2005 + WIN32 Platform SDK开发，完全绿色的。但它在关闭的时候会在自身所在文件夹下面防止一个 INI 配置文件，实际上我在程序里已经写好了所有默认值，但把 INI 文件放在程序所在位置，也是为了让用户知道那些地方可以配置。但有一项我写死在代码里面了，就是方块样本集合位图的行容量固定为 8，这样的目的是我可以对除法和取余（MOD）用位操作来实现。
下载链接：http://files.cnblogs.com/hoodlum1980/LLKHelper.rar
相同性质文章：《快速“美女找茬”（辅助工具）》
【补充说明】 by hoodlum1980 @ 2011-11-20
我发现有些人在肆无忌惮的使用“秒杀”级别的疑似外挂。所以也促使我进行改进。主要是加了系统全局性热键，程序自身的快捷键（因为按键的反应速度要比鼠标点击快），在比拼秒杀速度的时候取消开启线程，而是合并到 UI 线程一次性完成。改进搜索解的循环方式，从每次复位改为轮转式。最终我发现实际上成了反应速度的比拼。假使秒杀耗时是 0.1 秒（具体到底多少可能也无法精确测量），那么如果谁反应速度稍微快 0.1 秒，先行启动，就会赢。所以同为秒杀速度，由于秒杀耗时极短，远小于人能观察出的时间间隔，所以在算法上可能已经很难拼出优势来了。比如从其他方向下手进行改进。当然我也考虑了自动对别人应用各种障碍型道具，但是如果起跑反应慢一点的话，实际上一切都没用，因为你根本不会有应用道具的时间，游戏已经被对方结束了。反正已经够快了，估计暂时就这样了~。~