java - 为什么我用Java实现的随机Prim's Algorithm只会生成完整的网格？

我试图在Wikipedia https://en.wikipedia.org/wiki/Maze_generation_algorithmRandomized_Prim's_algorithm上遵循此伪代码
但是我的代码只会生成一个完整的网格。我对算法的功能了解不足。有人可以帮我解释我做错了吗？

我看过一些资料，但我无法解决

public class MazeGen {
private int dimension, nodeCounter;
private Node[][] nodes;
private List<Edge> walls;

public static void main(String[] args) {
    MazeGen g = new MazeGen(20);
    g.generate();
    g.printMaze();
}

private void generate() {
    pickCell();
    generateMaze();
}

private void generateMaze() {
    while (!walls.isEmpty()) {
        int v;
        Edge wall = walls.get(ThreadLocalRandom.current().nextInt(walls.size()));
        if ((!wall.nodes[0].visited && wall.nodes[1].visited)
                || (wall.nodes[0].visited && !wall.nodes[1].visited)) {
            if (!wall.nodes[0].visited)
                v = 0;
            else
                v = 1;

            includeNode(wall.nodes[v]);
            wall.nodes[Math.abs(v - 1)].visited = true;
        }
        walls.remove(wall);
    }
}

private void pickCell() {
    int i = ThreadLocalRandom.current().nextInt(dimension);
    int j = ThreadLocalRandom.current().nextInt(dimension);

    includeNode(nodes[i][j]);
}

private void includeNode(Node node) {
    node.visited = true;
    node.partOfMaze = true;
    walls.addAll(node.edges);
}

public void printMaze() {
    for (int i = 0; i < dimension; i++) {
        System.out.println();
        for (int j = 0; j < dimension; j++) {
            if (nodes[i][j].partOfMaze) {
                System.out.print(".");
            } else
                System.out.print("p");
        }
    }
}

public MazeGen(int n) {
    nodes = new Node[n][n];
    walls = new ArrayList<Edge>();
    dimension = n;

    createNodes();
    connectAdjacents();
}

private void connectAdjacents() {
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            verifyConnection(i, j, i, j + 1);
            verifyConnection(i, j, i + 1, j);
        }
    }
}

private void verifyConnection(int i, int j, int arg1, int arg2) {
    if (arg1 < dimension && arg2 < dimension)
        connect(i, j, arg1, arg2);
}

private void createNodes() {
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            nodes[i][j] = new Node();
        }
    }
}

private void connect(int row, int col, int row2, int col2) {
    nodes[row][col].edges.add(new Edge(nodes[row][col], nodes[row2][col2]));
    nodes[row2][col2].edges.add(new Edge(nodes[row][col], nodes[row2][col2]));
}

private class Node {
    boolean visited, partOfMaze;
    int number;
    List<Edge> edges;

    Node() {
        number = nodeCounter++;
        edges = new ArrayList<Edge>();
    }

    @Override
    public String toString() {
        return String.valueOf(number);
    }
}

private class Edge {
    Node[] nodes;

    Edge(Node n, Node n2) {
        nodes = new Node[2];
        nodes[0] = n;
        nodes[1] = n2;
    }

    @Override
    public String toString() {
        return nodes[0] + "-" + nodes[1];
    }
}

最佳答案

我认为您的算法正确，但是您没有保持正确的输出。
所有节点都应该是迷宫的一部分。应该是迷宫一部分的墙是当您处理它们时连接两个访问的节点的墙。

制作输出墙的另一个数组，然后在generateMaze方法中设置值。

private void generateMaze() {
    while (!walls.isEmpty()) {
        int v;
        Edge wall = walls.get(ThreadLocalRandom.current().nextInt(walls.size()));
        if ((!wall.nodes[0].visited && wall.nodes[1].visited)
                || (wall.nodes[0].visited && !wall.nodes[1].visited)) {
            if (!wall.nodes[0].visited)
                v = 0;
            else
                v = 1;

            includeNode(wall.nodes[v]);
            wall.nodes[Math.abs(v - 1)].visited = true;
            /////////////////////////////////////
            // remove this wall from the output walls
            /////////////////////////////////////
        } else {
            ////////////////////////////////
            // add this wall to the output walls
            ////////////////////////////////
        }
        walls.remove(wall);
    }
}