寻路算法（保姆级教程）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在计算机科学和游戏开发领域，“寻路算法”（Pathfinding Algorithms）是解决路径规划问题的核心工具。无论是游戏角色在迷宫中寻找出口，还是无人机在复杂环境中规划飞行路线，寻路算法都在背后发挥着关键作用。对于编程初学者和中级开发者而言，理解这类算法的原理和实现方式，不仅能提升问题解决能力，还能为后续学习人工智能、机器人学等进阶领域打下坚实基础。本文将从基础概念出发，结合实际案例和代码示例，逐步解析寻路算法的实现逻辑。

基础概念：迷宫、节点与图结构

在讨论具体算法之前，我们需要明确几个核心概念：

1. 迷宫与网格化：
   大多数寻路问题可以抽象为“迷宫”场景。例如，游戏角色需要在地图中避开障碍物，找到从起点到终点的路径。为了简化问题，通常将地图划分为规则的网格（如二维数组），每个网格称为一个节点（Node）。节点之间通过边（Edge）连接，边的权重代表移动代价（如距离或时间）。

   比喻：想象将一张城市地图切割成方块，每个方块代表一个路口，相邻路口之间的道路就是边，红绿灯或拥堵情况对应边的权重。

2. 图结构与邻接表：
   寻路问题的本质是图搜索问题。节点和边构成的集合称为图（Graph），而邻接表（Adjacency List）是存储节点之间连接关系的常用数据结构。例如，一个节点可能有四个邻居（上、下、左、右），这些邻居的信息通过邻接表记录。

   表格示例：
   | 节点 | 邻居列表 |
   |------|-------------------------|
   | A | B（权重1）、C（权重2） |
   | B | A（权重1）、D（权重3） |

经典算法详解：BFS、DFS 与 A*

1. 广度优先搜索（BFS）

原理：BFS 是一种“横向扩展”的算法，通过逐层探索所有可能路径，直到找到目标节点。其核心思想是优先访问距离起点最近的节点，因此适用于无权重图或需要寻找最短路径的场景。

比喻：想象向平静的湖面投入一颗石子，涟漪以同心圆形式向外扩散，最先到达目标点的路径即为最短路径。

实现步骤：

1. 使用队列（Queue）存储待探索的节点。
2. 从起点出发，标记已访问节点，并将邻居节点加入队列。
3. 重复上述过程，直到找到终点或队列为空。

代码示例（Python）：

from collections import deque  

def bfs(maze, start, end):  
    rows = len(maze)  
    cols = len(maze[0]) if rows > 0 else 0  
    visited = [[False]*cols for _ in range(rows)]  
    queue = deque()  
    queue.append((start, []))  # 存储节点和路径记录  
    visited[start[0]][start[1]] = True  

    while queue:  
        (current, path) = queue.popleft()  
        if current == end:  
            return path + [current]  # 返回完整路径  
        # 探索四个方向（上下左右）  
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:  
            x = current[0] + dx  
            y = current[1] + dy  
            if 0 <= x < rows and 0 <= y < cols:  
                if not visited[x][y] and maze[x][y] != " obstacle":  
                    visited[x][y] = True  
                    queue.append( ((x,y), path + [current]) )  
    return None  # 无路径时返回None  

案例分析：
假设有一个 5x5 的迷宫，起点为 (0,0)，终点为 (4,4)，障碍物用“X”表示：

maze = [  
    ["S", " ", " ", "X", " "],  
    [" ", "X", " ", "X", " "],  
    [" ", "X", " ", " ", " "],  
    [" ", " ", "X", " ", " "],  
    [" ", " ", " ", " ", "E"],  
]  

BFS 会优先探索上、下、左、右四个方向的邻居节点，最终找到一条路径如：
[(0,0) → (0,1) → (1,1) → ... → (4,4)]

2. 深度优先搜索（DFS）

原理：与 BFS 不同，DFS 是一种“纵向深入”的算法，优先沿着一条路径探索到底，若遇到死胡同则回溯到上一节点，尝试其他分支。其优点是内存占用较低，但缺点是可能无法找到最短路径。

比喻：想象在迷宫中一直向前走，直到撞墙才回头换方向，这种方式可能绕远路，但能覆盖更多区域。

实现步骤：

1. 使用栈（Stack）或递归实现节点的探索。
2. 从起点出发，标记已访问节点，并递归探索未访问的邻居。
3. 若路径无法到达终点，则回溯并尝试其他分支。

代码示例（递归版 Python）：

