基于递归分割的迷宫生成算法与自动寻路

小咪咪 2022-09-24 12:26 136阅读 0赞

代码下载：[基于递归分割的迷宫生成算法与自动寻路][Link 1]  
今天给大家介绍一个图形学里的东西—迷宫的生成算法。迷宫的生成算法有很多种，比如基于深度优先和广度优先的生成算法，在此介绍另外一种方法，基于递归分割的迷宫生成算法。网上大部分迷宫生成算法生成的迷宫墙壁都是线条，本文生成的迷宫墙壁是正方形，先给大家看个示例：  
![图一 迷宫展示][20160731135940049]  
下面就开始正式介绍基于递归分割的迷宫生成算法。

# 1. 生成迷宫 #

在生成迷宫之前，我们需要先确定迷宫的大小，迷宫的高和宽其实没啥大的要求，只有一点必须是奇数。必须是奇数的原因很简单，通过上图也可以看出，为了保证一行墙壁一行通路，大小只能是奇数。最外层墙壁不属于迷宫，是在给定高和宽基础上添加的两行两列。

## 1.1 初始化 ##

第一步根据给定的高和宽生成一个初始迷宫，初始迷宫只是在没有任何阻碍的迷宫外侧添加一圈墙壁，如下图所示：  
![图二 初始迷宫][20160731140035315]

## 1.2 画墙壁 ##

在初始迷宫的基础上，随机选择一行和一列，将其置成墙壁，将迷宫分成独立的四部分。这里需要注意一点，为了满足一行墙壁一行通路的条件，我们需要在偶数行置墙壁（忽略外部墙壁，下标从1开始）。此时生成的迷宫如下图：  
![图三 画完墙壁的迷宫][20160731140129118]

## 1.3 墙壁开洞 ##

为了保持迷宫的连通性，我们需要在上一步生成的四堵墙壁上开几个洞。可以看出，开一个洞和两个洞都不能保证迷宫的连通性，而开四个洞又使迷宫通路过多，所以我们随机选择三堵墙开洞。和生成墙壁相反，开洞的位置在奇数行。开洞之后生成的迷宫如下图所示：  
![图四 打完洞的迷宫][20160731140213166]  
此时四个独立的迷宫保持联通，而且相互之间只有一条路可以到达。

## 1.4 递归分割 ##

在完成上面三步之后，我们就生成了四个小迷宫，然后对小迷宫执行上面的两步直到迷宫高度或宽度为1为止。最终就会生成图一所示的迷宫。迷宫的生成代码如下：

/**
         * 在给定的线上打开一扇位置随机的门
         */
        private void openAdoor(int x1, int y1, int x2, int y2) {
            int pos;
            if (x1 == x2) {
                pos = y1 + r.nextInt((y2 - y1 )/2+ 1)*2;//在奇数位置开门
                blocked[x1][pos] = false;
            } else if (y1 == y2) {
                pos = x1 + r.nextInt((x2 - x1 )/2+ 1)*2;
                blocked[pos][y1] = false;
            } else {
                System.out.println("wrong");
            }
        }
    /**
         * 迷宫生成算法，采用递归方式实现，随机画横竖两条线，然后在线上随机开三扇门
         * @param x：迷宫起点的x坐标
         * @param y：迷宫起点的y坐标
         * @param height：迷宫的高度
         * @param width：迷宫的宽度
         * ***********
         * *         *
         * *         *
         * ***********
         * 针对上述迷宫，四个参数为：1,1,2,9
         */
        private void genMaze(int x, int y, int height, int width) {
            int xPos, yPos;
    
            if (height <= 2 || width <= 2)
                return;
    
            //横着画线，在偶数位置画线
            xPos=x+r.nextInt(height/2)*2+1;
            for (int i = y; i < y + width; i++) {
                blocked[xPos][i] = true;
            }
    
            //竖着画一条线，在偶数位置画线
            yPos=y+r.nextInt(width/2)*2+1;
            for (int i = x; i < x + height; i++) {
                blocked[i][yPos] = true;
            }
    
            //随机开三扇门，左侧墙壁为1，逆时针旋转
            int isClosed = r.nextInt(4) + 1;
            switch (isClosed) 
            {
            case 1:
                openAdoor(xPos + 1, yPos, x + height - 1, yPos);// 2
                openAdoor(xPos, yPos + 1, xPos, y + width - 1);// 3
                openAdoor(x, yPos, xPos - 1, yPos);// 4
                break;
            case 2:
                openAdoor(xPos, yPos + 1, xPos, y + width - 1);// 3
                openAdoor(x, yPos, xPos - 1, yPos);// 4
                openAdoor(xPos, y, xPos, yPos - 1);// 1
                break;
            case 3:
                openAdoor(x, yPos, xPos - 1, yPos);// 4
                openAdoor(xPos, y, xPos, yPos - 1);// 1
                openAdoor(xPos + 1, yPos, x + height - 1, yPos);// 2
                break;
            case 4:
                openAdoor(xPos, y, xPos, yPos - 1);// 1
                openAdoor(xPos + 1, yPos, x + height - 1, yPos);// 2
                openAdoor(xPos, yPos + 1, xPos, y + width - 1);// 3
                break;
            default:
                break;
            }
    
            // 左上角
            genMaze(x, y, xPos - x, yPos - y);
            // 右上角
            genMaze(x, yPos + 1, xPos - x, width - yPos + y - 1);
            // 左下角
            genMaze(xPos + 1, y, height - xPos + x - 1, yPos - y);
            // 右下角
            genMaze(xPos + 1, yPos + 1, height - xPos + x - 1, width - yPos + y - 1);
    
        }

