笔记:A*(A-Star)寻路算法 ts版

记录开发过程中的小问题,请多指教
由于是直接从微信文制过来,文章样式格式有点乱·····
完整样式请阅读微信原文
更多笔记和源码请访问公众号

原文链接:https://mp.weixin.qq.com/s/IE9u7iJ2kgzMNKxucBrOkg

公众号回复:
A*简装版
获取源码

技术摘要

A*寻路

四方向和八方向

二叉堆(最小堆)

目标不可抵达时返回最近的可抵达区域

禁止穿越障碍物拐角

双向A*寻路

多层A*

多单位分帧寻路

多单位间相互碰撞

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

四方向和八方向

在检索相邻格子时候,判断是否是对角线

二叉堆

OpenList需要实时添加节点,而且每次取出最小值的节点,所以采用二叉堆(最小堆)作为开启列表的容器更合理一些

最小堆:根结点的键值是所有堆结点键值中最小者

关于二叉堆的实现:

https://eloquentjavascript.net/1st_edition/appendix2.html

https://www.npmjs.com/package/heap

均可使用

search(grid: Grid, startX: number, startY: number, endX: number, endY: number, closest = 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中同时出现

然后以同时出现的节点和当前节点分别进行回溯得到节点数组

拼接两个数组后再把终点节点放进数组得到的就是最终路径

允许穿过障碍物拐角

禁止穿过障碍物拐角:

禁止穿越障碍物拐角时,只需要在获取当前节点的相邻节点时多一步判断即可:

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*

当前节点和目标节点距离较远时,使用尺寸比较大的格子进行检索,当接近目标时,切换到较小尺寸的格子进行检索

多单位分帧寻路

多单位进行A*寻路时,可以把他们放进一个队列,每帧对其中N个单位进行寻路,这样可以缓解一帧内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

46赞

二叉堆版本正在路上:joy:

你可以做得更好,终极版本,应该是 (二叉堆排 + 双向A*)

1赞

mark

mark

大佬,你怎么撤回了·····
多谢大佬指点,双向A*已get~

mark

期待版本,坐好沙发,哈哈

:ox:的一P

大佬,你自己没有在用的么·····
双向寻路我发现一个问题······
就是当目标不可到达的时候,就尴尬了············

mark

单向搜索不稳定,而且容易退化,双向搜索更加稳定和快速相遇

嗯,在目标点可以到达的时候确实比单向的要快~
就是当目标点不可抵达,需要以离目标点为新点的时候,双星,似乎不如单星
那就分两种情况吧~

http://qiao.github.io/PathFinding.js/visual/

大佬,这个算法怎么写的?我想做这种类型的逻辑然后自动寻路

mark

我上边的代码可以直接拿来用啊
用法很简单,new 一个grid,然后setWalkable
然后调用AStar,参数就是起始点和目标点,然后~得到路径。就想玩就是你的事了

(⊙o⊙)…
我刚想回复你·····
http://qiao.github.io/PathFinding.js/visual/
这个链接,可以清楚的看到 各种算法,包括你刚说的 跳点

1赞

大佬 牛批 A*算法 插眼

大佬,我下载了你那个工程,是只有pathFinding那个脚本才有用的是吗?