春天是萌芽的季节，也是踏入开源世界的最佳时机。很多新手朋友问我：“我想参与开源，但一看那些大型项目的源码就头晕，该怎么办？”

我的回答通常是：找一个“小而美”的算法，从纸上推演开始，一行一行把它变成代码。

路径规划算法中的 A，正是这样一个完美的入门课题——它逻辑清晰、可视化效果直观、实现代码不到 200 行，却能让你体验到从“理解原理”到“写出可用工具”的完整创造过程。更重要的是，A 在开源社区中有大量优秀的参考实现（如 PythonRobotics），你可以轻松对照学习，甚至提交你的第一个 Pull Request。

今天，我们就一起动手，用 Python 实现一个可以跑在网格地图上的 A* 寻路器。不需要高深数学，不需要复杂环境，只需一个文本编辑器和对开源的热情。

---

第一步：在纸上推演，搞懂 A* 的心跳

在打开编辑器之前，我们先拿出一张草稿纸，画一个 5x5 的网格。假设起点在左上角 (0,0)，终点在右下角 (4,4)，中间有一些障碍物（用 X 表示）。

A* 的核心思想就一句话：每次从待探索的节点中，选一个“综合成本最低”的节点往外走。

这个综合成本由公式决定：

f(n) = g(n) + h(n)

• g(n)：从起点走到当前节点 已经花费的实际代价。

• h(n)：从当前节点走到终点的 预估代价（启发函数，Heuristic）。

• f(n)：总代价，越小越好。

在网格地图中，我们通常规定：

• 水平或垂直移动一步，代价为 1。

• 启发函数 h(n) 使用 曼哈顿距离：|x₁ - x₂| + |y₁ - y₂|（因为不能斜着走）。

现在，我们从起点 (0,0) 开始推演（假设无障碍物）：

当前节点	g(n)	h(n) (到 (4,4))	f(n)
(0,0)	0	8	8
邻居 (1,0)	1	7	8
邻居 (0,1)	1	7	8

你会发现，起点两个邻居的 f(n) 相同。算法会任选其一，然后继续探索。在纸上多画几步，你会感受到 A* 总是“聪明地”朝着终点的方向收敛——这就是启发函数在起引导作用。

理解了这一步，你就抓住了 A 的灵魂。* 接下来，我们把它翻译成 Python。

---

第二步：搭起骨架，用 Python 实现 A*

我们新建一个文件 astar.py。为了让代码清晰，我们定义两个类：Node（节点）和 AStar（算法主体）。

# astar.py
import heapq
from typing import List, Tuple, Optional

class Node:
    """网格中的节点"""
    def __init__(self, x: int, y: int, parent=None):
        self.x = x
        self.y = y
        self.parent = parent
        self.g = 0   # 实际代价
        self.h = 0   # 启发代价
        self.f = 0   # 总代价

    def __lt__(self, other):
        # 用于优先队列比较
        return self.f < other.f

接着，在 AStar 类中，我们实现核心搜索逻辑：

class AStar:
    def __init__(self, grid: List[List[int]]):
        """
        grid: 二维列表，0 表示可通行，1 表示障碍物
        """
        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0])
        # 四方向移动：上下左右
        self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def heuristic(self, a: Tuple[int, int], b: Tuple[int, int]) -> int:
        """曼哈顿距离"""
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    def is_valid(self, x: int, y: int) -> bool:
        """检查坐标是否在网格内且不是障碍物"""
        return 0 <= x < self.rows and 0 <= y < self.cols and self.grid[x][y] == 0

    def find_path(self, start: Tuple[int, int], end: Tuple[int, int]) -> Optional[List[Tuple[int, int]]]:
        """
        返回从 start 到 end 的路径（坐标列表），如果无路则返回 None
        """
        open_list = []          # 优先队列（最小堆）
        closed_set = set()      # 已访问节点坐标集合

        start_node = Node(start[0], start[1])
        start_node.g = 0
        start_node.h = self.heuristic(start, end)
        start_node.f = start_node.h

        heapq.heappush(open_list, start_node)

        while open_list:
            current = heapq.heappop(open_list)

            # 到达终点，回溯路径
            if (current.x, current.y) == end:
                path = []
                while current:
                    path.append((current.x, current.y))
                    current = current.parent
                return path[::-1]  # 反转，从起点到终点

            closed_set.add((current.x, current.y))

            for dx, dy in self.directions:
                nx, ny = current.x + dx, current.y + dy

                if not self.is_valid(nx, ny):
                    continue
                if (nx, ny) in closed_set:
                    continue

                neighbor = Node(nx, ny, parent=current)
                neighbor.g = current.g + 1
                neighbor.h = self.heuristic((nx, ny), end)
                neighbor.f = neighbor.g + neighbor.h

                # 如果邻居已在 open_list 中且当前路径代价更高，则跳过
                # 简化起见，我们允许重复入队，优先队列会自行处理最小值
                heapq.heappush(open_list, neighbor)

        return None  # 无路可走

代码不过 70 行，但已经包含了 A 的完整逻辑。* 你可以用下面的测试代码跑一下：

if __name__ == "__main__":
    # 定义一个 7x7 网格，0 为路，1 为墙
    grid = [
        [0, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 1, 0],
        [0, 1, 1, 1, 0, 1, 0],
        [0, 1, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0]
    ]

    astar = AStar(grid)
    path = astar.find_path((0, 0), (6, 6))
    print("找到的路径:", path)

运行后，你会看到一条从左上绕开障碍物到达右下的坐标序列。如果想让结果更直观，可以自己画一个简单的网格打印函数，用 * 表示路径——这本身就是一个不错的练习。

---

第三步：借鉴开源项目，让代码更健壮

自己写的代码跑通了，很有成就感。但如果我们想把它用在实际项目中，还需要考虑更多细节：

• 如何支持八方向移动（可以斜着走）？

• 如何支持不同地形权重（比如草地走一步代价为 2）？

• 如何高效检查节点是否在 open_list 中并更新其 g 值？

这些问题，开源项目里早就有了成熟的解决方案。我强烈推荐你去看看 PythonRobotics 仓库中的 AStar 实现（路径：PathPlanning/AStar/a_star.py）。它的代码结构与我们类似，但增加了：

• 更规范的变量命名和注释。

• 对加权地图的支持。

• 与 matplotlib 结合的可视化展示。

这是你参与开源的绝佳切入点：克隆仓库，运行示例，然后对比你自己的代码，思考哪些地方可以优化。你甚至可以尝试提交一个 Issue，提出你对注释或文档的改进建议——很多新手的第一份开源贡献就是从文档开始的。