关于《连连看》的算法的详细介绍
关于《连连看》的算法的详细介绍
|
|
|
|
日期:2004-10-13 人气: 151 出处:闪吧 作者: orchin |
连连看所要求的是: 1:两个目标是相同的 2:两个目标之间连接线的折点不超过两个。(连接线由x轴和y轴的平行线组成) 那么分析一下连接的情况可以看到,一般分三种情况 1:直线相连 2:一个折点 3:两个折点 如图: 可以发现,如果有折点,每个折点必定有且至少有一个坐标(x或者y)是和其中一个目标点是相同的,也就是说,折点必定在两个目标点所在的x方向或y方向的直线上。 所以设计思路就是: 假设目标点 p1 , p2 ,如果有两个折点分别为z1 , z2 那么,所要进行的是 1:如果验证p1 , p2 直线连线,则连接成立 2:搜索以p1,p2的x,y方向四条直线(可能某两条直线会重合)上的有限点,每次取两点作为z1,z2 ,验证p1到z1/z1到z2/z2到p2 是否都能直线相连 ,是则连接成立。(如果z1=z2也就是只有一个折点喽,对判断没影响) 那么程序算法上,这里先就理论进行一个试验
var mmap=new Array();
这个是上面这几个函数的测试源码mmap[0]=new Array(0,0,0,0,0,0); mmap[1]=new Array(0,1,2,8,1,0); mmap[2]=new Array(0,5,5,4,3,0); mmap[3]=new Array(0,4,6,7,3,0); mmap[4]=new Array(0,8,2,6,7,0); mmap[5]=new Array(0,0,0,0,0,0); p1=new Array(1,4); p2=new Array(1,2); //定义一个二维数组作为游戏的映像,相同的数字代表相同的图标,0是空处,p1,p2是选择的点 linelink=function(o1,o2){ var t=new Array(0,0); if(o1[0]==o2[0] || o1[1]==o2[1]){ if(Math.abs(o1[0]-o2[0])+Math.abs(o1[1]-o2[1])<=1){ return true; }else{ t[0]=isNaN((o2[0]-o1[0])/Math.abs(o2[0]-o1[0])) ? o1[0] : o1[0]+((o2[0]-o1[0])/Math.abs(o2[0]-o1[0])); t[1]=isNaN((o2[1]-o1[1])/Math.abs(o2[1]-o1[1])) ? o1[1] : o1[1]+((o2[1]-o1[1])/Math.abs(o2[1]-o1[1])); return mmap[t[0]][t[1]]==0 ? linelink(t,o2) : false } }else{ return false; } } // 上面这个函数是判断任意两个点是否能直线连接(中间的点全为0) var parr=new Array(); pickpoint=function(q1,q2){ var j; parr.splice(0); for(j=0;j<mmap[q1[0]].length;j++){ parr=mmap[q1[0]][j]==0?parr.concat([[q1[0],j]]):parr; } for(j=0;j<mmap[q2[0]].length;j++){ parr=mmap[q2[0]][j]==0?parr.concat([[q2[0],j]]):parr; } for(j=0;j<mmap.length;j++){ parr=mmap[j][q1[1]]==0?parr.concat([[j,q1[1]]]):parr; } for(j=0;j<mmap.length;j++){ parr=mmap[j][q2[1]]==0?parr.concat([[j,q2[1]]]):parr; } } //上面这个函数是取出两个点的x和y直线方向上的所有空点保存进parr这个数组里面待搜索 islink=function(p1,p2){ var i,j if(p1==p2){ return false; } if(mmap[p1[0]][p1[1]]<>mmap[p2[0]][p2[1]]){ return false; } if(linelink(p1,p2)){ return true; }else{ for(i=0;i<parr.length;i++){ for(j=0;j<parr.length;j++){ if(linelink(p1,parr[i]) && linelink(p2,parr[j]) && linelink(parr[i],parr[j])) { trace(parr[i]+"->"+parr[j]); return true;} } } } return false; } //上面这个函数是校验两个目标点是否相连, //先判断是否同类点,再判断是否直线相连,最后搜索parr里的每对折点是否使目标点相连 pickpoint(p1,p2); //取得parr数组 trace(islink(p1,p2)); //测试p1,p2是否相连 嘿,运行试试? 点击浏览该文件 根据这个原理,把图标对照数组,动态建立数组,加上一些效果啊,鼠标检测啊,就成了下面这个这样的基本《连连看》游戏模块啦 点击浏览该文件 这个是作成游戏后的源码 点击浏览该文件 |