A-star寻路记

前段时间研究小游戏的同学用过A*算法寻路,当时我只是有个印象,恰巧最近有同学做数模问我,我也只能硬着头皮看一看了。先声明,太low或者有差错也不管哈。

题目要求

给定一个n*n的地图,其中有障碍物和跨越难度各不相同的地形,现要求找到总代价最小的路径。

如果光溜溜地摆出地图,要凭空想出一个方法挺难的,而且最重要的是复杂度也许很高。但我们有a-star。

启发式算法

这个名词大家一定不陌生,但对它的含义可能一知半解。常见的启发式算法如模拟退火算法、神经网络、蚁群算法等,它们在面对最优化问题时,并不从某个精妙的逻辑出发(像数学证明那样),而是以直观的感受构建算法,消耗有限的时间和空间尽量得到接近最优的可行解(但通常无法证明)。

A-star

直观地讲,你要找最小路径,那只能从出发点开始,一步步地试出来,不过呢,复杂度不仅达到了n次方,还有可能存在回路。A-star算法提供的解决方案是,用两张表分别存储被考虑用来寻找最短路径的区块(open)与不再考虑用来寻找最短路径的区块(closed),同时启发式算法能保证尽量选择较优的路径。

“代价”优先搜索

最基础的,从起始点出发,每次从open表中选总代价最小的项(F最小),向周围8个方向前进(将这些区块加入open表),这是A-star的主循环。

剪枝

新遇到的区块可以加入open列表,但扫描后的点会加入closed列表。

路径

搜索的路径需要被记录,可以用一个栈结构,从open列表进入时入栈,如果一个区块周围不再有符合要求的区块则回退。

要求

不能在closed表中,不能超出边界,不能是建筑,如果已在open列表,当前G值大于open表中记录的G值也不符合要求。

启发式

F=G+H

F即总代价,包括G实际经过的路程和H估算的该点离终点的距离。

估计路径

可以直接用笛卡尔距离,也可以直线+拐弯etc,总之提供一个大概的参考值。

JavaScript实现

等等,还没写

发表评论

电子邮件地址不会被公开。