js实现A*寻路算法

亦凉 2022-08-25 13:49 192阅读 0赞

js使用canvas绘制界面。

![SouthEast][]

定义两个类：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

[SouthEast]: /images/20220824/118f67ff043d44538549cba7d83523c3.png