(c++)迷宫自动寻路-队列-广度优先算法-附带寻路打印动画

摘要

　1.效果图

　　其中正方形代表障碍物，实心菱形代表移动者（人），空心菱形代表目标位置（都是可以在代码中修改的）

 　2.本例使用队列(链表实现)，以广度优先进行自动寻路。

1.实现代码

　　1.队列方法类

 coolQueue.h

 coolQueue.cpp

　　2.地图方法类

 mapClass.h

 mapClass.cpp

　　3.main函数

 main.cpp

2.思路

　　总体和数据结构的教科书上的大差不差：以起点为中心，每向外一步作为一轮循环，循环中把可走的位置入队，下一轮循环把上一轮入队的位置出队并再以这些位置为中心往外走一步，把可走位置入队，一直这样循环，直到遇到终点位置或者队列中为空（因为每一个方向都走不了则队列循环后为空）。

　　（想象一下在没有障碍物的地图中，以起点为中心向外扩散）

　　在上述过程中，把可走位置入队的同时留下方向标记（上一个位置走到此位置的方向），在循环结束后从终点位置倒推即可找到一条回到起点的路径。

　　此路径为最优解（最优解可能不止一条），因为算法中是从起点往外每一步进行一轮判断，因此如果找到了终点，那么就是在最少的步数内找到了终点，此时即可结束循环，此为最优解。如果不结束，继续找下去可能可以找到用更多步数的路径。

　　本例与书中的不同：

　　　　1.在找到路径后利用system("cls")清屏重新输出，来实现逐步走向终点的效果。

　　　　2.在一些细节的实现上使用不同的尝试(例如 mapClass::auto_find_way()中使用sin()，直接使用地图做方向标记等)

　　　　 3.支持循环多次寻路，支持重置障碍物位置