嗨！大家好，我是小蚂蚁。
这个系列合集关于 2D 游戏中的寻路算法，将主要包含下面的这些内容。
- 寻路算法的发展历程
- 几种寻路算法的区别
- A*寻路算法的原理与实现
在学习一个知识的时候，了解其发展的历程是很有必要的，了解寻路算法是怎样的由宽泛的查找，发展到相对精准的查找，我们最终所学习的现在游戏中普遍使用的 A* 寻路算法是怎样在之前算法的基础上改进演化而来的。了解寻路算法的进化过程，对于理解其中的原理会有很大的帮助。
算法的每一次改进都是站在前人的肩膀上进行的，每次改进的是什么，与原来的区别是什么，我们也会做一些对比和介绍。
最终，我们重点学习的是 A* 寻路算法的原理和实现。在目前的 2D 游戏中，A* 是最常用的寻路算法，可以满足大部分游戏中的自动寻路需求。我们将会详细深入的讲解其实现原理，并以微信小游戏制作工具为基础，从零开始将其实现。
先来看一下最终的效果吧！
我们最终会实现一个这样的示例，在 10x10 的游戏布局中，有兔子，有胡萝卜，有石头障碍，使用 A* 寻路算法帮助兔子找到获取胡萝卜的最佳路径。
目标确定好了，下面就让我们开始第一步吧！
寻路算法的发展历程
广度优先搜索（Breadth First Search）
最早的寻路搜索算法叫做广度优先搜索，什么是广度优先搜索呢？通俗的来讲就是从开始位置不停的向周围找，先找一圈，如果没有找到目标位置，就再找一圈，一圈一圈的直到找到目标位置为止。
举个例子，假设你现在要去商店买泡面加火腿肠，以解决自己肚子咕噜咕噜的预警，按照正常人的思维，你会先去确定一下要去的商店的位置，然后找一条最近的路线前往。但是计算机终究不及人脑发达，假设你按照广度优先搜索的方法去找一家商店，那你将会这样做：先挨个的看一下距离你最近的每一户有没有商店，没有的话就扩大一下范围，再挨个的看一下距离远一点儿的每一户有没商店......随着范围不停的扩大，你找的户数在增加，这样你迟早是能找到一家商店的。
这种方法也太傻了吧！想必你也这样认为。是的，最开始的寻路算法就是这样傻傻的。它不管目的地在自己的哪个方位，只知道一圈一圈的找。想象一下，把一块石头扔进一个平静的湖面，激起一层一层不断扩散的波纹，广度优先搜索的查找方式就是这样。
如图，星星的位置是查找的起点，查找会从起点开始，一圈一圈的向外扩散。
在游戏中通常不会是一片坦途，英雄怎么能不经过历练就直接拯救公主呢？在真实游戏中，起点和终点之间总会存在着各种障碍，比如说无法穿越的墙，想穿过需要消耗更多体力的沼泽和沙漠等等。此时，寻路算法就需要考虑更多的东西，例如是否障碍无法通过？是选择穿过消耗更多体力的沼泽，还是绕过沼泽达到目的地？
本篇教程为付费文章，剩余部分课前往公众号中继续阅读。
