Utilizzo di una pila per attraversare e risolvere un labirinto - Java

Question

Quindi sto provando a creare un programma di labirinto che risolva un labirinto di X e O's. Quello che mi piacerebbe fare è creare una classe di punti, in modo da poter creare una serie di punti bidimensionale che consenta di stampare su una pagina di output e di implementare lo stack in modo relativamente semplice.

L'algoritmo più semplice di l'idea generale mi piacerebbe implementare nel programma vero e proprio credo dovrebbe essere:

1) Move forward 
2) Are you at a wall? 
2a) If yes, turn left 
3) Are you at the finish? 
3a) If no, go to 1 
3b) If yes, solved 

ma sto avendo problemi a venire con un algoritmo più approfondita, così come ottenere la mia classe di punti situata. So per i punti che avrei dovuto impostare la coordinata X e impostare anche la coordinata Y così come i getter per i due. Pensi che abbia bisogno di più metodi di quei due? Ad esempio, dovrei creare un metodo che superi un x coord e y coord come parametri in modo da poterli spingere tutti insieme come uno, invece di impostare xey singolarmente?

Questo è ciò che un labirinto campione sarebbe simile, dove si inizia in basso a destra e cercare di attraversare in alto a sinistra, con una X le pareti, e come spazi aperti di O nel labirinto:

O O O O O X O 
X X O X O O X 
O X O O X X X 
X X X O O X O 
X X X X O O X 
O O O O O O O 
X X O X X X O 

Answer 1

È possibile utilizzare un

Stack<Point> points = new Stack<>(); 

// add a point 
Point p = new Point(x, y); 
if (points.contains(p)) 
    // been here before, in circles. 
else 
    points.add(p); 

Answer 2

Sei sicuro l'algoritmo avrebbe risolto ogni labirinto? Penso che sarebbe rimanere bloccati in questa semplice mock-up (dove S è cominciare e F è finitura):

xxxxxxxxxx 
Sooooooxxx 
xxxxxxoxxx 
xxxxxxFxxx 

vostro algoritmo dovrebbe procedere verso il basso la prima sala fino a quando non ha affrontato la caduta, girare a sinistra, si trova ad affrontare il muro "nord", gira di nuovo a sinistra e torna indietro nel primo corridoio, dove gira di nuovo a sinistra due volte e continua a ripetere questo problema.

L'algoritmo della regola della mano destra (vedere lo wikipedia page e altre sezioni per ulteriori labirinti) dovrebbe risolvere qualsiasi labirinto senza loop e dovrebbe essere abbastanza semplice da implementare in java.

Answer 3

Per l'algoritmo si potrebbe usare backtracking (EDIT anche se non corrispondono del tutto la vostra idea generale.) Non vi resta che realizzare i vostri movimenti sono "spinte" in uno stack virtuale, e devono essere unpushed (e quindi annullato). Potrebbe essere necessario implementare lo stack da soli se il "robot" è un oggetto effettivamente in movimento, ma puoi contare sullo stack di chiamate se vuoi solo risolvere il labirinto.

Answer 4

Per la parte dell'algoritmo, è preferibile una prima ricorsione di profondità attraverso lo stack. Qualcosa sulla falsariga di:

currentSpot = (0,0) // The starting point // 

while(! currentSpot.isExit()) { 

    if (! currentSpot.left().isWall()) stack.push(currentSpot.left()); 
    if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward()); 
    if (! currentSpot.right().isWall()) stack.push(currentSpot.right()); 

    currentSpot = stack.pop(); // Get the next location // 
} 

si vorrà la classe punto per tornare il prossimo punto in ciascuna direzione data (ad eccezione indietro), così come rilevare quando saresti ai bordi del labirinto. Probabilmente vorrai una classe Maze che contenga tutti i punti, stampi, memorizzi l'X/O, ecc. Quindi, potresti probabilmente sostituire il currentSpot corrente = (0,0) con currentSpot = Maze.getStartingSpot() ;

Answer 5

Per l'algoritmo, non è necessario uno stack. Solo se si utilizza il backtracking per annullare la decisione trasversale, è necessario disporre di uno stack.

Answer 6

Usa algoritmo parete seguace: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

Answer 7

Abbiamo affrontato questo problema una volta quando ero a scuola e abbiamo usato una soluzione simile a destra/sinistra regola della mano. Credo che l'abbiamo fatto mentre imparavamo sulle liste collegate. In poche parole, l'algoritmo era simile al seguente:

1. Vai a sinistra. Se possibile, ripetere.
2. In caso contrario, andare dritto. Se possibile, tornare al passaggio 1.
3. In caso contrario, andare a destra. Se possibile, tornare al passaggio 1.

Ad ogni passaggio, si controlla anche se il punto su cui si è in piedi è il traguardo. Se non si è in grado di continuare (ovvero, non è possibile andare a sinistra, a destra o a destra), quindi contrassegnare il punto su cui si è posizionati come "visitato" e il backup. Risciacqua e ripeti.