[量化投资接口]A Star PathFinding 寻路算法理论基础

A*寻路是用来解决什么问题的

用来计算玩家行进的最短路径的在计算的过程中避障求得最短的路径

A*寻路的基本原理

A*算法的基本逻辑是,从起点开始,搜索周围的节点进行排序比较,得到最优点,并将最优点作为新的起点再次搜索比较,重复这个搜索逻辑,直至找到终点,搜索结束,返回最短路径

A*寻路的详细原理

基于原理进行详细原理的拓展,如何得到最优点?

通过寻路消耗代价的计算公式:F=G+H,G表示的是节点距离起点的距离,H表示的是通过曼哈顿算法求得节点距离终点的距离,也就是横向距离+纵向距离的值;将节点中G和H相加得到F,也就总的代价

每次搜索时,都会将起点的周围节点放入开启列表当中,比较得到F值最小的最优点,每次把周围的节点放入开启列表时,需要进行判断**

是不是阻挡,是阻挡不放

是否在开启列表或者关闭列表中,在就不放,不在就放

搜索得到最优点,将最优点放入关闭列表,每次将存放都会进行判断该点是否是终点,如果是,寻路结束,如果不是则寻路继续

寻路结束,如果得到最短路径?

列表中的节点都包含F值和当前节点的父节点指针,父节点也就是在搜索时的起点,通过指针回溯,得到最短路径

else,如果是死路,那么在不断的搜索过程中,关闭列表存放的节点数量会越来越多,开启列表会越来越少,直至为空,说明走不到终点,为死路

寻路消耗公式

f=g+h

g值:,假设一个格子的单位为1,那么横格距离是1,斜格是4

h值::x+y

开启列表

一个容器,存放起点周围格子的寻路消耗的信息,每一个格子信息都包含

排序后,找出最小f值的格子,将他存放到关闭列表当中

每次把周围的点放入开启列表时,需要进行判断

是不是阻挡,是阻挡不放

是否在开启列表或者关闭列表中,在就放,不在就不放

关闭列表

存放最优点的容器,每次最优点放入关闭列表的时候,需要进行判断该点是否是终点

如果是,寻路结束,如果不是则寻路继续

格子对象的父对象

这个信息才能真正找到搜索路径,特殊的情况,如果在几次搜索格子的时,发现周围点的f值可能会相同,因为我们的搜索逻辑是基于寻路消耗公式来执行的,当找到终点搜索结束时,返回搜索路径就是从终点开始回溯父节点指针,从而得到最短路径

如果开启列表为空,判断为死路

文章为作者独立观点，不代表股票自动交易程序化数据接口观点

[量化投资接口]2Redis 的 Java 客户端