def dfs(maze, current, end, visited, path):  
    if current == end:  
        return path + [current]  # 找到终点  
    visited[current[0]][current[1]] = True  
    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:  
        x = current[0] + dx  
        y = current[1] + dy  
        if 0 <= x < len(maze) and 0 <= y < len(maze[0]):  
            if not visited[x][y] and maze[x][y] != " obstacle":  
                new_path = dfs(maze, (x,y), end, visited, path + [current])  
                if new_path is not None:  
                    return new_path  # 递归返回路径  
    return None  # 无路径时返回None  

优缺点对比：
| 算法 | 优点 | 缺点 |
|------|--------------------------|--------------------------|
| BFS | 能找到最短路径 | 内存占用高（需存储队列） |
| DFS | 内存效率高 | 可能找不到最优路径 |

3. A* 算法：启发式寻路的黄金标准

原理：A*（A-Star）算法结合了 BFS 的“探索优先级”和启发式函数（Heuristic Function）的“预估能力”，通过计算节点的总代价（已走代价 + 预估剩余代价）来动态选择最优路径。其公式为：
总代价 = g(n) + h(n)

• g(n)：从起点到当前节点的实际代价（如距离）。
• h(n)：当前节点到终点的预估代价（启发式函数）。

比喻：想象一位导航员，既知道已走的路程，又能通过地图预估剩余路程，从而选择最快路线。

常用启发式函数：

1. 曼哈顿距离：适用于只能横向、纵向移动的场景。
   h(n) = |x1 - x2| + |y1 - y2|
2. 欧几里得距离：适用于允许斜向移动的场景。
   h(n) = sqrt( (x1 - x2)^2 + (y1 - y2)^2 )

实现步骤：

1. 使用优先队列（如堆）存储节点，根据总代价排序。
2. 从起点开始，逐步探索邻居节点，更新总代价。
3. 当终点被弹出队列时，路径即为最优解。

代码示例（Python）：

import heapq  

def a_star(maze, start, end):  
    rows = len(maze)  
    cols = len(maze[0]) if rows > 0 else 0  
    heap = []  # 优先队列（总代价, 当前坐标, 路径）  
    heapq.heappush(heap, (0, start, [start]))  
    visited = set()  

    while heap:  
        (total_cost, current, path) = heapq.heappop(heap)  
        if current == end:  
            return path  # 返回完整路径  
        if current in visited:  
            continue  
        visited.add(current)  
        # 探索四个方向  
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:  
            x = current[0] + dx  
            y = current[1] + dy  
            if 0 <= x < rows and 0 <= y < cols:  
                if maze[x][y] != " obstacle":  
                    # 计算新的 g(n) 和 h(n)  
                    new_g = len(path) + 1  # 假设每步代价为1  
                    new_h = abs(x - end[0]) + abs(y - end[1])  # 曼哈顿距离  
                    new_total = new_g + new_h  
                    heapq.heappush(heap, (new_total, (x,y), path + [(x,y)]))  
    return None  

案例对比：
假设在相同迷宫中运行 A*，其路径可能更直接，例如优先向终点方向移动，而 BFS 可能绕行障碍物。

实际应用与优化技巧

1. 游戏开发中的路径规划

在游戏开发中，寻路算法常用于 NPC 的自主导航。例如：

• 动态障碍物处理：当玩家放置障碍物后，算法需重新计算路径。
• 权重调整：不同地形（如草地、泥地）赋予不同移动代价，使路径更符合真实场景。

2. 优化与变种算法

• Dijkstra 算法：适用于存在权重的图，但不依赖启发式函数。
• Jump Point Search（JPS）：通过预处理减少探索节点数量，提升 A* 在开放区域的效率。

3. 性能优化技巧

• 空间压缩：使用位掩码或稀疏矩阵存储地图，减少内存占用。
• 分层路径规划：将地图分为多个区域（如房间），优先在高层级规划路径，再细化到局部。

结论

寻路算法是计算机科学中一项兼具理论深度与实际价值的领域。从 BFS 的“横向探索”到 A* 的“智能预估”，每种算法都有其适用场景。对于开发者而言，理解这些算法的底层逻辑，并结合实际需求选择或改进算法，是提升系统效率的关键。无论是开发游戏、设计机器人，还是优化物流路径，掌握寻路算法都将为你打开一扇通往复杂问题解决方案的大门。

通过本文的代码示例和案例分析，希望读者能够：

1. 理解寻路算法的基本原理和实现逻辑；
2. 能够在简单场景中实现 BFS、DFS 和 A* 算法；
3. 为后续学习更复杂的路径规划技术（如 RRT、A* 变种）打下基础。

编程是一场永无止境的探索之旅，而寻路算法正是这场旅程中不可或缺的指南针。