CODEWITHSUNDEEP
javaalgorithmswinggraph-theorymaze
newbie
newbie

Reputation: 111

My Prim's algorithm does not generate maze properly

I am trying to implement a randomly generated maze using Prim's algorithm. But the program does not generate a maze properly. Please take a look and give me some advice

Here is my picture of a maze:

enter image description here

The maze should be look like this: enter image description here Prim's algorithm:

private void Prims(){
            List<Vertex> res = new ArrayList<>();
            PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>(CostComparator.compare_W());
            for (int i = 0; i < grids.length; i++){
                for(int j = 0; j < grids[i].length; j++){
                    priorityQueue.offer(grids[i][j]);
                }
            }
            grids[0][0].setG(0);
            while(!priorityQueue.isEmpty()){
                Vertex current = priorityQueue.poll();
                if(current.getPrevious() != null){
                    res.add(current);
                }
                for(Edge edge: current.getEdges()){
                    Vertex destination = edge.getDestination();
                    if(priorityQueue.contains(destination) && destination.getG() > edge.getWeight()){
                        destination.setPrevious(current);
                        destination.setG(edge.getWeight());
                    }
                }
            }
            for(int i = 0; i < res.size(); i++){
                if(i % 2 == 0){
                    res.get(i).setStyle(3);
                }
            }
            update(5);
        }

Vertex class:

public class Vertex {
    private int x, y, style;
    private int f, h, g;
    private Vertex previous;
    private List<Edge> edges;
    private boolean isVisited;
}

Edge class:

public class Edge {
    private int weight;
    private Vertex destination;
    private Vertex start;
}

I also read this article Implementing a randomly generated maze using Prim's Algorithm, but I haven't still be able to solve my problem. I saw @Hoopje in that post said that if both coordinate are even, then this cell must be a passage. otherwise, it is the wall. However, when I drew it out, it is not correct because it seems like a Chess board. Thank you.

Upvotes: 2

Views: 272

Answers (1)

Emily
Emily

Reputation: 1096

Java's PriorityQueue<T> does not update its internal state automatically when you change the weight of your vertices during relaxation. The solution to this is to remove and re-insert the vertex whenever you change its weight.

This may not be the only issue, but it is the one most apparent to me from just looking at your code.

Upvotes: 1

Related Questions