乐趣区

关于前端:请这样回答面试官什么是A星寻路

引言

本系列是《8 年主程手把手打造 Cocos 独立游戏开发框架》,欢送大家关注分享珍藏订阅。

很多小伙伴一听到 A 星算法,第一反馈就是它就是个寻路的算法,我会。确实是,把握了算法的人,天然感觉容易。然而对于游戏开发新人或者刚接触 A 星算法的人,这个算法还是很难很简单的。而且让把握的人在游戏我的项目中使用,也不肯定能第一工夫敲进去。上面追随笔者一起来看看。

本文源码和源工程在文末获取,小伙伴们自行返回。

什么是 A 星算法?

A 星算法(A-star algorithm)是一种广泛应用的门路布局算法,它被设计用来在图形或网络中寻找两个节点之间的最短门路。

A 星算法的原理

A 星算法是一种启发式搜索算法,联合了广度优先搜寻和最佳优先搜寻的特点。其核心思想是通过评估每个可能的门路,以找到从终点到指标节点的最佳门路。在 A 星算法中,每个节点都有两个要害值:

  1. G 值(代价):示意从终点到以后节点的理论代价,即曾经走过的门路长度。
  2. H 值(启发式值):示意从以后节点到指标节点的预计代价,即预计还须要走多远能力达到目标。

A 星算法的步骤

简略列举一下 A 星算法的步骤,大家写代码时能够依据算法的步骤间接 ” 翻译 ” 过去就行:

  1. 创立一个凋谢列表和一个敞开列表,用于存储待摸索和已摸索的节点。
  2. 将终点增加到凋谢列表,并将其 G 值设为 0。
  3. 反复以下步骤直到找到指标节点或凋谢列表为空:a. 从凋谢列表中抉择 F 值最小的节点(通常是 H 值 + G 值最小的节点)。b. 将该节点从凋谢列表移至敞开列表。c. 对该节点的街坊节点进行遍历,计算它们的 G 值和 H 值。d. 如果街坊节点不在凋谢列表中,将其增加到凋谢列表,并更新其 G 值和父节点。e. 如果街坊节点已在凋谢列表中,查看以后门路是否更短,如果更短则更新 G 值和父节点。
  4. 当找到指标节点或凋谢列表为空时,搜寻完结。

A 星算法的劣势

  1. 齐备性:如果存在可行解,A* 算法可能找到最佳门路。
  2. 启发式搜寻:通过应用启发式估计值,A* 算法能够在大型图形中高效搜寻,缩小搜寻空间。
  3. 适应性:A* 算法能够依据不同问题的需要和启发式函数进行定制。
  4. 广泛应用:A* 算法在多个畛域都有胜利的利用记录,因而被宽泛应用。

A 星算法实际

1. 关上上一篇文章的工程

如下图,笔者曾经编辑好整个地图的阻挡信息(红色局部),蓝色原点是终点地位。绿色的是起点地位。红色的是门路点。

2. 依据地图信息抽象化数据

创立网格,并且依据地图信息标记阻挡格子不可行走。

3. 创立 AStar 类

创立一个凋谢列表和一个敞开列表,用于存储待摸索和已摸索的节点。并且将终点退出 Open 集设置 G 值为 0。

4. 检索门路

反复以下步骤直到找到指标节点或凋谢列表为空:a. 从凋谢列表中抉择 F 值最小的节点(通常是 H 值 + G 值最小的节点)。b. 将该节点从凋谢列表移至敞开列表。c. 对该节点的街坊节点进行遍历,计算它们的 G 值和 H 值。d. 如果街坊节点不在凋谢列表中,将其增加到凋谢列表,并更新其 G 值和父节点。e. 如果街坊节点已在凋谢列表中,查看以后门路是否更短,如果更短则更新 G 值和父节点。直到达到起点检索完结。

5. 构建门路

通过链表反向造成门路。

6. 编写测试代码

仍旧通过 cc.Graphics 去绘制终点、起点、门路和阻挡。

每次点击地图之后从新生成门路并且从新绘制。

7. 后果演示

总结

A 星算法是一种弱小的门路布局算法,通过综合思考理论代价和启发式预计,可能在游戏寻路中中寻找最佳门路。它的原理简略但功能强大,为解决许多游戏中的导航和布局问题提供了无力的工具。

本文的重点内容次要有以下几点,不晓得小伙伴们是否曾经了解:

  • 本系列是《8 年主程手把手打造 Cocos 独立游戏开发框架》,欢送大家关注分享珍藏订阅。
  • A 星算法的概念、原理、步骤和劣势以及实际。
  • 源码通过关注“亿元程序员”发送 ”Astar” 获取。

AD: 笔者曾经上线的小游戏《填色之旅》《贪吃蛇掌机经典》《重力迷宫球》大家能够自行点击搜寻体验。

感兴趣的小伙伴记得关注 ” 亿元程序员 ” 哦,一位有着 8 年游戏行业教训的主程。学习游戏开发不迷路。感谢您的关注,心愿能给到您帮忙, 也心愿通过您能帮忙到大家。

喜爱的能够点个 、点个 在看 哦!请把该文章 分享 给你感觉有须要的其余小伙伴。谢谢。

退出移动版