引言
本系列是《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年游戏行业教训的主程。学习游戏开发不迷路。感谢您的关注，心愿能给到您帮忙, 也心愿通过您能帮忙到大家。
喜爱的能够点个赞、点个在看哦！请把该文章分享给你感觉有须要的其余小伙伴。谢谢。