游戏 AI / 系统课时
怎样平滑网格路径避免折线
怎样平滑网格路径避免折线
A* 在网格上找到的路径通常由相邻格子中心组成,角色直接逐点移动会频繁转向。本节用“可见性裁剪”把多余节点删掉,同时保留绕开障碍的关键拐点,最终得到更适合角色执行的路径。
学习目标
- 理解网格路径出现锯齿和多余拐点的原因
- 用视线检测删除可直接跨越的中间节点
- 知道平滑时为什么必须把角色半径和碰撞安全纳入判断
从节点路径变成转向点
A* 的职责是从搜索图中找出一条代价较低的节点链,它并不保证角色移动轨迹视觉上平滑。四方向或八方向网格都会把连续空间离散成格子,因此原始结果常包含“走一格、转一次”的折线。
真正交给移动系统的路径可以更短:从当前锚点开始,尝试直接连到更远的后续节点;如果中间没有障碍,就跳过这些节点。只有当直连会穿过障碍时,才保留必要拐点。

用最远可见节点做裁剪
下面的 Python 示例使用 Bresenham 栅格线检查两个节点之间是否穿过阻塞格,并始终选择当前锚点能够直接看到的最远后续节点。它适合演示算法核心;真实游戏里应把 line_of_sight 替换成引擎的射线、胶囊体或导航空间检测。
from typing import List, Set, Tuple
Point = Tuple[int, int]
def line_of_sight(a: Point, b: Point, blocked: Set[Point]) -> bool:
x0, y0 = a
x1, y1 = b
dx, dy = abs(x1 - x0), abs(y1 - y0)
sx = 1 if x0 < x1 else -1
sy = 1 if y0 < y1 else -1
err = dx - dy
while True:
if (x0, y0) in blocked:
return False
if (x0, y0) == (x1, y1):
return True
e2 = 2 * err
if e2 > -dy:
err -= dy
x0 += sx
if e2 < dx:
err += dx
y0 += sy
def smooth_path(path: List[Point], blocked: Set[Point]) -> List[Point]:
if len(path) <= 2:
return path[:]
result = [path[0]]
anchor = 0
while anchor < len(path) - 1:
candidate = len(path) - 1
# 从终点向前找,保留当前锚点能直接到达的最远节点。
while candidate > anchor + 1 and not line_of_sight(
path[anchor], path[candidate], blocked
):
candidate -= 1
result.append(path[candidate])
anchor = candidate
return result
blocked = {(2, 1), (2, 2), (2, 3)}
raw_path = [
(0, 1), (1, 1), (1, 2), (1, 3),
(1, 4), (2, 4), (3, 4), (4, 4)
]
print(smooth_path(raw_path, blocked))预期输出:
[(0, 1), (2, 4), (4, 4)]原路径有 8 个节点,裁剪后只剩 3 个转向点。关键不是“节点越少越好”,而是每次跨越都必须通过同一套可通行性判定。
平滑不能破坏碰撞安全
只检查格子中心连线仍可能产生切角:线段数学上没有进入阻塞格,但角色有实际半径,贴近墙角时仍会碰撞。因此角色越宽,检测也应越接近真实碰撞体,而不是永远使用一条零宽射线。
如果游戏允许任意角度移动,可以用胶囊体扫掠或带半径的导航检测验证两点直连;如果角色仍受网格规则约束,则应使用“超级覆盖线”或同时检查对角线两侧格子,避免从两个相邻障碍之间切过去。
什么时候还需要曲线
可见性裁剪解决的是“转向点过多”,不等于让角色运动连续。车辆、飞行器或有转向速度限制的单位,还需要在这些安全转向点之上做圆弧、样条或转向控制。
这时应先得到一条碰撞安全的折线路径,再让运动层生成连续轨迹,并对生成后的曲线重新做碰撞验证。搜索层保证可达,裁剪层减少冗余节点,运动层负责视觉和动力学平滑,三者分开更容易定位问题。