第十六单元：迷宫算法 · 左手定则与深度优先搜索

封神冰川深处，冰封的迷宫残酷而寂静。层层冰墙之间，有些门被牢牢堵死，有些门却会因你的脚步声而悄然开启。出口确实存在——但如何在错综复杂的冰室中找到那条路？这正是计算机科学中经典的迷宫求解问题（maze solving）。本单元由两个关卡组成，你将学习两种截然不同却都威力强大的迷宫算法：先用简洁的左手定则（Left-Hand Rule）贴墙逃生，再用系统化的深度优先搜索（DFS）配合栈（stack）和二维地图去搜寻宝藏。

16.1.1 什么是迷宫算法（What Is a Maze Algorithm）

16.1.1.1 在墙与路之间找到出口 Finding an exit among walls and passages

迷宫算法是一类自动寻路的方法：给定一个由墙壁和通道组成的网格，算法要找出从起点到出口（或到某个目标）的路径。迷宫可以抽象成图论里的图（graph）——每个房间是一个节点，能互通的门是连接节点的边。找路的过程，本质上就是在图上做遍历（traversal）。

16.1.2 两种探索思路（Two Exploration Strategies）

16.1.2.1 贴墙走 vs. 系统搜索 Wall-following vs. systematic search

本单元的两关分别代表两类经典算法。第 33 关"脆弱的迷宫"用左手定则：不需要记地图，只要一直贴着左边的墙走，对简单连通的迷宫必能到达出口。第 34 关"冰块中的宝藏"用DFS + 二维地图：需要构建地图、用栈系统地搜索、记录访问过的房间——它更复杂，但能处理"先找宝藏、再回出口"这样的多目标任务。

图1：两种迷宫探索思路——左：左手定则贴墙走；右：DFS 借助地图与栈系统搜索

16.2.1 方向常量（Direction Constants）

16.2.1.1 用列表存放四个方向 Store the four directions in a list

迷宫是网格，英雄每次只能朝上、下、左、右四个方向之一移动。为了让代码清晰、便于旋转，我们把四个方向按顺时针（或逆时针）顺序放进一个列表常量。这样"下一个方向"就变成了列表里的"下一个索引",转向就成了简单的索引运算。

# 方向常量：按固定顺序排列（脆弱的迷宫）
DIRECTIONS = ["left", "up", "right", "down"]

# 房间之间的固定距离——每次移动跨一格
distanceBetweenRooms = 16

16.2.2 左右转换（Turning Left and Right）

16.2.2.1 用查找表实现"左转" Use a lookup table to turn left

左手定则的核心动作是"相对当前朝向左转"。有两种实现方式。一种是字典查找表：直接写死"面朝某方向时，左手边是哪个方向"。另一种是索引旋转：在 DIRECTIONS 列表上用取模 % 4 得到相邻方向。关卡里两种都用到了。

# 方式一：查找表——面朝 key 时，左手边是 value
LEFT_FOR = {
    "left":  "down",
    "up":    "left",
    "down":  "right",
    "right": "up"
}

# 方式二：索引旋转——取列表里的下一个方向（顺时针转）
def findNextDirection(current):
    return DIRECTIONS[(DIRECTIONS.index(current) + 1) % 4]

16.2.3 moveXY 移动英雄（Moving the Hero）

16.2.3.1 精确移动到目标坐标 Move precisely to a target coordinate

hero.moveXY(x, y) 让英雄直线走到指定坐标点。和 moveRight 之类的相对移动不同，moveXY 是绝对坐标移动，非常适合迷宫这种"格点式"的精确走位。在冰迷宫里还有个小细节:冰面很滑，关卡里连续调用了两次 moveXY 到同一点，以确保英雄稳稳停在格子中央而不打滑越位。

# 移动到目标点；冰面易滑，调用两次确保停稳
hero.moveXY(tryPoint.x, tryPoint.y)
hero.moveXY(tryPoint.x, tryPoint.y)   # 第二次：防滑，停回格心

16.3.1 探测门是否通畅（Is the Door Open）

16.3.1.1 走之前先看看路通不通 Check the path before you move

迷宫里的门有的堵死、有的开着。hero.isPathClear(start, end) 会检测从 start 到 end 两点之间的路径是否畅通无阻，返回 True（通）或 False（堵）。它是英雄的"眼睛"——在真正 moveXY 之前，先用它探一探目标方向能不能走。

