1-heuristic寻路简介

heuristic是启发式的意思，因此heuristic寻路就是启发式寻路，其所用的算法是贪心算法。

启发式寻路之所以是启发式的，是因为在寻路的过程中，我们会给它一个提示，比如你每迈出一步的时候，要朝离目标点最近的位置迈出。

【资料图】

在上图中，从start节点向end节点寻路的时候，它所迈出的每一步都是离end最近的。

可是每一步最近不代表整条路就是最近的，比如它从上面越过障碍物会更近。

这种只在乎眼前的利益，不考虑全局得失的算法，就是贪心算法。

启发式寻路虽然有很大的缺陷，但它是寻路的基础算法之一，以后我们可以以此为基础进行不断优化。

2-ts代码实现

以下代码是寻路逻辑的实现。至于效果的显示，我是用canvas做的，不算重点，我就不贴出来了，想要的可以微信我(1051904257)。

解释一下上面的代码。

mapSize是地图尺寸，它没有单位的概念，不要将其理解为像素。

start起点、end终点的概念无需多说，其值是其在地图中的索引位。

我们可以通过getPos(n: number)方法获取索引位所对应的行列位。

obstruction 是障碍物，其内元素是构成障碍物的节点的索引位。

road 是探索出的道路，其内元素是构成道路的节点的索引位。

basic 是探索基点，比如一开始的探索基点是起点，从起点迈出离终点最近的一步后，我们会以这一步的节点为基点，继续往前探索。

state 是探索状态，finding探索中、fail探索失败、success探索成功。

explorer() 是寻路方法，它会遍历基点周边的8个节点，然后找到离终点最近的点，并记下探索状态state。state为finding时，会继续探索，否则停止探索。

当然，为了便于查看寻路的过程，我们也可以逐步寻路。

整体的heuristic寻路逻辑便是如此，不过它还有一个严重的bug，那就是可能会被死胡同堵死。

在数字为8的黑色格子处，已经无路可走了，便认为探索失败了。

在这种情况下，我可以尝试让它回头，回到上一个路口4，不再走这条死路，而是走离终点较近的另一条路。

接下来，我们就解决一下这个Bug。

3-回头是岸

突然想起一句话：学海无涯，回头是岸。人生路漫漫哪有一帆风顺的，遇到过不去的可以绕道试试。

言归正传，继续说一下heuristic遇到死胡同时，如何回头是岸，绕道而行。

整体代码如下：

效果如下：

说一下我们添加了哪些代码。

explored 是探索过的基点集合，其中元素的key就是节点的索引位，value 是其前面的点。

explored 可以让我们记住来路，以便回头。

explorer(extrude?: number) 方法中有了一个extrude参数，表示要在遍历周围8点时，排除的点。此点用于在会回头时，不再走过去被堵死的老路，而是走一条新路。

其排除逻辑如下

被堵时的回头逻辑如下：

走出死胡同时，需要把死胡同里的路删掉。

关于heuristic寻路咱们就说到这，下一章我们会再说更优良的寻路方法。

关键词：