Recursion << Previous Next >> SST

SA

搜尋演算法（Search Algorithms）
用 DFS 或 BFS 的邏輯探索迷宮。

# 範例 1：DFS 探索（深度優先）
def dfs():
    for i in range(4):
        if not wall_in_front():
            move()
            dfs()
            turn_left()
            turn_left()
            move()
            turn_left()
            turn_left()
        turn_left()

dfs()

# 範例 2：BFS 模擬（需額外結構支援）
# Reeborg 不支援 queue，但可模擬 BFS 的層級探索

# 範例 3：探索直到找到物品
def search():
    if object_here():
        take()
        return
    for i in range(4):
        if not wall_in_front():
            move()
            search()
            turn_left()
            turn_left()
            move()
            turn_left()
            turn_left()
        turn_left()

search()

深入探討 BFS（廣度優先搜尋）在 Reeborg 世界的模擬方式！雖然 Reeborg 不支援真正的 queue 結構，但我們可以透過層級探索的邏輯來模擬 BFS 的行為。以下是三個範例，每個都展示如何在 Reeborg 的限制下模擬 BFS 的層級探索：

範例 1：探索四個方向（模擬 BFS 的鄰接節點）
這個範例模擬 BFS 的「一層一層探索」概念，先嘗試所有方向再深入。

這段程式碼會嘗試探索機器人周圍的四個方向，每次都回到原點，模擬 BFS 的「同層探索」。

def explore_level():
    for i in range(4):  # 嘗試四個方向
        if not wall_in_front():
            move()
            # 模擬記錄節點（可加上 take() 或其他動作）
            turn_left()
            turn_left()
            move()  # 回到原點
            turn_left()
            turn_left()
        turn_left()

explore_level()

範例 2：探索並記錄層級（模擬 BFS 的層級記憶）
這個範例加入層級變數，模擬 BFS 的層級控制。

這段程式碼會探索所有第一層的方向，然後對每個方向再探索下一層，模擬 BFS 的層級展開。

def bfs_level(depth):
    if depth == 0:
        return
    for i in range(4):
        if not wall_in_front():
            move()
            bfs_level(depth - 1)  # 探索下一層
            turn_left()
            turn_left()
            move()  # 回到原點
            turn_left()
            turn_left()
        turn_left()

bfs_level(2)  # 探索兩層深度

範例 3：尋找物品（模擬 BFS 的目標搜尋）
這個範例模擬 BFS 尋找目標（例如物品），並在找到後停止。

這段程式碼模擬 BFS 尋找物品的過程，並在找到目標後停止探索。

found = False

def bfs_search(depth):
    global found
    if depth == 0 or found:
        return
    for i in range(4):
        if not wall_in_front():
            move()
            if object_here():
                take()
                found = True
                return
            bfs_search(depth - 1)
            if not found:
                turn_left()
                turn_left()
                move()
                turn_left()
                turn_left()
        turn_left()

bfs_search(3)  # 最多探索三層深度

以上這些範例雖然不是真正的 BFS（因為缺乏 queue 與 visited 記錄），但已經能在 Reeborg 的限制下模擬「層級探索」的核心概念。

Recursion << Previous Next >> SST