# 2. 自动寻路 #

在完成迷宫的生成之后，下一步就是指定起始点，然后在迷宫中寻找路径。路径的搜寻方法很多，可以递归寻找，从起始点开始递归深搜所有可行的位置直到找到结束点。递归的方法可以改成采用堆栈的实现，将每个点四个方向中可行的方向保留在堆栈中，然后每次从堆栈中弹出一个位置进行下一轮的判断，直到找到结束点。但是上面两种方法不能保证找到的路径时最短的。我们可以将堆栈替换成队列，以此获得最短路径。由于路径寻找算法比较简单，在此只给出伪代码，伪代码如下：

getShortestPath(start,end){
        queue.add(start); visited[start]=true;
        while(!queue.isEmpty()){
            p=queue.poll();
            search p’s four neighbours {
                if(n[i] is not visited and not blocked){
                    if(n[i]==end) break;
                    q.add(n[i]); visited[n[i]]=true; 
                }
            }
        }
        //回溯寻找路径
    }

![图五 迷宫中的路径寻找][20160731140511622]

# 3. 迷宫的绘制 #

迷宫的生成和路径寻找都已经有了，下一步是将上述迷宫和路径画出来。我们采用Java的绘图系统进行绘制。首先，整个迷宫都绘制在一个JPanel构件上，绘制的基本原理就是重构(overriding)面板的paint函数。paint函数会根据迷宫的每一个位置是否有墙壁绘制不同颜色的正方形，然后在正方形外侧画四条白线。这里需要注意一点，迷宫坐标系是行主优先，java绘图系统是列主优先，所以在绘制过程中需要进行坐标转换。在路径寻找过程中，首先让用户设置起始点。起始点的设置通过鼠标点击来确定在迷宫的哪个位置。这里通过一个独立的内部类来实现。路径的绘制和迷宫的绘制类似，只是需要根据路径的坐标绘制指定位置。  
在使用过程中，用户首先点击“生成迷宫”绘制一个全新的迷宫（初始情况下会包含一个默认的迷宫），然后点击“设置起始点”在迷宫中选择起始和结束点，之后点击“自动寻路”即可寻找路径并绘制，点击“重置”会将当前的起始点与路径消除。每次寻路的流程是，点击“设置起始点”，然后点击“自动寻路”，最后“重置”。  
![图五 按键设置][20160731140550880]  
迷宫的生成与自动寻路涉及递归和堆栈队列等数据结构，是非常不错的数据结构算法实例，希望大家能有所收获。

[Link 1]: http://download.csdn.net/detail/yutianzuijin/9591410
[20160731135940049]: /images/20220719/3d799f4477f348d3adb3c4eba88825b0.png
[20160731140035315]: /images/20220719/03b298669de5494ba29ba672d34cee07.png
[20160731140129118]: /images/20220719/ce408371e95f4579bca2efab3b84b16f.png
[20160731140213166]: /images/20220719/e8a9e2ccd086475093c51fb74dc4fbee.png
[20160731140511622]: /images/20220719/5a08dbf3aeda486b87e9a1299e42eb6f.png
[20160731140550880]: /images/20220719/f19e8381c73441629025a6cf2d031deb.png