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)) },}); 源码地址 总结
以上是内存溢出为你收集整理的cocos2d-js版本A*算法全部内容，希望文章能够帮你解决cocos2d-js版本A*算法所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）