JS

算法核心

A*估值算法

寻路估值算法有非常多：常用的有广度优先算法，深度优先算法，哈夫曼树等等，游戏中用的比较多的如：A*估值

算法描述

对起点与终点进行横纵坐标的运算

代码实现

start: 起点坐标(point)
end: 终点坐标(point)
Math.abs(start.getX() - end.getX()) + Math.abs(start.getY() - end.getY());

算法逻辑

寻路过程中检索关联点(路径点)
对关联点分类(分为已经关联与未关联)
对未关联的点用寻路算法对其进行一次标识(每个点需要3种标识)
对比关联点的标识找出下一步的最优路径
循环上几步的操作，直到终点

算法实现

定义一个容器，在js中使用数组[ ]，为了更好描述算法，在Array中实现几个方法

判断容器中是否存在该点:

// 根据对象判断
Array.prototype.isExistByValue = function(value) {

    for (var i = 0; i < this.length; i++) {

        if (value.getX() == this[i].getX() && value.getY() == this[i].getY()) {

            return this[i];// 对象总是为真
        }
    }

    return false;
}
// 根据对象中的属性值判断
Array.prototype.isExistByProperty = function(x, y) {

    for (var i = 0; i < this.length; i++) {

        if (x == this[i].getX() && y == this[i].getY()) {

            return true;
        }
    }

    return false;
}

移除一个点:

// 根据点的属性值移除点
Array.prototype.removeValue = function(x, y) {

    for (var i = 0; i < this.length; i++) {

        if (x == this[i].getX() && y == this[i].getY()) {

            this.splice(i,1);
        }
    }
}

// 根据对象删除点
Array.prototype.remove = function(value) {

    for (var i = 0; i < this.length; i++) {

        if (value == this[i]) {

            this.splice(i,1);
        }
    }
}

添加一个点:

// 根据点的坐标属性添加点到容器中
Array.prototype.add = function(x, y) {

    var v = new pathUtils.locationPoint(x,y);
    this.push(v);
}

根据点对象从容器中拿取该点，没有return null:

Array.prototype.getValue = function(value) {

    for (var i = 0; i < this.length; i++) {

        if (value.getX() == this[i].getX() && value.getY() == this[i].getY()) {

            return this[i];
        }
    }

    return null;
}

根据点的某一属性取出该点:

// 把最小F值的point找出来
Array.prototype.getValueByProperty = function() {

    var minF = this[0].getF();
    for (var i = 0; i < this.length; i++) {

        if (minF > this[i].getF()) {

            minF = this[i].getF();
        }
    }
    for (var i = 0; i < this.length; i++) {

        if (minF == this[i].getF()) {

            return this[i];
        }
    }

    return this[0];
}

寻路逻辑:

pathUtils.pathLogic = function(start, end, obstacArr) {

    this.openList = [];
    this.closeList = [];
    this.openList.push(start);
    while(this.openList.length != 0){

        var smallF = this.openList.getValueByProperty();
        this.openList.remove(smallF);
        this.closeList.push(smallF);
        var suround = this.getSurroundPath(smallF,obstacArr);

        for (var i = 0; i < suround.length; i++) {

            var tempObj = this.openList.isExistByValue(suround[i]);
            if (tempObj) {

                this.foundInOpenList(smallF,tempObj);
            }else{

                this.notFoundInOpenList(smallF,end,suround[i]);
            }
        }
        if (this.openList.getValue(end) != null) {

            this.closeList.push(end);

            return this.closeList;

        }
    }
}

pathUtils.calcG = function(start, point) {

    var G = (Math.abs(point.getX() - start.getX()) + Math.abs(point.getY() - start.getY())) == 1 ? utils.Const.PATH_HORIZONTAL_VERTICAL : utils.Const.PATH_OBLIQUITY;

    return (G + point.getParentPoint().getG());
}
pathUtils.calcH = function(end, point) {

    var h = Math.abs(point.getX() - end.getX()) + Math.abs(point.getY() - end.getY());
    return h * utils.Const.PATH_HORIZONTAL_VERTICAL;
}

pathUtils.getSurroundPath = function(point, obstacArr) {

    var surroundArr = [];

    for (var i = point.getX() - 1; i <= point.getX() + 1; i++) {

        for (var j = point.getY() -1; j <= point.getY() + 1; j++) {

            if (this.closeList.isExistByProperty(i,j)) continue;
            if (obstacArr && obstacArr.length && obstacArr.isExistByProperty(i,j)) continue;

            surroundArr.add(i,j);
        }
    }

    return surroundArr;
}

pathUtils.foundInOpenList = function(tempPoint, point) {

    var G = this.calcG(tempPoint,point);
    if (G < point.getG()) {

        point.setParentPoint(tempPoint);
        point.setG(G);
        point.calcF();
    }
}

pathUtils.notFoundInOpenList = function(tempPoint, end, point) {

    point.setParentPoint(tempPoint);
    point.setG(this.calcG(tempPoint,point));
    point.setH(this.calcH(end,point));
    point.calcF();
    this.openList.push(point);
}

算法细节

需要注意的几点

点对象中标识G的计算
点对象中标识H的计算
点对象已经被关联过
点对象未被关联过

要点突破

当前起点与终点的parent是为null(没有父节点的概念)
G值计算:
1. 相对于起点G值一直增大(横竖走一步消耗为10,斜向走一步消耗为14)
2. G值有8个方向需要计算
3. G值总是越靠近终点值越小
H值计算:
1. 相对于起点H值一直减小(离终点近一步-10,离终点远一步+10)
2. H值有4个方向需要计算
3. H值相对于终点是不变的
点已被关联过:
1. 如果某个相邻方格已经在openList里了, 检查如果用新的路径 (就是经过最优点的路径) 到达它的话, G值是否会更低一些
2. 如果新的G值更低, 那就把它的parent改为目前选中的方格, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的)
3. 如果新的 G 值比较高, 就说明经过最优点再到达该相邻点不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做
点未被关联过:
1. 检查它所有相邻并且可以到达 (障碍物和closeList的方格都不考虑) 的方格. 如果这些方格还不在openList里的话, 将它们加入openList, 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的parent为该最优点

算法总结

A*算法并非是寻路中最好的算法，但由于其实现简单所以在工程中大量使用
A*寻路整体不是非常难，只要注意细节就不会出现bug

发恳写代码