prim算法生成迷宫java

下面是使用 Prim 算法生成迷宫的 Java 代码：

import java.util.*;

public class MazeGenerator {
    private int height, width;
    private int[][] maze;
    private Random rand = new Random();

    public MazeGenerator(int h, int w) {
        height = h;
        width = w;
        maze = new int[height][width];
    }

    public void generateMaze() {
        // Initialize the maze with walls
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                maze[y][x] = 1;
            }
        }

        // Pick a random starting cell
        int startX = rand.nextInt(width);
        int startY = rand.nextInt(height);

        // Mark the starting cell as part of the maze
        maze[startY][startX] = 0;

        // Create a list of frontier cells
        ArrayList<int[]> frontier = new ArrayList<>();
        if (startX > 0) {
            frontier.add(new int[]{startX - 1, startY, startX, startY});
        }
        if (startX < width - 1) {
            frontier.add(new int[]{startX + 1, startY, startX, startY});
        }
        if (startY > 0) {
            frontier.add(new int[]{startX, startY - 1, startX, startY});
        }
        if (startY < height - 1) {
            frontier.add(new int[]{startX, startY + 1, startX, startY});
        }

        // While there are frontier cells
        while (!frontier.isEmpty()) {
            // Pick a random frontier cell
            int[] f = frontier.remove(rand.nextInt(frontier.size()));
            int fx = f[0];
            int fy = f[1];
            int px = f[2];
            int py = f[3];

            // If the cell is not part of the maze yet
            if (maze[fy][fx] == 1) {
                // Mark it as part of the maze
                maze[fy][fx] = 0;

                // Create walls between the new cell and its parent
                if (fx > px) {
                    maze[fy][px + 1] = 1;
                } else if (fx < px) {
                    maze[fy][px - 1] = 1;
                } else if (fy > py) {
                    maze[py + 1][fx] = 1;
                } else if (fy < py) {
                    maze[py - 1][fx] = 1;
                }

                // Add the new frontier cells
                if (fx > 0 && maze[fy][fx - 1] == 1) {
                    frontier.add(new int[]{fx - 1, fy, fx, fy});
                }
                if (fx < width - 1 && maze[fy][fx + 1] == 1) {
                    frontier.add(new int[]{fx + 1, fy, fx, fy});
                }
                if (fy > 0 && maze[fy - 1][fx] == 1) {
                    frontier.add(new int[]{fx, fy - 1, fx, fy});
                }
                if (fy < height - 1 && maze[fy + 1][fx] == 1) {
                    frontier.add(new int[]{fx, fy + 1, fx, fy});
                }
            }
        }
    }

    public void printMaze() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (maze[y][x] == 1) {
                    System.out.print("# ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        MazeGenerator maze = new MazeGenerator(10, 10);
        maze.generateMaze();
        maze.printMaze();
    }
}

这个代码使用了一个二维数组来表示迷宫，其中 1 表示墙，0 表示通路。首先，将整个迷宫都初始化为墙。然后，随机选择一个起始点，并将其标记为通路。接着，将起始点周围的四个格子作为“边界格子”加入一个列表中。在每一轮循环中，从边界格子列表中随机选择一个格子。如果这个格子还没有被标记为通路，就将它标记为通路，并在它和它的父格子之间创建一堵墙。然后，把这个格子周围还未标记为通路的格子加入边界格子列表。重复这个过程，直到边界格子列表为空。最后，打印出生成的迷宫。