游戏 AI / 系统课时

让泥地和道路拥有不同代价

让泥地和道路拥有不同代价

如果每个格子的移动代价都等于 1,A* 只会倾向于走几何距离更短的路线。真实关卡里,道路、泥地、浅水或危险区域的通行成本往往不同。本节把地形成本纳入 g 值,让算法即使多走几步,也能主动避开昂贵区域。

学习目标

  • 把地形移动成本加入 A* 的累计代价 g
  • 理解高代价格子为什么会改变最终路径
  • 在存在不同地形成本时保持启发式函数的正确性

把“最短”改成“总代价最低”

普通四方向网格里,如果每走一步都记 1,那么累计代价只等于步数。加入地形后,从当前节点进入相邻格子的更新规则应改为:

g′(n)=g(current)+cost(n)g'(n)=g(current)+cost(n)

例如道路成本为 1、泥地成本为 5。直穿泥地虽然只走 6 步,但累计代价可能远高于绕路走 8 步道路。A* 比较的是 f = g + h,所以只要 g 正确记录真实移动成本,搜索就会自然偏向更便宜的路线。

道路与泥地代价改变A*选路结果

在 A* 中累加地形成本

下面的示例把字符地图转换成网格。R 代表道路,M 代表泥地,起点 S 和终点 G 都按道路成本计算。启发式仍使用曼哈顿距离,但乘以全图最小单步成本 1,保证它不会高估剩余代价。

python
import heapq

TERRAIN_COST = {
    'R': 1,
    'M': 5,
    'S': 1,
    'G': 1,
}


def astar(terrain: list[str], start: tuple[int, int], goal: tuple[int, int]):
    rows, cols = len(terrain), len(terrain[0])
    min_step_cost = min(TERRAIN_COST.values())

    def heuristic(a: tuple[int, int], b: tuple[int, int]) -> int:
        distance = abs(a[0] - b[0]) + abs(a[1] - b[1])
        return distance * min_step_cost

    open_heap = [(heuristic(start, goal), 0, start)]
    g_score = {start: 0}
    came_from: dict[tuple[int, int], tuple[int, int]] = {}

    while open_heap:
        _, current_g, current = heapq.heappop(open_heap)
        if current_g != g_score.get(current):
            continue

        if current == goal:
            path = [current]
            while current in came_from:
                current = came_from[current]
                path.append(current)
            path.reverse()
            return path, g_score[goal]

        r, c = current
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue

            neighbor = (nr, nc)
            # 这里采用“进入目标格子时支付该地形成本”的统一规则。
            next_g = current_g + TERRAIN_COST[terrain[nr][nc]]
            if next_g < g_score.get(neighbor, float('inf')):
                g_score[neighbor] = next_g
                came_from[neighbor] = current
                f = next_g + heuristic(neighbor, goal)
                heapq.heappush(open_heap, (f, next_g, neighbor))

    return [], float('inf')


if __name__ == '__main__':
    terrain = [
        'RRRRRRR',
        'RRRRRRR',
        'SMMMMMG',
        'RRRRRRR',
        'RRRRRRR',
    ]

    path, total_cost = astar(terrain, (2, 0), (2, 6))
    print(path)
    print('total_cost =', total_cost)

预期输出:

text
[(2, 0), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6)]
total_cost = 8

直线穿过中间泥地需要进入 5 个泥地格,再进入终点,总成本为 26;绕到上一行虽然需要 8 次移动,但全是成本为 1 的格子,因此总代价只有 8。

启发式也要跟着成本模型检查

地形成本改变后,最容易犯的错误是只修改 g,却继续使用一个可能高估真实剩余成本的 h。对于四方向移动,安全做法是用曼哈顿距离乘以“最小可能单步成本”。

如果最便宜地形成本是 1,那么:

h(n)=(∣xn−xg∣+∣yn−yg∣)×1h(n)=(|x_n-x_g|+|y_n-y_g|)\times 1

这样 h 只给出乐观下界,不会假设未来一定要经过泥地。若以后引入道路成本 0.5,就应把最小单步成本同步改成 0.5,而不是继续乘 1。

用代价表达偏好而不是硬禁行

高代价和不可通行是两种不同语义。泥地成本 5 表示“能走,但尽量别走”;墙体则应该直接从邻居集合中排除。若把所有不喜欢的区域都设成极大成本,算法仍可能在别无选择时穿过去,而且会让调参变得困难。

实际项目中可以先保持少量清晰的地形等级,例如道路 1、草地 2、泥地 5,再通过游戏体验逐步调整。只要 g 使用真实地形成本、h 保持不高估,A* 就能稳定地在“距离更短”和“通行更便宜”之间做出正确权衡。

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

目录与阅读设置

阅读设置

17

记录一个想法

让泥地和道路拥有不同代价

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

登录哪都通