迷宮

 導航迷宮的簡單演算法。以下是逐步的詳細解釋：

1. 迷宮結構定義

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1],
    [1, 1, 0, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1]
]

• 迷宮是一個 5x8 的矩陣，1 代表牆壁，0 代表可以通行的路徑。
• 這個設定可以用來模擬一個簡單的迷宮環境。

2. 起點與終點

row, col = 1, 1
goal_row, goal_col = 3, 6

• 起點設在 (1, 1)，終點設在 (3, 6)。
• 程式會從起點開始導航，直到抵達終點為止。

3. 方向與初始設定

directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
current_direction = 1  # 初始方向設為「右」

• directions 列表定義了四個方向：
  • (-1, 0)：上
  • (0, 1)：右
  • (1, 0)：下
  • (0, -1)：左
• current_direction 表示目前的方向索引。初始設定為 1，即向右。

4. 判斷是否完成導航

def not_done():
    return (row, col) != (goal_row, goal_col)

• 這個函數用來檢查是否抵達終點，如果當前位置和終點相同，導航結束。

5. 檢查前方是否能通行

def can_move(offset_row, offset_col):
    next_row, next_col = row + offset_row, col + offset_col
    return maze[next_row][next_col] == 0

• 這個函數檢查指定方向是否可以通行（即檢查目標位置是否為 0）。

6. 方向控制

def turn_left():
    global current_direction
    current_direction = (current_direction - 1) % 4

def turn_right():
    global current_direction
    current_direction = (current_direction + 1) % 4

• turn_left() 和 turn_right() 用來改變當前的方向。
• 方向以 0, 1, 2, 3 循環編號，這樣可以使用取餘數 (%) 簡單地處理方向的切換。

7. 前進一格

def move_forward():
    global row, col
    offset_row, offset_col = directions[current_direction]
    row += offset_row
    col += offset_col
    maze[row][col] = 2  # 標記已走過的路徑
    print(f"Moved to ({row}, {col})")

• 根據當前方向來移動，並將移動後的位置標記為 2（表示已經走過）。

8. 主導航邏輯

while not_done():
    # 優先檢查左轉
    turn_left()
    offset_row, offset_col = directions[current_direction]
    if can_move(offset_row, offset_col):
        move_forward()
    else:
        # 恢復方向並檢查前方
        turn_right()
        offset_row, offset_col = directions[current_direction]
        if can_move(offset_row, offset_col):
            move_forward()
        else:
            # 如果前方不能通行，右轉再檢查
            turn_right()
            offset_row, offset_col = directions[current_direction]
            if can_move(offset_row, offset_col):
                move_forward()

• 這段代碼實現了迷宮導航的核心邏輯：
  1. 左轉優先：每次先嘗試左轉並檢查是否可以通行。
  2. 若無法左轉前進：恢復原方向並檢查前方能否通行。
  3. 若無法前進：右轉並再檢查一次，確保探索所有可能的路徑。

9. 結果

當抵達終點時，程式會輸出 Reached the goal!，並列出過程中每一步的位置變化。

執行結果

Moved to (1, 2)
Moved to (2, 2)
Moved to (3, 2)
Moved to (3, 3)
Moved to (3, 4)
Moved to (2, 4)
Moved to (1, 4)
Moved to (1, 5)
Moved to (1, 6)
Moved to (2, 6)
Moved to (3, 6)
Reached the goal!

總結

這個程式通過簡單的優先策略（左轉優先、前方次之、右轉最後）來探索迷宮。它會標記已經走過的路，避免無限迴圈，最終成功從起點導航到終點。