進階技巧：大規模地圖與效能最佳化
在真實應用中，地圖可能非常大（數百萬個節點），而且障礙物可能動態變化（例如交通堵塞）。標準的 A* 在這種場景下會太慢。
本章將介紹三種業界常用的最佳化技術：
- Jump Point Search (JPS) — 網格地圖上比 A* 快 10-100 倍
- 層級尋路 (Hierarchical Pathfinding) — 分割地圖為多層級
- 動態路徑規劃 — 即時避開移動中的障礙物
Jump Point Search (JPS)
JPS 是 A* 在均勻網格地圖上的最佳化版本。它利用網格地圖的對稱性，一次跳過多個格子，大幅減少需要探索的節點數。
JPS 的核心直覺
在網格地圖中，如果一個區域是空的（沒有障礙物），A* 會把這個區域內的所有格子都加入 Open Set——但其實這些格子很多都是多餘的。
JPS 的發現在於：在空曠區域中，我們不需要探索每個格子，只要找出「關鍵轉折點 (Jump Points)」即可。
傳統 A* 探索路徑：
. . . . . . . .
. S . . . . . . ← 探索所有格子
. . . . . . G .
JPS 探索路徑（只探索轉折點）：
. . . . . . . .
. S—→—→—→—→—→—→ G ← 一跳跳過中間所有空格
. . . . . . . .
實作 JPS
def jump(grid, current, direction, goal):
"""
從 current 沿 direction 方向跳躍
回傳跳躍點 (Jump Point) 或 None
"""
x, y = current
dx, dy = direction
nx, ny = x + dx, y + dy
# 超出邊界或碰到障礙物
if not (0 <= nx < len(grid[0]) and 0 <= ny < len(grid)):
return None
if grid[ny][nx] == 1:
return None
# 到達目標
if (nx, ny) == goal:
return (nx, ny)
# 檢查強迫鄰居 (Forced Neighbors)
# 水平移動時檢查上下是否有障礙物
if dx != 0:
# 檢查上方
if ny > 0 and grid[ny-1][nx] == 1 and grid[ny-1][x] == 0:
return (nx, ny)
# 檢查下方
if ny < len(grid)-1 and grid[ny+1][nx] == 1 and grid[ny+1][x] == 0:
return (nx, ny)
# 繼續水平跳躍
return jump(grid, (nx, ny), direction, goal)
# 垂直移動時檢查左右是否有障礙物
if dy != 0:
if nx > 0 and grid[ny][nx-1] == 1 and grid[y][nx-1] == 0:
return (nx, ny)
if nx < len(grid[0])-1 and grid[ny][nx+1] == 1 and grid[y][nx+1] == 0:
return (nx, ny)
# 垂直移動時也要嘗試對角線（遞迴）
if (jump(grid, (nx, ny), (1, dy), goal) or
jump(grid, (nx, ny), (-1, dy), goal)):
return (nx, ny)
return jump(grid, (nx, ny), direction, goal)
return None
def jps_search(grid, start, goal):
"""Jump Point Search 主流程"""
import heapq
pq = [(0, start[0], start[1])]
g_score = {start: 0}
came_from = {start: None}
explored = []
def heuristic(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])
while pq:
_, x, y = heapq.heappop(pq)
current = (x, y)
explored.append(current)
if current == goal:
path = []
while current is not None:
path.append(current)
current = came_from[current]
return list(reversed(path)), explored
# 獲取當前節點的有用鄰居
neighbors = []
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1),
(1,1), (-1,1), (1,-1), (-1,-1)]:
jp = jump(grid, current, (dx, dy), goal)
if jp:
neighbors.append((jp, dx, dy))
for jp, _, _ in neighbors:
jx, jy = jp
# 計算成本
step_cost = abs(jx - x) + abs(jy - y)
tentative_g = g_score[current] + step_cost
if tentative_g < g_score.get(jp, float('inf')):
g_score[jp] = tentative_g
heapq.heappush(pq, (tentative_g + heuristic(jp, goal), jx, jy))
came_from[jp] = current
return None, explored
JPS vs A* 效能比較
import time
import random
# 建立大地圖（100x100）
size = 100
grid = [[0] * size for _ in range(size)]
# 隨機放置障礙物
random.seed(42)
for _ in range(int(size * size * 0.2)):
x, y = random.randint(0, size-1), random.randint(0, size-1)
if (x, y) != (0, 0) and (x, y) != (size-1, size-1):
grid[y][x] = 1
start = (0, 0)
goal = (size-1, size-1)
print("=== 大規模地圖比較（100x100）===")
# A*
start_time = time.time()
astar_path, astar_explored = astar(grid, start, goal)
astar_time = time.time() - start_time
print(f"A* 探索節點: {len(astar_explored)}, 耗時: {astar_time:.4f}s")
# JPS
start_time = time.time()
jps_path, jps_explored = jps_search(grid, start, goal)
jps_time = time.time() - start_time
print(f"JPS 探索節點: {len(jps_explored)}, 耗時: {jps_time:.4f}s")
print(f"\nJPS 節點減少: {len(astar_explored)/len(jps_explored):.1f}x")
print(f"JPS 速度提升: {astar_time/jps_time:.1f}x")
層級尋路 (Hierarchical Pathfinding)
對於超大型地圖（如 MMORPG 的世界地圖），即使是 JPS 也可能太慢。這時候需要使用層級尋路：
class HierarchicalPathfinder:
"""兩層級的路徑規劃"""
def __init__(self, grid, cluster_size=10):
self.grid = grid
self.cluster_size = cluster_size
self.clusters = {}
self._build_clusters()
def _build_clusters(self):
"""將大地圖分割為叢集"""
height, width = len(self.grid), len(self.grid[0])
cluster_id = 0
for cy in range(0, height, self.cluster_size):
for cx in range(0, width, self.cluster_size):
cluster_id += 1
# 計算叢集邊界上的入口/出口點
entrances = []
# 上邊界
for x in range(cx, min(cx + self.cluster_size, width)):
if self.grid[cy][x] == 0 and cy > 0 and self.grid[cy-1][x] == 0:
entrances.append((x, cy))
# 下邊界
by = min(cy + self.cluster_size - 1, height - 1)
for x in range(cx, min(cx + self.cluster_size, width)):
if self.grid[by][x] == 0 and by < height-1 and self.grid[by+1][x] == 0:
entrances.append((x, by))
# 左邊界
for y in range(cy, min(cy + self.cluster_size, height)):
if self.grid[y][cx] == 0 and cx > 0 and self.grid[y][cx-1] == 0:
entrances.append((cx, y))
# 右邊界
rx = min(cx + self.cluster_size - 1, width - 1)
for y in range(cy, min(cy + self.cluster_size, height)):
if self.grid[y][rx] == 0 and rx < width-1 and self.grid[y][rx+1] == 0:
entrances.append((rx, y))
self.clusters[cluster_id] = {
'bounds': (cx, cy, cx + self.cluster_size, cy + self.cluster_size),
'entrances': entrances
}
print(f"地圖已分割為 {cluster_id} 個叢集")
def find_path(self, start, goal):
"""兩層級路徑規劃"""
# 找出起點與終點所在的叢集
start_cluster = self._find_cluster(start)
goal_cluster = self._find_cluster(goal)
if start_cluster == goal_cluster:
# 同一個叢集：直接使用 A*
return astar(self.grid, start, goal)[0]
# 不同叢集：先規劃叢集層級的路徑
# 簡化版：找到最近的入口點，用 A* 走到入口，跨叢集，再走到終點
path = []
# 從起點走到所在叢集的出口
start_exits = self.clusters[start_cluster]['entrances']
if start_exits:
nearest_exit = min(start_exits,
key=lambda e: abs(e[0]-start[0]) + abs(e[1]-start[1]))
seg1, _ = astar(self.grid, start, nearest_exit)
if seg1:
path.extend(seg1[:-1])
current_pos = nearest_exit
# 從終點叢集的入口走到終點
goal_entrances = self.clusters[goal_cluster]['entrances']
if goal_entrances:
nearest_entrance = min(goal_entrances,
key=lambda e: abs(e[0]-goal[0]) + abs(e[1]-goal[1]))
seg2, _ = astar(self.grid, nearest_entrance, goal)
if seg2:
path.extend(seg2)
return path if path else None
def _find_cluster(self, pos):
x, y = pos
cx = x // self.cluster_size
cy = y // self.cluster_size
return cy * (len(self.grid[0]) // self.cluster_size) + cx + 1
動態障礙物處理
在真實世界中，障礙物會移動（例如行人、車輛）。我們需要能即時重新規劃路徑。
def dynamic_pathfinding(grid, start, goal, dynamic_obstacles):
"""
動態路徑規劃：當障礙物改變時增量更新
"""
# 每當障礙物改變時，只在路徑附近重新搜尋
# 而不是重新搜尋整個地圖
# 1. 先用 A* 找到初始路徑
path, _ = astar(grid, start, goal)
if not path:
return None
# 2. 檢查路徑是否被動態障礙物阻擋
for obs in dynamic_obstacles:
if obs in path:
# 3. 只在障礙物附近重新規劃
obs_idx = path.index(obs)
local_start = path[max(0, obs_idx - 10)] # 障礙物前 10 步
local_goal = path[min(len(path) - 1, obs_idx + 10)] # 障礙物後 10 步
# 暫時標記動態障礙物
grid[obs[1]][obs[0]] = 1
# 局部重新規劃
local_path, _ = astar(grid, local_start, local_goal)
if local_path:
# 拼接路徑
new_path = path[:max(0, obs_idx - 10)] + local_path + path[min(len(path)-1, obs_idx + 10):]
return new_path
# 如果局部重新規劃失敗，全域重新規劃
path, _ = astar(grid, start, goal)
return path
return path
使用 Vibe Coding 實作進階尋路
🔥 【進階尋路詠唱範例】
「請幫我實作一個動態路徑規劃系統：1. 使用 200x200 的網格地圖，隨機生成障礙物。2. 實作 JPS 演算法並與 A* 比較效能。3. 實現層級尋路，地圖分割為 20x20 的叢集。4. 加入 3 個動態移動的障礙物。5. 當動態障礙物擋住路徑時，自動局部重新規劃。6. 用 Pygame 視覺化展示整個過程。」
本日總結
在本章中，你學到了：
- ✅ Jump Point Search (JPS)：利用網格對稱性，一次跳過多個格子
- ✅ JPS vs A 比較*：在大地圖上 JPS 可快 10-100 倍
- ✅ 層級尋路：將大地圖分割為叢集，先規劃高層路線
- ✅ 動態障礙物處理：只在路徑附近局部重新規劃
- ✅ 最佳化策略選擇：根據地圖大小與動態程度選擇合適的演算法
恭喜你完成了整個 A 路徑規劃與圖形演算法* 課程！你現在已經具備了圖形理論、BFS/DFS、Dijkstra、A*、JPS、層級尋路與動態路徑規劃的完整知識，能夠在各種真實場景中應用路徑規劃技術。