共计 1686 个字符，预计需要花费 5 分钟才能阅读完成。
引言
本系列是《8 年主程手把手打造 Cocos 独立游戏开发框架》，欢送大家关注分享珍藏订阅。
很多小伙伴一听到 A 星算法，第一反馈就是它就是个寻路的算法，我会。确实是，把握了算法的人，天然感觉容易。然而对于游戏开发新人或者刚接触 A 星算法的人，这个算法还是很难很简单的。而且让把握的人在游戏我的项目中使用，也不肯定能第一工夫敲进去。上面追随笔者一起来看看。
本文源码和源工程在文末获取，小伙伴们自行返回。
什么是 A 星算法？
A 星算法（A-star algorithm）是一种广泛应用的门路布局算法，它被设计用来在图形或网络中寻找两个节点之间的最短门路。
A 星算法的原理
A 星算法是一种启发式搜索算法，联合了广度优先搜寻和最佳优先搜寻的特点。其核心思想是通过评估每个可能的门路，以找到从终点到指标节点的最佳门路。在 A 星算法中，每个节点都有两个要害值：
- G 值（代价）：示意从终点到以后节点的理论代价，即曾经走过的门路长度。
- H 值（启发式值）：示意从以后节点到指标节点的预计代价，即预计还须要走多远能力达到目标。
A 星算法的步骤
简略列举一下 A 星算法的步骤，大家写代码时能够依据算法的步骤间接 ” 翻译 ” 过去就行：
- 创立一个凋谢列表和一个敞开列表，用于存储待摸索和已摸索的节点。
- 将终点增加到凋谢列表，并将其 G 值设为 0。
- 反复以下步骤直到找到指标节点或凋谢列表为空：a. 从凋谢列表中抉择 F 值最小的节点（通常是 H 值 + G 值最小的节点）。b. 将该节点从凋谢列表移至敞开列表。c. 对该节点的街坊节点进行遍历，计算它们的 G 值和 H 值。d. 如果街坊节点不在凋谢列表中，将其增加到凋谢列表，并更新其 G 值和父节点。e. 如果街坊节点已在凋谢列表中，查看以后门路是否更短，如果更短则更新 G 值和父节点。
- 当找到指标节点或凋谢列表为空时，搜寻完结。
A 星算法的劣势
- 齐备性：如果存在可行解，A* 算法可能找到最佳门路。
- 启发式搜寻：通过应用启发式估计值，A* 算法能够在大型图形中高效搜寻，缩小搜寻空间。
- 适应性：A* 算法能够依据不同问题的需要和启发式函数进行定制。
- 广泛应用：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 年游戏行业教训的主程。学习游戏开发不迷路。感谢您的关注，心愿能给到您帮忙, 也心愿通过您能帮忙到大家。
喜爱的能够点个 赞、点个 在看 哦！请把该文章 分享 给你感觉有须要的其余小伙伴。谢谢。
