[教程][C#][算法] 迷宫生成算法入门——Recursive Backtracker + 实现

10 Nov 2013

Comments

C# • Maze • 原创 • 教程 • 算法 • 迷宫

之前在这篇（[教程][C#][算法] A*寻路算法入门——详解+实现）说到了“迷宫”
于是心血来潮，做了点研究，找到了几个不错的迷宫生成算法。

这篇文章不需要任何特定基础
你甚至可以用纸和笔直接手动生成迷宫！
（但是你要知道什么叫做堆栈）

【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 上：

https://github.com/garyng/Maze

每一个格子为一个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 整个迷宫生成的过程）

右击迷宫能保存

好啦就这样！

Published by Gary Ng

GARY'S ZONE

[教程][C#][算法] 迷宫生成算法入门——Recursive Backtracker + 实现

【Recursive Backtracker】

【例子】

【C#实现】

【截图】

Related Posts

[教程] Proxifier突破区域限制 18 Apr 2016

[原创][C#] gITEBooksGrabber —— it-ebooks.info电子书下载神器 28 Mar 2016

[原创][教程] Windows 下搭建Jekyll离线部落格环境 18 Mar 2016