java - problem - maze algorithm



Prims Algorithmus zum Generieren eines Labyrinths: Holen der Nachbarzelle (2)

Ich basiere ein Labyrinth-Generator-Programm auf dem Prim-Algorithmus:

Dieser Algorithmus ist eine randomisierte Version des Prim-Algorithmus.

  1. Beginnen Sie mit einem Gitter voller Wände.
  2. Wähle eine Zelle aus und markiere sie als Teil des Labyrinths. Fügen Sie die Wände der Zelle der Wandliste hinzu.
  3. Während es in der Liste Wände gibt:
    1. Wählen Sie eine zufällige Wand aus der Liste. Wenn die Zelle auf der gegenüberliegenden Seite noch nicht im Labyrinth ist:
      1. Machen Sie die Wand zu einem Durchgang und markieren Sie die Zelle auf der gegenüberliegenden Seite als Teil des Labyrinths.
      2. Fügen Sie die benachbarten Wände der Zelle zur Wandliste hinzu.
    2. Wenn die Zelle auf der gegenüberliegenden Seite bereits im Labyrinth war, entferne die Wand von der Liste.

(aus Wikipedia )

Ich verstehe den Algorithmus schon, ich stecke nur auf diesem Teil fest: "Zu wissen, ob die Nachbarzelle Teil des Labyrinths ist oder nicht" (das bedeutet, die Nachbarzelle zuerst holen) Da die Zellen eigentlich Knoten eines Baumes sind (der Labyrinth, ein zweidimensionales Array von Zellen) und die Wände sind die Kanten zwischen diesen Knoten, ich dachte, es wäre notwendig, jede Wand mit einem Paar von Punkten (x, y) zu identifizieren. Woher weiß ich, ob zwei Zellen durch eine Wand verbunden sind? (Denken Sie daran, dass jede Zelle 4 Wände hat)

Ich dachte über die Verwendung der equals () -Funktion nach. Ich frage nur nach einem Pseudocode oder nach deiner besten Erklärung, die die Dinge leichter machen würde.

Meine Wall-Klasse hat drei Attribute: bool isWall (bestimmt, ob es sich um eine Wand oder einen Durchgang zwischen Zellen handelt); int x; int y (Bezeichner).

Wenn Sie denken, dass ich mehr Attribute benötigen würde, würde ich mich freuen zu wissen. Ich weiß, dass es einen leichten Weg gibt, ich stecke einfach fest;) Danke für deine Zeit!


Answer #1

Ich kann nicht kommentieren, um die Diskussion so schlecht hinzuzufügen, antworten Sie einfach mit einer Antwort. Grundsätzlich hat Lee Meandor die richtige Idee.

Dies ist die Grundstruktur der Beziehung zwischen Zelle und Zelle.

Eine Zelle hat also eine Nord-Süd-West- und Ost-Wand.

Eine Mauer ist zwischen zwei benachbarten Zellen, die sie verbinden.

Class Cell{

   Wall North;
   Wall South;
   Wall East;
   Wall West;

}


Class Wall{
    // You can store the cells that are connected to the wall but it's not necessary.
    Cell 1;
    Cell 2;

    bool isUP;
}

Es ist wichtig zu beachten, dass die Zellen auf die richtigen Wände zeigen.

Das ist eine wichtige logische Arbeit :).

Wenn Sie Hilfe brauchen, lassen Sie einfach einen Kommentar fallen.


Answer #2

Lass uns sehen, was wir definieren können:

 Cell[][] maze; // prepopulate with cells in a rectangular fashion. 
                // Populate adjacent cells with walls.
 {
     maze = new Cell[m][n];
     for (i = 0 .. m) {
         for (j = 0 .. n) {
             cell = maze[i][j] = new Cell(m, n);

             // fix top wall
             if (i == 0) { // first row
                 cell.wall[0] = new Wall();
                 cell.wall[0].setIsEdge();
             } else {
                 cell.wall[0] = maze[i-1][j].wall[2]; // my up is last row's down
             }

             // fix bottom wall
             cell.wall[2] = new Wall();
             if (i == m-1) { // last row
                 cell.wall[2].setIsEdge();
             }

             // fix left wall
             if (j == 0) { // leftmost column
                 cell.wall[3] = new Wall();
                 cell.wall[3].setIsEdge();
             } else {
                 cell.wall[3] = maze[i][j-1].wall[1]; // my left is last col's right
             }

             // fix right wall
             cell.wall[1] = new Wall();
             if (j == n-1) { // rightmost column
                 cell.wall[1].setIsEdge();
             }
         }
     }
 }

 List walls = new List();

 class Cell {
     Wall[] walls = new Wall[4]; // 0 is up, 1 is right, 2 is down, 3 is left (count clockwise)
     boolean isInMaze = false;
     int x;
     int y;
     Cell(col, row) {
         x = col;
         y = row;
     }
 }

 class Wall {
     boolean isOpen = false; // open walls are passages
     boolean isEdge = false; // edges have nothing on the other side.
     Cell[] cells = new Cell[2];
 }

 Cell aCell = maze[randomx][randomy]; // make sure x,y in bounds
 initializeCellInMaze(aCell, null);

 while (!walls.isEmpty()) {
    aWall = walls.get(randomWall); // in range
    if (!(aWall.cell[0].isInMaze && aWall.cell[1].isInMaze)) {
        // opposite cell NOT in maze
        wall.setIsOpen();
        Cell otherCell;
        if (wall.cell[0].isInMaze) {
            otherCell = wall.cell[1];
        } else {
            otherCell = wall.cell[0];
        }
        initializeCellInMaze(otherCell, aWall);
    }
    walls.remove(aWall); // or use index
 }

 initializeCellInMaze(cell, wallToSkip) {
     cell.setIsInMaze();
     for (i = 0 .. 3) if (cell.wall[i] != wallToSkip) walls.add(cell.wall[i]);
 }