一直想用js自己写写游戏啥的，所以之前花了些时间去研究寻路算法，在寻路算法中说的比较多的估计就是A*了，但是那时候觉得A*不是很好理解，没弄明白，所以我尝试了另外一种寻路算法，点击这里穿越，这种算法确实能准确的找到一条可行的路线，但也仅仅是可行，因为这种算法找出来的路线和最佳路线就完全扯不上边，本来可以走更短的距离到达终点，却非要绕一大圈，肯定不乐意了。所以我又回去折腾了一下寻径算法。

其实A*寻路算法就好比是上面那种比较蠢的算法的升级版吧，在那个算法的基础上引入了F,G,H这三个东西，那么他们是干什么的呢？

首先我们需要知道一个公式：F = G + H

其中，F 是从起点经过该点到终点的总路程，G 为起点到该点的“已走路程”，H 为该点到终点的“预计路程”。

寻路步骤：

1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.

2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A.

3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格

4. 从 "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块),检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑) 的方格. 如果这些方格还不在 "开启列表" 里的话, 将它们加入 "开启列表", 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的 "父方格" 为 C.

5. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 如果新的G值更低, 那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做.

就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表". 再继续找出它周围可以到达的方块, 如此循环下去...

那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经被找到.

最后以终点为起点通过 "父方块" 可以依次索引到最初的 "起始方块", 这样就得到了路径.

点击这里查看demo