游戏 AI / 系统课时

A*为什么需要地图抽象

A*为什么需要地图抽象

寻路算法不能直接理解“地面、墙体、斜坡和房间”这些场景对象。它需要的是一组可枚举的位置,以及位置之间能否到达、移动代价多少。地图抽象的目标,就是把连续世界转成算法可以搜索的离散空间。

学习目标

  • 理解直线移动和随机探索为什么无法解决一般寻路问题
  • 说清地图抽象至少要提供哪些搜索信息
  • 能判断网格、路点和导航网格分别适合什么场景

为什么直接朝目标移动不够

最简单的 NPC 移动方式,是每帧朝目标位置前进。空旷场地里它看起来有效,但一旦中间出现墙体、河流或不可跨越高差,NPC 只能撞在障碍上。它知道“目标在哪”,却不知道“从哪里绕过去”。

随机探索虽然能偶尔绕开障碍,却没有方向性,也无法保证在有限时间内找到路线。更关键的是,算法没有一个明确的“下一步候选集合”,就无法系统地比较不同路线。

因此,寻路真正需要解决的不是“往哪个方向走”,而是把问题改写成:当前位置可以到哪些位置,这些位置离目标还有多远,经过它们要付出多少代价。

地图抽象到底提供什么

A* 搜索通常把地图看成一个图。图中的节点代表可停留或可经过的位置,边代表两个位置之间允许移动,边权代表移动代价。算法只在这张图上工作,并不直接处理场景里的模型、贴图或碰撞体。

连续关卡抽象为可搜索图的关系

一个可用的搜索空间至少要回答三类问题:

  • 节点是什么:例如格子中心、人工路点或导航多边形。
  • 邻居是谁:例如四方向、八方向,或同一导航区域中可直接通行的位置。
  • 代价是多少:例如直走代价、斜走代价、泥地额外代价,甚至危险区域惩罚。

A* 后续使用的启发式距离,也依赖这个抽象。只有先把“位置”和“连接关系”定义清楚,算法才知道该从哪些候选节点中继续扩展。

抽象粒度会直接改变寻路结果

地图抽象不是越精细越好。节点越多,路线通常越贴近真实地形,但搜索需要处理的状态也越多;节点太少,搜索更快,却可能错过窄路、拐角或局部障碍。

常见做法有三类:

抽象方式 节点含义 优点 典型代价
网格 Grid 一个离散格子 规则、易实现、易调试 大地图节点数量多
路点 Waypoint 人工或自动生成的关键位置 节点少、路线清晰 需要维护连接关系
导航网格 NavMesh 可行走区域多边形 适合连续 3D 场景 构建与动态更新更复杂

二维方格地图通常从网格开始最合适;开放 3D 场景更常使用导航网格;固定道路网络或飞行航线则可能更适合路点图。

什么时候说明抽象有问题

如果 A* 的搜索逻辑没有错误,却仍然出现“明明有路却找不到”“穿墙”“无法通过看起来很宽的通道”,首先应检查搜索空间,而不是立刻修改启发式函数。

常见根因是可通行状态标错、邻接关系漏连、角色尺寸没有计入、世界坐标映射到错误节点,或者抽象粒度过粗。A* 只能在你提供的空间里寻找最优路线;如果正确路线根本没有被表示出来,算法再准确也不可能找到它。

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

目录与阅读设置

阅读设置

17

记录一个想法

A*为什么需要地图抽象

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

登录哪都通