连连看外挂“连通检测”算法
最近出于兴趣,我做了一个QQ连连看的外挂,可以自动分析图案,在游戏窗口上作出图案提示和模拟连线,然后还是需要用户根据提示进行点击。本来想模拟鼠标直接点击,但是该版本游戏客户端对模拟鼠标消息好像有什么干扰,找了一下午还是没有搞明白,所以就先做到此了,如果真的模拟鼠标了,那可成了真的外挂了,当心公司找我麻烦。
这类外挂算是游戏外挂中的一种,而且我觉得算是比较文明的一种,因为它还是建立在游戏规则之上,只是用程序来模仿玩家的操作,发挥程序的操作速度。整个外挂的运行过程就是获取游戏窗口句柄,定位游戏窗口区域,按照一定规则和比例提取图片某些像素的颜色,分析图片进行分组,判断相同的图案是否可以连通(连连看要求连线不超过2个弯角),提示用户。

由于外挂程序只是出于我个人兴趣,所以程序和源代码我不在此发布,但是对于核心的连连看“连通”算法,我想拿出来与大家分享,如果大家有什么好的建议可以告诉我。
在图案分析成功之后,可以看到上图中的外挂程序LLK,已经将连连看游戏窗口中的图案按照编号保存在了 short map[11][19] 中,其中背景区域为0,相同的图片为相同的值,分析过程比较简单,这里就不多说了。
接下来,就是测试任意两个相同图案是否可以连通,连通规则是两个图案之间的连接线不能超过2个弯角。开始我想了回溯、递归等经典算法,但是考虑到这里的图片太多了,而且两个图案之间并不关心具体的路径,所以不需要用迷宫算法。应该存在一种符合某种规律的连线,可以适应普遍情况,要找出这个规律,最好的办法还是从玩游戏中逐渐体会,于是我带着问题参加到游戏竞赛中,加上这段时间老要进去测试程序,我的连连看分数已经-1000多分了,看来写好外挂后要还是有用武之地的呵呵~!
精细仔细观察后,我发现可以连通的两个图案之间,总是存在一条横的或者竖的线段,使得这条线段上没有图案,并且两个图案到这条线段的两个端点也没有图案,真是这个规律,将判断两个任意相同图案的思路变得简单了很多,这便是以下的函数实现的功能,形象地说,便是分别从Y轴和X轴进行扫描,寻找两个图案的连线。而以前的思路是从一个图案出发,去搜索另一个图案,或者知道另一个图案的坐标,去搜索路径看是否到达,显然后者效率要低得多。
最近评论