# 先探测，再决定走不走
tryPoint = pointInDirection(tryDir, hero.pos)
if hero.isPathClear(hero.pos, tryPoint):
    # 路通！可以朝这个方向移动
    hero.moveXY(tryPoint.x, tryPoint.y)

16.3.2 目标点计算（Computing the Target Point）

16.3.2.1 由方向算出下一个坐标 Compute the next coordinate from a direction

要用 isPathClear 探测，得先算出"朝某方向走一格"会到哪个坐标。pointInDirection 就是把"方向名"转成"目标坐标点"的工具——它根据方向在当前坐标上加减一个 distanceBetweenRooms。注意坐标系：向上 y 增大，向下 y 减小,向左 x 减小,向右 x 增大。

# 根据方向，从当前 pos 计算目标坐标
def pointInDirection(direction, pos):
    if direction == "left":
        return Vector(pos.x - distanceBetweenRooms, pos.y)
    elif direction == "right":
        return Vector(pos.x + distanceBetweenRooms, pos.y)
    elif direction == "down":
        return Vector(pos.x, pos.y - distanceBetweenRooms)
    elif direction == "up":
        return Vector(pos.x, pos.y + distanceBetweenRooms)

16.4.1 靠墙走原理（Why Wall-Following Works）

16.4.1.1 永远让左手贴着墙 Always keep your left hand on the wall

左手定则（也叫"靠墙法"）的规则朴素得惊人：始终让左手扶着墙,一直往前走。只要迷宫是简单连通的（所有墙都连成一体、出入口在外墙上），这样走一定能走到出口,绝不会永远迷失。原因是拓扑上的:贴着一堵连通的墙走,等于沿着它的边界绕一圈,最终必然遍历到出口。

16.4.2 尝试转向逻辑（The Turn-Try Loop）

16.4.2.1 优先左转,不通就顺时针试下一个 Try left first, then rotate clockwise

算法的每一步都遵循同一个套路:相对当前朝向,优先尝试左转的方向;如果那个方向的门堵着,就顺时针依次尝试下一个方向,直到找到一条通路走过去。走通之后,记下新的朝向 prev,进入下一轮。用 LEFT_FOR[prev] 拿到"左手方向"作为首选,再用 findNextDirection 逐个换方向。

# 左手定则主循环（关键片段）
prev = "up"                       # 初始朝向
while True:
    tryDir = LEFT_FOR[prev]       # 首选:相对当前朝向左转
    while True:
        tryPoint = pointInDirection(tryDir, hero.pos)
        if hero.isPathClear(hero.pos, tryPoint):
            prev = tryDir            # 记住走通的新朝向
            hero.moveXY(tryPoint.x, tryPoint.y)
            hero.moveXY(tryPoint.x, tryPoint.y)  # 防滑
            break                    # 走通了,跳出内层,进入下一步
        tryDir = findNextDirection(tryDir)  # 堵住,顺时针换下一个方向再试

16.5.1 二维数组地图（The 2D Array Map）

16.5.1.1 把迷宫抽象成网格 Abstract the maze into a grid

当任务变复杂(要找宝藏再回出口),光靠贴墙走就不够了——我们需要在"脑中"建一张地图。第 34 关用二维数组 maze 来表示整个迷宫:每个格子存一个字符,"X" 表示墙,"." 表示已知的通路,"?" 表示尚未探明的房间。行列间隔布局让"房间"和"房间之间的门"都能被表示出来。

# 用字符常量表示格子的三种状态
wall = "X"       # 墙,不可通过
unknown = "?"    # 未探明的房间
empty = "."      # 已知通路

# 构建空白迷宫地图:外围一圈墙,内部按行列交错填充
maze = []
for i in range(height):
    maze.append([wall])       # 每行以左边界墙开头
# ……再逐行按 i%2 / j%2 判断填 wall 还是 unknown……

16.5.2 行列与坐标转换（Row/Col to Coordinates）

16.5.2.1 网格索引 ↔ 游戏坐标 Convert grid indices to game coordinates

地图里用行列(row/col)索引方便,但让英雄移动要用游戏坐标(x/y)。所以需要一个转换函数,把网格索引乘上房间间距、再加一个偏移量 zeroShift,换算成实际坐标。四个方向函数(north/south/east/west)就是在此基础上,一次跨两格(跨过中间的"门格")算出邻居房间的坐标与行列。

