游戏 AI / 系统课时

怎样平滑网格路径避免折线

怎样平滑网格路径避免折线

A* 在网格上找到的路径通常由相邻格子中心组成,角色直接逐点移动会频繁转向。本节用“可见性裁剪”把多余节点删掉,同时保留绕开障碍的关键拐点,最终得到更适合角色执行的路径。

学习目标

  • 理解网格路径出现锯齿和多余拐点的原因
  • 用视线检测删除可直接跨越的中间节点
  • 知道平滑时为什么必须把角色半径和碰撞安全纳入判断

从节点路径变成转向点

A* 的职责是从搜索图中找出一条代价较低的节点链,它并不保证角色移动轨迹视觉上平滑。四方向或八方向网格都会把连续空间离散成格子,因此原始结果常包含“走一格、转一次”的折线。

真正交给移动系统的路径可以更短:从当前锚点开始,尝试直接连到更远的后续节点;如果中间没有障碍,就跳过这些节点。只有当直连会穿过障碍时,才保留必要拐点。

从锯齿节点路径裁剪为安全转向点

用最远可见节点做裁剪

下面的 Python 示例使用 Bresenham 栅格线检查两个节点之间是否穿过阻塞格,并始终选择当前锚点能够直接看到的最远后续节点。它适合演示算法核心;真实游戏里应把 line_of_sight 替换成引擎的射线、胶囊体或导航空间检测。

python
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))

预期输出:

text
[(0, 1), (2, 4), (4, 4)]

原路径有 8 个节点,裁剪后只剩 3 个转向点。关键不是“节点越少越好”,而是每次跨越都必须通过同一套可通行性判定。

平滑不能破坏碰撞安全

只检查格子中心连线仍可能产生切角:线段数学上没有进入阻塞格,但角色有实际半径,贴近墙角时仍会碰撞。因此角色越宽,检测也应越接近真实碰撞体,而不是永远使用一条零宽射线。

如果游戏允许任意角度移动,可以用胶囊体扫掠或带半径的导航检测验证两点直连;如果角色仍受网格规则约束,则应使用“超级覆盖线”或同时检查对角线两侧格子,避免从两个相邻障碍之间切过去。

什么时候还需要曲线

可见性裁剪解决的是“转向点过多”,不等于让角色运动连续。车辆、飞行器或有转向速度限制的单位,还需要在这些安全转向点之上做圆弧、样条或转向控制。

这时应先得到一条碰撞安全的折线路径,再让运动层生成连续轨迹,并对生成后的曲线重新做碰撞验证。搜索层保证可达,裁剪层减少冗余节点,运动层负责视觉和动力学平滑,三者分开更容易定位问题。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

怎样平滑网格路径避免折线

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通