ES6 实现 A 星寻路算法

说明

这是自己用 ES6 语法结合 HTML5 中 canvas 元素绘图 API 实现的 A 星寻路算法。A 星寻路算法是一种具有启发性的寻路算法。寻路的意思很简单：给起始点和终点，找出到达终点的路径，在寻找路径的过程中，避开障碍物。启发性就有意思了，它是 A 星算法在寻路效率上优于其他算法的一个特征。意思是指，它有能力确保在每一次按路径移动时移动的代价最小。

核心思想

你也许会听过这样一个问题：如何找到迷宫的出口？答案就是：一直贴着所在位置墙壁的右侧前进。如果迷宫有出口的话，就一定能找到。寻找迷宫的出口，就是一种寻路。上述答案采用的方式是一种遍历的思路，如果运气不好的话，可能得走过迷宫的每一处地方才能找到出口，运气好坏取决于你所处的起点。A 星算法就显得“聪明”一些，它的核心公式如下：

F = G + H

其中 F 指移动到当前位置的移动总代价，G 指从起点移动到当前位置的移动代价，H 指从当前当前位置移动到终点的移动代价。

在这个项目中，为了尽可能地简化问题，将地图划分为十分规整的方块，并规定从一个方块移动到相邻方块的移动代价为 1。且只能上下左右移动，不能在斜对角方向上移动。在这种情况下，从一个方块移动到对角方块的移动代价会是 2，如果允许沿斜线移动，那么移动代价会是 Math.sqrt(1 * 1 + 1 * 1) ≈ 1.4 （勾股定理）。

这样定义的移动代价也被称为“曼哈顿距离”，名称来源于美国的曼哈顿市。曼哈顿市的街道布局呈网格状分布，如果想从市中一个地方到另一个地方去，只有沿街道绕路过去，不能通过对角线直接到达，这样理解会更加形象。A 星算法中，每一次寻路移动，都按照最小的 F 值前进。F 值什么时候最小呢？就是在 G 和 H 同时最小的时候，此时选择出来移动到的目标点在约束下与起点和终点的距离同时达到最小。以此循环，每一步选择 F 值最小的点，直到找到终点。将每一步找到的点记录下来，就形成一条从起点到达终点的路径，寻路结束。

算法实现

算法需要准备两个列表，一个开放列表用于存储待检查的点，一个关闭列表用于存储不再考虑的点。

1. 首先将起点设为当前点，并将起点放入关闭列表。
2. 检查当前点周围可到达的点（此项目中不允许沿斜线移动，所以最多检查相邻的上、下、左、右四个点），可达的意思是此点存在，且不为墙壁，同时既不在开放列表中，又不在关闭列表中。将可达的点设为当前点的子对象（用于最后回溯），然后将可达点放入开放列表。
3. 检查开放列表中的每一个点，找到 F 值最小的点。注意 F 值为最小的点可能有多个，此时还要检查取出点与当前点的距离（曼哈顿距离）。最终保证取出来的点满足两个条件，一是 F 值最小，二是与当前点距离最近。如果经历这样的筛选，取出的点仍有多个，那就在其中随便取一个，遇到岔路了，“条条大路通罗马”是这种情况的最好说明。
4. 将取出点从开放列表中删除，放入关闭列表，并设为当前点。
5. 重复 3 ~ 4 步，直到终点放入了关闭列表（寻路成功，找到了终点）或者开放列表为空（寻路失败，所有待检查的点都无法通行，走入了死胡同）。
6. 如果寻路成功，从关闭列表的最后一个点（终点），找到此点的父对象，一路回溯，最终找到终点，将这些点记录下来，就是找到的最短路径。

演示

链接

GitHub DEMO

思考

A 星算法为什么能寻路成功？它有两个重要的前置条件：

1. 知道起始点。
2. 按照最小的 F 值前进。

这就是算法的严谨与美丽，有约束，有条件，指出方向，结果是必然的。人生呢？如果要找寻人生迷宫的出路，怎样才能找到一条最短路径？有些人不知起点，有些人不知终点，有些人贴着墙壁行走。自己属于哪一种？我不知道，谁又能知道呢？