實戰：地圖導航 API 與遊戲 AI
在本章中，我們將把 A* 路徑規劃技術應用到兩個真實場景：
- 地圖導航 API — 用 FastAPI 包裝成 RESTful API，供前端調用
- 遊戲 AI — 實作敵人自動追蹤玩家的路徑規劃
實戰一：路徑規劃 API
建立 FastAPI 服務
# pathfinding_api.py
from fastapi import FastAPI, HTTPException
from pydantic import BaseModel
import heapq
from typing import List, Tuple, Optional
app = FastAPI(title="路徑規劃 API", version="1.0.0")
# === A* 演算法實作 ===
def astar_search(grid, start, goal):
"""A* 搜尋（支援 8 方向移動）"""
height, width = len(grid), len(grid[0])
def heuristic(a, b):
# 對角線距離（8 方向用 Chebyshev）
return max(abs(a[0] - b[0]), abs(a[1] - b[1]))
# 8 個移動方向
directions = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (-1,1), (1,-1), (-1,-1)]
pq = [(0, 0, start[0], start[1])]
g_score = {start: 0}
came_from = {start: None}
explored_count = 0
while pq:
f, g, x, y = heapq.heappop(pq)
current = (x, y)
explored_count += 1
if current == goal:
path = []
while current is not None:
path.append(current)
current = came_from[current]
return list(reversed(path)), explored_count, len(path)
if g > g_score.get(current, float('inf')):
continue
for dx, dy in directions:
nx, ny = x + dx, y + dy
neighbor = (nx, ny)
if 0 <= nx < width and 0 <= ny < height and grid[ny][nx] == 0:
# 對角線移動成本為 sqrt(2)，直線為 1
move_cost = 1.414 if dx != 0 and dy != 0 else 1
tentative_g = g + move_cost
if tentative_g < g_score.get(neighbor, float('inf')):
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic(neighbor, goal)
heapq.heappush(pq, (f_score, tentative_g, nx, ny))
came_from[neighbor] = current
return None, explored_count, 0
# === API 模型 ===
class PathRequest(BaseModel):
grid: List[List[int]]
start: Tuple[int, int]
goal: Tuple[int, int]
allow_diagonal: bool = True
class PathResponse(BaseModel):
path: List[Tuple[int, int]]
explored_count: int
path_length: float
success: bool
class HealthResponse(BaseModel):
status: str
algorithm: str
version: str
@app.get("/", response_model=HealthResponse)
def root():
return HealthResponse(
status="healthy",
algorithm="A* (A-Star) Pathfinding",
version="1.0.0"
)
@app.post("/pathfind", response_model=PathResponse)
def pathfind(req: PathRequest):
"""
使用 A* 演算法計算最短路徑
"""
# 驗證輸入
if not req.grid or not req.grid[0]:
raise HTTPException(status_code=400, detail="地圖不可為空")
h, w = len(req.grid), len(req.grid[0])
if not (0 <= req.start[0] < w and 0 <= req.start[1] < h):
raise HTTPException(status_code=400, detail="起點超出地圖範圍")
if not (0 <= req.goal[0] < w and 0 <= req.goal[1] < h):
raise HTTPException(status_code=400, detail="終點超出地圖範圍")
if req.grid[req.start[1]][req.start[0]] == 1:
raise HTTPException(status_code=400, detail="起點為障礙物")
if req.grid[req.goal[1]][req.goal[0]] == 1:
raise HTTPException(status_code=400, detail="終點為障礙物")
path, explored, length = astar_search(req.grid, req.start, req.goal)
return PathResponse(
path=path if path else [],
explored_count=explored,
path_length=length,
success=path is not None
)
@app.get("/random_map")
def random_map(width: int = 20, height: int = 20, obstacle_ratio: float = 0.2):
"""生成隨機地圖"""
import random
random.seed(42)
grid = [[0] * width for _ in range(height)]
for y in range(height):
for x in range(width):
if random.random() < obstacle_ratio:
grid[y][x] = 1
grid[0][0] = 0 # 確保起點暢通
grid[height-1][width-1] = 0 # 確保終點暢通
return {"grid": grid, "width": width, "height": height,
"start": [0, 0], "goal": [width-1, height-1]}
if __name__ == "__main__":
import uvicorn
uvicorn.run(app, host="0.0.0.0", port=8000)
測試 API
# 啟動 API
python pathfinding_api.py
# 測試路徑規劃
curl -X POST "http://localhost:8000/pathfind" \
-H "Content-Type: application/json" \
-d '{
"grid": [[0,0,0,1,0],[0,1,0,1,0],[0,1,0,0,0],[0,0,0,1,0],[1,0,0,0,0]],
"start": [0,0],
"goal": [4,4]
}'
實戰二：遊戲 AI 敵人追蹤
import pygame
import sys
import random
# === 遊戲設定 ===
WINDOW_WIDTH = 800
WINDOW_HEIGHT = 600
GRID_SIZE = 40
COLS = WINDOW_WIDTH // GRID_SIZE
ROWS = WINDOW_HEIGHT // GRID_SIZE
# 顏色
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 200, 0)
RED = (200, 0, 0)
BLUE = (0, 100, 255)
YELLOW = (255, 255, 0)
GRAY = (100, 100, 100)
def heuristic(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def astar_move(grid, start, goal):
"""簡化版 A* — 只回傳下一步"""
if start == goal:
return start
pq = [(0, start[0], start[1])]
g_score = {start: 0}
came_from = {start: None}
while pq:
_, x, y = heapq.heappop(pq)
current = (x, y)
if current == goal:
# 回溯到第一步
while came_from[current] != start:
current = came_from[current]
return current
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
nx, ny = x + dx, y + dy
neighbor = (nx, ny)
if 0 <= nx < COLS and 0 <= ny < ROWS and grid[ny][nx] == 0:
tentative_g = g_score[current] + 1
if tentative_g < g_score.get(neighbor, float('inf')):
g_score[neighbor] = tentative_g
heapq.heappush(pq, (tentative_g + heuristic(neighbor, goal), nx, ny))
came_from[neighbor] = current
return start # 找不到路徑，原地不動
def run_game():
pygame.init()
screen = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT))
pygame.display.set_caption("A* 遊戲 AI — 敵人追蹤玩家")
clock = pygame.time.Clock()
# 建立地圖（隨機障礙物）
grid = [[0] * COLS for _ in range(ROWS)]
random.seed(123)
obstacle_count = int(COLS * ROWS * 0.15)
for _ in range(obstacle_count):
x, y = random.randint(0, COLS-1), random.randint(0, ROWS-1)
if (x, y) != (0, 0) and (x, y) != (COLS-1, ROWS-1):
grid[y][x] = 1
player_pos = [0, 0]
enemy_pos = [COLS-1, ROWS-1]
font = pygame.font.Font(None, 24)
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_UP and player_pos[1] > 0:
if grid[player_pos[1]-1][player_pos[0]] == 0:
player_pos[1] -= 1
elif event.key == pygame.K_DOWN and player_pos[1] < ROWS-1:
if grid[player_pos[1]+1][player_pos[0]] == 0:
player_pos[1] += 1
elif event.key == pygame.K_LEFT and player_pos[0] > 0:
if grid[player_pos[1]][player_pos[0]-1] == 0:
player_pos[0] -= 1
elif event.key == pygame.K_RIGHT and player_pos[0] < COLS-1:
if grid[player_pos[1]][player_pos[0]+1] == 0:
player_pos[0] += 1
# 敵人 AI：使用 A* 追蹤玩家
next_move = astar_move(grid, tuple(enemy_pos), tuple(player_pos))
enemy_pos = list(next_move)
# 繪圖
screen.fill(BLACK)
for y in range(ROWS):
for x in range(COLS):
rect = pygame.Rect(x*GRID_SIZE, y*GRID_SIZE, GRID_SIZE-1, GRID_SIZE-1)
if grid[y][x] == 1:
pygame.draw.rect(screen, GRAY, rect)
else:
pygame.draw.rect(screen, (30, 30, 40), rect, 1)
# 畫玩家
pygame.draw.rect(screen, GREEN,
(player_pos[0]*GRID_SIZE, player_pos[1]*GRID_SIZE, GRID_SIZE-1, GRID_SIZE-1))
# 畫敵人
pygame.draw.rect(screen, RED,
(enemy_pos[0]*GRID_SIZE, enemy_pos[1]*GRID_SIZE, GRID_SIZE-1, GRID_SIZE-1))
# 顯示資訊
text = font.render(f"玩家: {player_pos} 敵人: {enemy_pos}", True, WHITE)
screen.blit(text, (10, 10))
if player_pos == enemy_pos:
over_text = font.render("💀 遊戲結束！敵人追上你了！", True, RED)
screen.blit(over_text, (WINDOW_WIDTH//2 - 150, WINDOW_HEIGHT//2))
pygame.display.flip()
clock.tick(5) # 每秒 5 幀，讓 AI 移動慢一點
pygame.quit()
sys.exit()
if __name__ == "__main__":
run_game()
使用 Vibe Coding 整合路徑規劃
🔥 【路徑規劃整合詠唱範例】
「請幫我建立一個網頁版路徑規劃展示：1. 使用 React + Canvas 繪製網格地圖。2. 使用者可以繪製障礙物、設定起點終點。3. 點擊「開始搜尋」按鈕，調用後端 API 進行 A* 規劃。4. 動畫展示 A* 的探索過程與最終路徑。5. 顯示搜尋統計：探索節點數、路徑長度、耗時。6. 支援比較 A* 與 Dijkstra 的探索範圍差異。」
本日總結
在本章中，你學到了：
- ✅ FastAPI 路徑規劃 API：將 A* 包裝成 RESTful 服務
- ✅ 輸入驗證：確保地圖、起點、終點的正確性
- ✅ 遊戲 AI 敵人追蹤：使用 A* 實作敵人的自動導航
- ✅ Pygame 遊戲實作：完整的主循環、事件處理、繪圖
- ✅ 8 方向移動：支援斜角移動，路徑更自然
下一章，我們將學習如何在大規模地圖上做路徑規劃效能最佳化！