本教程详细介绍了如何在 python 中实现网格地图的路径规划。利用类似广度优先搜索的策略，从起点开始，逐步将可通行节点标记为指向起点的方向。一旦到达目标点，即可通过回溯这些方向，高效地重建出从起点到目标的最优路径。文章包含示例代码，帮助读者理解并应用此寻路方法。
1. 简介与问题定义
路径规划是人工智能和计算机科学中的一个基本问题，广泛应用于游戏开发、机器人导航和物流优化等领域。本教程将重点介绍如何在二维网格地图中寻找从起点到终点的最短路径。
我们的地图表示为一个嵌套列表（即二维数组），其中包含以下几种值：
0: 代表墙壁或不可通行区域。1: 代表空地或可通行区域。2, 3, 4: 代表不同类型的障碍物，但同样不可通行。*: 代表路径的起点。$$$: 代表路径的终点。
目标是编写一个 Python 函数，能够：
从起点开始，在地图中填充表示回溯方向的符号，直到到达终点。从终点开始，沿着这些方向符号回溯，以重建出最短路径。返回包含该路径的地图（路径上的节点被特殊符号标记）。
需要注意的是，尽管问题提及 A* 算法，但针对无权图（即所有可通行路径的成本相同，例如本例中每一步移动成本都视为1）寻找最短路径时，广度优先搜索（BFS）是一种简单且有效的算法，它能够保证找到最短路径。本教程将基于 BFS 的思想实现路径填充和回溯。
立即学习“Python免费学习笔记（深入）”；
2. 地图表示与基本设置
首先，我们定义一个示例地图和一些常量，包括起点、终点以及用于标记方向的符号。
mapList = [ # 示例地图，你可以根据需要修改 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 2, 2, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 2, 2, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 2, 2, 3, 3, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 2, 2, 3, 3, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 0, 0], [0, 0, 2, 2, 2, 2, 1, 1, 2, 2, 3, 3, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 2, 2, 2, 2, 1, 1, 2, 2, 3, 3, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 3, 3, 3, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0], [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],]# 定义起点和终点坐标及符号sourceRow, sourceColumn = 6, 2destinationRow, destinationColumn = 2, 15sourceSymbol = "*"destinationSymbol = "$$$"# 定义方向符号up = "^"down = "v"right = ">"left = "<"# 在地图上标记起点和终点mapList[sourceRow][sourceColumn] = sourceSymbolmapList[destinationRow][destinationColumn] = destinationSymboldef print_map(map_data): """辅助函数：打印地图""" for row in map_data: print(" ".join(map(str, row))) print("-" * 40)print("--- 初始地图 ---")print_map(mapList)
3. 路径填充：广度优先搜索 (BFS) 策略
这一步的目标是从起点开始，向所有可通行的相邻节点扩散，并用方向符号标记这些节点。每个方向符号都指向其父节点（即扩散过程中上一步到达的节点），这样最终我们可以从终点沿着这些符号回溯到起点。
我们使用一个队列 tempList 来实现 BFS。每次从队列中取出一个点，检查其四个相邻点：
如果相邻点是终点，则停止扩散。如果相邻点是可通行区域 (1)，则将其标记为指向当前点的方向，并加入队列。
# 用于 BFS 队列tempList = [(sourceRow, sourceColumn)]def fill_with_directions(current_point: tuple, current_map: list): """ 从当前点开始，向四周可通行区域填充方向符号。 方向符号指示从该点回溯到父节点（即当前点）的方向。 """ r, c = current_point # 定义四个方向的偏移量：(dr, dc) # (1, 0) -> 下, (-1, 0) -> 上, (0, 1) -> 右, (0, -1) -> 左 neighbor_offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上，下，左，右 for dr, dc in neighbor_offsets: nr, nc = r + dr, c + dc # 相邻点的坐标 # 检查边界 if not (0 <= nr < len(current_map) and 0 <= nc < len(current_map[0])): continue # 如果到达终点 if current_map[nr][nc] == destinationSymbol: return True # 找到终点，返回True # 如果相邻点是可通行区域 (1) if current_map[nr][nc] == 1: # 根据相对位置填充方向符号 if dr == -1: # 相邻点在上方，当前点在下方，所以相邻点应指向下 current_map[nr][nc] = down elif dr == 1: # 相邻点在下方，当前点在上方，所以相邻点应指向上 current_map[nr][nc] = up elif dc == -1: # 相邻点在左方，当前点在右方，所以相邻点应指向右 current_map[nr][nc] = right elif dc == 1: # 相邻点在右方，当前点在左方，所以相邻点应指向左 current_map[nr][nc] = left # 将新填充的点加入队列，以便后续探索 tempList.append((nr, nc)) return False # 未找到终点# 执行 BFS 扩散while tempList: current_point = tempList.pop(0) # 取出队列中的第一个点 if fill_with_directions(current_point, mapList): print("--- 填充方向后的地图 (到达终点) ---") print_map(mapList) break # 找到终点，停止扩散
4. 路径回溯与重建
当 fill_with_directions 函数返回 True 时，表示我们已经从起点扩散到了终点。此时，地图上除了起点和终点，所有路径上的可通行节点都被标记了方向符号。接下来，我们将从终点开始，沿着这些方向符号反向追踪，直到回到起点，并将路径上的节点标记为 *。
# 从终点开始回溯current_path_point = None# 首先找到终点周围哪个点被标记了方向，作为回溯的起点# 定义四个方向的偏移量neighbor_offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 上，下，左，右possible_signs = [up, down, left, right]for dr, dc in neighbor_offsets: nr, nc = destinationRow + dr, destinationColumn + dc # 检查边界 if not (0 <= nr < len(mapList) and 0 <= nc < len(mapList[0])): continue if mapList[nr][nc] in possible_signs: current_path_point = (nr, nc) break# 回溯并标记路径while current_path_point: r, c = current_path_point current_item = mapList[r][c] # 如果回溯到起点，则停止 if current_item == sourceSymbol: current_path_point = None break # 将当前点标记为路径的一部分 mapList[r][c] = '*' # 根据当前点的方向符号，移动到下一个回溯点（即其父节点） if current_item == up: # 当前点指向父节点上方，说明父节点在当前点下方 current_path_point = (r + 1, c) elif current_item == down: # 当前点指向父节点下方，说明父节点在当前点上方 current_path_point = (r - 1, c) elif current_item == left: # 当前点指向父节点左方，说明父节点在当前点右方 current_path_point = (r, c + 1) elif current_item == right: # 当前点指向父节点右方，说明父节点在当前点左方 current_path_point = (r, c - 1) else: # 理论上不应该发生，除非路径断裂或遇到非方向符号的可通行区域 print(f"Error: Encountered unexpected item {current_item} at {current_path_point}") breakprint("--- 最终路径地图 ---")print_map(mapList)
5. 完整函数封装
为了方便使用，我们可以将上述逻辑封装到一个函数中。
def find_path_in_map(initial_map: list, start_coords: tuple, end_coords: tuple): """ 在网格地图中寻找从起点到终点的最短路径。 Args: initial_map (list): 嵌套列表表示的地图。 0: 墙壁, 1: 可通行, 2/3/4: 障碍物。 start_coords (tuple): 起点坐标 (row, column)。 end_coords (tuple): 终点坐标 (row, column)。 Returns: list: 包含标记路径的地图，如果找不到路径则返回None。 """ # 创建地图的深拷贝，避免修改原始地图 current_map = [row[:] for row in initial_map] sourceRow, sourceColumn = start_coords destinationRow, destinationColumn = end
以上就是使用 Python 实现网格地图 A* 路径规划教程的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1378339.html
微信扫一扫 
支付宝扫一扫 
