cocos2d-js版本A*算法

前端之家收集整理的这篇文章主要介绍了cocos2d-js版本A*算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

A*算法的东西网上讲了很多~但还是不可避免的要去研究一下,cocos官网上有一个cocos2dx版本的A星算法(cocos2d-x A星算法),正好拿来改造一下,顺便踩踩cocos2d-js的坑

原理和伪代码部分可以参考这个(A*算法伪代码)废话不多说,直接上正题.

主要有2个封装原型类:

1、GameLayer:负责加载地图、保持地图跟随、坐标转换、地图上物品判断、接受触控事件

var GameLayer = cc.Layer.extend({
    _tileMap:null,_bgLayer:null,_objectLayer:null,_batchNode:null,_cat:null,bonesCount:null,ctor:function () {
        // ////////////////////////////
        // 1. super init first
	    this._super();
	    // 加载地图
	    this._tileMap = new cc.TMXTiledMap(res.CatMaze_tmx);
	    this._bgLayer = this._tileMap.getLayer("Background");
	    this._objectLayer = this._tileMap.getLayer("Objects");
	    this.addChild(this._tileMap);
	    
	    // 25*25 tiles
	    cc.log("map size width:"+this._tileMap.getMapSize().width+"		height:	"+this._tileMap.getMapSize().height);
	    
	    // tile size: 32*32
	    cc.log("tile size width:"+this._tileMap.getTileSize().width+"		height:	"+this._tileMap.getTileSize().height);
	    
	    // tile坐标
	    var spawnTileCoord = cc.p(24,0);
	    var spawnPos = this.positionForTileCoord(spawnTileCoord);
	    
	    // 视角跟随
	    this.setViewpointCenter(spawnPos);
	    // 背景音乐
	    cc.audioEngine.playMusic(res.SuddenDefeat_mp3,true);

	    cc.spriteFrameCache.addSpriteFrames(res.CatMaze_plist);
	    
	    //存放在地图上面~则会跟随地图
	    this._batchNode = new cc.SpriteBatchNode(res.CatMaze_png);
	    this._tileMap.addChild(this._batchNode);
	    
	    this._cat = new CatSprite(this);
	    this._cat.setPosition(spawnPos);
	    this._batchNode.addChild(this._cat);
	    
	    // bmfont 字体
	    this.bonesCount = new cc.LabelBMFont("Bones: 0",res.Arial_fnt);
	    this.bonesCount.setPosition(400,30);
	    this.addChild(this.bonesCount);
	    
	    cc.eventManager.addListener({
	    		event: cc.EventListener.TOUCH_ONE_BY_ONE,swallowTouches: true,onTouchBegan:function (touch,event) {
	    			// 猫移动向该点
	    			var point = event.getCurrentTarget()._tileMap.convertTouchToNodeSpace(touch);
	    			cc.log("touch point x:	"+point.x+"y:	"+point.y);
	    			event.getCurrentTarget()._cat.moveToward(point);
	    			return true;
	    		}
	    },this);
	    
	    this.scheduleUpdate();
        return true;
    },// 坐标转换为tile
    positionForTileCoord:function(p){
    	var x = (p.x * this._tileMap.getTileSize().width) + this._tileMap.getTileSize().width / 2;
    	var y = (this._tileMap.getMapSize().height *this. _tileMap.getTileSize().height) -
    	(p.y *this._tileMap.getTileSize().height) - this._tileMap.getTileSize().height / 2;
    	return cc.p(x,y);
    },// 地图跟随
    setViewpointCenter:function(position){
    	var size = cc.director.getWinSize();
    	var x = Math.max(position.x,size.width / 2);
    	var y = Math.max(position.y,size.height / 2);
    	x = Math.min(x,(this._tileMap.getMapSize().width * this._tileMap.getTileSize().width) - size.width / 2);
    	y = Math.min(y,(this._tileMap.getMapSize().height * this._tileMap.getTileSize().height) - size.height / 2);
    	var p = cc.p(x,y);
    	var center = cc.p(size.width/2,size.height/2);
    	var viewPoint = cc.pSub(center,p);

    	this._tileMap.setPosition(viewPoint);
    },update:function(){
    	this.setViewpointCenter(this._cat.getPosition());
    },tileCoordForPosition:function(position){
    	var x = parseInt( position.x / this._tileMap.getTileSize().width);
    	var y = parseInt(((this._tileMap.getMapSize().height *this._tileMap.getTileSize().height) - position.y) / this._tileMap.getTileSize().height);
    	return cc.p(x,//是否是墙壁
    isWallAtTileCoord:function(tileCoord){
    	return this.isPropAtTileCoordForLayer("Wall",tileCoord,this._bgLayer);
    },//显示骨头
    showNumBones:function(numBones)
    {
    	this.bonesCount.setString("Bones: "+ numBones);
    },isValidTileCoord:function(tileCoord){
    	if (tileCoord.x < 0 || tileCoord.y < 0 ||
    			tileCoord.x >= this._tileMap.getMapSize().width ||
    			tileCoord.y >= this._tileMap.getMapSize().height)
    	{
    		return false;
    	}
    	else
    	{
    		return true;
    	}
    },//是否有骨头
    isBoneAtTilecoord:function(tileCoord)
    {
    	//bone 存放在_objectLayer上
    	return this.isPropAtTileCoordForLayer("Bone",this._objectLayer);
    },//是否有狗
    isDogAtTilecoord:function(tileCoord) 
    {
    	return this.isPropAtTileCoordForLayer("Dog",//是否为出口
    isExitAtTilecoord:function(tileCoord) 
    {
    	return this.isPropAtTileCoordForLayer("Exit",//判断tile上存放了什么
    isPropAtTileCoordForLayer:function(prop,layer)
    {
    	if (!this.isValidTileCoord(tileCoord))
    	{
    		return false;
    	}
    	
    	//获得tile对应id
    	var gid = layer.getTileGIDAt(tileCoord);
    	
    	//这里返回的是dict类型
    	var properties = this._tileMap.getPropertiesForGID(gid);
    	if (properties==null)
    	{
    		return false;
    	}
    	return properties[prop]==1;
    },//移除tiles
    removeObjectAtTileCoord:function(tileCoord){
    	this._objectLayer.removeTileAt(tileCoord);
    },winGame:function(){
    	cc.log("win");
    	this.endScene();
    },loseGame:function(){
    	cc.log("lose");
    	this.endScene();
    },endScene:function()
    {
    	var self = this;
    	this._cat.runAction(cc.sequence( cc.scaleBy(0.5,3.0),cc.delayTime(1.0),cc.scaleTo(0.5,0.0),cc.callFunc(self.showRestartMenu,self)
    			));
    	this._cat.runAction(cc.repeatForever(cc.rotateBy(0.5,360.0)));
    },showRestartMenu:function(){
    	cc.log("showRestartMenu");
    },//是否可以通过
    walkableAdjacentTilesCoordForTileCoord:function(tileCoord){
    		var tmp = [];
    		// 上
    		var p1=cc.p(tileCoord.x,tileCoord.y - 1);
    		if (this.isValidTileCoord(p1) && !this.isWallAtTileCoord(p1)){
    			tmp.push(p1);
    		}
    		// 左
    		var p2=cc.p(tileCoord.x - 1,tileCoord.y);    		
    		if (this.isValidTileCoord(p2) && !this.isWallAtTileCoord(p2)){
    			tmp.push(p2);
    		}
    		// 下
    		var p3=cc.p(tileCoord.x,tileCoord.y + 1);    
    		if (this.isValidTileCoord(p3) && !this.isWallAtTileCoord(p3)){
    			tmp.push(p3);
    		}
    		// 右
    		var p4=cc.p(tileCoord.x + 1,tileCoord.y);    
    		if (this.isValidTileCoord(p4) && !this.isWallAtTileCoord(p4)){
    			tmp.push(p4);
    		}
    		cc.log("tileCoord: "+tileCoord.x+" "+tileCoord.y);
    		for(var i = 0;i<tmp.length;i++){
    			cc.log("tmp "+i+":	"+tmp[i].x+	"  "+tmp[i].y);
    		}
    		return tmp;
    }
});
2、CatSprite:负责A*算法实现、猫展示动画
var CatSprite = cc.Sprite.extend({
	_gameLayer:null,_facingForwardAnimation:null,_facingBackAnimation:null,_facingLeftAnimation:null,_facingRightAnimation:null,_bonenum:0,_shortestPath:[],//最短路径
	_spOpenSteps:[],//开放列表
	_spClosedSteps:[],//关闭列表
	_tempShortestPath:[],ctor:function(gameLayer){
		this._super("#cat_forward_1.png");
		this._gameLayer = gameLayer;

		this._facingForwardAnimation = this.createCatanimation("forward");
		
		this._facingBackAnimation = this.createCatanimation("back");
	
		this._facingLeftAnimation = this.createCatanimation("left");
		
		this._facingRightAnimation = this.createCatanimation("right");
			
		return true;
	},moveToward:function(target){
		cc.log("moveToward");
		var fromTileCoord = this._gameLayer.tileCoordForPosition(this.getPosition());
		var toTileCoord = this._gameLayer.tileCoordForPosition(target);
		
		if(toTileCoord.x == fromTileCoord.x&&toTileCoord.y==fromTileCoord.y){
			cc.log("You're already there! :P");
			return;
		}
		if(!this._gameLayer.isValidTileCoord(toTileCoord) ||this._gameLayer.isWallAtTileCoord(toTileCoord)){
			cc.audioEngine.playEffect(res.hitWall_wav);
			return;
		}
		cc.log("From:	" + fromTileCoord.x + "	"+ fromTileCoord.y);
		cc.log("To:	" + toTileCoord.x + "	"+ toTileCoord.y);
		
		this._spOpenSteps = [];
		this._spClosedSteps = [];
		// 首先,添加猫的方块坐标到open列表
		this.insertInOpenSteps(new ShortestPathStep(fromTileCoord));
		do{
			//这里要当心死循环		
			var currentStep = this._spOpenSteps[0];
			currentStep.retain();		
			cc.log("currentStep:"+currentStep.getPosition().x+"  "+currentStep.getPosition().y);
			// 添加当前步骤到closed列表
			this._spClosedSteps.push(currentStep);
			// 将它从open列表里面移除
			this._spOpenSteps.splice(0,1);
			// 如果当前步骤是目标方块坐标,那么就完成了
			if (toTileCoord.x == currentStep.x&&toTileCoord.y==currentStep.y){
				cc.log("path found");
				this.constructPathAndStartAnimationFromStep(currentStep);
				this._spOpenSteps = [];
				this._spClosedSteps = [];
				break;		
			}
			//this.printPath(currentStep);
			var adjSteps = this._gameLayer.walkableAdjacentTilesCoordForTileCoord(currentStep.getPosition());
			for (var i = 0; i < adjSteps.length; ++i){
				var step = new ShortestPathStep(adjSteps[i]);
				if (this.indexOf(this._spClosedSteps,step)!=-1){
			
					continue;
				}
				var moveCost = this.costToMoveFromStepToAdjacentStep(currentStep,step);
				var index = this.indexOf(this._spOpenSteps,step);
				if (index == -1){
					step.setParent(currentStep);
					step.setGscore(currentStep.getGscore() + moveCost);
					step.setHscore(this.computeHscoreFromCoordToCoord(step.getPosition(),toTileCoord));
					this.insertInOpenSteps(step);
				}else{
					step = this._spOpenSteps[index];
					if ((currentStep.getGscore() + moveCost) < step.getGscore()){
						step.setGscore(currentStep.getGscore() + moveCost);
						// 因为G值改变了,F值也会跟着改变
						// 所以为了保持open列表有序,需要将此步骤移除,再重新按序插入
						// 在移除之前,需要先保持引用
//						step.retain();
						// 现在可以放心移除,不用担心被释放
						this._spOpenSteps.splice(index,1);
//						// 重新按序插入
						this.insertInOpenSteps(step);
//						// 现在可以释放它了,因为open列表应该持有它
//						step.release();
					}
				}
			}
		}while (this._spOpenSteps.length > 0);

		for (var i = 0;i<this._shortestPath.length;i++){
			cc.log("Description:",this._shortestPath[i].getDescription());
		}		

	},//序列帧动画
	createCatanimation:function(animType)
	{
		var animation = new cc.Animation();
		for (var i = 1; i <= 2; ++i)
		{
			animation.addSpriteFrame(cc.spriteFrameCache.getSpriteFrame("cat_"+animType+"_"+i+".png"));
		}
		animation.setDelayPerUnit(0.2);
		animation.retain()
		return animation;
	},//用来判断step所在位置
	indexOf:function(array,step){
		if(array.length>0){
			for(var i = 0;i<array.length;i++){
				if(array[i].isEqual(step)){
					return i;
				}
			}
		}
		return -1;
	},//插入一个step  维护一个有序列表
	insertInOpenSteps:function(step)
	{
		var stepFscore = step.getFscore();
		var count = this._spOpenSteps.length;
		var i ;
		for (i = 0; i < count; ++i)
		{
			if (stepFscore <= this._spOpenSteps[i].getFscore())
			{
				break;
			}
		}

		this._spOpenSteps.splice(i,step);
	},//计算H值
	computeHscoreFromCoordToCoord:function(fromCoord,toCoord)
	{
		// 这里使用曼哈顿方法,计算从当前步骤到达目标步骤,在水平和垂直方向总的步数
		// 忽略了可能在路上的各种障碍
		return Math.abs(toCoord.x - fromCoord.x) +  Math.abs(toCoord.y - fromCoord.y);
	},//这里可以扩展~
	costToMoveFromStepToAdjacentStep:function(fromStep,toStep){
		//return ((fromStep->getPosition().x != toStep->getPosition().x)
		//	&& (fromStep->getPosition().y != toStep->getPosition().y)) ? 14 : 10;
		return 1;
	},//构造最短路径
	constructPathAndStartAnimationFromStep:function(step){
		this._shortestPath=[];
		do{
			// 起始位置不要进行添加
			if (step.getParent())
			{
				// 总是插入到索引0的位置,以便反转路径
				this._shortestPath.splice(0,step); 
			}
			step = step.getParent();   // 倒退
		} while (step);                 // 直到没有上一步
		for (var i = 0;i<this._shortestPath.length;i++){
			cc.log("Description:",this._shortestPath[i].getDescription());
		}
		this.popStepAndAnimate();
	},//打印路径
	printPath:function(step){
		this._tempShortestPath=[];
		do{
			// 起始位置不要进行添加
			if (step.getParent())
			{
				// 总是插入到索引0的位置,以便反转路径
				this._tempShortestPath.splice(0,step); 
			}
			step = step.getParent();   // 倒退
		} while (step);                 // 直到没有上一步
		for (var i = 0;i<this._tempShortestPath.length;i++){
			cc.log("Description:",this._tempShortestPath[i].getDescription());
		}
		cc.log("---------------------------------------------------------------------");
	},//展示运动
	popStepAndAnimate:function(){
		var currentPosition = this._gameLayer.tileCoordForPosition(this.getPosition());
		if(this._gameLayer.isBoneAtTilecoord(currentPosition)){
			this._bonenum++;
			this._gameLayer.showNumBones(this._bonenum);
			this._gameLayer.removeObjectAtTileCoord(currentPosition);
		}else if(this._gameLayer.isDogAtTilecoord(currentPosition)){
			if (this._bonenum <= 0){
				this._gameLayer.loseGame();
				return;
			}else{
				this._bonenum--;
				this._gameLayer.showNumBones(this._bonenum);
				this._gameLayer.removeObjectAtTileCoord(currentPosition);
			}
		}else if (this._gameLayer.isExitAtTilecoord(currentPosition)){
			this._gameLayer.winGame();
		}
		
		var  s = this._shortestPath[0];
		
		if(s==undefined){
			return;
		}
		s.retain();
		var futurePosition = s.getPosition();
	
		var diff = cc.pSub(futurePosition,currentPosition);
		if (Math.abs(diff.x) > Math.abs(diff.y)){
			if (diff.x > 0){
				this.runAction(cc.animate(this._facingRightAnimation));
			}else{
				this.runAction(cc.animate(this._facingLeftAnimation));
			}
		}else{
			if (diff.y > 0){
				this.runAction(cc.animate(this._facingForwardAnimation));
			}else{
				this.runAction(cc.animate(this._facingBackAnimation));
			}
		}
			
		var moveAction = cc.moveTo(0.4,this._gameLayer.positionForTileCoord(s.getPosition()));
		
		this._shortestPath[0].retain();
		this._shortestPath.splice(0,1);
		var moveCallback = cc.callFunc(this.popStepAndAnimate,this);
		this.runAction(cc.sequence(moveAction,moveCallback))	
	},});

源码地址 原文链接:https://www.f2er.com/cocos2dx/344715.html

猜你在找的Cocos2d-x相关文章