于是心血来潮，做了点研究，找到了几个不错的迷宫生成算法。
这篇文章不需要任何特定基础
你甚至可以用纸和笔直接手动生成迷宫！
（但是你要知道什么叫做堆栈）
【Recursive Backtracker】
基本步骤：1、随便选一个格子听得云里雾里吧？
2、在该格子的相邻4个格子中，找出4面墙壁都完好的格子，随便选一个，然后将现在的格子与相邻的格子之间的墙壁打通，将选中的相邻入栈，已访问的格子数量+1；如果在相邻的4个格子之中都找不到4面墙壁都完好的格子，出栈，然后将其设置为下一轮的选中格子
3、继续一直到没有格子可选择（就是已经访问的格子等于总格子）
【例子】
假设我们有一个3*3的正方格：
现在随便选一个格子（紫色）：
然后找出相邻的格子（4面墙都完好的）（蓝色）：
在他们之中随便选一个（绿色）
将其推入堆栈
（这里我用号码来表示格子在堆栈内的位置
0为最尾端，也就是最底层）
将其设置为下一轮选中的格子
打通他们之间的墙，两个格子相连（紫色）：
下一轮
找出4面墙都完好的格子
（刚开始的紫色框框(2,1)，已经西面的墙已经倒下，所以不选）
随便选一个格子：
打通墙壁：
下一轮：
下一轮的时候
你会发现到(2,0)的邻居都没有完好的4面墙了
所以我们把弹出堆栈，也就是(2,0) （用红色表示）
将其设为下一轮的选中格子
下一轮
下一轮：
下一轮
下一轮
下一轮
到这里我们已经有一个很不错的迷宫了：
起点为黄色
【C#实现】
全部代码已经push 到GitHub 上：
每一个格子为一个class，名为Node
using System;
using System.Collections.Generic;
using System.Linq;
using System.Drawing;
namespace MazeGen
{
public class Node
{
private bool _isFrontier;
private List<ParentInfo> _parentInfo = new List<ParentInfo>();
private bool _isBacktracked;
private bool _isStart;
private Point _pos;
private const int _count = 4;
private Node _down;
private Node _up;
private Node _right;
private Node _left;
/// <summary>
/// Status of the four wall
/// 0 = still there
/// 1 = destroyed
/// ____________________
/// |Left|Down|Right| Up |
/// |_8__|_4__|__2__|_0__|
/// </summary>
private int _wall = 0;
/// <summary>
/// Mark the wall as destroyed
/// </summary>
/// <param name="index">Up = 0 Left = 1 Down = 2 Right = 3</param>
public void UnWall(int index)
{
_wall |= 1 << index;
}
/// <summary>
/// Get a wall's status
/// </summary>
/// <param name="index"></param>
/// <returns>True = Wall destroyed </returns>
public bool GetWall(int index)
{
return (_wall & (1 << index)) == (1 << index);
}
/// <summary>
/// Mark the wall as not destroyed
/// </summary>
/// <param name="index"></param>
public void SetWall(int index)
{
_wall &= ~(1 << index);
}
public Node this[int index]
{
get
{
return SwitchNodeProp(index);
}
set
{
SwitchNodeProp(index, value);
}
}
private Node SwitchNodeProp(int index, Node value = null)
{
switch (index)
{
case 0:
return ReturnNodeProp(ref _up, value);
case 1:
return ReturnNodeProp(ref _right, value);
case 2:
return ReturnNodeProp(ref _down, value);
case 3:
return ReturnNodeProp(ref _left, value);
}
return null;
}
private Node ReturnNodeProp(ref Node prop, Node value = null)
{
if (value == null)
{
return prop;
}
else
{
prop = value;
return null;
}
}
public Node Left
{
get
{
return _left;
}
set
{
_left = value;
}
}
public Node Right
{
get
{
return _right;
}
set
{
_right = value;
}
}
public Node Up
{
get
{
return _up;
}
set
{
_up = value;
}
}
public Node Down
{
get
{
return _down;
}
set
{
_down = value;
}
}
public int Count
{
get
{
return _count;
}
}
public int Wall
{
get
{
return _wall;
}
set
{
_wall = value;
}
}
public bool isStart
{
get
{
return _isStart;
}
set
{
_isStart = value;
}
}
public Point Pos
{
get
{
return _pos;
}
set
{
_pos = value;
}
}
/// <summary>
/// For recursive backtracking and Growing Tree
/// </summary>
public bool isBacktracked
{
get
{
return _isBacktracked;
}
set
{
_isBacktracked = value;
}
}
/// <summary>
/// For Prim's algorithm
/// A list of parents
/// </summary>
public List<ParentInfo> parentInfo
{
get
{
return _parentInfo;
}
set
{
_parentInfo = value;
}
}
/// <summary>
/// For Prim's AQlgorithm
/// Mark a node as frontier
/// </summary>
public bool isFrontier
{
get
{
return _isFrontier;
}
set
{
_isFrontier = value;
}
}
}
}
每一面墙壁的状态储存在一个Int内
4个bits 组成的：
0为墙壁还在
1为墙壁已摧毁
迷宫生成的base class 是这样的：
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing.Drawing2D;
using System.Drawing.Imaging;
namespace MazeGen
{
public abstract class Maze
{
public delegate void ProgressChangedEventHandler(int done, int total);
public delegate void DoneEventHandler();
public event ProgressChangedEventHandler ProgressChanged;
public event DoneEventHandler Completed;
private int _selIndex = 0;
private List<List<Node>> _nodes = new List<List<Node>>();
public Maze(List<List<Node>> nodes)
{
_nodes = nodes;
}
/// <summary>
/// Initialize a new 2d array of nodes
/// </summary>
/// <param name="width"></param>
/// <param name="height"></param>
public Maze(int width, int height)
{
for (int x = 0; x < width; x++)
{
List<Node> nX = new List<Node>();
for (int y = 0; y < height; y++)
{
Node nY = new Node();
nY.Pos = new Point(x, y);
if (y > 0)
{
nY.Up = nX[y - 1];
nX[y - 1].Down = nY;
}
if (x > 0)
{
nY.Left = _nodes[x - 1][y];
_nodes[x - 1][y].Right = nY;
}
nX.Add(nY);
}
_nodes.Add(nX);
}
}
/// <summary>
/// Visualize nodes
/// </summary>
/// <param name="sz">The size of a node</param>
/// <returns></returns>
public Bitmap Visualize(Size sz)
{
Bitmap b = new Bitmap(_nodes.Count * sz.Width + 1, _nodes[0].Count * sz.Height + 1);
using (Graphics g = Graphics.FromImage(b))
{
for (int x = 0; x < _nodes.Count; x++)
{
for (int y = 0; y < _nodes[x].Count; y++)
{
if (!_nodes[x][y].GetWall(0))
{
//Up
g.DrawLine(Pens.Black, sz.Height * x, sz.Width * y, sz.Height * (x + 1), sz.Width * y);
}
if (!_nodes[x][y].GetWall(3))
{
//Left
g.DrawLine(Pens.Black, sz.Height * x, sz.Width * y, sz.Height * x, sz.Width * (y + 1));
}
if (!_nodes[x][y].GetWall(1))
{
//Right
g.DrawLine(Pens.Black, sz.Height * (x + 1), sz.Width * y, sz.Height * (x + 1), sz.Width * (y + 1));
}
if (!_nodes[x][y].GetWall(2))
{
//Down
g.DrawLine(Pens.Black, sz.Height * x, sz.Width * (y + 1), sz.Height * (x + 1), sz.Width * (y + 1));
}
if (_nodes[x][y].isBacktracked)
{
g.FillRectangle(new SolidBrush(Color.FromArgb(100, Color.Pink)), sz.Height * x, sz.Width * y, sz.Width, sz.Height);
}
if (_nodes[x][y].isFrontier)
{
g.FillRectangle(new SolidBrush(Color.FromArgb(100, Color.Purple)), sz.Height * x, sz.Width * y, sz.Width, sz.Height);
}
if (_nodes[x][y].isStart)
{
g.FillRectangle(new SolidBrush(Color.FromArgb(100, Color.Blue)), sz.Height * x, sz.Width * y, sz.Width, sz.Height);
}
}
}
};
return b;
}
protected virtual void OnProgressChanged(int done, int total)
{
if (ProgressChanged != null)
{
ProgressChanged(done, total);
}
}
protected virtual void OnComplete()
{
if (Completed != null)
{
Completed();
}
}
/// <summary>
/// Generate a new maze
/// </summary>
public virtual void Generate()
{
}
/// <summary>
/// Get the 2d list of nodes
/// </summary>
public List<List<Node>> Nodes
{
get
{
return _nodes;
}
}
public virtual string Name
{
get
{
return "";
}
}
/// <summary>
/// For Growing Tree Algorithm
/// </summary>
public int SelectionMethod
{
get
{
return _selIndex;
}
set
{
_selIndex = value;
}
}
}
}
Visualize 负责将整个迷宫画出来
这个是Recursive Backtracker 的实现核心（在Generate 函数内）
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing.Drawing2D;
using System.Drawing.Imaging;
namespace MazeGen
{
/// <summary>
/// Recursive Backtracking - Maze Generation
/// </summary>
public class MazeRec : Maze
{
public MazeRec(List<List<Node>> nodes)
: base(nodes)
{
}
/// <summary>
/// Initialize a new 2d array of nodes
/// </summary>
/// <param name="width"></param>
/// <param name="height"></param>
public MazeRec(int width, int height)
: base(width, height)
{
}
public override void Generate()
{
int visitedCount = 1;
int total = this.Nodes.Count * this.Nodes[0].Count;
Stack<Node> visitedCell = new Stack<Node>();
Random r = new Random();
//Node current = this.Nodes[r.Next(this.Nodes.Count-1)][r.Next(this.Nodes[0].Count-1)];
Node current = this.Nodes[(int)(r.NextDouble() * this.Nodes.Count * 10) % this.Nodes.Count][(int)(r.NextDouble() * this.Nodes[0].Count * 10) % this.Nodes.Count];
current.isStart = true;
//Node end = this.End.X == -1 ? this.Nodes[(int)(r.NextDouble() * this.Nodes.Count * 10) % this.Nodes.Count][(int)(r.NextDouble() * this.Nodes[0].Count * 10) % this.Nodes.Count] : this.Nodes[this.End.X][this.End.Y];
//end.isEnd = true;
while (visitedCount < total)
{
//List all available neighbour cells
List<Node> readyNeighbourCells = new List<Node>();
//Store the index of the neighbour cells
List<int> readyNeighbourCellsIndex = new List<int>();
for (int i = 0; i < current.Count; i++)
{
if (current[i] != null && current[i].Wall == 0)
{
readyNeighbourCells.Add(current[i]);
readyNeighbourCellsIndex.Add(i);
}
}
//no cells found
if (readyNeighbourCells.Count == 0)
{
current = visitedCell.Pop();
current.isBacktracked = true;
OnProgressChanged(visitedCount, total);
continue;
}
//Random select a cell
int randIndex = (int)(r.NextDouble() * 10) % readyNeighbourCells.Count;
int index = readyNeighbourCellsIndex[randIndex];
Node neighbour = readyNeighbourCells[randIndex];
// Knock the wall
// 0-2 1-3
current.UnWall(index);
neighbour.UnWall((index + 2) % 4);
visitedCell.Push(neighbour);
current = neighbour;
visitedCount++;
OnProgressChanged(visitedCount, total);
}
//Backtrack to start point
while (visitedCell.Count>0)
{
current = visitedCell.Pop();
current.isBacktracked = true;
OnProgressChanged(visitedCount, total);
}
OnComplete();
}
public override string Name
{
get
{
return "Recursive Backtracker";
}
}
}
}
【截图】
无图无真相
（会animate 整个迷宫生成的过程）
右击迷宫能保存
好啦就这样！< br/> 转载时必须在正文之中标注并保留原文链接、作者等信息。
