本教程详细介绍了如何在 python 中实现网格地图的路径规划。利用类似广度优先搜索的策略，从起点开始，逐步将可通行节点标记为指向起点的方向。一旦到达目标点，即可通过回溯这些方向，高效地重建出从起点到目标的最优路径。文章包含示例代码，帮助读者理解并应用此寻路方法。
路径规划是人工智能和计算机科学中的一个基本问题，广泛应用于游戏开发、机器人导航和物流优化等领域。本教程将重点介绍如何在二维网格地图中寻找从起点到终点的最短路径。
我们的地图表示为一个嵌套列表（即二维数组），其中包含以下几种值：
目标是编写一个 Python 函数，能够：
需要注意的是，尽管问题提及 A* 算法，但针对无权图（即所有可通行路径的成本相同，例如本例中每一步移动成本都视为1）寻找最短路径时，广度优先搜索（BFS）是一种简单且有效的算法，它能够保证找到最短路径。本教程将基于 BFS 的思想实现路径填充和回溯。
立即学习“Python免费学习笔记（深入）”；
首先，我们定义一个示例地图和一些常量，包括起点、终点以及用于标记方向的符号。
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, 2
destinationRow, destinationColumn = 2, 15
sourceSymbol = "*"
destinationSymbol = "$$$"
# 定义方向符号
up = "^"
down = "v"
right = ">"
left = "<"
# 在地图上标记起点和终点
mapList[sourceRow][sourceColumn] = sourceSymbol
mapList[destinationRow][destinationColumn] = destinationSymbol
def print_map(map_data):
"""辅助函数：打印地图"""
for row in map_data:
print(" ".join(map(str, row)))
print("-" * 40)
print("--- 初始地图 ---")
print_map(mapList)这一步的目标是从起点开始，向所有可通行的相邻节点扩散，并用方向符号标记这些节点。每个方向符号都指向其父节点（即扩散过程中上一步到达的节点），这样最终我们可以从终点沿着这些符号回溯到起点。
我们使用一个队列 tempList 来实现 BFS。每次从队列中取出一个点，检查其四个相邻点：
# 用于 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 # 找到终点，停止扩散
当 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}")
break
print("--- 最终路径地图 ---")
print_map(mapList)为了方便使用，我们可以将上述逻辑封装到一个函数中。
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* 路径规划教程的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
312
收藏
