面试题库 › 游戏开发 › A*寻路算法的原理与实现

A*寻路算法的原理与实现

难度 ★★☆在 1 场真实面经中被问到 方向:游戏开发考点:图论

常见岗位:引擎与图形

答案要点

  1. f(n)=g(n)+h(n),g 为起点到 n 的实际代价,h 为到终点的启发估计
  2. 开放列表用按 f 排序的优先队列,关闭集合记录已确定节点,父指针回溯路径
  3. h 可采纳(不高估)保证最优;h 满足一致性时出队节点无需重新打开
  4. h=0 退化为 Dijkstra,h 高估接近贪心最佳优先,速度快但可能不是最短路
  5. 启发选择:四方向曼哈顿距离,八方向对角距离,任意方向欧氏距离

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题