编辑代码

  
       function Point()
       {
           this.x=0;
           this.y=0;
           this.G=0; //G值 开始点 到当前点的移动量
           this.H=0; //H值　当前点移动目的地的移动量估算值
           this.value = 0; //当前点的权重
           this.father=null;
};
       Point.prototype={
           Console:function(){
               console.log("x:"+this.x+" and y:"+this.y);
    },
           Init:function(x,y,father){
               this.x = x;
               this.y = y;
               this.father = father;
    }
};
       function AStar(){
    //地图存放二维数组
           this.map=[];
           //行数
           this.rowCount=0;
           //列数
           this.colCount=0;
           //出发点
           this.startPoint=new Point();
           //终点
           this.endPoint=new Point();
           //存放Opint类的open数组
           this.openList=[];
           //存在Opint类的close数组
           this.closeList=[];
};
       AStar.prototype={
    //是否为障碍物
           IsBar:function(x,y){
               if(this.map[x
        ][y
        ]==3){
                   console.log("bar...");
                   return true;
        }
               else{
                   console.log("no bar...")
                   return false;
        }
    },
    //当前坐标是否在OpenList
           IsInOpenList:function(x,y){
                for(var i=0;i<this.openList.length;i++){
                    if(this.openList[i
            ].x == x && this.openList[i
            ].y == y) {
                        return true;
            }
        }
               return false;
    },
    //当前坐标是否在CloseList
           IsInCloseList:function(x,y){
               for(var i=0;i<this.closeList.length;i++){
                   if(this.closeList[i
            ].x == x&& this.closeList[i
            ].y == y) {
                       return true;
            }
        }
               return false;
    },
    //计算G值;(p是Point类)
           GetG:function(p) {
               if(p.father==null){
                   return 0;
        }
               return p.father.G + levelMap[p.x
        ][p.y
        ];
    },
    //计算H值
           GetH:function(p,pb){
               var h = 0;
               if(p.x >= pb.x && p.y >= pb.y) {
                  for(var i = pb.x; i <= p.x; i++) {        
                      h += levelMap[i
                ][p.y
                ];
            }
                  for(var j = pb.y; j <= p.y; j++) {
                      h += levelMap[pb.x
                ][j
                ];
            }
                  return h;
        } else if(p.x >= pb.x && p.y <= pb.y) {
                  for(var i = pb.x; i <= p.x; i++) {
                      h +=  levelMap[i
                ][p.y
                ];
            }
                  for(var j = p.y; j <= pb.y; j++) {
                      h += levelMap[pb.x
                ][j
                ];
            }                 
                  return h;
        } else if(p.x <= pb.x && p.y >= pb.y) {
                  for(var i = p.x; i <= pb.x; i++) {
                      h += levelMap[i
                ][p.y
                ];
            }
                  for(var j = p.y; j <= pb.y; j++) {
                      h += levelMap[pb.x
                ][j
                ];
            }
                  return h;
        } else if(p.x <= pb.x && p.y <= pb.y) {
                  for(var i = p.x; i <= pb.x; i++){
                      h += levelMap[i
                ][p.y
                ];
            }
                  for(var j = p.y; j <= pb.y; j++){
                      h += levelMap[pb.x
                ][j
                ];
            }
                  return h;
        }
        //return Math.abs(p.x-pb.x)+Math.abs(p.y-pb.y);
    },
    //添加当前点的上下左右相邻的方格到Open列表中
           AddNeiToOpenList: function(curPoint) {
               for(var x = curPoint.x-1; x <= (+curPoint.x+1); x++){
                    for(var y = curPoint.y-1; y <= (+curPoint.y+1); y++){
                //排除自身以及超出下标的点
                        if((x >= 0 && x < this.colCount && y >= 0 && y < this.rowCount) && !(curPoint.x == x && curPoint.y == y)){
                    //排除斜对角
                            if(Math.abs(x-curPoint.x) + Math.abs(y-curPoint.y) == 1){
                        //不是障碍物且不在关闭列表中
                                if(this.IsBar(x,y)== false && this.IsInCloseList(x,y) == false) {
                            //不存在Open列表
                                    if(this.IsInOpenList(x,y) == false) {
                                        var point=new Point();
                                        point.x = x;
                                        point.y = y;
                                        point.father = curPoint;
                                        point.G = this.GetG(point);
                                        point.H=this.GetH(point,this.endPoint);
                                        this.openList.push(point);
                            }
                            //存在open表中，需要重新计算G值 
                                    else {
                                      var point = this.GetPointFromOpenList(x, y);      
                                      //如果从当前点移动到已经在open表中的该点G值变小，更新该点G值以及父节点                                
                                      if((curPoint.G + point.value) < point.G) {
                                        point.father = curPoint;
                                        point.G = curPoint.G + point.value;
                                }
                            }
                        }
                    }
                }
            }
        }
    },
    //在openlist集合中获取G+H为最小的Point点
           GetMinFFromOpenList:function(){
               var minPoint=null;
               var index=0;
               for(var i = 0; i < this.openList.length; i++) {
                   if(minPoint == null || minPoint.G + minPoint.H >= this.openList[i
            ].G + this.openList[i
            ].H) {
                       minPoint=this.openList[i
                ];
                       index=i;
            }
        }
               return{
                   minPoint: minPoint,
                   index: index
        }
    },
 
           GetPointFromOpenList:function(x,y){
               for(var i = 0; i < this.openList.length; i++) {
                   if(this.openList[i
            ].x == x && this.openList[i
            ].y == y) {
                       return this.openList[i
                ];
            }
        }
               return null;
    },
    //开始寻找节点
           FindPoint:function(){
              console.time("time2")
               this.openList.push(this.startPoint);
               while(this.IsInOpenList(this.endPoint.x, this.endPoint.y) == false || this.openList.length == 0) {
                   var curPoint = this.GetMinFFromOpenList().minPoint;
                   console.log("curPoint:"+curPoint);
                   var index=this.GetMinFFromOpenList().index;
                   if(curPoint==null){
                       console.log("没有路");
                       return;
            }
                   this.openList.splice(index,
            1);
                   this.closeList.push(curPoint);
                   this.AddNeiToOpenList(curPoint);
        }

               var p = this.GetPointFromOpenList(this.endPoint.x, this.endPoint.y);

               while(p.father!=null){
                   p = p.father;
                   this.map[p.x
            ][p.y
            ]=4;
        }
        //把终结点也设置成4
               this.map[this.endPoint.x
        ][this.endPoint.y
        ]=4;
            	 console.timeEnd("time2")
    },
           PrintMap:function(){}
};

       //地图类    map数组保存数字标识 :0 默认　1 开始点　2 结束点　3 障碍物
       function Map(id){
           this.map=[];
           this.container=document.getElementById(id);
           this.colCount=0;
           this.rowCount=0;
}
       var levelMap = [];
       Map.prototype = {
           init:function(colCount,rowCount) {
               this.colCount = colCount;
               this.rowCount = rowCount;
               for(var colIndex = 0; colIndex < this.colCount;colIndex++){
                   this.map.push([]);
                   //权重数组
                   levelMap.push([]);
                   for(var rowIndex=0;rowIndex<this.rowCount;rowIndex++){
                       this.map[colIndex
                ].push(0);
                       levelMap[colIndex
                ].push(Math.random()*10);
            }
        }
    },
           drawMap:function(callback){
               for(var colIndex=0;colIndex<this.map.length;colIndex++){
                   for(var rowIndex=0;rowIndex<this.map[colIndex
            ].length;rowIndex++){
                       var div=document.createElement("div");
                       div.style.top=colIndex*50+5+"px";
                       div.style.left=rowIndex*50+5+"px";
                       div.setAttribute("colIndex",colIndex);
                       div.setAttribute("rowIndex",rowIndex);
                       div.onclick=callback;
                       this.container.appendChild(div);
            }
        }
    },
           drawPoints:function(){
               var divs=this.container.children;
               console.log(divs.length);
               console.log(this.map);
               var timer=1000;
               for(var i=0;i<divs.length;i++){
                   var colIndex=divs[i
            ].getAttribute("colIndex");
                   var rowIndex=divs[i
            ].getAttribute("rowIndex");
                   if(this.map[colIndex
            ][rowIndex
            ]==4){
                       divs[i
                ].style.backgroundColor="red";
            }
        }
    },
           getPoint:function(colIndex,rowIndex){
               return this.map[colIndex
        ][rowIndex
        ];
    },
           setStartPoint:function(colIndex,rowIndex){
               this.map[colIndex
        ][rowIndex
        ]=1;
    },
           setEndPoint:function(colIndex,rowIndex){
               this.map[colIndex
        ][rowIndex
        ]=2;
    },
           setBarPoint:function(colIndex,rowIndex){
               this.map[colIndex
        ][rowIndex
        ]=3;
    },
           clearMap:function(){
               this.map.splice(0,this.map.length);
               this.container.innerHTML="";
    }
}
 
       var rowInput=document.querySelector("#rowInput");
       var colInput=document.querySelector("#colInput");
       var createMapBtn=document.querySelector("#createMapBtn");
       var prompt=document.querySelector("#prompt");
       var findPoint=document.querySelector("#findPoint");
       var curMap=new Map("main");
       var state=0; //状态标识　0选择开始节点标识　1选择结束节点标识 2选择障碍物标识
       var aStar=new AStar(); //寻路类
 
       createMapBtn.onclick=function(){
 
           curMap.clearMap();
           curMap.init(colInput.value,rowInput.value);
           aStar.map=curMap.map;
           aStar.colCount=colInput.value;
           aStar.rowCount=rowInput.value;
           curMap.drawMap(function(){
                var colIndex=this.getAttribute("colIndex");
                var rowIndex=this.getAttribute("rowIndex");
                if(curMap.getPoint(colIndex,rowIndex)!=0){
                    return;
        }
                if(state==0){
                    this.style.backgroundColor="blue";
                    curMap.setStartPoint(colIndex,rowIndex);
                    aStar.startPoint.x = colIndex;
                    aStar.startPoint.y = rowIndex;
                    aStar.startPoint.value = levelMap[colIndex
            ][rowIndex
            ];
                    state=1;
                    prompt.innerHTML="请点击格子，设置终点";
        }else if(state==1){
                    this.style.backgroundColor="yellow";
                    curMap.setEndPoint(colIndex,rowIndex);
                    aStar.endPoint.x=colIndex;
                    aStar.endPoint.y=rowIndex;
                    prompt.innerHTML="请点击格子，设置障碍物";
                    console.log(findPoint);
                    findPoint.style.display="block";
                    state=2;
        }else if(state==2){
                    curMap.setBarPoint(colIndex,rowIndex);
                    this.style.backgroundColor="black";
        }
    });
           prompt.innerHTML="请点击格子，设置起始点";
}
       findPoint.onclick=function(){
           aStar.FindPoint();
           curMap.drawPoints();
}