A*算法JavaScript实现

128kj

浏览: 595161 次
来自: ...

最近访客更多访客>>

hcmfys

caizi12

sdtvyyb_007

hanqunfeng

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

javascript

javascript html 算法

欢迎访问博主的网站：http://www.108js.com/link.html

A星算法步骤：
关于A*算法可参看：
http://www.108js.com/article/article5/50017.html

1.起点先添加到开启列表中

2.开启列表中有节点的话，取出第一个节点，即最小F值的节点,
   判断此节点是否是目标点，是则找到了，跳出。
   根据此节点取得八个方向的节点，求出G，H，F值；
   判断每个节点在地图中是否能通过，不能通过则加入关闭列表中，跳出
   判断每个节点是否在关闭列表中，在则跳出；
   判断每个节点是否在开启列表中，在则更新G值，F值，还更新其父节点；不在则将其添加到开启列表中，计算G值，H值，F值，添加其节点。

3.把此节点从开启列表中删除，再添加到关闭列表中；

4.把开启列表中按照F值最小的节点进行排序，最小的F值在第一个；

5.重复2，3，4步骤，直到目标点在开启列表中，即找到了；目标点不在开启列表中，开启列表为空，即没找到。
我们怎么确定这条路径呢？很简单，从目标开始，朝父节点移动。这最终会引导你回到起始格，这就是你的路径！

例：如上面第一个图是从（3，2）到（3，8）的A*搜索路径。

<html>
<head><title>A*算法JavaScript实现</title>
<script>
//A*算法
  var map=[//地图(1可通过 0不可通过)
       [1,1,1,1,1,1,1,1,1,1],
       [1,1,1,1,0,1,1,1,1,1],
       [1,1,1,1,0,1,1,1,1,1],
       [1,1,1,1,0,1,1,1,1,1],
       [1,1,1,1,0,1,1,1,1,1],
       [1,1,1,1,0,1,1,1,1,1]];

    
  var openList=[];//开启列表,存入节点Node
  var closeList=[];//关闭列表
  var COST_STRAIGHT = 10;//垂直方向或水平方向移动的路径评分
  var COST_DIAGONAL = 14;//斜方向移动的路径评分
  var row=6;//行
  var column=10;//列

  function showCloseList(){
       for(i=0;i<closeList.length;i++){
           alert("C--"+closeList[i].toString());
       }
   }
   function showOpenList(){
       for(i=0;i<openList.length;i++){
           alert("O--"+openList[i].toString());
       }
   }

 //从起点(x1,y1)查找目标(x2,y2),（-1：错误，0：没找到，1：找到了）
  function search1(x1,y1,x2,y2){
        if(x1<0||x1>=row||x2<0||x2>=row||y1<0||y1>=column||y2<0||y2>=column){
            return -1;
        }
        if(map[x1][y1]==0||map[x2][y2]==0){
            return -1;
        }
        var sNode=new Node(x1,y1,null);//起点
        var eNode=new Node(x2,y2,null);//目标
        
        openList.push(sNode);
        var resultList=search(sNode, eNode);
        if(resultList.length==0){
            return 0;
        }
        for(i=0;i<resultList.length;i++){
            map[resultList[i].getX()][resultList[i].getY()]=2;
        }
        return 1;
    }

