Prim ' s Algorithmus für die Generierung von einem Labyrinth: Immer die Nachbar-Zelle

Ich bin stützend einen Labyrinth-generator-Programm auf dem Prim-Algorithmus:

Dieser Algorithmus ist eine randomisierte version des Prim-Algorithmus.

  1. Beginnen Sie mit einem Netz voller Wände.
  2. Wählen Sie eine Zelle, markieren Sie Sie als Teil des Labyrinths. Fügen Sie die Wände der Zelle mit der Wandmalerei.
  3. Zwar gibt es Wände in der Liste:
    1. Wählen Sie eine zufällige Wand aus der Liste.
      Wenn die Zelle auf der gegenüberliegenden Seite nicht in das Labyrinth noch:

      1. Machen die Wand ein 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 mit der Wandmalerei.
    2. Wenn die Zelle auf der gegenüberliegenden Seite war schon in das Labyrinth, entfernen Sie die Wand aus der Liste.

(aus Wikipedia)

Verstehe ich den Algorithmus schon, ich bin nur fest auf diesen Teil:
"Zu wissen, ob der Nachbar Zelle bildet einen Teil des Labyrinths oder nicht" (das bedeutet, dass Immer der Nachbar Zelle zuerst)
Die Zellen sind eigentlich Knoten eines Baumes (das Labyrinth, ein bi-dimensionales array von Zellen) und die Wände sind die Kanten zwischen diesen Knoten, ich dachte, es wäre notwendig, zu erkennen, jede Wand mit einem paar von Punkten (x,y). Wie weiß ich, ob zwei Zellen miteinander verbunden sind durch eine Wand?
(denken Sie daran, dass jede Zelle hat 4 Wände)

Ich dachte über die Verwendung der equals () - Funktion. Ich Frage nur für einen pseudo-code oder Ihre beste Erklärung zu, würde die Dinge einfacher.

Meiner Wand Klasse hat drei Attribute: bool isWall(bestimmt, ob es eine Wand oder einen Durchgang zwischen den Zellen); int x; int y (Identifier).

Wenn Sie denken, dass ich brauchen würde, mehr Attribute ich das gerne wissen. Ich weiß, es gibt einen einfachen Weg, ich bin nur geklebt 😉
Vielen Dank für Ihre Zeit!

  • Übrigens, ich bin stützend einige der Umsetzung auf diesen code, gepostet von @danny.lesnik: stackoverflow.com/questions/11459752/...
  • Sie überlegen, eine Wand, definiert durch das jeweilige paar von Zellen trennt.
  • Also das hinzufügen zu @bcr das bedeutet, dass ein Wand-Objekt hätte "isWall' und 'cell1' und 'cell2' als Attribute. Die Zellen sollten entweder die x -, y-Position in Ihnen, oder Sie würde schauen durch das Labyrinth-array, um es zu finden. Nur mit x und y ist ein problem für eine Wand-als das nicht definieren. Jede Wand kann verstanden werden als die Verbindung von zwei x,y-Stellungen, ob Sie denken, der Ecken einer Zelle in einem raster Punkt oder die Zentren der Zelle.
  • Die Wand-Liste zu haben, eine Zelle + Wand-pair-Mädchen in ihm Sinn zu machen. Eine Wand allein hat kein "gegenüber" - Seite. Sie haben entweder eine Zelle, so dass Sie überprüfen können, die gegenüber einem ODER man könnte einfach beide Zellen. Man wird immer in das Labyrinth, weil das ist, wie die Mauern Holen Sie sich in die Liste der Wände. Der andere könnte oder nicht.
InformationsquelleAutor José Del Valle | 2013-08-14
  1. 1

    Lets 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]);
 }
    InformationsquelleAutor Lee Meador
  2. 1

    Kann ich keinen Kommentar hinzufügen, um die Diskussion so schlecht ist, Antworten Sie einfach mit einer Antwort. Im Grunde Lee Meandor hat die richtige Idee.

    Prim ' s Algorithmus für die Generierung von einem Labyrinth: Immer die Nachbar-Zelle

    Dies ist die grundlegende Struktur der Zelle zu Wand zu Zelle Bezug.

    So eine Zelle hat eine Nord-Süd-west-und Ost-Wand.

    Einer Wand zwischen zwei benachbarten Zellen 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;
}

    Die wichtige Sache im Auge zu behalten ist für die Zellen zu sein, zeigt auf die richtigen Wände.

    Dass einige wichtige Logik funktioniert :).

    Wenn Sie dabei Hilfe benötigen, werfen Sie einfach einen Kommentar.

    • Arbeiten Sie es jetzt, diese Antwort und Lee ' s Antworten waren hilfreich. Lasst uns hoffen, es wird funktionieren
    InformationsquelleAutor progrenhard
  3. 0

    Nun, ich verbrachte den ganzen Nachmittag Codierung der Labyrinth-generator, basierend auf Ihre Hilfe.
    Nun ich bin immer diese Art von Labyrinthen (sorry für den big screen-shot habe ich nicht ein Bild-editor hier.

    Prim ' s Algorithmus für die Generierung von einem Labyrinth: Immer die Nachbar-Zelle

    Ich denke, das problem ist, wie ich zurückkehren werde der Nachbar-Zelle. Vielleicht auch nicht.
    Dies ist, wie ich zurückkehren werde der Nachbar-Zelle, ich habe es der @progenhard Weg, die Wand hat 2 Zellen, cell1 und cell2, wenn cell1 besetzt ist, zurück cell2 und Umgekehrt:

    public Cell getNeighbourCell(Wall wall, Cell cell) {
    if (wall.getCell1().equals(cell)) {
        return wall.getCell2();

    } else {

        return  wall.getCell1();

    }
}

    Nochmals vielen Dank!

    InformationsquelleAutor José Del Valle
Schreibe einen Kommentar