本帖最后由 季理GiLiGiLi 于 2023-11-13 15:33 编辑
最近，学习了一下寻路算法，就用我们编辑器写了一个demo，具体效果如下：
那就来简单说说两个算法吧~！
Dijkstra算法就是通过在每一个地图格子中加入一个权值G，这个G值表示的是上一个格子到当前格子所需要花费的代价。Dijkstra在每次搜索的时候都会计算周围格子的G值，然后每次都选择G值最小的格子作为下一个拓展格子。搜索到最后，Dijkstra能返回代价最小的路径，也就是最优路径。而AStar算法 则相当于 Dijkstra算法 的扩展，它利用启发信息寻找最优路径。A* 算法需要在地图中搜索节点，并设定适合的启发函数进行指导。通过评价各个节点的代价值，获取下一需要拓展的最佳节点，直至到达最终目标点位置。A* 算法优点在于对环境反应迅速，搜索路径直接，是一种直接的搜索算法，因此被广泛应用于路径规划问题。其缺点是实时性差，每一节点计算量大、运算时间长，而且随着节点数的增多，算法搜索效率降低，而且A* 算法并没有完全遍历所有可行解，所得到的结果不一定是最优解。
如果说，Dijkstra算法的权值函数是G，那么，A*算法的权值函数就是F=G+H，其中，H为一个启发函数。
因为当A*算法启发函数值恒为0时，就相当于Dijkstra算法，故这里只贴A*算法代码。（已附完整项目）。
/**
* 算法思想:
1. 把起点加入 open list 。
2. 重复如下过程：
a. 遍历open list ，查找F值最小的节点，把它作为当前要处理的节点，然后移到close list中
b. 对当前方格的 8 个相邻方格一一进行检查，如果它是不可抵达的或者它在close list中，忽略它。否则，做如下操作：
□ 如果它不在open list中，把它加入open list，并且把当前方格设置为它的父亲
□ 如果它已经在open list中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更近。如果更近，把它的父亲设置为当前方格，并重新计算它的G和F值。
如果你的open list是按F值排序的话，改变后你可能需要重新排序。
c. 遇到下面情况停止搜索：
□ 把终点加入到了 open list 中，此时路径已经找到了，或者
□ 查找终点失败，并且open list 是空的，此时没有路径。
3. 从终点开始，每个方格沿着父节点移动直至起点，形成路径。
*/
findPath(startPoint: Cell, endPoint: Cell) {
//清除上一次算法留下的节点与节点之间的父子关系
this.clearCellRelationship();
//初始化开表和闭表
let openList: Cell[] = []; //待检查列表
let closeList: Cell[] = []; //closeList中的每个方格都是不需要再关注的。
openList.push(startPoint); //将起点加入openlist
while (openList.length > 0) {
//遍历open list ，查找F值最小的节点，把它作为当前要处理的节点，然后移到close list中
let minPoint = this.findMinPoint(openList);
let idx = openList.findIndex((p) => { return p.CellObj.guid == minPoint.CellObj.guid })
openList.splice(idx, 1);
closeList.push(minPoint);
//寻找MinPoint周围的点（边界和障碍物不会算在内）
let surroundPoints = this.findSurroundPoint(minPoint);
surroundPoints.forEach((son) => {
//如果SurroundPoints中的点在Close表中出现过,无视
if (closeList.includes(son)) return;
if (openList.includes(son)) {
let newPathG = this.calcG(son, minPoint);
if (newPathG < son.G) {
son.Parent = minPoint;
son.G = newPathG;
son.F = newPathG + son.F;
}
} else {
//若该点没有在Open表中出现过，则直接计算F值存入点内，且将该点的父亲设置为minPoint
this.calcF(son, endPoint);
son.Parent = minPoint;
openList.push(son);
}
});
//若已经到达终点，则退出循环
if (openList.includes(endPoint)) {
break;
}
}
return this.getPathWay(endPoint);//返回寻路结果
}
完整项目demo：
AStarAlgorithm.rar
(110.14 KB, 下载次数: 102)
| 
