6
第6-1课：A* 算法
source link: https://blog.csdn.net/orbit/article/details/108729346
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
在第3-7课：推箱子游戏中，我们已经应用了 A* 算法，但是并没有展开介绍该算法的原理，这一课来补上。A（A-Star）算法和 Dijkstra 算法一样，都是求最短路径的搜索算法，不过 Dijkstra 算法比较直接，上来就是 BFS 搜索；A 算法则用了一点“启发”技术，所谓的启发，其实都是很简单的距离向量的判断。但是不要小看这一点“启发”，会使得 A* 算法在搜索效率上优于 Dijkstra 算法。除了介绍 A* 算法的原理，这一课还将演示一个程序，结合这个演示程序大家可以理解 A* 算法是如何被应用到实际应用中的。“推箱子游戏”展示了另一种 A* 算法的应用，当然，它们的数据模型是不一样的，请体会一下我一直强调的算法和算法应用的区别。
演示程序设计
很多古老的二维 RPG 游戏（Role-Playing Game，角色扮演游戏）中角色的自动移动，大多数都是用的 A* 算法自动寻路并绕开障碍物的，因为 A* 算法不仅实现简单，效果也不差。这一课将向大家直观地展示 A* 算法的寻路效果，我设计了一个 A* 算法的演示程序。《算法的乐趣》这本书也是用的这个演示程序，但是没有展开介绍是如何将 A* 算法应用到这个演示程序中的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK