最近准备面试一家游戏公司，不得不说游戏公司现在真不好进啊（是不是我太菜了TAT）。终于有了一家找我上来就甩给我一道题，初级Unity面试题。需求如下：
1.有且只有一条正确路径
2.每一个格子都是连通的
3.每一个格子至少有一面墙
4.用Unity实现
5.需要两个按钮一个重新生成新迷宫，一个自动寻路。
平常的时候我也是比较注重算法训练，但是刚刚上手这个题目还是有一点点懵，所以网上查了一下资料。我当时主要看的算法有两种，第一种Prime算法，第二种深度优先探索（DFS）。大神们写的都很好，做的时候我也有了一些自己的心得，以此记录一下。
首先是Prime，这种算法的思路：
1.建一个数组，将数组中所有元素初始设为墙。（我用的int数组，0是墙，路是1）
2.做一个预处理，先将迷宫最外层先全部设置成路。（这是为了后面迷宫生成的判断条件，并保护最外层迷宫）
3.随机在迷宫中选择一个墙加入数组，最好不要选择最外层，后面的起点终点方便规定一些。
4.做一个While循环，条件是数组中元素不为0，每一次循环，随机在数组中挑选一个元素（墙）出来，并判断该墙四周的路是否小于等于1，若符合则将该墙变为路，并将该墙四周的墙新加入数组。
5.跳出循环后规定起点和终点。（条件是起点，终点的墙必须和里面的路连通）
这样我们的迷宫数组就规划好啦，剩下还有一个难点，就是自动寻路功能。这也是Prime在本题里面不太好用的地方，他有两个需求不好达到，所以我有尝试了一下深度优先的方法，思路如下：
1.建一个数组，将数组中所有元素初始设为墙。（我用的int数组，0是墙，路是1）
2.做一个预处理，先将迷宫最外层先全部设置成路。（这是为了后面迷宫生成的判断条件，并保护最外层迷宫）（1，2其实是一样的）
3.随机选择一个最外层墙入栈作为起点（这里数据结构是用的堆栈）
4.一样用While循环，终止条件是栈中元素为空。每一次循环，选择栈顶元素（不要弹出去），在此元素的四个方向中随机选择一个方向的墙体，判断它是否可以入栈，判断条件是：该墙体的四周有且仅有一条路。若符合，则将它入栈，并把该墙体变为路。若该栈顶元素四个方向均无符合条件的墙体，则将该元素弹出。
5.跳出循环后规定终点。（条件是终点的墙必须和里面的路连通）
这一种方法的好处是，路径比较好规划，随机性没有那么强。但是在这里我也没有找到一个很好的方法去做一个路径规划的判定。但是我们要知道，这条路径一定是足够长的，因为他是会有很长的一条路径的从头到尾连通的。所以我们可以有一个很大概率能找到最短路径的方法，以该数组一个大致的长度为界限。小于该长度的时候，将无用的元素移除。这样我们就能有一个还算不错的寻路方法了。
由于本人还是个菜鸟，代码就不贴了，有想要探讨的小伙伴可以私聊我，也请大佬能教教如何写更好的寻路方法。