# 网格索引 → 游戏坐标
def coorConvert(i, dist):
    return i * distanceBetweenRooms / 2 + zeroShift.x

# 求北面邻居:行 +2(跨过门格),返回坐标与新行列
def north():
    return {
        'x': coorConvert(hero.col),
        'y': coorConvert(hero.row + 2),
        'row': hero.row + 2, 'col': hero.col
    }

16.6.1 用栈实现 DFS（DFS with a Stack）

16.6.1.1 后进先出,一条路走到底 Last in, first out — go deep first

深度优先搜索(DFS)的思想是"一条路走到黑",走不通再回退换路。它天然可以用栈(stack)实现——栈是"后进先出(LIFO)"的结构:把待探索的房间压入栈,每次取出最新压入的那个继续深入;走进死胡同就回退到栈里上一个岔路口。每个栈元素还记录了"到达这里的路径",这样找到目标时就能直接返回整条路。

# 用栈做 DFS(关键片段,简化示意)
def findPath(m, needExit):
    stack = [[hero.row, hero.col, ""]]   # [行, 列, 到此的路径]
    visited = []                       # 已访问房间记录
    while len(stack):
        current = stack.pop()          # LIFO:取最新压入的房间
        row, col, path = current[0], current[1], current[2]
        # 到达目标就返回路径;否则把可走的邻居压栈……

16.6.2 记录已访问房间（Tracking Visited Rooms）

16.6.2.1 别重复进同一个房间 Don't enter the same room twice

DFS 最容易犯的错就是兜圈子——绕回已经走过的房间,陷入死循环。解决办法是维护一个 visited 列表:每探索一个房间,先检查它在不在 visited 里;若在就跳过(continue),否则记下它再继续。房间用 "行-列" 拼成的字符串唯一标识,判断非常方便。

# 用"行-列"字符串唯一标识房间,避免重复访问
strPos = str(row) + "-" + str(col)
if visited.index(strPos) != -1:   # 已经来过
    continue                          # 跳过,不再重复探索
visited.append(strPos)              # 首次到达,记录下来

# 邻居若是通路(".")就带上方向压入栈,继续深入
if m[row - 1][col] == ".":
    stack.append([row - 2, col, path + "S"])

这一节聚焦每一关的策略、思路与算法设计,只展示用于说明的关键片段,完整通关程序请你自己动手完成。

第 33 关 · 脆弱的迷宫

🧊 脆弱的迷宫 —— 左手定则贴墙逃生

图2：脆弱的迷宫——有些门会因脚步声开启,用 isPathClear 探路、左手定则贴墙,一步步走出冰迷宫

策略：不记地图,只管贴着左墙走

这一关的迷宫是简单连通的,出口在外墙上——正是左手定则的理想场景。策略非常干脆:完全不需要构建地图或记录访问,只要每一步都优先朝"当前朝向的左手方向"走,堵住就顺时针换方向,一直循环下去,英雄自然会被墙"领"到出口。冰门虽脆弱、会因脚步声开启,但 isPathClear 会如实告诉你当下哪扇门通。

思路拆解:方向表 + 探路 + 前进

先用 DIRECTIONS 列表和 LEFT_FOR 字典准备好方向数据与"左转"映射。主循环里,先取 LEFT_FOR[prev] 作为首选方向,用 pointInDirection 算出目标点,再用 isPathClear 探测:通就 moveXY 过去并更新 prev;不通就 findNextDirection 顺时针换下一个方向重试。关键在于每次都从"左手方向"开始试,这保证了贴墙的一致性。

# 关键片段:每步从左手方向开始尝试
prev = "up"
while True:
    tryDir = LEFT_FOR[prev]          # 首选左手方向
    while True:
        tryPoint = pointInDirection(tryDir, hero.pos)
        if hero.isPathClear(hero.pos, tryPoint):
            prev = tryDir
            hero.moveXY(tryPoint.x, tryPoint.y)
            hero.moveXY(tryPoint.x, tryPoint.y)   # 防滑
            break
        tryDir = findNextDirection(tryDir)   # 换方向重试

左手定则的适用前提：本关能用左手定则,是因为迷宫简单连通、出入口在外墙。如果迷宫中间有"孤岛"或环形回路,单纯贴墙可能绕不出来——那就需要下一关的 DFS 了。理解"算法有适用边界",比记住算法本身更重要。

第 34 关 · 冰块中的宝藏

