js使用canvas绘制界面。
定义两个类:Node保存点及A*算法中的F=G+H值;Point。
/** * 节点 * p : 节点对应的坐标 * pn : 节点的父节点 * g : A*-g * h : A*-h */ function Node(p, pn, g, h) { if ( !(p instanceof Point) || isNaN(g) || isNaN(h)) { throw new Error("非法参数"); } this.g = g; this.h = h; this.f = g + h; this.p = p; this.pn = pn; this.equals = function(obj){ if(!(obj instanceof Node)){ return false; } return this.p.equals(obj.p); } } /** * 点 */ function Point(x, y) { if (isNaN(x) || isNaN(y)) { throw new Error("非法参数"); } this.x = x; this.y = y; this.equals = function(obj){ if(!(obj instanceof Point)){ return false; } return this.x == obj.x && this.y == obj.y; } }
算法实现:探索新节点->是否被访问 ?跳过:(是否已被记录?(是否需要更新?更新:""):加入开放列表):“”,直到寻找到终点或地图说有点被访问 结束循环。
//寻路 while(true){ if(openList.length == 0){ break; } var node = openList.shift(); if(node.p.equals(constants.END_POINT)){ rsNode = node; break; } var nodeArr = utils.explore(node, constants.MAP_ARRAY, constants.END_POINT); closeList.push(node); //判断探索到的节点是否已被访问 若未访问过则加入到 开放列表 for(var i in nodeArr){ var n = nodeArr[i]; //判断开放列表是否已存在节点 是否需要更新 if(utils.inArray(n, closeList) == -1){ var off = utils.inArray(n, openList); if(off == -1){ openList.push(n); }else{ var u = openList[off]; //已探索过此节点,且现在有更优路径 if(u.f > n.f){ openList.splice(off, 0); openList.push(n); } } } } openList.sort(utils.sortNode); }
源码:http://download.csdn.net/detail/lj745280746/7007935
参考:http://wenku.baidu.com/link?url=0qHr1lg5ngTQasT6e4J12ZEnVc4A5wiybpD3MRfkzNVP7Z7NUkLJaGeGNPdUmy-Il7dedpJjwbEhkJmJIOgdE5EMRUlBYhyCfd7rW0UbPSC