基础 | 图与路径查找----BFS
本系列为笔者初学c/c++和游戏AI开发的学习过程，算法为主，不涉及到具体的游戏开发软件学习(如unity，虚幻4等),若有错误请在评论区留下批评意见。
语言：c/c++ (11及以上)
平台：macOS mojave
编辑器/编译器：vs Code / g++
图与路径查找
四、BFS 广度优先搜索
4.1 广度优先搜索
广度优先搜索（Breadth First Search）是一种盲目搜索算法，图形搜索算法。
简单来讲，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。
----维基百科
以上图为例，我们先搜索节点1，再搜索节点1的全部子节点2、3、4，接着搜索节点2的全部子节点......以此类推，直到树的全部节点都搜索过。
对于图来说，广度优先搜索的过程也是一样的。直到把一个节点的全部子节点遍历完，才会进行下一个节点的遍历。
4.2 算法逻辑步骤
广度优先搜索的实现可归纳为以下几个步骤：
首先将根节点放入队列中
从队列中取出第一个节点，并检验它是否为目标。
如果找到目标，则结束搜索并回传结果。
否则将它所有尚未检验过的直接子节点加入队列中。
队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
重复步骤2。
4.3 算法代码实现
对应在游戏场景中，整个分割后的地图就是一个个节点组成的图（数学上），每个节点的子节点就是该节点周围的8个节点。
因此，与A*算法类似，我们用一个openList存储未遍历的节点，closeList存储遍历过的节点，并且返回closeList列表当做需要渲染的搜索路径。
这里笔者犯了个错误，应该先讲BFS再讲A*算法，因为A*算法是BFS算法的改良，很多概念应该先理解了BFS才更好。
我们用指针来记录从起始节点A到目标节点B的路径节点，并返回一个列表：
在算法主体 findPath（）方法中实现BFS：
在代码实现过程中，我们因为项目需求而将BFS算法的步骤做了简单的拆解，不仅记录全部的搜索过程，还记录了一条从A到B的路径。
当然，图里的步骤 2.1 需要消耗大量的计算资源，后面如果有需要可以再进一步的优化。
由于我们之前在Game类中编写大地图的时候，已经为项目拓展留下了空间，因此只要在原来的基础上加入新的模块，用来获取BFS算法返回的结果即可。
4.3 结果演示
参考
维基百科
相关代码下载 https://github.com/linpeijie/GameToy
