javascript 解一笔画游戏

布满荆棘的人生 2022-09-20 09:12 130阅读 0赞

偶然玩到这个游戏，十几关过去后就比较头疼了，于是写了个解题程序。。。

分析游戏：

游戏由 点、线（点与点之间的关系）构成。规则：不能走重复路径；所有线走完则过关。

解题方式是递归遍历所有路径，暴力破解一样。

思路：

两个类 Pointer、Line。

Pointer属性：no编号，orientations方向（数组，所有与点连接的点编号），equals（）比较节点是否为同一个节点。

Line属性：p1编号小的点，p2编号大的点。

使用多线程以每个节点为初始点开始递归遍历，走一步删除走过的线，某节点遍历完仍无解则还原被删除的线。解题成功则修改全局变量PATH，如果有其它线程解题成功（PATH非空）则直接returne，直至退出当前线程。

代码：

//点
    function Pointer(no, orientation) {
    	if (isNaN(no) || typeof orientation != 'string' || orientation == "") {
    		console.info("no:" + no  + "    orientation:" + orientation);
    		throw new Error("非法参数");
    	};
    
    	this.no = no;
    	this.orientations = orientation.split(',').sort(function(a, b) {
    		if (parseInt(a) > parseInt(b)) {
    			return 1;
    		} else if (parseInt(a) < parseInt(b)) {
    			return -1;
    		} else {
    			return 0;
    		}
    	});
    	this.oriStr = this.orientations.toString();
    
    	this.equals = function(obj) {
    		if (!(obj instanceof Pointer)) {
    			return false;
    		}
    		if (this.no == obj.no && this.oriStr == obj.oriStr) {
    			return true;
    		} else {
    			return false;
    		}
    	};
    }

//线
    function Line(p1, p2) {
    	//参数为点，且不能为同一个点
    	if (!(p1 instanceof Pointer) || !(p2 instanceof Pointer) || p1.equals(p2)) {
    		console.info("p1:" + p1.no + "    p2:" + p2.no);
    		throw new Error("错误，节点不能指向自身！节点编号:" + p1.no);
    	};
    
    	//线的属性两个点　p1,p2赋值
    	p1.no > p2.no ? (this.p1 = p2, this.p2 = p1) : (this.p1 = p1, this.p2 = p2);
    
    	this.equals = function(obj) {
    		if (!(obj instanceof Line)) {
    			return false;
    		}
    		if (this.p1.equals(obj.p1) && this.p2.equals(obj.p2)) {
    			return true;
    		} else {
    			return false;
    		}
    
    	};
    }

如果分支很多，第一个节点就错误的话耗时相当长，所以遍历时使用了多线程，引入Concurrent.Thread框架，使用方式请百度，我也第一次用。本来直接用setTimeout，因为js多线程是模拟的，setTimeout执行的函数如果很吃CPU的话，后面的setTimeout照样阻塞，还是大神写的框架好用，一下就解决了。为什么初始节点下无解会那么慢（无敌版几个小时），初始节点下有解那么快（<1s）？我也没搞懂，差距也太大了吧。。。断点看了简单版所有流程，没啥异常。有大神看破了的话，请指点迷津。

//计算求解
    function calculate(ptrArr, lineArr) {
    	
    	for (var i = 0; i < ptrArr.length; i ++) {
    		Concurrent.Thread.create(pathFinding, ptrArr[i], ptrArr, lineArr.slice(0));
    	}
    
    	return "";
    }

//寻路   
    function pathFinding(p, ptrArr, lineArr) {
    	var rs = p.no + "->";
    	// console.info(rs);
    
    	var orientations = p.orientations;
    	//临时路径，寻路错误时还原
    	var tmpLineArr = lineArr.slice(0);
    	for (var i = 0; i < orientations.length; i ++) {
    		var p2 = getPointerInArray(orientations[i], ptrArr);
    		if (p2 == null) {
    			return "";
    		}
    		var l = new Line(p, p2);
    		var index = lineIndexOf(l, tmpLineArr);
    		//线不存在　已被走过
    		if (index == -1) {
    			continue;
    		}
    		// console.info(tmpLineArr[index]);
    		//经过的线段删除
    		tmpLineArr.splice(index, 1);
    		//如果线　全部走完　则解题成功
    		if (tmpLineArr.length == 0) {
    			return rs + p2.no + "|";
    		}
    
    		//递归　下一个点的所有分支
    		var tmpRs = pathFinding(p2, ptrArr, tmpLineArr);
    		if (tmpRs.substr(-1) == "|") {
    			//如果数组长度等于初始长度　说明这是递归最外一层　解题成功
    			if (lineArr.length == LINE_COUNT) {
    				PATH = rs + tmpRs;
    				// document.write(PATH);
    			}
    
    			return rs + tmpRs;
    		} else if (tmpRs == "*") {
    			return "*";
    		}
    
    		//其他线程解题成功　该线程终止
    		if (PATH != "") {
    			return "*";
    		}
    
    		//如果是节点最后一个分支　不做无谓的还原
    		if (tmpLineArr.length < lineArr.length && i < orientations.length - 1) {
    			//还原点
    			// console.info("r2: tmpArrLength=" + tmpLineArr.length + "; lineArrLength=" + lineArr.length);
    			tmpLineArr = lineArr.slice(0);
    		}
    	}
    
    	return "";
    }

注释还是很详细滴~

界面、输入校验还不够完善，懒得搞了，喜欢折腾的自己去弄吧。

算法或实现方式有建议的请赐教。

图：

![SouthEast][]

![Image 1][]

请使用chrome/firefox，使用低版本ie需注释console.info().

![Image 1][]

游戏地址：[http://www.4399.com/flash/97076.htm][http_www.4399.com_flash_97076.htm]。无敌版最后关卡已通过测试。

下载地址：[http://download.csdn.net/detail/lj745280746/6826219][http_download.csdn.net_detail_lj745280746_6826219].

[SouthEast]: /images/20220828/0dc868e60eac4b4e87e9fb59466c19eb.png
[Image 1]: 
[http_www.4399.com_flash_97076.htm]: http://www.4399.com/flash/97076.htm
[http_download.csdn.net_detail_lj745280746_6826219]: http://download.csdn.net/detail/lj745280746/6826219