算法核心


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

05-11 21:54