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实现

等等,还没写

一直在想脚手架

最初用的就是vue-cli,但每次都是向导式的配置,很不透明,希望能从尽量简单的系统开始研究。然后就发现了poi。

vue-cli创建好的项目不仅配置好了代码检查、babel、ts、css预处理等功能,还带一个目录结构,即main.js、App.vue等。

poi创建好的项目目录是空的,我可以稍微做两步。比如新建一个js文件,然后createElement,appendChild,再启动dev-server,我一下就明白了入口文件(entry)是什么意思(虽然以前也明白,但理解方式不同),那就是编译好的代码从这里执行,打包的时候,如果用到了某个模块,在引入的时候,那个模块的代码就会执行,但这个模块导出的东西可以在之后用,循环引用时模块可能不会被编译到最终的文件等等。

然后是Vue的使用,如果用Vue-cli,那么就不会注意到main.js里的new Vue,实际上这里新建了一个根实例,并且挂载到一个html元素上($mount)。它的render属性是一个函数,接受一个渲染函数h,并且返回h(App),App是引入的一个vue组件(被vue-loader从vue文件编译成了js)。为什么用render而不用template呢,因为vue通常用runtime版本的,不带编译模板的功能,需要build时编译好(编译vue文件),如果用template的话,main.js或index.js又不会被编译,所以就会出错。所以可以引入vue.esm,也可以自己写渲染函数,也可以引入一个vue组件,再在vue组件内引用别的文件。