Java基于深度优先遍历的随机迷宫生成算法

Java基于深度优先遍历的随机迷宫生成算法攻略

算法思路

这里介绍的是基于深度优先遍历(DFS)的随机迷宫生成算法。该算法的基本思路是，从起点开始，每次选择一个相邻且未被访问过的节点作为下一个遍历的节点，直到到达终点，期间可以任意回溯。在此基础上加入了随机化操作，即在选择相邻节点时随机打乱遍历顺序，以此生成"随机"的迷宫。

实现步骤

1. 首先，我们需要定义一个Maze类表示迷宫，并初始化地图。可以采用二维数组来表示地图，用数字0表示可通行的路径，1表示障碍(不可通行的墙壁)。

public class Maze {
    private int[][] map;  //地图
    private int height;  //迷宫高度
    private int width;  //迷宫宽度

    //构造函数，初始化地图
    public Maze(int height, int width) {
        this.height = height;
        this.width = width;
        this.map = new int[height][width];
        //初始化地图，全部设置为墙壁
        for(int i=0; i<height; i++) {
            for(int j=0; j<width; j++) {
                map[i][j] = 1;
            }
        }
        //生成起点
        int startX = 1 + (int)(Math.random()*(height-2));
        int startY = 1 + (int)(Math.random()*(width-2));
        map[startX][startY] = 0;
    }
}

1. 接着，定义一个枚举类型(或者整数常量)表示方向，用于表示向上、向下、向左、向右四个方向。方便后面使用时的标识和操作。

public enum Direction {
    UP, DOWN, LEFT, RIGHT;
}

1. 然后，定义一个方法用于遍历地图。遍历的过程需要借助深度优先遍历算法，在每个节点处延伸四个方向，如果在当前可探索的路径上，随机选择一个未走过的方向前进；如果当前已经无法前进，就返回上一层继续遍历，直到找到终点。

public void generateMaze() {
    //从起点开始遍历
    dfs(1, 1);
}

private void dfs(int x, int y) {
    //标记当前节点已经访问过
    map[x][y] = 0;
    //获取当前节点的所有邻居
    List<Direction> neighbors = getNeighbors(x, y);
    //随机打乱邻居集合的顺序
    Collections.shuffle(neighbors);
    //遍历所有邻居节点
    for(Direction direction : neighbors) {
        switch (direction) {
            case UP:
                //判断邻居是否可走
                if(x-2 > 0 && map[x-2][y] == 1) {
                    //将中间节点也标记为可走的路径
                    map[x-1][y] = 0;
                    dfs(x-2, y);
                }
                break;
            case DOWN:
                if(x+2 < height-1 && map[x+2][y] == 1) {
                    map[x+1][y] = 0;
                    dfs(x+2, y);
                }
                break;
            case LEFT:
                if(y-2 > 0 && map[x][y-2] == 1) {
                    map[x][y-1] = 0;
                    dfs(x, y-2);
                }
                break;
            case RIGHT:
                if(y+2 < width-1 && map[x][y+2] == 1) {
                    map[x][y+1] = 0;
                    dfs(x, y+2);
                }
                break;
        }
    }
}

//获取某个节点的所有邻居，即上下左右四个方向分别相距一个节点的位置
private List<Direction> getNeighbors(int x, int y) {
    List<Direction> neighbors = new ArrayList<>();
    if(x-2 > 0) {
        neighbors.add(Direction.UP);
    }
    if(x+2 < height-1) {
        neighbors.add(Direction.DOWN);
    }
    if(y-2 > 0) {
        neighbors.add(Direction.LEFT);
    }
    if(y+2 < width-1) {
        neighbors.add(Direction.RIGHT);
    }
    return neighbors;
}

1. 最后，运行generateMaze方法即可生成迷宫。

示例说明

以下是两个生成迷宫的示例说明。

示例一

//生成20x20的迷宫
Maze maze = new Maze(20, 20);
//生成迷宫
maze.generateMaze();
//输出迷宫地图
for(int i=0; i<maze.getHeight(); i++) {
    for(int j=0; j<maze.getWidth(); j++) {
        if(maze.getMap(i, j) == 0) {
            System.out.print(" ");
        } else {
            System.out.print("#");
        }
    }
    System.out.println();
}

运行结果：

# # # # # # # # # # # # # # # # # # # 
#                   #         #     # 
#   # # # # # # #   #   # # # #   # 
#   #           #   #   #         # 
#   #   #   #   #   #   #   # # # # 
#   #   #   #   #       #   #     # 
#   #       #   #   #   #   #   # # 
#   #   #       #   #   #       # # 
#   #   # # #   #   #   #   #   #   
#   #       #       #   #   #   #   
#   #   #   #   # # # # # #   # #   
#   #   #       # # # # # # #     # 
#   #   #   #   #             #   # 
#       #   #   #   #   #     #   # 
#   # # # # # #   #   #   #   #   # 
#   #             #   #       #   # 
#   # # # # # # # #   #   #   #   # 
#               #     #       #   # 
# # # # # # #   # #   #   #   #   # 
#               #         # # # # # 

示例二

//生成30x15的迷宫
Maze maze = new Maze(30, 15);
//生成迷宫
maze.generateMaze();
//输出迷宫地图
for(int i=0; i<maze.getHeight(); i++) {
    for(int j=0; j<maze.getWidth(); j++) {
        if(maze.getMap(i, j) == 0) {
            System.out.print(" ");
        } else {
            System.out.print("#");
        }
    }
    System.out.println();
}

运行结果：

# # # # # # # # # # # # # # 
#     #           #     # 
# # # #   # # #   #   # # 
#     #   #   #       # 
# #   #   #   #   #   # 
#     #   #       #      
# # # # # #   # # # # # 
#         #   #     #   # 
#   # # # # # # # # # # 
#               #     # 
# # # # #   #   #   # # 
#         #   #          
# # # # # # #   # # # # 
#     #           #     # 
# #   #   # # #   # # #  
#     #               # 
# # # # # #   # # # # # 
#     #   #           # 
# # # #   #   # # #   # 
#         #       #   # 
# # # # # # #   # # # # 
#         #     #     # 
# # # # #   # # # # # # 
#     #           #      
# #   #   # # #   #   # 
#       #       #   #   
# # # # # # # # # # # #