如何在Micromouse Simulator中制作BFS算法？

Question

我是Python初学者，我在课堂上进行了这项活动。基本上，我需要帮助在 python 中制作一个在 MMS 中运行的算法（Micromouse Simulator。https://github.com/mackorone/mms。这是我们正在使用的应用程序存储库的链接）。我已经尝试解决这个问题一天了，但没有取得任何进展。我需要任何方式的帮助，无论是代码还是指南，任何东西。我现在真的很绝望。

这是我到目前为止得到的代码。虽然没用，但这就是我尝试过的。它绕了一圈，但错过了迷宫的某些部分，并且没有遍历迷宫的每个部分。

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()

Answer 1

您需要创建一个队列来跟踪要访问的单元格，并创建一个集合来跟踪已经访问过的单元格。

1. 初始化一个具有起始位置的队列和一组具有相同起始位置的队列。

2. 当队列不为空时：

   A.将单元格从队列中出列。

   B.如果它是目标单元格，你就完成了

   C.如果不是，对于每个不是墙且尚未被访问过的相邻单元：

   D。将邻居添加到访问集中

   F。将邻居加入队列

3. 如果退出循环，则意味着没有通往目标的路径：

代码实现如下：

import API
import sys
from collections import deque
def log(string):
    sys.stderr.write("{}\n".format(string))
    sys.stderr.flush()
def get_neighbors(x, y):
    deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    neighbors = []
    for dx, dy in deltas:
        nx, ny = x + dx, y + dy
        if nx >= 0 and ny >= 0 and nx < API.mazeWidth() and ny < API.mazeHeight():
            if not API.wallPresent(x, y, dx, dy):
                neighbors.append((nx, ny))
    return neighbors
def bfs():
    log("Running...")
    start = (0, 0)
    goal = (API.mazeWidth() - 1, API.mazeHeight() - 1)
    queue = deque([start])
    visited = set([start])

    while queue:
        cell = queue.popleft()
        x, y = cell
        API.setColor(x, y, "G")
        API.setText(x, y, f"({x},{y})")
        log(f"Visiting {x},{y}")
        if cell == goal:
            log("Goal reached! 🐀")
            return
        for neighbor in get_neighbors(x, y):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    log("No path to the goal.")
if __name__ == "__main__":
   bfs()