2

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.

newbie
  • 101
  • 1
  • 8
  • 1
    *"But the result is not correct."* Please edit the question to explain what specifically about the result is not correct. – kaya3 Nov 24 '19 at 03:49
  • @kaya3 Hi. After running the program, the maze seems like not correct as the included image. Is there any mistake in my Prim's algorithm? – newbie Nov 24 '19 at 05:27
  • What, specifically, about the included image is not correct? https://stackoverflow.com/help/how-to-ask – kaya3 Nov 24 '19 at 05:29
  • @kaya3 I have tried to edit my question and also attached a proper maze image. My question is my program does not generate a maze properly. Sorry for a bad description. – newbie Nov 24 '19 at 05:47
  • Please make your code [mre] – c0der Nov 25 '19 at 06:22

1 Answers1

1

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.

Emily
  • 1,030
  • 1
  • 12
  • 20
  • I did not know that. Thanks for letting me know this. Is there anything wrong with my algorithm – newbie Nov 24 '19 at 18:22
  • @newbie if this answer did solve your problem you can accept it - if you have follow up question feel free to ask another one! – Martin Frank Dec 10 '19 at 05:34