首页
社区
课程
招聘
[原创][讨论]连连看外挂寻路算法
发表于: 2013-10-18 15:09 13048

[原创][讨论]连连看外挂寻路算法

2013-10-18 15:09
13048

最近心情不太好,就想发泄一下,于是qq连连看就成了我的目标(能不能不要在意这些细节。。。),然后就搞了个秒杀外挂。外挂好搞,今天主要是来讨论一下连连看的寻路算法。
正文开始。连连看这游戏的规则就是两个相同的棋子之间的连线不能超过2折,如图所示:



这其实意味着两颗棋子间的所有可能连通路径都被限制在了以这两个棋子为交叉点的一个#字中,如图:



空心圆表示没有棋子,黑色实心圆表示有棋子,而两个红色棋子的所有可能的连通路径都在这个“#”字中,因为一旦路径中有一点在“#”字之外,路径必会超过2折。
这样范围就缩小了,然后单看纵向:



在这张图中我用颜色标示出了两个红色棋子在自己那一列的纵向上的可连通区域(黄色和绿色),其中绿色是两颗棋子的可连通区域的交集,不难发现,如果绿色区域上的两个格子(同一行)没有障碍可连通则寻路成功,横向同理(你自己把图横过来看 = =)
所以寻路算法的思路也就明晰了:
1、在纵(横)向上分别找两颗棋子的可连通区域A1、A2
2、A1、A2取交集A
3、判断A中是否有可连通路径
下面上代码,代码比较渣,大家莫笑


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

上传的附件:
收藏
免费 5
支持
分享
最新回复 (10)
雪    币: 351
活跃值: (80)
能力值: ( LV9,RANK:210 )
在线值:
发帖
回帖
粉丝
2
无非就是搜索。。。DFS和BFS都可以搞。。
2013-10-18 15:13
0
雪    币: 118
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
3
寻路算法是设计游戏干的活。
外挂就是要找那个放大镜的callback
啪啪啪啪啪 世界就清静了
2013-10-18 18:18
0
雪    币: 14
活跃值: (88)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
经典“连你个毛线”。顶楼主!!
2013-10-18 19:31
0
雪    币: 124
活跃值: (469)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
5
int check_2p(int x1,int y1,int x2,int y2){
       
        int y,x,k;
    int line1=0,line2=0,line3=0;//连同与否的标志
        //在y轴方向上是否存在连同
        for(y=0;y<11&&(x1!=x2);y++){
                //y1=y2
                line1=1;
                for(k=(y<y1?y:y1)+1;k<(y<y1?y1:y)&&y!=y1;k++)
                        if(image[k][x1]!=0){
                                line1=0;
                                break;
                        }
                        if(image[y][x1]!=0&&y!=y1)        line1=0;
                       
                        line2=1;
                        for(k=(y<y2?y:y2)+1;k<(y<y2?y2:y)&&y!=y2&&line1;k++)
                                if(image[k][x2]!=0){
                                        line2=0;
                                        break;
                                       
                                }
                                if(image[y][x2]!=0&&y!=y2)        line1=0;
                               
                                line3=1;
                                for(k=(x1<x2?x1:x2)+1;k<(x1<x2?x2:x1)&&line1&&line2;k++)
                                        if(image[y][k]!=0){
                                                line3=0;
                                                break;
                                        }
                                        if(line1&&line2&&line3){
                                                return line1&&line2&&line3;
                                        }
                                       
        }
        //在x轴方向上是否存在连同
        for(x=0;x<19&&(y1!=y2);x++){
               
                line1=1;
                for(k=(x<x1?x:x1)+1;k<(x<x1?x1:x)&&x!=x1;k++)
                        if(image[y1][k]!=0){
                                line1=0;
                                break;
                        }
                       
                        if(image[y1][x]!=0&&x!=x1)        line1=0;
                       
                        line2=1;
                        for(k=(x<x2?x:x2)+1;k<(x<x2?x2:x)&&line1&&x!=x2;k++)
                                if(image[y2][k]!=0){
                                        line2=0;
                                        break;
                                }
                               
                                if(image[y2][x]!=0&&x!=x2)        line2=0;
                               
                                line3=1;
                                for(k=(y1<y2?y1:y2)+1;k<(y1<y2?y2:y1)&&line1&&line2;k++)
                                        if(image[k][x]!=0){
                                                line3=0;
                                                break;
                                        }
                                       
                                        if(line1&&line2&&line3){
                                                return line1&&line2&&line3;
                                        }
        }
        return 0;
       
}
2013-10-19 09:07
0
雪    币: 55
活跃值: (519)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
6
围观.坐等加精.
2013-10-19 09:30
0
雪    币: 110
活跃值: (34)
能力值: (RANK:50 )
在线值:
发帖
回帖
粉丝
7
回溯一下暴力解决……
2013-10-19 15:34
0
雪    币: 54
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
厉害。。。。。
2013-10-19 15:45
0
雪    币: 238
活跃值: (55)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
9
代码高亮还是不错的,高效的话能不能直接调用胜利的call呢,不要在意这些细节。。。
2013-10-19 20:33
0
雪    币: 18
活跃值: (81)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
10
确实可行
2013-10-19 20:43
0
雪    币: 39
活跃值: (51)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
11
好牛逼的样子
2014-4-28 12:55
0
游客
登录 | 注册 方可回帖
返回
//