如何在Micromouse模拟器（MMS）中实现Python BFS迷宫遍历算法？

问题背景 #

我是Python初学者，想在Micromouse模拟器（MMS）中使用BFS算法遍历迷宫所有路径，自己尝试修改代码但毫无进展，恳请提供代码或指导。

原尝试代码：

import API
import sys

def log(string):
    sys.stderr.write("{}\n".format(string))
    sys.stderr.flush()

def main():
    log("Running...")
    API.setColor(0,0,"G")
    API.setText(0,0,"S")

    y = 0
    x = 0
    cur_pos = (x, y)
    orient = 0
    visited = set()

    while True:
        #pathfinding algorithm
        if cur_pos not in visited:
            visited.add(cur_pos)
            if not API.wallLeft():
                API.turnLeft()
                orient = API.getCurrentOrientation(orient, 'L')
            while API.wallFront():
                API.turnRight()
                orient = API.getCurrentOrientation(orient, 'R')
            API.moveForward()
            x,y = API.updateCoordinates(x,y, orient)
            cur_pos = (x, y)
            API.setColor(x, y,"G")
            API.setText(x,y,f"({x},{y})")
            log(visited)
            log(f"Moving to {x},{y}")
        else:
            if not API.wallLeft():
                API.turnLeft()
                orient = API.getCurrentOrientation(orient, 'L')
            while API.wallFront():
                API.turnRight()
                orient = API.getCurrentOrientation(orient, 'R')
            API.moveForward()
            x,y = API.updateCoordinates(x,y, orient)
            cur_pos = (x, y)
            API.setColor(x, y,"G")
            API.setText(x,y,f"({x},{y})")
            log(visited)
            log(f"Moving to {x},{y}")


if __name__ == "__main__":
    main()

原代码问题分析 #

你当前的代码是基于左手法则的随机遍历逻辑，并非BFS算法：

• 没有BFS核心的队列结构，无法按层级顺序访问节点
• 缺少回溯机制，走到已访问区域后无法返回上一个分支点继续探索
• 无法记录每个节点的访问路径，导致无法覆盖所有迷宫区域

BFS全遍历实现方案 #

BFS的核心是用队列存储待探索的节点，同时记录每个节点的父节点（用于回溯）。下面是适配MMS模拟器的完整实现：

import API
import sys
from collections import deque

def log(string):
    sys.stderr.write("{}\n".format(string))
    sys.stderr.flush()

# 方向映射：0=上,1=右,2=下,3=左（对应MMS的方向定义）
DIRS = [(-1,0), (0,1), (1,0), (0,-1)]

def turn_to_face(current_orient, target_orient):
    """计算需要左转/右转的次数并执行转向"""
    diff = (target_orient - current_orient) % 4
    if diff == 1:
        API.turnRight()
    elif diff == 3:
        API.turnLeft()
    elif diff == 2:
        API.turnRight()
        API.turnRight()
    return target_orient

def move_backward(current_orient):
    """后退一步（转向180度，前进，再转回来）"""
    temp_orient = turn_to_face(current_orient, (current_orient + 2) % 4)
    API.moveForward()
    new_orient = turn_to_face(temp_orient, current_orient)
    return new_orient

def main():
    log("BFS maze traversal starting...")
    API.setColor(0,0,"G")
    API.setText(0,0,"S")

    # BFS队列：每个元素是 (x坐标, y坐标, 当前方向, 父节点路径)
    queue = deque()
    visited = set()
    start_x, start_y = 0, 0
    start_orient = 0  # 默认初始方向向上

    visited.add((start_x, start_y))
    queue.append((start_x, start_y, start_orient, []))

    while queue:
        x, y, orient, path = queue.popleft()
        log(f"Exploring ({x}, {y})")

        # 标记当前位置
        API.setColor(x, y, "G")
        API.setText(x, y, f"({x},{y})")

        # 检查四个方向的邻居
        for dir_idx in range(4):
            dx, dy = DIRS[dir_idx]
            nx, ny = x + dx, y + dy
            neighbor_pos = (nx, ny)

            # 邻居未访问且当前方向到邻居没有墙
            if neighbor_pos not in visited:
                # 转向目标方向
                new_orient = turn_to_face(orient, dir_idx)
                # 前进到邻居
                API.moveForward()
                # 标记为已访问
                visited.add(neighbor_pos)
                # 更新路径并加入队列
                new_path = path + [(x, y)]
                queue.append((nx, ny, new_orient, new_path))
                # 回到当前节点，继续探索其他方向
                new_orient = move_backward(new_orient)
                # 恢复当前方向
                orient = turn_to_face(new_orient, dir_idx)

        # 如果当前节点没有未访问邻居，回溯到父节点
        if path:
            parent_x, parent_y = path[-1]
            # 计算需要转向的方向
            dx = parent_x - x
            dy = parent_y - y
            target_dir = DIRS.index((dx, dy))
            # 转向父节点方向
            orient = turn_to_face(orient, target_dir)
            # 前进到父节点
            API.moveForward()
            log(f"Backtracking to ({parent_x}, {parent_y})")
        else:
            # 回到起点，遍历完成
            log("Maze traversal completed!")
            break

if __name__ == "__main__":
    main()

关键代码解释 #

1. 队列与路径记录：用deque实现BFS队列，每个节点存储坐标、当前方向和回溯路径，确保能回到上一个分支点。
2. 方向控制：turn_to_face函数计算当前方向到目标方向的转向操作，适配MMS的转向API；move_backward函数实现机器人后退，用于探索完一个邻居后返回原节点。
3. 遍历逻辑：对每个节点的四个方向逐一检查，若邻居未访问则移动过去探索，之后返回原节点继续处理其他方向；当节点所有邻居都已访问时，回溯到父节点。
4. 迷宫标记：用API.setColor和API.setText标记已访问的位置，方便可视化遍历过程。

内容的提问来源于stack exchange，提问作者Yuno