A*寻路算法

对于初学者而言,A*寻路已经是个比较复杂的算法了,为了便于理解,本文降低了A*算法的难度,规定只能横竖(四方向)寻路,而无法直接走对角线,使得整个算法更好理解。

简而言之,A*寻路就是计算从起点经过该点到达终点的路程,并使得总路程达到最小值,因此引入一个公式:

F=G+H;

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

文本规定只能横竖(四方向)寻路,那么设置G=1,那么如果计算H的值?

由于H是预计路程,则在计算H时将不考虑障碍点,直接计算H到终点的路程,通过行列差来计算得到。

A*算法的核心就是按照这个公式逐步查找,直到查找到终点,算法引入开启列表和关闭列表,用于存储被开启和关闭的节点。

初期,地图上的节点都是未开启也未关闭的初始状态,当检测到一个节点时,就要将其周围节点存入开启列表中,通过计算父节点到各子节点的F值来检测,选取子节点中F值最小的节点放入关闭列表中,并将该节点的父节点改为目前的检测点(即该节点成为之后节点的父节点),然后开始查找下一个节点,如此循环,直到查找到终点。

本文为了降低算法难度,因此限制了寻路条件为四方向,后期可以加入斜方向的查找,即可以八方向寻路。

A*寻路算法的具体实现,详见代码。

效果展示

GitHub开源

博文中的A*寻路算法已开源在GitHub上,希望与大家一起分享、改进!

开源地址 https://github.com/twobin/AStarPathFinding

上一篇:Django REST framework+Vue 打造生鲜超市(十二)


下一篇:HighCharts基本使用