Python    ·    算法    ·    广度优先搜索

    摘要：本文围绕一段机器人自动寻路的代码，按“定义规则 → 核心算法 → 兜底策略”三步拆解：用方向字典把现实方位翻译成坐标加减；用广度优先搜索（BFS）求出带朝向约束的最短动作序列；再用“前沿探索”解决终点未知、道路被堵的情况（局限：禁止右转）

---------------------------------------------------------------------------------------------------------------------------------

 文章目录

1. 前言：机器人是怎么“看见”世界的

2. 第一步：定义规则 —— 机器人的“世界观”

3. 第二步：核心算法 —— 机器人的“探索大脑”（BFS）

4. 第三步：兜底策略 —— 机器人的“聪明策略”

---------------------------------------------------------------------------------------------------------------------------------

1. 前言：机器人是怎么“看见”世界的

机器人站在网格地图的某个格子上，用 (x, y) 记坐标，同一时刻只朝东、南、西、北中的一个方向，每一步只能前进、左转、右转或后转。地图上有墙壁、有边界，还有一大片从未去过的未知区域；关键设定是它看不到全局地图，只知道自己这一格四周能不能走。 于是任务被拆成两层：已知终点时怎么走最短，以及终点未知或路径被堵死时怎么办。前者交给 BFS，后者交给前沿探索。整段代码因此只有三块 —— 一张方向字典、一个 _plan 搜索函数、一个 isFrontier 兜底判断。

2. 第一步：定义规则 —— 机器人的“世界观”

原理：把“方位”翻译成“坐标增量”。

人用东南西北思考，计算机只会做加减，DELTA 就是这张翻译表。

方向	坐标增量 (dx, dy)	含义
东	(+1, 0)	列号 +1，向右一格
南	(0, +1)	行号 +1，向下一格
西	(-1, 0)	列号 -1，向左一格
北	(0, -1)	行号 -1，向上一格

三个字典各管一件事：

DELTA 管“走一步”的位移，只与方向有关

TURN_* 管“转一下”之后的新朝向，只与当前朝向有关

BLOCKED 把“墙壁”和“边界”归成同一类不可通行物，判断时不必分情况写 if

方向写成查表之后，寻路函数里只剩“位置 + 朝向”两种数据，动作被压缩成一次字典取值；将来扩展成八方向，也只改这张表，算法一行都不用动

3. 第二步：核心算法 —— 机器人的“探索大脑”（BFS）

原理：把“位置 + 朝向”当成一个不可分割的状态，从起点逐层向外扩散。每个动作的代价都是 1 步，队列的先进先出特性保证：第一次被弹出并判定为终点的状态，一定是步数最少的。这就是广度优先搜索

代码位置	写法		作用		为什么必须这样
状态	(pos, d)		把位置和朝向捆成一个搜索节点		同一格朝向不同，能走的下一步就不同，只记位置会被误判成同一个点
parent	{start: None}		记录“从哪来、做了什么动作”，同时兼作 visited		key 存在即访问过，省掉一个 set
出队	queue.popleft()		队首出队，逐层扩散		换成 pop() 就变成深度优先，找到的路不再最短
终判	pos != startPos and isGoal(pos)		命中终点就回溯		不排除起点，会立刻返回空路径，被误判成“找到了”
扩展	candidates 三元组		前进 / 左转 / 后转统一成 (位置, 朝向, 动作)		循环体里不再分情况，扩展只有五行
剪枝	if state in parent: continue		同一状态只入队一次		否则队列会指数膨胀
判墙	nextPos not in openSet		挡住墙壁和边界		放在入队之前，队列里不会出现垃圾状态
回溯	actions.reverse()		把倒着收的动作翻正		顺着 parent 往回走是从终点到起点
指标		结论		说明
状态总数		≤ 4 × 可走格数 N		每个格子最多 4 种朝向
每状态扩展		≤ 3 个动作		前进 / 左转 / 后转；右转连做三次左转等价，省掉这一支
时间复杂度		O(N)		每个状态只出队一次
空间复杂度		O(N)		parent 与队列各占一份

· 状态 = (位置, 朝向)：只记位置不够。站在同一格，面朝东和面朝北可走的下一步完全不同，必须带上朝向，否则两条不同的路会被误判成同一个点

  · popleft() 是 BFS 的灵魂：换成 pop() 就退化成深度优先，找到的路不再是最短路径

 · pos != startPos：排除“起点本身就是终点”，否则会立刻返回一条空路径，被上层误判成“已经找到了”。

4. 第三步：兜底策略 —— 机器人的“聪明策略”

原理：BFS 本身不关心“终点”是什么，它只认一个判定函数 isGoal。既然函数能当参数传，就可以把“去终点”和“去任何没看过的地方”都写成判定函数，复用同一个 _plan。

优先级	传入的判定函数	触发条件	机器人做什么
① 直奔终点	lambda p: p == (tx, ty)	知道终点坐标，且路径可达	取最短路径的第一步
② 去开地图	isFrontier	① 返回 None（路被堵死）	走向“四周还有未知格”的格子，像战争迷雾一样推图
③ 原地转身	无，直接 return "左转"	② 也返回 None（未知区域探完了）	换个朝向，下一帧再试 —— 宁可原地转，绝不卡死

三档策略的返回结构是统一的：都是一个动作字符串。上层只管执行，不必知道它来自搜索、探图还是兜底 —— 接口统一，上层逻辑就永远只有“拿到动作 → 执行”两行。

5. 调用方：吃金币与记忆初始化

原理：_plan 只负责“从A点到B点怎么走”，但机器人每一步真正要回答的是“现在该做什么动作”。答案按优先级分两层：眼前有金币就先吃（不需要搜索），没有就找一个记过的金币走过去（调用 _plan）。而 memory 里的 coinCells 就是“记过的金币”这张清单。

代码（吃金币的决策函数）

代码（记忆初始化与金币登记）

上段代码的四处关键写法

代码位置	写法	为什么这样写
记忆自检	not memory or not isinstance(memory[0], dict)	跨回合运行时 memory 可能是旧格式或空值，不清空会直接抛异常
金币清单	memory[0].setdefault("coin", [])	memory[0] 原本只有 open/wall，setdefault 一次完成“取 + 补”
金币注销	if (x, y) in coinCells: coinCells.remove((x, y))	走到金币格即视为吃掉，从清单划掉，避免回头再绕一次
代价	整段是 O(1) 的列表操作	这一步放在每帧开头，不能有搜索开销

吃金币决策函数的四处关键写法

代码位置	写法	为什么这样写
感知顺序	("front", …), ("left", …), ("back", …), ("right", …)	front 最省事排第一；命中即 return，不会白算后面的
右转禁发	("right", "左转")	学号尾号 9 禁用右转，看到金币也只发左转，宁多转一次不违规
候选排序	sorted(coinCells, key=lambda p: abs(p[0]-x)+abs(p[1]-y))	按曼哈顿距离由近到远，先试最可能走通的
闭包绑定	lambda p, c=c: p == c	写成 lambda p: p == c 会让所有判定都指向最后一枚金币
失败继续	if actions: return actions[0]	金币被墙围住就换下一个，不能让机器人死等