Python 中如何使用 Strategy Pattern 实现不同的寻路算法？

2026-11-04数据小陈

每次调用 find_path(grid, start, end) 时传入网格是合理的。Python 传递参数时不会复制整个二维列表，函数参数和原变量绑定的是同一个对象。网格变大后，主要开销来自搜索访问的节点，以及队列、堆和其他辅助存储。

NPC 可以持有策略，地图由外部创建并共享。是否需要进一步集中到寻路服务，取决于是否要统一调度、缓存，或限制每帧的寻路工作量。

网格参数不会自动复制

执行下面的调用时：

path = self.strategy.find_path(self.grid, start, destination)

find_path 内的 grid 与 self.grid 指向同一个对象。传入参数时，Python 不会遍历或复制其中的单元格。

传递一个 $1000 \times 1000$ 的网格和传递小网格一样，都不需要先复制全部元素。但策略也可以修改共享地图：

def change_grid(grid):
    grid[0][0] = 1  # 调用方也会看到这个修改

寻路时应将网格视为只读数据，把已访问节点、累计代价和前驱节点保存在单次搜索的局部变量中。如果直接在共享网格上标记访问状态，不同 NPC 的搜索可能相互影响。

让策略依赖寻路所需的接口

传入二维列表本身没有架构问题，所有策略依赖同一种地图表示是一种正常的数据契约。

如果不希望算法了解二维列表的内部结构，可以给地图提供 walkable() 和 neighbors() 方法。算法负责搜索，地图负责判断哪些位置能走、哪些位置相邻。无需把渲染、音效或整个游戏控制器交给策略。

下面的示例采用这些约定：

坐标使用 (row, col)。
0 表示可通行，1 表示障碍。
只允许上下左右移动，每步代价为 1。
返回路径包含起点和终点；无法到达或端点不可通行时返回 []。

原始代码的粘贴内容缺少 Python 必需的缩进，下面的示例补齐了缩进，也提供了实际的搜索实现。

BFS、Dijkstra 和 A* 共用一个策略接口

from abc import ABC, abstractmethod
from collections import deque
from heapq import heappop, heappush


class Grid:
    def __init__(self, cells):
        if not cells or not cells[0]:
            raise ValueError("grid must not be empty")
        if any(len(row) != len(cells[0]) for row in cells):
            raise ValueError("grid must be rectangular")
        self.cells = cells
        self.rows = len(cells)
        self.cols = len(cells[0])

    def walkable(self, point):
        row, col = point
        return (
            0 <= row < self.rows
            and 0 <= col < self.cols
            and self.cells[row][col] == 0
        )

    def neighbors(self, point):
        row, col = point
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            neighbor = (row + dr, col + dc)
            if self.walkable(neighbor):
                yield neighbor


def reconstruct_path(previous, end):
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    return path[::-1]


class PathfindingStrategy(ABC):
    @abstractmethod
    def find_path(self, grid, start, end):
        raise NotImplementedError


class BFSStrategy(PathfindingStrategy):
    def find_path(self, grid, start, end):
        if not grid.walkable(start) or not grid.walkable(end):
            return []

        queue = deque([start])
        previous = {start: None}

        while queue:
            current = queue.popleft()
            if current == end:
                return reconstruct_path(previous, end)

            for neighbor in grid.neighbors(current):
                if neighbor not in previous:
                    previous[neighbor] = current
                    queue.append(neighbor)

        return []


class DijkstraStrategy(PathfindingStrategy):
    def estimate(self, point, end):
        return 0

    def find_path(self, grid, start, end):
        if not grid.walkable(start) or not grid.walkable(end):
            return []

        frontier = [(self.estimate(start, end), 0, start)]
        costs = {start: 0}
        previous = {start: None}

        while frontier:
            _, cost, current = heappop(frontier)
            if cost != costs[current]:
                continue
            if current == end:
                return reconstruct_path(previous, end)

            for neighbor in grid.neighbors(current):
                new_cost = cost + 1
                if new_cost < costs.get(neighbor, float("inf")):
                    costs[neighbor] = new_cost
                    previous[neighbor] = current
                    priority = new_cost + self.estimate(neighbor, end)
                    heappush(frontier, (priority, new_cost, neighbor))

        return []


class AStarStrategy(DijkstraStrategy):
    def estimate(self, point, end):
        return abs(point[0] - end[0]) + abs(point[1] - end[1])


class NPC:
    def __init__(self, name, grid, strategy, position=(0, 0)):
        self.name = name
        self.grid = grid
        self.strategy = strategy
        self.position = position

    def plan_path(self, destination):
        return self.strategy.find_path(
            self.grid, self.position, destination
        )


grid = Grid([[0] * 5 for _ in range(5)])
runner = NPC("Runner", grid, AStarStrategy())
walker = NPC("Walker", grid, BFSStrategy())
scout = NPC("Scout", grid, DijkstraStrategy())

print(runner.plan_path((0, 2)))

# 可以在运行时切换策略。
runner.strategy = BFSStrategy()
print(runner.plan_path((0, 2)))

示例中的 Dijkstra 使用累计代价作为优先级，A* 在此基础上加上启发式估计，因此可以复用堆搜索逻辑。两者向 NPC 提供相同的接口。

plan_path() 只计算路径。游戏循环应按实际移动进度更新 position，避免每次搜索都从原始示例中写死的 (0, 0) 出发。

NPC 和地图分别负责什么

对于这个简单网格游戏，可以让 NPC 保存当前位置和策略引用，由外部将共享地图注入 NPC。NPC 发起请求，策略完成计算，地图提供邻接关系和通行规则。

原始示例在每个 NPC 的构造函数中创建地图，使不同 NPC 各自拥有独立网格。如果它们生活在同一张地图上，共享同一个 Grid 实例通常更符合游戏模型。

当大量 NPC 需要排队搜索、限制每帧计算量或复用路径结果时，可以引入统一的寻路服务，由地图控制器委托该服务执行搜索。仅仅因为网格较大，并不需要把所有寻路逻辑放进地图控制器。

大网格的性能与算法选择

对于等权网格，BFS 就能找到最短路径。Dijkstra 更适合移动代价非负且各不相同的情况。示例中的代价统一为 1；如果增加地形权重，需要同时修改地图接口和代价累加逻辑。

示例中的 Manhattan distance 适用于四方向、单位代价移动。在这些前提下，它不会高估剩余距离，A* 可以保持最短路径保证。若增加对角线、传送门或更低的移动代价，必须重新检查启发式函数是否适用。

对于 $1000 \times 1000$ 的网格，需要关注搜索覆盖范围，以及 costs、previous、队列和堆的大小。在合适的地图和启发式下，A* 可能减少搜索量，但不保证每次都比 BFS 或 Dijkstra 更快。更换算法也不一定会让 NPC 走出明显不同的路线；如果需要不同的行为，还需要在通行规则、移动代价或目标选择中体现差异。