오후 훑 기 를 기록 한 A 성 길 찾기 알고리즘

        open  close 
         open    (         close   ，         open ，         ，      )
open            close   ，        ，            。
（8         ）

//      
function manhattan(point, endPoint) {
    return Math.abs(point.x - endPoint.x) + Math.abs(point.y - endPoint.y);
}

/**
 * 
 * @param {Number} row  
 * @param {Number} col  
 */
var aStar = function (row, col) {
    if (row <= 0 || col <= 0) {
        console.error('error query');
        return;
    }
    //     
    this._list = [];
    this._row = row;
    this._col = col;
    for (var i = 0; i < row; i++) {
        this._list[i] = [];
        for (var j = 0; j < col; j++) {
            this._list[i][j] = 1;
        }
    }
};

/**
 *      
 */
aStar.prototype.addObstacle = function (points) {
    if (typeof points.length !== 'undefined') {
        for (var i = 0; i < points.length; i++) {
            var point = points[i];
            this._list[point.x][point.y] = 0;
        }
    } else {
        this._list[points.x][points.y] = 0;
    }
};

/**
 *     (direction!==4  8      )
 */
aStar.prototype.getRoute = function (startPoint, endPoint, direction) {
    if (!this._list[startPoint.x][startPoint.y] || !this._list[endPoint.x][endPoint.y]) {
        console.error('           ');
        return [];
    }

    if (startPoint.x == endPoint.x && startPoint.y == endPoint.y) {
        console.error('         ');
        return [];
    }

    this._openList = [];    //                    
    this._closeList = {};   //              

    //      open    
    var head = null;
    var node = this._createNode(head, startPoint, endPoint);
    this._addNodeToOpenList(node);

    return this._getRoute(endPoint, direction);
};

aStar.prototype._getRoute = function (endPoint, direction) {
    //  open          
    var list = this._getOpenMin();
    if (list.length === 0) {
        return [];
    }

    for (var i = 0; i < list.length; i++) {
        var e = list[i];
        var index = e.index;
        var node = e.node;

        if (node.data.H === 0/**      */) {
            var route = [];
            while (node.head) {
                route.splice(0, 0, node.point);
                node = node.head;
            }
            route.splice(0, 0, node.point);
            return route;
        }

        //   close    
        this._addOpenToCloseList(index, node);

        //     
        /**
         *   p closed   ：   。
         *   p  open   ：            。
         *   p   open   ：                 ，  F       。   ，           。
         */
        this._getNeighbor(node.point, function (point) {
            if (this._list[point.x][point.y]/**      */ && !this._closeList[point.x + ',' + point.y]/**   close   */) {
                var n = this._createNode(node, point, endPoint);
                this._addNodeToOpenList(n);
            }
        }, direction);
    }

    return this._getRoute(endPoint, direction);
};

/**
 *        
 * 
 * @param {any} point    
 * @param {any} cb   
 * @param {bool} d 8    4  ，  8 8  
 * 
 */
aStar.prototype._getNeighbor = function (point, cb, d) {
    var xMin = point.x > 0 ? (point.x - 1) : 0;
    var xMax = (point.x < this._col - 1) ? (point.x + 1) : point.x;
    var yMin = point.y > 0 ? (point.y - 1) : 0;
    var yMax = (point.y < this._row - 1) ? (point.y + 1) : point.y;
    for (var i = xMin; i <= xMax; i++) {
        for (var j = yMin; j <= yMax; j++) {
            if (d === 4) {
                //4  
                if ((i !== point.x && j === point.y) || (i === point.x && j !== point.y)) {
                    cb.call(this, { x: i, y: j });
                }
            } else {
                if (this._judgeAcross(point, { x: i, y: j })) {
                    //8  
                    if (i !== point.x || j !== point.y) {
                        cb.call(this, { x: i, y: j });
                    }
                }
            }
        }
    }
};

/**
 *     8            
 */
aStar.prototype._judgeAcross = function (p1, p2) {
    if (p1.x !== p2.x && p1.y !== p2.y) {
        if (this._list[p1.x][p2.y] === 0 && this._list[p2.x][p1.y] === 0) {
            return false;
        }
    }
    return true;
};

/**
 *  open          close   ，   open   
 */
aStar.prototype._addOpenToCloseList = function (index, node) {
    var k = node.point.x + ',' + node.point.y;
    this._closeList[k] = node;
    this._openList.splice(index, 1);
};

/**
 *      open  
 */
aStar.prototype._addNodeToOpenList = function (node) {
    for (var i = this._openList.length - 1; i >= 0; i--) {
        var n = this._openList[i];
        if (n.point.x === node.point.x && n.point.y === node.point.y) {
            if (n.data.F < node.data.F) {
                return;
            }
            this._openList.splice(i, 1);
            break;
        }
    }
    this._openList.push(node);
};

aStar.prototype._createNode = function (head, point, endPoint) {
    var addG = 1;
    if (head && head.x !== point.x && head.y !== point.y) {
        addG = 1.414213562373095;
    }
    var G = head ? head.data.G + 1 : 0;
    var H = manhattan(point, endPoint);
    return {
        head: head,
        data: {
            F: G + H,
            G: G,
            H: H
        },
        point: point
    };
};

aStar.prototype._getOpenMin = function () {
    var min = [];
    var minF = 0;
    for (var i = this._openList.length - 1; i >= 0; i--) {
        var element = this._openList[i];
        if (!minF) {
            minF = element.data.F;
        }
        if (element.data.F === minF) {
            min.push({ index: i, node: element });
        } else if (element.data.F < minF) {
            minF = element.data.F;
            min = [{ index: i, node: element }];
        }
    }
    return min;
};

var a = new aStar(30, 30);

a.addObstacle({ x: 0, y: 1 });
a.addObstacle({ x: 2, y: 0 });
a.addObstacle({ x: 2, y: 1 });
a.addObstacle({ x: 2, y: 2 });
a.addObstacle({ x: 1, y: 3 });
a.addObstacle({ x: 10, y: 20 });
a.addObstacle({ x: 14, y: 13 });
a.addObstacle({ x: 14, y: 14 });
a.addObstacle({ x: 14, y: 15 });
a.addObstacle({ x: 14, y: 16 });

console.time('a');
var route = a.getRoute({ x: 0, y: 0 }, { x: 20, y: 15 });
console.timeEnd('a');

for (var i = 0; i < route.length; i++) {
    var p = route[i];
    a._list[p.x][p.y] = '@';
}

for (var i = 0; i < a._list.length; i++) {
    console.log(a._list[i].toString());
}