【A*/A star】启发式路径搜索算法
本帖最后由 Lthero 于 2021-5-31 18:38 编辑A*教程
视频：https://www.bilibili.com/video/BV1bv411y79P?from=search&seid=1736083035601105399
图文：https://www.redblobgames.com/pathfinding/a-star/introduction.html
redblob有代码，我在此基础上修改了一些内容，并做了可视化
核心代码
'''A star算法部分
https://www.bilibili.com/video/BV1bv411y79P?from=search&seid=1736083035601105399
https://www.redblobgames.com/pathfinding/a-star/introduction.html
'''
# 每个结点的附近四个结点
def neighbors(the_one):
return [, the_one - 1], + 1, the_one], , the_one + 1],
- 1, the_one]]
# 当前代价
def weight(first, second):
return 1
# 预估代价，采用欧式距离
def heuristic(first, second):
x_dis = abs(first - second)
y_dis = abs(first - second)
return math.sqrt(pow(x_dis, 2) + pow(y_dis, 2))
# 主代码
def A_star(the_map):
# 迷宫长度宽度
len_row = len(the_map)
len_col = len(the_map)
# 起点
start = , man_y]
# 出口
target = , door_y]
# 等待遍历的点，左边是当前的总代价=当前（距离起点）代价+预估代价
frontier = [(0, start)]
# 记录当前结点的来向结点
came_from = {}
# 记录已经走过的结点，用字典存，key是结点的(x,y)降维后的一个数字,如下面,value是当前代价
# start * 3.141 + start * 2.727 只是个标识，数字随便乘的，当作cost_so_far的key
cost_so_far = {}
came_from * 3.141 + start * 2.727] = None
cost_so_far * 3.141 + start * 2.727] = 0
# 等待遍历的点不为空
while len(frontier) != 0:
# 弹出总代价最小的结点
ww = frontier.pop(0)
current = ww
# 当前结点就是出口，退出
if current == target and current == target:
break
# 遍历当前结点的上下左右的邻居结点
for next_one in neighbors(current):
# 下面都是对这个邻居结点操作
# 邻居结点没超过地图范围 && 邻居结点还在障碍物中
if 0 <= next_one <= len_col and 0 <= next_one <= len_row and next_one not in barriers:
# 计算 到达邻居结点的当前代价
new_cost = cost_so_far * 3.141 + current * 2.727] + weight(current, next_one)
# 如果邻居结点不在已经走过的集合中 或者 走邻居结点的代价小于走当前结点的代价
if next_one * 3.141 + next_one * 2.727 not in cost_so_far.keys() or new_cost < cost_so_far[
current * 3.141 + current * 2.727]:
# 记录到邻居结点的当前代价是new_cost
cost_so_far * 3.141 + next_one * 2.727] = new_cost
# 计算 邻居结点的总代价
priority = new_cost + heuristic(target, next_one)
# 如果下一个结点是终点，res_flag设置1，提前退出
if next_one == target and next_one == target:
came_from * 3.141 + target * 2.727] = current
res_flag = 1
else:
#不是终点，把这个邻居结点放在frontier中
came_from * 3.141 + next_one * 2.727] = current
frontier.append((priority, next_one))
#重新排序，确保总代价最小的结点在第一个
frontier.sort(key=lambda x: x)
if res_flag == 1:
break
#输出路径
p = target
path.append(, target])
while came_from * 3.141 + p * 2.727] != start:
path.append( * 3.141 + p * 2.727], came_from * 3.141 + p * 2.727]])
p = came_from * 3.141 + p * 2.727]
path.append(, start])
came_from.clear()
cost_so_far.clear()
一般迷宫
特殊情况
这种情况，用迪克斯特拉算法，程序运行很慢，我等了5分钟没出结果。
但A*算法只用了不到1秒。
这个迷宫也太特殊了吧 sam喵喵 发表于 2021-4-27 21:42
这个迷宫也太特殊了吧
普通的迷宫当然有解，这种情况下迪克算法或者深度优先时间复杂度就太高了，突显下A*的特点吧 学习一下 大佬 资源里没有close.png duanshifeng1994 发表于 2021-6-12 14:39
大佬 资源里没有close.png
我是随便找的图，表示障碍的。你可以替换下 马一下 可能会用到 redblobgames不错~~
页:
[1]