思路：深度优先的深宫生成算法，通常使用堆栈实现，这种方法是使用计算机生成迷宫的最简单的方法之一。我们将迷宫看作一个大的棋盘，用一个二维数组表示。随机选择一个单元格为迷宫的起点，对这个单元格的四面墙。随机选择一面墙，如果与此墙相邻的单元格也是墙，则将这面墙及对面的单元格打成通路，并将其添加到栈中，以便于回溯。而后，以此单元格为基点，重复该过程。
直到遇到死路，即四面墙均无法形成通路。此时，通过回溯，直到有可形成通路的单元格。继续生成路径。直到回溯到起点。则已经访问每个可能性单元格。
如上所述，如该算法使用递归，可能在一些计算机体系结构上引起堆栈溢出问题。通过将回溯信息存储在栈中，可以将算法重新排列成循环。这也提供了一种显示解决方案的快速方法，通过在任何给定点开始并回溯到开始。
特性：一般来说，使用深度优先搜索生成的迷宫较其它算法而言可能分支效少，但每条分支长度较长。因为算法在回溯之前沿着每个分支尽可能地探查。为了给深度优先搜索生成的迷宫添加困难和有趣的因素，你可以影响你应该访问哪个方向的可能性，而不是完全随机。通过使它更可能访问你的所指定的单元格，这样可以使你有一个更有趣的迷宫。在某些地方尝试定向通道“偏置”可能导致创建有趣的设计，例如棋盘图案，X等。
算法步骤 :
使初始单元格成为当前单元格并将其标记为已访问;
虽然有未访问的单元格;
如果当前小区具有没有被访问的任何邻居;
随机选择一个未访问的邻居;
将当前单元推送到栈;
移除当前单元格和所选单元格之间的墙;
使所选单元格成为当前单元格，并将其标记为已访问;
否则如果栈不为空;
从堆栈中弹出单元格;
使其成为当前单元格;
如果栈为空结束循环;
UnityC#代码：
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class Maze : MonoBehaviour { // Use this for initialization
void Start () {
ShowMap (CreateMaze (55, 29));
}
int[,] CreateMaze(int x,int y) {
Stack<Vector2> path = new Stack<Vector2> ();
int[,] map = new int[x, y];
for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
map[j,i] = 1;
}
}
Vector2 startPoint = new Vector2 (1, 1);
map [(int)startPoint.x, (int)startPoint.y] = 0;
Vector2 currentPoint = startPoint;
path.Push (currentPoint);
while (true) {
int index = Random.Range (0, 100);
for (int i = 0; i < 4; i++) {
Vector2 currentDir = Loop4Dir(index+i);
Vector2 checkWall = currentPoint+currentDir;
Vector2 checkPoint = currentPoint+currentDir+currentDir;
if (checkPoint.x<0||checkPoint.y<0||checkPoint.x > x-1||checkPoint.y > y-1)
{
continue;
}
if (map[(int)checkPoint.x,(int)checkPoint.y]== 1) {
map[(int)checkWall.x,(int)checkWall.y] = 0;
map[(int)checkPoint.x,(int)checkPoint.y] = 0;
currentPoint = checkPoint;
path.Push (currentPoint);
i = 0;
index = Random.Range(0,100);
}
}
if (currentPoint==startPoint) break;
currentPoint = path.Pop();
}
return map;
}
void ShowMap(int[,] map){
for (int i = 0; i < map.GetLength(1); i++) {
for (int j = 0; j < map.GetLength(0); j++) {
switch (map[j,i]) {
case 1:{
GameObject tempGO = GameObject.CreatePrimitive(PrimitiveType.Cube);
tempGO.transform.position = new Vector3(j,0,i);
}
break;
default:break;
}
}
}
}
Vector2 Loop4Dir(int index){
index %= 4;
switch (index) {
case 0: return Vector2.up;
case 1: return Vector2.right;
case 2: return -Vector2.up;
default:return -Vector2.right;
}
}
}
最终生成的参考图:
