Unity 算法 之 A星(A Star/A*)寻路算法实现和封装,并带动态演示Demo
Demo 使用操作说明
1、按空格可以刷线地图,更新地图的障碍物位置(动态随机设置)
2、鼠标左键设置开始点位置
3、鼠标右键设置目标点位置
4、开始点和目标点都不为空,即会动态绘制路径
寻路原理
1)首先有一张一定宽高的地图 (定义好 Point 点的地图,其中 Point 中有 IsWall 属性)
2)设定开始点,和目标点
3)传入 FindPath 开始寻找较短路径,找到返回true,否则 false
4)为 true 就可以通过 目标点的父亲点的父亲点的父亲点,直到父亲点为开始点,这些点集合即是路径
5)FindPath 寻找原理
(1)开列表,关列表初始化
(2)添加开始点到开列表,然后获得周围点集合,接着又把开始点从开列表中移除,并添加到关列表
(3)判断这些周围点集合是否已经在开列表中,不在则更新这些点的F 和 父亲点,并添加到开列表;再则重新计算G值,G较小则更新GF 和父亲点
(4)从周围点集合中找到 F 最小的点,然后获得周围点集合,接着又把找到 F 最小的点从开列表中移除,并添加到关列表
(5)接着执行第 3) 步骤
(6)直到目标点被添加到开列表中,则路径找到
(7)否则,直到开列表中没有了数据,则说明没有合适路径
1