Java - Erschaffe ein Labyrinth mit einer einzigartigen Lösung

Question

Also versuche ich gerade ein Java-Programm zu machen, das durch ein Labyrinth eine einzige Lösung findet. Um dies zu tun Ich verwende ein Verfahren zu schaffen, die ein Labyrinth schafft, die eine einzigartige Lösung hat:

private void Create (int x, int y, int val) { 
     int[] perm = randPerm(4); 
     m[x][y] ^= val; 
     for (int i=0; i<4; ++i) { 
      int p = perm[i]; 
      if (m[x+DX[p]][y+DY[p]] == 15) { 
       m[x][y] ^= TWO[p]; 
       Create(x+DX[p], y+DY[p], TWO[p^2]); 
      } 
     } 
    } 

Also, bevor ich mache das Verfahren beginnen, das Labyrinth zu lösen Ich versuche, herauszufinden, wie das obige Verfahren immer erstellt ein Labyrinth mit einem eindeutigen Pfad (wie zum Beispiel p^2 verwendet wird). Wie funktioniert die obige Methode?

private int[][] m; // maze representation 
    private int rows; // number of rows in the maze 
    private int cols; // number of columns in the maze 
    private final static byte[] TWO = { 1, 2, 4, 8, 16}; 
    private final static byte[] DX = { 0,+1, 0,-1}; 
    private final static byte[] DY = {-1, 0,+1, 0}; 
    private boolean done; // used in finding a single solution. 
    private long count; // used in finding the number of solutions. 
    private Random r;  // for generating random integers. 

public Maze (int nr, int nc, int seed) { 
     r = new Random(seed); 
     rows = nr; cols = nc; 
     m = new int[nr+2][nc+2]; 
     for (int r=1; r<=nr; ++r) 
     for (int c=1; c<=nc; ++c) 
      m[r][c] = 15; 
     for (int r=0; r<nr+2; ++r) 
      m[r][0] = m[r][nc+1] = 16; 
     for (int c=0; c<nc+2; ++c) 
     m[0][c] = m[nr+1][c] = 16; 
     Create(nr/2+1, nc/2+1, 0); 
    } 

private int[] randPerm(int n) { 
     int[] perm = new int[n]; 
     for (int k=0; k<n; ++k) perm[k] = k; 
     for (int k=n; k>0; --k) { 
     int rand = r.nextInt(k); 
     int t = perm[rand]; perm[rand] = perm[k-1]; perm[k-1] = t; 
     } 
     return(perm); 
    } 

Answer 1

Nun, es dauerte eine Weile, aber hier ist, was ich habe.

Zuerst wird der Konstruktor für Maze erzeugt ein Raster von Größe nc +2 x nr +2 füllt alle der Randzellen mit 16 und alle der inneren Zellen mit 15. Dann ruft es rekursiv Create() beginnend mit den Koordinaten für eine Zelle in der Mitte des Rasters.

Create() beginnt mit int[] perm = randPerm(4); Aufruf, die eine Reihe von Länge erzeugt 4 die Ints 0 - 3, und macht einen einfachen Zufall Shuffle auf es enthält. Der Inhalt von perm[] wird verwendet, um ein Wertepaar von DX[] und DY[] auszuwählen.

Diese Methode verwendet den ^ Operator, der eine XOR oder Exclusive Or Funktion den Wert der Zelle zu verändern, auf das das Verfahren aufgerufen wird, und die benachbarten Zellen in zufälliger Reihenfolge, wie durch den Inhalt von perm[] diktierte DX[] und DY[] wenn der Inhalt der Zelle 15 ist. Wenn Sie nur nach 15 suchen, werden zuvor geänderte Zellen nicht geändert, und die Wände um den Rand bleiben unverändert. Außerdem kann mit dieser Methode keine der mittleren Zellen in 16 geändert werden.

Jede Zelle, die den Wert enthält 15XOR'd ist mit einem Wert von TWO[], auch nach dem Zufallsprinzip ausgewählt, ohne 16 da p von den Inhalten perm abgeleitet wird, die sich zwischen 0 - 3 eingeschränkt sind. Auf diese Weise wird jede Zelle, die 15 enthält, in eine andere Nummer geändert - aber diese Zahlen können vor der Zeit bekannt sein, da die möglichen Werte der mittleren Zellen durch alle möglichen Ergebnisse von 15^TWO[p] eingeschränkt sind.

Da das Random Objekt r mit einem seed Variable initialisiert ist, glaube ich die gleichen seed mit erzeugt das gleiche Labyrinth jedes Mal, wenn die JVM initialisiert wird. Wenn Sie also den Wert von seed ändern, würden Sie ein anderes Labyrinth erzeugen, das sich von jedem anderen Wert von seed unterscheidet. Ich könnte mich aber in diesem Punkt irren, und es könnte jedes Mal anders sein, unabhängig vom Wert von seed. Ich kenne mich nicht mit dem Inneren von Random aus.

Wie Sie wissen könnten, ob das Labyrinth tatsächlich lösbar ist oder nicht, kann ich nicht sagen, ohne zu wissen, was jeder mögliche Wert im Labyrinth darstellt. Ich könnte mir vorstellen, dass einige Zahlen als unpassierbar gelten, während andere nicht sind?

Und da, was präsentiert wurde, ich glaube nicht, könnte man garantieren, dass jedes Labyrinth eine gültige Lösung hat, da diese Implementierung ist wirklich nur eine zufällige Reihe von Fliesen zu schaffen, und es gibt sicher einige sein Fälle, in denen nicht eine Lösung ist. Aber du hast nicht festgelegt, dass jedes Labyrinth lösbar sein muss; einfach einzigartig. Wenn Sie jedes Mal einen lösbaren Pfad garantieren wollten, müsste hier eine zusätzliche Logik eingefügt werden, um dies zu ermöglichen.