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))
},});
源码地址
