迷宫专题总结

素颜马尾好姑娘i 2022-06-05 09:27 244阅读 0赞

（一） 实现一个迷宫的类，要求是可以产生指定大小的迷宫，有一条从起点到终点的路，有分叉与障碍

经过一天的奋战，建立起了一个基本达到上面要求的类Maze

enum MazeState {BLOCK, PASSABLE, START, END};
    class Maze
    {
    public:
        Maze(const int,const int);
        int resize(const int,const int);
        int make(void);
        void output(std::vector<MazeState> &tar)
        {
            tar=maze;
        }
        void output(const std::string&);
        int getHorizSize(void)
        {
            return 2*XM+1;
        }
        int getVerticalSize(void)
        {
            return 2*YM+1;
        }
    private:
        int XM, YM;
        std::vector<MazeState> maze;
    };

Maze类只有一个构造函数，接受XM和YM参数，产生一个(2\*XM+1)\*(2\*YM+1)大小的迷宫数组，存放在maze容器中。

maze容器存放迷宫数据，其中每个点的状态由MazeState枚举类表示，BLOCK为障碍，PASSABLE为可通行，START END为起点终点。

make函数负责生成随机迷宫，在构造函数和resize函数中被调用。

output有两个版本，一个接受字符串参数，将迷宫输出到指定的文件中；一个接受vector参数，将迷宫输出到指定的容器中。

getHorizSize和getVerticalSize返回迷宫的宽和高。

其中最主要的部分就是make函数。

思路是：利用XM\*YM个2\*2的方块来构建迷宫，再在左边和上边分别加上一列和一行作为边界，这样构建出来的迷宫的大小就为2\*XM+1和2\*YM+1。

过程：

1.  清空maze，填充(2\*XM+1)\*(2\*YM+1)个BLOCK；构建XM\*YM大小的全BLOCK状态的容器map，构建堆栈route，元素类型为pair<int,int> 。  
    
2.  利用map和route产生路线：
    
    1.  随机指定起始点now (0~XM\*YM-1)，产生随机方向turn (右上左下)，将map\[now\]和maze中对应方块的左上角元素设为PASSABLE。将<now, turn>压入route。
    2.  检查是否map中元素都为PASSABLE状态，是的话结束循环。  
        
    3.  从turn开始逆时针寻找对应方向相邻方块，要求是坐标合法(左右方向的与原坐标在同一行，上下方向的不超出范围)且为BLOCK状态。
    4.  若4个方向都不满足要求，则从route中弹出上一个点的坐标与方向。
    5.  若有一方向满足要求，将<now, turn>压入route，修改该方向方块与maze中对应左上角元素为PASSABLE，修改now为新坐标，turn为新随机方向。回到第2步。
    6.  产生位于左边界的起始点，令此点为START，其右点为PASSABLE；产生位于右边界的结束点，令此点为END，其左点为PASSABLE

经过测试，自我感觉基本实现了要求。

这种方法的优点是比较简单容易实现，可以保证从起点到终点肯定有一条路径可走，同时不会出现宽度超过1的路。但感觉实现的迷宫还不够复杂。