JavaScript连连看核心算法与实现源码解析

JavaScript连连看核心算法与实现源码解析

闲暇之余，笔者编写了一款JavaScript连连看游戏。代码注释详尽，适合希望深入理解此类游戏逻辑的开发者参考学习。

连连看游戏的核心难点在于路径搜索，即判断用户点击的两个方块之间是否存在合法连通路径。此前见过基于递归的实现方式，笔者尝试探索非递归的解决方案，发现其实现难度同样可控。

路径搜索策略遵循由简入繁的原则：首先判断两点是否在同一直线上且可直接连通；其次分析两点通过两个拐角是否连通；最后处理不在同一直线上的复杂情况。

该代码已在IE6、IE8以及Firefox 3.0.3浏览器环境下完成测试，兼容性良好。

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>JS连连看源码完美注释版</title>
</head>
<style>
table{
border-collapse: collapse;
 }
td{
border: solid #ccc 1px;
height: 36px;
width: 36px;
cursor: pointer;
 }
td img{
height: 30px;
width: 30px;
border: solid #fff 3px;
   /*
filter: alpha(opacity=80);
-moz-opacity: 0.8;
opacity: 0.8;
   */
 }
</style>
<script>
//以下部分为路径搜索算法部分,与表现层无关
//全局变量
var X = 16;//总行数
var Y = 14;//总列数
var types = 15;//图形种类
//布局矩阵
//为了算法方便，矩阵的第一行，第一列，最后一行，最后一列都标注为0，天然通路。
var arr = new Array(Y);
var tbl;//显示布局的table元素
var p1 = null;//搜索路径用的第1个点的坐标
var p2 = null;//搜索路径用的第2个点的坐标
var e1 = null;//第1个点对应的元素
var e2 = null;//第2个点对应的元素
//路径搜索，给出两个点，搜索出通路
//通路用可连通的点表示
function getPath(p1, p2){
 //开始搜索前对p1,p2排序，使p2尽可能的在p1的右下方。
 //这样做可以简化算法
 if(p1.x>p2.x){
 var t = p1; 
 p1 = p2;
 p2 = t; 
 }
 else if(p1.x==p2.x){
 if(p1.y>p2.y){
 var t = p1; 
 p1 = p2;
 p2 = t; 
 }
 }
 //通过分析连连看中两点之间的位置关系，逐步由简到难分析每一种类型
 //第一种类型， 两点是否在一条直线上，而且两点之间可直线连通
 if((onlineY(p1, p2)||onlineX(p1, p2)) && hasLine(p1, p2)){
 status = 'type 1';
 return [p1,p2];
 }
 //第二种类型， 如果两点中任何一个点被全包围，则不通。
 if( !isEmpty({x:p1.x, y:p1.y+1}) && !isEmpty({x:p1.x, y:p1.y-1}) && !isEmpty({x:p1.x-1, y:p1.y}) && !isEmpty({x:p1.x+1, y:p1.y}) ){
 status = 'type 2';
 return null;
 }
 if( !isEmpty({x:p2.x, y:p2.y+1}) && !isEmpty({x:p2.x, y:p2.y-1}) && !isEmpty({x:p2.x-1, y:p2.y}) && !isEmpty({x:p2.x+1, y:p2.y}) ){
 status = 'type 2';
 return null;
 }
 //第三种类型， 两点在一条直线上，但是不能直线连接
 var pt0, pt1, pt2, pt3;
 //如果都在x轴，则自左至右扫描可能的路径，
 //每次构造4个顶点pt0, pt1, pt2, pt3，然后看他们两两之间是否连通
 if(onlineX(p1, p2)){
 for(var i=0; i<Y; i++){
 if(i==p1.y){
 continue;
 }
 pt0 = p1;
 pt1 = {x: p1.x, y: i};
 pt2 = {x: p2.x, y: i};
 pt3 = p2;
 //如果顶点不为空，则该路不通。
 if(!isEmpty(pt1) || !isEmpty(pt2)){
 continue;
 }
 if( hasLine(pt0, pt1) && hasLine(pt1, pt2) && hasLine(pt2, pt3) ){
 status = '(x:' + pt0.x + ',y:' + pt0.y + ')' + ', (x:' + pt1.x + ',y:' + pt1.y + ')' + ', (x:' + pt2.x + ',y:' + pt2.y + ')' + ', (x:' + pt3.x + ',y:' + pt3.y + ')';
 return [pt0, pt1, pt2, pt3];
 }
 }
 }
 //如果都在y轴，则自上至下扫描可能的路径，
 //每次构造4个顶点pt0, pt1, pt2, pt3，然后看他们两两之间是否连通
 if(onlineY(p1, p2)){
 for(var j=0; j<X; j++){
 if(j==p1.x){
 continue; 
 }
 pt0 = p1;
 pt1 = {x:j, y:p1.y};
 pt2 = {x:j, y:p2.y};
 pt3 = p2;
 //如果顶点不为空，则该路不通。
 if(!isEmpty(pt1) || !isEmpty(pt2)){
 continue;
 }
 if( hasLine(pt0, pt1) && hasLine(pt1, pt2) && hasLine(pt2, pt3) ){
 status = '(x:' + pt0.x + ',y:' + pt0.y + ')' + ', (x:' + pt1.x + ',y:' + pt1.y + ')' + ', (x:' + pt2.x + ',y:' + pt2.y + ')' + ', (x:' + pt3.x + ',y:' + pt3.y + ')';
 return [pt0, pt1, pt2, pt3];
 }
 }
 }
 //第四种类型， 两点不在一条直线上。
 //先纵向扫描可能的路径
 //同样，每次构造4个顶点，看是否可通
 for(var k=0; k<Y; k++){
 pt0 = p1;
 pt1 = {x:p1.x, y:k};
 pt2 = {x:p2.x, y:k};
 pt3 = p2;
 status = '(x:' + pt0.x + ',y:' + pt0.y + ')' + ', (x:' + pt1.x + ',y:' + pt1.y + ')' + ', (x:' + pt2.x + ',y:' + pt2.y + ')' + ', (x:' + pt3.x + ',y:' + pt3.y + ')';
 //特殊情况，如果pt0和pt1重合
 if(equal(pt0,pt1)){
 //如果pt2不为空，则此路不通
 if(!isEmpty(pt2)){
 continue;
 }
 if( hasLine(pt1, pt2) && hasLine(pt2, pt3) ){
 return [pt1, pt2, pt3];
 }
 else{
 continue;
 }
 }
 //特殊情况，如果pt2和pt3重合
 else if(equal(pt2,pt3)){
 //如果pt1不为空，则此路不通
 if(!isEmpty(pt1)){
 continue;
 }
 if( hasLine(pt0, pt1) && hasLine(pt1, pt2) ){
 return [pt0, pt1, pt2];
 }
 else{
 continue;
 }
 }
 //如果pt1, pt2都不为空,则不通
 if(!isEmpty(pt1) || !isEmpty(pt2)){
 continue;
 }
 if( hasLine(pt0, pt1) && hasLine(pt1, pt2) && hasLine(pt2, pt3) ){
 return [pt0, pt1, pt2, pt3];
 }
 }
 //横向扫描可能的路径
 for(var k=0; k<X; k++){
 pt0 = p1;
 pt1 = {x:k, y:p1.y};
 pt2 = {x:k, y:p2.y};
 pt3 = p2;
 status = '(x:' + pt0.x + ',y:' + pt0.y + ')' + ', (x:' + pt1.x + ',y:' + pt1.y + ')' + ', (x:' + pt2.x + ',y:' + pt2.y + ')' + ', (x:' + pt3.x + ',y:' + pt3.y + ')';
 if(equal(pt0,pt1)){
 if(!isEmpty(pt2)){
 continue;
 }
 if( hasLine(pt1, pt2) && hasLine(pt2, pt3) ){
 return [pt1, pt2, pt3];
 }
 }
 if(equal(pt2,pt3)){
 if(!isEmpty(pt1)){
 continue;
 }
 if( hasLine(pt0, pt1) && hasLine(pt1, pt2) ){
 return [pt0, pt1, pt2];
 }
 }
 if(!isEmpty(pt1) || !isEmpty(pt2)){
 continue;
 }
 if( hasLine(pt0, pt1) && hasLine(pt1, pt2) && hasLine(pt2, pt3) ){
 return [pt0, pt1, pt2, pt3];
 }
 }
 //status='type4';
 return null;
 /********** end type 4 **************/
}
function equal(p1, p2){
 return ((p1.x==p2.x)&&(p1.y==p2.y));
}
function onlineX(p1, p2){
 return p1.y==p2.y;
}
function onlineY(p1, p2){
 return p1.x==p2.x; 
}
function isEmpty(p){
 return (arr[p.y][p.x]==0); 
}
function hasLine(p1, p2){
 if(p1.x==p2.x&&p1.y==p2.y){
 return true; 
 }
 if(onlineY(p1, p2)){
 var i = p1.y>p2.y?p2.y:p1.y;
 i = i+1;
 var max = p1.y>p2.y?p1.y:p2.y;
 for(; i<max; i++){
 var p = {x: p1.x, y: i};
 if(!isEmpty(p)){
 break
 }
 }
 if(i==max){
 return true;
 }
 return false;
 }
 else if(onlineX(p1, p2)){
 var j = p1.x>p2.x?p2.x:p1.x;
 j = j+1;
 var max = p1.x>p2.x?p1.x:p2.x;
 for(; j<max; j++){
 var p = {x: j, y: p1.y};
 if(!isEmpty(p)){
 break
 }
 }
 if(j==max){
 return true;
 }
 return false;
 }
}
//以下部分为表现层部分,包括绘图, 初始化矩阵, 绑定鼠标事件...
function $(id){return document.getElementById(id)}
var t1, t2;//测试用
//图片基路径
var IMG_PATH = 'https://www.jb51.net';
//初始化
function init(){
 //构造图片库
 var imgs = new Array(30);
 for(var i=1; i<=30; i++){
 imgs[i] = 'r_' + i + '.gif';
 }
 tbl = $('tbl');
 //构造table
 for(var row=0;row<Y-2;row++){
 var tr=tbl.insertRow(-1);
 for(var col=0;col<X-2;col++) {
 var td=tr.insertCell(-1);
 }
 }
 //构造矩阵
 for(var i=0; i<Y; i++){
 arr[i] = new Array(X);
 for(var j=0; j<X; j++){
 arr[i][j] = 0;
 }
 }
 var total = (X-2)*(Y-2);
 var tmp = new Array(total);//产生随机位置用
 for(var i=0; i<total; i++){
 tmp[i] = 0;
 }
 for(var i=0; i<total; i++){
 if(tmp[i]==0){
 var t = Math.floor(Math.random()*types) + 1;
 tmp[i] = t;
 while(true){
 var c = Math.floor(Math.random()*(total-i)) + i;
 if(tmp[c]==0){
 tmp[c] = t;
 break;
 }
 }
 }
 }
 var c = 0;
 for(var i=1; i<Y-1; i++){
 for(var j=1; j<X-1; j++){
 arr[i][j] = tmp[c++];
 tbl.rows[i-1].cells[j-1].innerHTML = '<img src="' + IMG_PATH + imgs[arr[i][j]] + '" />';
 } 
 }
 //绑定鼠标事件
 var img1, img2;
 document.body.onclick = function(e){
 var el = document.all?event.srcElement:e.target;
 if(el.parentNode.tagName!='TD'){
 return;
 }
 if(!img1){
 img1 = el;
 }
 else{
 img2 = el;
 }
 el.style.border = 'solid #3399FF 3px';
 el = el.parentNode;
 if(el.innerHTML==''){
 p1 = p2 = e1 = e2 = null;
 }
 var r = el.parentNode.rowIndex +1;
 var c = el.cellIndex +1;
 if(p1==null){
 //el.childNodes[0].style.border = 'solid #ccc 3px';
 p1 = {x:c, y:r};
 e1 = el;
 }
 else{
 p2 = {x:c, y:r};
 e2 = el;
 if(!equal(p1, p2)&&e1.innerHTML==el.innerHTML){
 var path = getPath(p1, p2);
 if(path!=null){
 e1.innerHTML = e2.innerHTML = '';
 arr[p1.y][p1.x] = arr[p2.y][p2.x] = 0;
 }
 }
 if(t1){t1.style.backgroundColor = '';}
 t1 = e1;
 if(t2){t2.style.backgroundColor = '';}
 t2 = e2;
 img1.style.border = 'solid #fff 3px';
 img2.style.border = 'solid #fff 3px';
 p1 = p2 = e1 = e2 = img1 = img2 = null;
 t1.style.backgroundColor = t2.style.backgroundColor = 'lightpink';
 }
 }
}
</script>
<body onload="init();">
 js连连看完美注释版<br />
 <table id="tbl" cellspacing="0" cellpadding="0" border="1">
 </table>
</body>
</html>