为什么我用Java实现的随机Prim's Algorithm只会生成完整的网格? [英] Why does my implementation of randomized Prim's Algorithm in Java just generate a full grid?

问题描述

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

I attempted to follow this pseudocode on wikipedia https://en.wikipedia.org/wiki/Maze_generation_algorithmRandomized_Prim's_algorithm but my code just generates a full grid. I seem to be missing something in my understanding of what the algorithm does. Can someone help explain what I'm doing wrong?

我看过一些资料，但我无法将其包裹住

I've looked at a few sources but I can't wrap my head around it

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];
    }
}

推荐答案

忘记维基百科，他们会对言论自由进行审查，并操纵信息，特别是在政治和社会领域.因此，我还删除了我在迷宫生成"上的Wikipedia页面上添加的所有内容(请参阅页面历史记录).

Forget Wikipedia, they censor free speech and manipulate information, especially in political and social areas. For that reason I also deleted all my additions to the Wikipedia page on "maze generation" (see page history).

"Prim's" MST算法的思想是在断开连接的子图之间保持切割"(一组边)，并始终选择最便宜的边来连接这些子图.标记访问过的顶点以避免生成循环.

The idea of "Prim's" MST algorithm is to maintain a "cut" (a set of edges) between disconnected subgraphs and always select the cheapest edge to connect these subgraphs. Visited vertices are marked to avoid generating cycles.

通过在完整的网格图中使用边缘随机权重，或者从空的网格图开始并动态添加随机加权的边缘，可以将其用于迷宫生成.

This can be used for maze generation by using edge random weights in a full grid graph or by starting with an empty grid graph and adding randomly weighted edges on the fly.

有关迷宫生成的信息，请参见我的GitHub存储库:

See my GitHub repository on maze generation for details:

https://github.com/armin-reichert/mazes

https://github.com/armin-reichert/mazes/blob/master/mazes-algorithms/src/main/java/de/amr/maze/alg/mst/PrimMST.java

public void createMaze(int x, int y) {
        cut = new PriorityQueue<>();
        expand(grid.cell(x, y));
        while (!cut.isEmpty()) {
            WeightedEdge<Integer> minEdge = cut.poll();
            int u = minEdge.either(), v = minEdge.other();
            if (isCellUnvisited(u) || isCellUnvisited(v)) {
                grid.addEdge(u, v);
                expand(isCellUnvisited(u) ? u : v);
            }
        }
    }

    private void expand(int cell) {
        grid.set(cell, COMPLETED);
        grid.neighbors(cell).filter(this::isCellUnvisited).forEach(neighbor -> {
            cut.add(new WeightedEdge<>(cell, neighbor, rnd.nextInt()));
        });
    }

这篇关于为什么我用Java实现的随机Prim's Algorithm只会生成完整的网格?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！