使用 Python 实现网格地图 A* 路径规划教程

云晨大大_6531

发布时间：2025-11-07 11:40:41

1075人浏览过

来源于php中文网

原创

使用 Python 实现网格地图 A* 路径规划教程

本教程详细介绍了如何在 python 中实现网格地图的路径规划。利用类似广度优先搜索的策略，从起点开始，逐步将可通行节点标记为指向起点的方向。一旦到达目标点，即可通过回溯这些方向，高效地重建出从起点到目标的最优路径。文章包含示例代码，帮助读者理解并应用此寻路方法。

1. 简介与问题定义

路径规划是人工智能和计算机科学中的一个基本问题，广泛应用于游戏开发、机器人导航和物流优化等领域。本教程将重点介绍如何在二维网格地图中寻找从起点到终点的最短路径。

我们的地图表示为一个嵌套列表（即二维数组），其中包含以下几种值：

0: 代表墙壁或不可通行区域。
1: 代表空地或可通行区域。
2, 3, 4: 代表不同类型的障碍物，但同样不可通行。
*: 代表路径的起点。
$$$: 代表路径的终点。

目标是编写一个 Python 函数，能够：

从起点开始，在地图中填充表示回溯方向的符号，直到到达终点。
从终点开始，沿着这些方向符号回溯，以重建出最短路径。
返回包含该路径的地图（路径上的节点被特殊符号标记）。

需要注意的是，尽管问题提及 A* 算法，但针对无权图（即所有可通行路径的成本相同，例如本例中每一步移动成本都视为1）寻找最短路径时，广度优先搜索（BFS）是一种简单且有效的算法，它能够保证找到最短路径。本教程将基于 BFS 的思想实现路径填充和回溯。

立即学习“Python免费学习笔记（深入）”；

python学习

Python 编程学习助手 skill，面向零基础用户。当用户表达以下意图时触发： - 学习 Python 基础概念（变量、数据类型、循环、函数、类等） - 请求 Python 练习题或测验 - 请求审查或调试 Python 代码 - 请求 Python 项目实战指导（爬虫、数据分析、Web 开发等入门项目） - 泛化表述如"教我 Python""我想学编程""Python 怎么写""帮我学 Python" 此 skill

下载

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, 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)

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}")
        break

print("--- 最终路径地图 ---")
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

Linux怎么安装Python3以及管理工具pip

如何安全地使用 Python 重命名含元数据的音频文件

如何在 Pandas 中正确加载含连续尾部分隔符的 CSV 文件并保留所有空列

如何在Python 3.12中监控文件写入进度并显示进度条？

如何在Python中解析网页源码中的SVG映射字符加密？