基于深度优先的迷宫生成算法

思路：深度优先的深宫生成算法，通常使用堆栈实现，这种方法是使用计算机生成迷宫的最简单的方法之一。我们将迷宫看作一个大的棋盘，用一个二维数组表示。随机选择一个单元格为迷宫的起点，对这个单元格的四面墙。随机选择一面墙，如果与此墙相邻的单元格也是墙，则将这面墙及对面的单元格打成通路，并将其添加到栈中，以便于回溯。而后，以此单元格为基点，重复该过程。

直到遇到死路，即四面墙均无法形成通路。此时，通过回溯，直到有可形成通路的单元格。继续生成路径。直到回溯到起点。则已经访问每个可能性单元格。

如上所述，如该算法使用递归，可能在一些计算机体系结构上引起堆栈溢出问题。通过将回溯信息存储在栈中，可以将算法重新排列成循环。这也提供了一种显示解决方案的快速方法，通过在任何给定点开始并回溯到开始。

特性：一般来说，使用深度优先搜索生成的迷宫较其它算法而言可能分支效少，但每条分支长度较长。因为算法在回溯之前沿着每个分支尽可能地探查。为了给深度优先搜索生成的迷宫添加困难和有趣的因素，你可以影响你应该访问哪个方向的可能性，而不是完全随机。通过使它更可能访问你的所指定的单元格，这样可以使你有一个更有趣的迷宫。在某些地方尝试定向通道“偏置”可能导致创建有趣的设计，例如棋盘图案，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;

        }

    }

}

最终生成的参考图: