游戏 AI / 系统课时
斜向移动什么时候值得允许
斜向移动什么时候值得允许
把 A* 从四方向扩展到八方向,最明显的变化是路径更短、更接近角色真实运动,但同时会引入斜向步长、切角和启发式不匹配三个问题。本节用可运行示例判断什么时候该允许斜向移动,以及怎样避免“穿墙角”。
学习目标
- 理解四方向与八方向移动在路径长度和代价模型上的差异
- 正确处理斜向步长、切角规则与启发式函数的匹配
- 能根据角色体积和关卡约束决定是否开放斜向邻居
斜向移动改变了什么
四方向网格每次只能上、下、左、右移动,路径常出现明显折线;八方向额外允许四个对角邻居,在开阔区域中可以显著缩短路径。若直走代价设为 1,常见做法是把斜走代价设为约 1.414,这样代价才接近真实几何距离。
问题不只是“多四个邻居”。一旦允许斜走,搜索空间、最短路径长度和启发式函数都要一起调整。继续用只适合四方向的估价方法,可能让启发式高估真实剩余代价,从而破坏 A* 的最优性条件。

切角必须单独处理
如果当前位置右侧和上侧都是障碍,而右上角格子本身可通行,单纯检查目标格会允许角色从两个障碍之间“斜穿”过去。对有碰撞体积的角色,这通常等价于穿墙。
稳妥规则是:从 (r, c) 斜向移动到 (r+dr, c+dc) 时,除了目标格可通行,还要求两个相邻正交格 (r+dr, c) 与 (r, c+dc) 都可通行。这样会略微减少可走路线,但能让离散网格更接近实际碰撞空间。
用可运行示例验证
下面的示例实现同一套 A*,通过参数切换四方向、八方向和防切角规则。四方向使用曼哈顿启发式,八方向使用 Octile 思路计算估价。
import heapq
import math
def astar(grid, start, goal, diagonal=False, prevent_corner_cut=True):
rows, cols = len(grid), len(grid[0])
straight = [(1, 0), (-1, 0), (0, 1), (0, -1)]
diagonal_moves = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
moves = straight + (diagonal_moves if diagonal else [])
def walkable(r, c):
return 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#"
def heuristic(node):
dr = abs(node[0] - goal[0])
dc = abs(node[1] - goal[1])
if not diagonal:
return dr + dc
# 八方向移动时,先走可共享的对角步,再走剩余直线步。
low, high = min(dr, dc), max(dr, dc)
return low * math.sqrt(2) + (high - low)
pq = [(heuristic(start), 0.0, start)]
best = {start: 0.0}
while pq:
_, g, current = heapq.heappop(pq)
if g > best.get(current, math.inf):
continue
if current == goal:
return g
r, c = current
for dr, dc in moves:
nr, nc = r + dr, c + dc
if not walkable(nr, nc):
continue
is_diagonal = dr != 0 and dc != 0
if is_diagonal and prevent_corner_cut:
# 斜走时同时检查两侧正交格,阻止穿过障碍夹角。
if not walkable(r + dr, c) or not walkable(r, c + dc):
continue
step = math.sqrt(2) if is_diagonal else 1.0
new_g = g + step
if new_g < best.get((nr, nc), math.inf):
best[(nr, nc)] = new_g
heapq.heappush(
pq,
(new_g + heuristic((nr, nc)), new_g, (nr, nc)),
)
return None
open_grid = ["....."] * 5
corner_grid = [".#.", "#..", "..."]
print(f"4-dir cost: {astar(open_grid, (0, 0), (4, 4)):.3f}")
print(f"8-dir cost: {astar(open_grid, (0, 0), (4, 4), diagonal=True):.3f}")
print("corner cut allowed:", astar(corner_grid, (0, 0), (1, 1), True, False))
print("corner cut blocked:", astar(corner_grid, (0, 0), (1, 1), True, True))预期输出
4-dir cost: 8.000
8-dir cost: 5.657
corner cut allowed: 1.4142135623730951
corner cut blocked: None开阔区域里,八方向从 8 个直线步代价降到约 5.657;而墙角示例说明,若只看目标格是否可通行,就会产生不合理的斜穿路径。
启发式要和移动规则一起换
四方向且每步代价相同时,曼哈顿距离最自然;八方向且斜向代价约为 1.414 时,更适合使用 Octile 距离。关键不是函数名字,而是启发式不能系统性高估真实最小剩余代价。
若游戏使用自定义移动成本,还应让启发式按“全图最小单步成本”缩放。启发式过大虽然可能搜索更快,却可能把 A* 变成偏贪心的近似搜索。
什么时候值得开放斜向
适合开放斜向移动的场景包括俯视角动作、RTS、开放地形和角色可以连续转向的地图。若关卡由窄走廊、方格机关或严格轴向移动构成,四方向通常更符合规则,也更容易调试。
真正的判断标准是:移动模型、碰撞模型和代价模型是否一致。只有三者都允许角色安全地沿对角线移动,八方向邻接才是对真实空间的合理抽象。