原创文章,转载请联系作者
时光只解催人老,不信多情,长恨离亭,泪滴春衫酒易醒。
前言
最近接触了一个挺有意思的小课题,跟大家分享一下。就是利用A*
算法,来计算迷宫可行路径。有关这个算法的知识,大家可以看看
A星算法维基百科以及A星算法详解来稍作了解。
代码地址在此Maze,喜欢Python
的小可爱们可以拿去练练手。
提要说明
本题中的迷宫,是以宫格类型呈现的,在代码中的呈现为二维数组
。其次在迷宫中的移动,也只有上、下、左、右四个动作可选。如下所示:
其中1代表入口,2代表障碍物不可通行,3代表出口
1 | [[3, 2, 2, 2, 2, 2, 2, 2, 1], |
其实在A*算法
中,对单位搜索区域的描述为–节点nodes
。在本题中,我们可以把搜索区域视为正方形,会更简单一点。
A*算法逻辑解析
A*算法
的逻辑其实并不是很难,简化起来就是两个词:评估、循环。
从起点开始行动,首先找到起点周围可以行走的节点
,然后在这个节点中,评估
出距离终点最优(最短)的节点
。那么这个最优
节点,将作为下一步行动的点,以此类推,直至找到终点。
可以看到,在这个逻辑中,其实最重要的就是评估
这一步了。A*算法
的评估函数为:f(n) = g(n) + h(n)
g(n)
–代表移动到这个点的代价,在本题中均为1.因为只可以水平或者数值运动。要是斜角可以移动的话,那么这个值就为√2
h(n)
–从这个点移动到终点的代价,这是一个猜测值。本题中,将迷宫视作坐标系的话,那么h(n)
就是取和终点x、y各自差值的最小者。譬如点[4,2]和终点[1,1]的h(n)
取值为:1
代码实现
代码中对点的描述,均为实际值,并非以0为开始值计算。
定位起点和终点,使用列表存储四个移动命令,以下代码env_data
代表迷宫数组:
1 | # 上下左右四个移动命令,只具备四个移动命令 |
判断节点所有可执行的移动命令:
1 | def valid_actions(loc): |
拿到节点周围移动单位为1
的所有可到达点,不包括此节点:
1 | def get_all_valid_loc(loc): |
h(n)
函数体现:
1 | def compute_cost(loc): |
开始计算
使用road_list
来保存走过的路径,同时用另一个集合保存失败的节点——即此节点附近无可用节点,死胡同。
1 | # 已经走过的路径list,走过的路 |
看运行结果
结语
人生苦短,我用Python
。代码地址在此Maze,喜欢Python
的小可爱们可以拿去练练手。
在研究迷宫的过程中,发现生成迷宫的算法也是很有意思的,等忙完这段时间再去研究研究。嘻~
以上