//查找核心算法
    function search(sNode,eNode){
      var resultList=[];
      var isFind=false;
      var node=null;
      while(openList.length>0){
         //取出开启列表中最低F值，即第一个存储的值的F为最低的
         node=openList[0];
        
         //判断是否找到目标点
         if(node.getX()==eNode.getX()&&node.getY()==eNode.getY()){
              isFind=true;
              break;
          }
               
          //上
          if((node.getY()-1)>=0){
               checkPath(node.getX(),node.getY()-1,node, eNode, COST_STRAIGHT);
          }
          
           //下
          if((node.getY()+1)<column){
              checkPath(node.getX(),node.getY()+1,node, eNode, COST_STRAIGHT);
           }                                 
             
           //左
           if((node.getX()-1)>=0){
              checkPath(node.getX()-1,node.getY(),node, eNode, COST_STRAIGHT);
            }

           //右
           if((node.getX()+1)<row){
               checkPath(node.getX()+1,node.getY(),node, eNode, COST_STRAIGHT);
           }
        
          //左上
          if((node.getX()-1)>=0&&(node.getY()-1)>=0){
              checkPath(node.getX()-1,node.getY()-1,node, eNode, COST_DIAGONAL);
          }
      
          //左下
           if((node.getX()-1)>=0&&(node.getY()+1)<column){
              checkPath(node.getX()-1,node.getY()+1,node, eNode, COST_DIAGONAL);
           }
            
           //右上
           if((node.getX()+1)<row&&(node.getY()-1)>=0){
               checkPath(node.getX()+1,node.getY()-1,node, eNode, COST_DIAGONAL);
           }
    
           //右下
           if((node.getX()+1)<row&&(node.getY()+1)<column){
               checkPath(node.getX()+1,node.getY()+1,node, eNode, COST_DIAGONAL);
           }
           
            //从开启列表中删除
            //添加到关闭列表中       
            closeList.push(openList.shift());
      
            //开启列表中排序，把F值最低的放到最底端
            openList.sort(compare);
        }
        if(isFind){
            getPath(resultList, node);
        }
        return resultList;
    }

  
    //查询此路(x,y)是否能走通
    function checkPath(x,y,parentNode,eNode,cost){
       var node=new Node(x, y, parentNode);
        //查找地图中是否能通过
        if(map[x][y]==0){
            closeList.push(node);
            return false;
        }
        
     //查找关闭列表中是否存在
     if(isListContains(closeList, x, y)!=-1){    
          return false;
      }
      //查找开启列表中是否存在
      var index=-1;
      if((index=isListContains(openList, x, y))!=-1){
         //G值是否更小，即是否更新G，F值
         if((parentNode.getG()+cost)<openList[index].getG()){
            node.setParentNode(parentNode);
            countG(node, eNode, cost);
            countF(node);
            openList[index]=node;
        }
      }else{
        //添加到开启列表中
        node.setParentNode(parentNode);
        count(node, eNode, cost);
        openList.push(node);    
      }
        return true;
    }

    //集合中是否包含某个元素(-1：没有找到，否则返回所在的索引)
    function isListContains(list, x, y){
        var i,node;
        for(i=0;i<list.length;i++){
            node=list[i];
            if(node.getX()==x&&node.getY()==y){
                return i;
            }
        }
        return -1;
    }

    //从终点往返回到起点
    function getPath(resultList,node){
        if(node.getParentNode()!=null){
            getPath(resultList, node.getParentNode());
        }
        resultList.push(node);
    }
    
    //计算G,H,F值
    function count(node, eNode,cost){
        countG(node, eNode, cost);
        countH(node, eNode);
        countF(node);
    }
    //计算G值
    function countG(node,eNode,cost){
        if(node.getParentNode()==null){
            node.setG(cost);
        }else{
            node.setG(node.getParentNode().getG()+cost);
        }
    }
    //计算H值
    function countH(node,eNode){
        node.setF((Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY()))*10);
    }
    //计算F值
    function countF(node){
        node.setF(node.getG()+node.getH());
    }
    
 
//节点类
function  Node(x,y,parentNode) {
        this.x=x;
        this.y=y;
        this.parentNode=parentNode;//父节点
        this.g=0; //当前点到起点的移动耗费
        this.h=0;//当前点到终点的移动耗费，即曼哈顿距离|x1-x2|+|y1-y2|(忽略障碍物)
        this.f=0; //f=g+h
    }
    
    Node.prototype.getX=function() {
        return this.x;
    }
    Node.prototype.setX=function(x) {
        this.x = x;
    }
    Node.prototype.getY=function() {
        return this.y;
    }
    Node.prototype.setY=function(y) {
        this.y = y;
    }
    Node.prototype.getParentNode=function() {
        return this.parentNode;
    }
    Node.prototype.setParentNode=function(parentNode) {
        this.parentNode = parentNode;
    }
    Node.prototype.getG=function() {
        return this.g;
    }
    Node.prototype.setG=function(g) {
        this.g = g;
    }
    Node.prototype.getH=function() {
        return this.h;
    }
    Node.prototype.setH=function(h) {
        this.h = h;
    }
    Node.prototype.getF=function() {
        return this.f;
    }
    Node.prototype.setF=function(f) {
        this.f = f;
    }
    Node.prototype.toString=function(){
        return "("+this.x+","+this.y+","+this.f+")";
     }

//节点比较类
  function compare(o1, o2) {
    return o1.getF()-o2.getF();
 }

function init(){
   var flag=search1(3, 2, 3, 8);
   if(flag==-1){
      alert("传输数据有误！");
   }else if(flag==0){
      alert("没找到！");
    }else{          
     for( x=0;x<6;x++){
      for( y=0;y<10;y++){
       if(map[x][y]==1){
         document.write("* ");
       }else if(map[x][y]==0){
         document.write("〓");
       }else if(map[x][y]==2){//输出搜索路径
         document.write("※");
       }
      }
      document.write("<br/>");
     }
   }
}
     
</script>
<head>
<body onLoad="init()"> 
</body></html>

一些运行结果在上面。
演示及源码下载：http://www.108js.com/article/article5/50019.html

查看图片附件

0
顶

0
踩

分享到：

用像素块遮挡图片的某部分 | HTML5 Canvas简单动画：圆周运动

2013-11-28 10:49
浏览 1274
评论(0)
分类:Web前端
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论