早前写了一篇关于A*算法的文章：《》

最近在写个js的UI框架，顺便实现了一个js版本的A*算法，与之前不同的是，该A*算法是个双向A*。

 

双向A*有什么好处呢？

我们知道，A*的时间复杂度是和节点数量以及起始点难度呈幂函数正相关的。

这个http://qiao.github.io/PathFinding.js/visual/该网址很好的演示了双向A*的效果，我们来看一看。

绿色表示起点，红色表示终点，灰色是墙面。稍浅的两种绿色分别代表open节点和close节点：

 

当路径通过狭窄通道时，如果起点离通道较近，则很容易找到了终点，把起点和终点交换一下，如图：

 

 

可以注意到，被查找的节点多了不止一倍。

 

我们可以认为，终点在狭窄地带是最差结果，在开阔地带是最优结果。再来看看双向A*算法的寻址：

 

可以看到，和单向的最优结果是很接近的。

 

观察浅绿色寻路节点我们可以注意到，当open节点第一次接触到之后，中止了查找。

根据该思路，实现算法如下：

while (true) {            minFNode = anra.AStarUtil.findMinNode(openList);            openList.removeObject(minFNode);            if (!closedList.contains(minFNode))                closedList.push(minFNode);            if (closedList.length > 500) {                return;            }            if (minFNode == null || minFNode.equals(endNode))                break;            anra.AStarUtil.search(this, minFNode, openList, closedList, endNode);            BIminFNode = anra.AStarUtil.findMinNode(BIopenList);            BIopenList.removeObject(BIminFNode);            if (!BIclosedList.contains(BIminFNode))                BIclosedList.push(BIminFNode);            if (BIclosedList.length > 500) {                return;            }            if (BIminFNode == null || BIminFNode.equals(startNode))                break;            anra.AStarUtil.search(this, BIminFNode, BIopenList, BIclosedList, startNode);            for (var i = 0; i < openList.length; i++) {                for (var j = 0; j < BIopenList.length; j++) {                    if (BIopenList[j].equals(openList[i])) {                        BIminFNode = BIopenList[j];                        minFNode = openList[i];                        middleNode = minFNode;                        break;                    }                }                if (middleNode)                    break;            }            if (middleNode)                break;        }

findMinNode:function (openList) {        if (openList.length == 0)            return null;        else if (openList.length == 1)            return openList[0];        openList.sort(function (a, b) {            return a.f() - b.f();        });        return openList[0];    },    /*搜索*/    search:function (router, node, openList, closedList, endNode) {        var nodes = this.findAroundNode(router, node);        if (nodes == null)            return;        for (var i = 0; i < 8; i++) {            if (nodes[i] == null || nodes[i].level == null)continue;            nodes[i].g = (i > 3 ? nodes[i].level[0]                : nodes[i].level[1]) + node.g;            nodes[i].h = this.caculateH(nodes[i], endNode);            if (closedList.contains(nodes[i])) {                continue;            }            if (!openList.contains(nodes[i])) {                openList.push(nodes[i]);                nodes[i].parent = node;            } else {                var idx = openList.indexOf(nodes[i]);                var n = openList[idx];                if (nodes[i].g < n.g) {                    openList.remove(idx);                    closedList.push(n);                    nodes[i].parent = n.parent;                    openList.splice(idx, 0, nodes[i]);                }            }        }    },    /*查找指定节点周围的可用节点*/    findAroundNode:function (router, node) {        if (node == null)return null;        var nodes = [];        nodes[0] = ANodeFactory.create(router, node.i, node.j + 1);        nodes[1] = ANodeFactory.create(router, node.i, node.j - 1);        nodes[2] = ANodeFactory.create(router, node.i + 1, node.j);        nodes[3] = ANodeFactory.create(router, node.i - 1, node.j);        nodes[4] = ANodeFactory.create(router, node.i - 1, node.j + 1);        nodes[5] = ANodeFactory.create(router, node.i + 1, node.j - 1);        nodes[6] = ANodeFactory.create(router, node.i + 1, node.j + 1);        nodes[7] = ANodeFactory.create(router, node.i - 1, node.j - 1);        return nodes;    },    caculateH:function (p, endNode) {        return (Math.abs(endNode.i - p.i) + Math.abs(endNode.j            - p.j))            * p.level[0];    },