算法核心
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值计算:
相对于起点G值一直增大(横竖走一步消耗为10,斜向走一步消耗为14)
G值有8个方向需要计算
G值总是越靠近终点值越小
H值计算:
相对于起点H值一直减小(离终点近一步-10,离终点远一步+10)
H值有4个方向需要计算
H值相对于终点是不变的
点已被关联过:
如果某个相邻方格已经在openList里了, 检查如果用新的路径 (就是经过最优点的路径) 到达它的话, G值是否会更低一些
如果新的G值更低, 那就把它的parent改为目前选中的方格, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的)
如果新的 G 值比较高, 就说明经过最优点再到达该相邻点不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做
点未被关联过:
- 检查它所有相邻并且可以到达 (障碍物和closeList的方格都不考虑) 的方格. 如果这些方格还不在openList里的话, 将它们加入openList, 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的parent为该最优点
算法总结
A*算法并非是寻路中最好的算法，但由于其实现简单所以在工程中大量使用
A*寻路整体不是非常难，只要注意细节就不会出现bug