❄️ 冰块中的宝藏 —— DFS 搜宝并返回出口

图3：冰块中的宝藏——构建二维地图、边走边用 isPathClear 更新,再用栈做 DFS 先找宝藏、拿到后回到红十字出口

策略：建图 + 边探边搜 + 两阶段目标

这是本单元的综合关,任务是先拿宝藏,再走到红十字出口。单靠贴墙走无法满足"多目标",所以要上 DFS。整体策略分三层:(1) 建图——先用二维数组 maze 铺好墙与未知房间;(2) 探测更新——每到一个房间,用 checkPaths 配合 isPathClear 把四周的门探明,把 "?" 更新成 "." 或保持墙;(3) DFS 求路——用 findPath 在已知地图上搜索:没拿到宝藏时搜"最近的未知房间"去探索,拿到宝藏后(hero.gold 达标)就搜"通往出口"的路。

思路拆解一:探测并更新地图

checkPaths 把英雄当前房间标为通路 ".",再朝四个方向用 isPathClear 探测:凡是相邻的"门格"畅通、且对应房间还是 "?" 的,就把它更新为已知通路。这样地图会随着探索一点点"点亮"。

# 关键片段:探测四周门,更新地图上的 ? 
def checkPaths(cMap):
    cMap[hero.row][hero.col] = "."   # 当前房间标为通路
    dirs = [[1, 0, north], [-1, 0, south], [0, 1, west], [0, -1, east]]
    for d in dirs:
        dx, dy, dPosFunc = d[0], d[1], d[2]
        if cMap[hero.row + dx][hero.col + dy] == "?" and \
           hero.isPathClear(hero.pos, dPosFunc()):
            cMap[hero.row + dx][hero.col + dy] = "."
    return cMap

思路拆解二:栈式 DFS 搜路径

findPath 用栈从当前位置出发搜索。栈里每个元素是 [行, 列, 路径字符串]。取出栈顶后先判重(visited),再看是否命中目标:未拿宝藏时,遇到还是 "?" 的房间就返回路径去探它;已拿宝藏时,到达出口行列就返回路径并加上 "!" 表示"到出口"。没命中就把四周通路邻居带上方向(N/S/E/W)压栈继续深入。

# 关键片段:DFS 里的目标判断与邻居压栈
# 目标一:还没拿宝藏,找到未知房间就去探
if not needExit and m[row][col] == "?":
    return path
# 目标二:已拿宝藏,到达出口行列
if needExit and row == exitRow and col == exitCol:
    return path + "!"
# 否则:把四周通路邻居(±2 跨格)带方向压栈
if m[row - 1][col] == ".":
    stack.append([row - 2, col, path + "S"])

思路拆解三:主循环——探索、判宝、走路

主循环把三块拼起来:先 checkPaths 更新地图;检查 hero.gold 判断宝藏是否到手,更新 treasureFound;用 findPath 求出一条路径字符串;若有路就逐字符 moveDir 走过去(每步移动并同步更新 hero.row/col);走到 "!" 时结束搜索。反复循环直到走出出口。

# 关键片段:主循环骨架
while inSearch:
    maze = checkPaths(maze)          # 1) 探测更新地图
    if hero.gold > 0:              # 2) 判断宝藏是否到手
        treasureFound = True
    path = findPath(maze, treasureFound)  # 3) DFS 求路径
    if not path:
        hero.say("Arrrr!")       # 暂时无路可走
    else:
        for p in range(len(path)):
            moveDir(path[p])          # 4) 逐步移动并同步行列

两阶段目标是本关的灵魂：用一个布尔量 treasureFound(即 needExit)切换 DFS 的目标:没拿宝藏时目标是"探索未知",拿到后目标变成"回出口"。同一套 DFS 代码,靠一个开关服务两个阶段——这是参数化搜索的巧妙之处。别把两个目标写死成两份重复代码。

边走边建图,而非一次看全：英雄看不到整张迷宫,只能到一处探一处。所以地图是动态生长的:checkPaths 每轮点亮周围,DFS 只在"已知部分"上搜索,搜到未知房间就去实地探明。这正是 AI 在未知环境中"感知—建模—规划—行动"循环的缩影。

16.8.1 新手最容易踩的坑（Pitfalls for Beginners）

16.8.1.1 迷宫算法的典型问题 Typical issues with maze algorithms

图4：方向算反、忘记判重、栈用错方法、行列不同步,是本单元最常见的失误