A*/A星/AStar算法 视频笔记,Unity代码实现
视频来源:https://www.bilibili.com/video/av23095766?from=search&seid=5873495875101903731
代码来源:https://www.jianshu.com/p/22dfcca70064
平面划分若干方块,假设红色是起点紫色是终点棕色为障碍物
从起点移动时,有8个方向
直线方向有前,后,左,右,每个直线方向的方格认为需要走10(或1)
斜线方向,左上,左下,右上,右下,每个斜线方向的方格,认为需要走14(或1.4)
因为正方形的斜边是边长的根号二倍,近似取1.4
直线10
斜线14
起点周围的8个方格,都是我们可能移动的下一点。我们用一个变量g 来存到下一点需要的距离。也就是10或者14
我们接下来估计一下到终点可能需要的距离的英文多少,从起点开始的8个方向我们任意选一个方向,作为下一个起点。
我们只算直线距离忽略障碍
从新的起点开始(假设我们选择的是画圆圈的这个地方),到终点的距离,只算直线就是8个方格,也就是80
同样的方法我们算出其他几个方格为起点时的距离
每个方格对应红色值我们用变量h 来存
现在我们知道,
g 可能是10或者14
h 则需要我们去计算,可能是80120110等
用一个变量F = G + H,显然F 就是红色的起点部分经由某个方向到终点的估计距离,也就是下图的紫色值
显然90这个值最小,我们选择下一步走到这里来,忘掉前面的计算,再次对周围8个方向进行上面的运算
显然下一步我们就要走74这个方格了,继续往下算,当然,当周围8个方格中有障碍时,障碍方块可以不要计算
最后我们的路径就差不多是这样了。