Creator | A*（A-Star）寻路实现及优化浅析
演示
A*
四方向和八方向
二叉堆（最小堆）及位运算
返回最近目的地
穿越障碍物拐角
双向A*
多层A*
多单元分帧寻路
多单元间相互碰撞
IDA*/最佳优先搜索/跳点搜索
A*
首先请拜读各路神仙的文章和代码，然后就可以不用看我继续哔哔了
A*寻路初探：
https://www.jianshu.com/p/e52d856e7d48
A comprehensive path-finding library in javascript：
https://github.com/qiao/PathFinding.js
演示地址：
http://qiao.github.io/PathFinding.js/visual/
TypeScript版本：
https://www.cnblogs.com/gamedaybyday/p/7778995.html
ps:源码需在公众号回复：A*简装版
四方向和八方向
在检索相邻格子时候，判断是否是对角线
二叉堆
由于OpenList需要实时添加节点，而且每次取出最小值的节点，所以采用二叉堆（最小堆）作为开启列表的容器更合理一些
最小堆：根结点的键值是所有堆结点键值中最小者
二叉堆的实现：
https://eloquentjavascript.net/1st_edition/appendix2.html
https://www.npmjs.com/package/heap
寻路：
public search(grid: Grid, startX: number, startY: number, endX: number, endY: number, closest: boolean = false): Array < Node > {
grid.cleanDirty();
let start = grid.getNode(startX, startY);
let end = grid.getNode(endX, endY);
let openHeap = this.newHeap();
let closestNode = start; // set the start node to be the closest if required
start.h = this.heuristic(start, end);
grid.markDirty(start);
openHeap.push(start);
while (openHeap.size() > 0) {
// Grab the lowest f(x) to process next. Heap keeps this sorted for us.
let currentNode = openHeap.pop();
// End case -- result has been found, return the traced path.
if (currentNode === end) {
return this.backtrace(currentNode);
}
// Normal case -- move currentNode from open to closed, process each of its neighbors.
currentNode.closed = true;
// Find all neighbors for the current node.
let neighbors = grid.neighbors(currentNode);
for (let i = 0; i < neighbors.length; ++i) {
let neighbor = neighbors[i];
if (neighbor.closed || neighbor.isWall()) {
// Not a valid node to process, skip to next neighbor.
continue;
}
// The g score is the shortest distance from start to current node.
// We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
let gScore = currentNode.g + neighbor.getCost(currentNode);
let beenVisited = neighbor.visited;
if (beenVisited == VISITED.NONE || gScore < neighbor.g) {
// Found an optimal (so far) path to this node. Take score for node to see how good it is.
neighbor.visited = VISITED.START;
neighbor.parent = currentNode;
neighbor.h = neighbor.h || this.heuristic(neighbor, end);
neighbor.g = gScore;
neighbor.f = neighbor.g + neighbor.h;
grid.markDirty(neighbor);
if (closest) {
// If the neighbour is closer than the current closestNode or if it's equally close but has
// a cheaper path than the current closest node then it becomes the closest node
if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) {
closestNode = neighbor;
}
}
if (beenVisited == VISITED.NONE) {
// Pushing to heap will put it in proper place based on the 'f' value.
openHeap.push(neighbor);
} else {
// Already seen the node, but since it has been rescored we need to reorder it in the heap
openHeap.rescoreElement(neighbor);
}
}
}
}
if (closest) {
return this.backtrace(closestNode);
}
// No result was found - empty array signifies failure to find path.
return [];
}返回最近目的地
当目标位置不可抵达时：
返回离目标位置最近的可抵达区域：
if (closest) {
// If the neighbour is closer than the current closestNode or if it's equally close but has
// a cheaper path than the current closest node then it becomes the closest node
if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) {
closestNode = neighbor;
}
}双向A*
以 起点->终点 和 终点->起点 分别进行A*寻路，直到某个节点在两个OpenList中同时出现，然后以同时出现的节点和当前节点分别进行回溯得到节点数组就是最终路径
节点在两个OpenList中同时出现：
//startOpenHeap
if (neighbor.visited === VISITED.END) {
let ret = this.biBacktrace(currentNode, neighbor);
ret.push(end);
return ret;
}
//endOpenHeap
if (neighbor.visited === VISITED.START) {
let ret = this.biBacktrace(neighbor, currentNode);
ret.push(end);
return ret;
}穿越障碍物拐角
允许穿越障碍物拐角：
禁止穿越障碍物拐角：
禁止穿越障碍物拐角时，只需要在获取相邻节点时多一步判断：
public neighbors(node: Node): Node[] {
let ret = [];
let x = node.x;
let y = node.y;
let s0 = false,
d0 = false,
s1 = false,
d1 = false,
s2 = false,
d2 = false,
s3 = false,
d3 = false;
if (!this.isWall(x, y - 1)) {
ret.push(this.nodes[x][y - 1]);
s0 = true;
}
if (!this.isWall(x + 1, y)) {
ret.push(this.nodes[x + 1][y]);
s1 = true;
}
if (!this.isWall(x, y + 1)) {
ret.push(this.nodes[x][y + 1]);
s2 = true;
}
if (!this.isWall(x - 1, y)) {
ret.push(this.nodes[x - 1][y]);
s3 = true;
}
if (!this.crossDiagonal) {
return ret;
}
if (this.crossCorner) {
d0 = s0 || s1;
d1 = s1 || s2;
d2 = s2 || s3;
d3 = s3 || s0;
} else {
d0 = s0 && s1;
d1 = s1 && s2;
d2 = s2 && s3;
d3 = s3 && s0;
}
if (d0 && !this.isWall(x + 1, y - 1)) {
ret.push(this.nodes[x + 1][y - 1]);
}
if (d1 && !this.isWall(x + 1, y + 1)) {
ret.push(this.nodes[x + 1][y + 1]);
}
if (d2 && !this.isWall(x - 1, y + 1)) {
ret.push(this.nodes[x - 1][y + 1]);
}
if (d3 && !this.isWall(x - 1, y - 1)) {
ret.push(this.nodes[x - 1][y - 1]);
}
return ret;
}多层A*
A*占用CPU的时间取决于当前节点和目标节点的距离，距离越远，相应的检索格子数量会越多，所以游戏中可以设计两层或者多层A*。当距离目标节点距离较远时，使用尺寸比较大的格子进行检索，当接近目标时，切换到较小尺寸的格子进行检索，这样可以减少检索的格子数量，节省CPU时间
多单元分帧寻路
多单元进行A*寻路时，可以把他们放进一个队列，每帧对其中N个单元进行A*寻路，减少当前帧内CPU的占用
多单元间相互碰撞
下面只是几种思考方式，具体如何取舍，决定权在你
①单元自身增加障碍物属性
②单元间碰撞检测，单元等待/重新寻路
③单元间碰撞检测，单元使用一定的移动规则，比如向左/向右/向前
④队伍中选出领队，对领队进行A*，队伍中其他单元跟随领队，需要处理单元间的相互碰撞，以及队伍的队形
⑤为每个单元的目标位置都加上一个偏移量
IDA*/最佳优先搜索/跳点搜索
IDA*：迭代加深搜索A*算法，使用回溯方法，在检索过程中采用估值（剪枝）函数，以减少不必要的检索，节省空间，但代价是会产生重复检索，难点在于估值函数的设定
https://www.xuebuyuan.com/1573926.html
IDA*的基本思路是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求下，可以证明找到的这个解一定是最优解。在程序实现上，IDA*要比A* 方便，因为不需要保存结点，不需要判断重复，也不需要根据H值对结点排序，占用空间小。 而这里在IDA*算法中也使用合适的估价函数，来评估与目标状态的距离。
在一般的问题中是这样使用IDA*算法的，当前局面的估价函数值+当前的搜索深度 > 预定义的最大搜索深度时，就进行剪枝。
这个估值函数的选取没有统一的标准，找到合适的该函数并不容易，但是可以大致按照这个原则：在一定范围内加大各个状态启发函数值的差别
最佳优先搜索：运用贪心算法的思想，优先检索离终点近的节点。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。最佳优先搜索得到的路径不一定是最优路径
https://www.ituring.com.cn/article/497664
跳点搜索： 通过一定规则来裁剪相邻节点，设置为跳点。 比如方向相同，权重相等的节点所形成的大面积可行走区域，就可以省略其中相邻节点的检索
https://blog.csdn.net/yjxxtd/article/details/93506231
声明：发布此文是出于传递更多知识以供交流学习之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与我联系，我将及时更正、删除，谢谢。
作者：请容我安眠
更多笔记和源码请关注：【微信公众号】 CocosCreator笔记