A* search algorithm
与广度优先算法不同的是 A*不会去探索所有的边界方块,而是选择当前“代价”最低的方块进行探索.
代价可以被分为:当前(路程)代价,又常被表示称f-cost,你从出发开始走了多少格子当前代价就是几.另一部分代价叫做预估代价,用来表示当前方块到最终方块大概需要走多少步,并不是一个精确的数值,也不代表一定会走这么多步.不过会用这个估计值来指导算法去优先探索更有希望的路径.
最常遇到的代价有欧拉距离(Euler distance) (x1-x2)^2+(y1-y2)^2,也就是两点间的直线距离,当然还有更容易计算的曼哈顿距离(Manhattan distance),也就是两点在竖直方向和水平方向的距离总和,|x1-x2|+|y1-y2|=14,曼哈顿距离不用开方,速度快 ,所以我们这里就用它来充当“预估代价,接下来把这两个代价想加,优先挑选优先挑选总代价最低的方块进行探索.会少走不少弯路,也一定是最短路径.
代码实现:
def a_star_search(graph,start,goal):
frontier=priorityQueue()
#frontier中存放了这一论探测过的所有边界方块,另外它是一个优先队列,也就是说他能通过代价自动排序并没次取出代价最低的方块
frontier.put(start,0)
#队列里面先存放一个元素,那就是起点
came_from={}
#是一个从当前方块到之前方块的映射;代表路径的来向
cost_so_far={}
#代表了方块的当前代价
came_from[start]=None
cost_so_far[start]=0
#这两行将起点的came_from置空,并将起点的当前代价设置成0,保存算法数据的有效性
while not frontier.empty():
current=frontier.get ()
if current==goal:
break
#接下来只要frontier这个队列不为空循环就会一直执行下去;每次循环,算法从优先队列里抽取出代价最低的方块然后检测这个是不是终点块,如果是,算法结束,否则再继续执行下去
for next in graph.neighbors(burrent):
#接下来算法会对这个方块上下左右的相邻块,也就是这里next表示的方块进行如下的操作
new_costs=cost_so_far[current]+graph.cost{current,next}
#算法会先去计算这个next方块的”新代价“,它等于之前代价加上从current到next的代价,由于用的是网格,所以后部分是一
if next not in cost_so_far or new_cost<cost_so_far[next]
cost_so_far[next]=new_cost
priority=new_cost+heuristic(goal,next)
#只要next块没有被探测过,活着next的当前代价比之前找到的还要低,就把它加入到优先队列里
并且这里的总代价等于“当前代价”+“预估代价”;预估代价在这里用到的是之前讲道德曼哈顿距离
frontier.put(next,priority)
came_from[next]=current
return came_from,cost_so_far
如果我们把整张地图抽象成网格的形式,图的结点太多遍历起来会非常低效,于是我们可以把网给地图简化成节点更少的路标形式(Waypoints),需要注意的是这里任意两个节点直接的距离就不再是1了,而是结点之间的实际距离.
我们还可以用自上而下分层的方式来存储地图,比如四叉树(Quad Tree),又或者像Unity中使用的导航三角网(Navigation Mesh),这样我们的算法速度会得到进一步优化