title: "Advanced Techniques: Large-Scale Maps & Performance" description: "Learn JPS, hierarchical pathfinding, and dynamic obstacle handling for massive maps." order: 6
Advanced Techniques: Large-Scale Maps & Performance
Real maps can be huge (millions of nodes) with dynamic obstacles (traffic jams). Standard A* is too slow.
Three industry-standard optimizations:
- Jump Point Search (JPS) - 10-100x faster on grid maps
- Hierarchical Pathfinding - split maps into levels
- Dynamic Path Planning - real-time obstacle avoidance
Jump Point Search (JPS)
JPS is A* optimized for uniform grid maps. It exploits grid symmetry to skip multiple cells at once.
Core Intuition
In open areas, A* adds every cell to Open Set - but many are redundant. JPS only explores key turning points (Jump Points).
Traditional A*:
. . . . . . . .
. S . . . . . . <- explores every cell
. . . . . . G .
JPS (jump points only):
. . . . . . . .
. S------------> G <- jumps over empty space
. . . . . . . .
JPS Implementation
def jump(grid, current, direction, goal):
"""
Jump from current along direction.
Returns Jump Point or None.
"""
x, y = current
dx, dy = direction
nx, ny = x + dx, y + dy
# Out of bounds or obstacle
if not (0 <= nx < len(grid[0]) and 0 <= ny < len(grid)):
return None
if grid[ny][nx] == 1:
return None
# Reached goal
if (nx, ny) == goal:
return (nx, ny)
# Check forced neighbors
# Horizontal: check up/down for obstacles
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)
# Vertical: check left/right for obstacles
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 main loop"""
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
# Get jump points from current node
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* Performance
import time, random
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, goal = (0,0), (size-1,size-1)
print("=== Large Map Comparison (100x100) ===")
t0 = time.time()
astar_path, astar_explored = astar(grid, start, goal)
t1 = time.time()
print(f"A* explored: {len(astar_explored)}, time: {t1-t0:.4f}s")
t0 = time.time()
jps_path, jps_explored = jps_search(grid, start, goal)
t1 = time.time()
print(f"JPS explored: {len(jps_explored)}, time: {t1-t0:.4f}s")
print(f"
JPS node reduction: {len(astar_explored)/len(jps_explored):.1f}x")
print(f"JPS speedup: {(t1-t0)/max(t1-t0,0.001):.1f}x")
Hierarchical Pathfinding
For massive maps (MMORPG worlds), even JPS may be too slow. Use hierarchical pathfinding:
class HierarchicalPathfinder:
"""Two-level hierarchical pathfinding"""
def __init__(self, grid, cluster_size=10):
self.grid = grid
self.cluster_size = cluster_size
self.clusters = {}
self._build_clusters()
def _build_clusters(self):
"""Split large map into clusters"""
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 = []
# Top border
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))
# Bottom border
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))
# Left border
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))
# Right border
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"Map split into {cluster_id} clusters")
def find_path(self, start, goal):
"""Two-level pathfinding"""
start_c = self._find_cluster(start)
goal_c = self._find_cluster(goal)
if start_c == goal_c:
return astar(self.grid, start, goal)[0]
# Different clusters: route through entrances
path = []
start_exits = self.clusters[start_c]["entrances"]
if start_exits:
nearest = min(start_exits, key=lambda e: abs(e[0]-start[0])+abs(e[1]-start[1]))
seg, _ = astar(self.grid, start, nearest)
if seg: path.extend(seg[:-1])
goal_entrances = self.clusters[goal_c]["entrances"]
if goal_entrances:
nearest = min(goal_entrances, key=lambda e: abs(e[0]-goal[0])+abs(e[1]-goal[1]))
seg, _ = astar(self.grid, nearest, goal)
if seg: path.extend(seg)
return path or None
def _find_cluster(self, pos):
x, y = pos
cx, cy = x//self.cluster_size, y//self.cluster_size
return cy * (len(self.grid[0])//self.cluster_size) + cx + 1
Dynamic Obstacle Handling
Real obstacles move (pedestrians, vehicles). We need real-time replanning.
def dynamic_pathfinding(grid, start, goal, dynamic_obstacles):
"""Dynamic pathfinding with local replanning"""
path, _ = astar(grid, start, goal)
if not path:
return None
for obs in dynamic_obstacles:
if obs in path:
obs_idx = path.index(obs)
local_start = path[max(0, obs_idx-10)]
local_goal = path[min(len(path)-1, obs_idx+10)]
grid[obs[1]][obs[0]] = 1
local_path, _ = astar(grid, local_start, local_goal)
if local_path:
path = path[:max(0, obs_idx-10)] + local_path + path[min(len(path)-1, obs_idx+10):]
else:
path, _ = astar(grid, start, goal)
grid[obs[1]][obs[0]] = 0
return path
Performance Optimization Strategies
| Strategy | Effect | Difficulty | |----------|:------:|:----------:| | Hierarchical | Plan highways first, then local roads | High | | Bidirectional A* | Search from both ends, halves search space | Medium | | ALT (A+Landmarks)* | Triangle inequality heuristics | High | | Jump Point Search | Skip nodes on grid maps | Low | | Path caching | Return cached paths for repeated queries | Low |
Summary
- JPS: 10-100x faster on uniform grids using forced neighbors
- Hierarchical: split massive maps into manageable clusters
- Dynamic: re-plan locally around moving obstacles
- Choose technique based on map size, obstacle density, and real-time needs
Course Summary
This course covered: graph theory, BFS/DFS, Dijkstra, A*, and advanced optimizations - the complete graph search toolkit.