Comment trouver tous les chemins de labyrinthe disponibles?

Question

J'essaye d'écrire un programme qui est donné un labyrinthe et essaie de trouver la sortie. M est l'entrée, E est la sortie, 1s sont des murs et 0s sont des chemins. Il est supposé trouver chaque chemin et mettre P dans le chemin. Il est supposé trouver tous les chemins disponibles. En ce moment, il trouve une partie d'un chemin.

Voici le code:

public class Maze 
{ 
    private int size; 
    private String[][] board; 
    private int total; //# of boards 
    private int eX; 
    private int eY; 
    private int mX; 
    private int mY; 

    public Maze(int size, String[][] board) 
    { 
     this.size = size; 
     this.board = board; 
     total = 0; 

    } 

    private void find(String c) 
    { 
     int x=0, y=0; 
     for(int i = 0; i < size; i++) 
     { 
      for(int j = 0; j < size; j++) 
      { 
       if(board[i][j].equals(c)) 
       { 
        x = i; 
        y = j; 
       } 
      } 
     } 
     if(c.equals("M")) 
     { 
      mX = x; 
      mY = y; 
     } 
     else if(c.equals("E")) 
     { 
      eX = x; 
      eY = y; 
     } 
    } 

    public void findPath() 
    { 
     find("M"); 
     find("E"); 
     findNext(mX, mY); 
    } 

    public void findNext(int x, int y) 
    { 
     String last = board[x][y]; 
      if(board[x][y].equals("P")) board[x][y] = "1"; 
     board[x][y] = "P"; 

     if(rightAvailability(x,y)) 
     { 
      findNext(x+1, y); 
     } 
     else if(leftAvailability(x,y)) 
     { 
      findNext(x-1, y); 
     } 
     else if(aboveAvailability(x,y)) 
     { 
      findNext(x, y+1); 
     } 
     else if(belowAvailability(x,y)) 
     { 
      findNext(x, y-1); 
     } 
     else 
     { 
      total++; 
      printBoard(); 
     } 

     board[x][y]= last; 
    } 

    public boolean rightAvailability(int x, int y) 
    { 
     if(x+1 >= size) return false; 
     else if(board[x+1][y].equals("1")) return false; 
     else if(board[x+1][y].equals("P")) return false; 
     else return true; 
    } 
    public boolean leftAvailability(int x, int y) 
    { 
     if(x-1 < 0) return false; 
     else if(board[x-1][y].equals("1")) return false; 
     else if(board[x-1][y].equals("P")) return false; 
     else return true; 
    } 
    public boolean aboveAvailability(int x, int y) 
    { 
     if(y+1 >= size) return false; 
     else if(board[x][y+1].equals("1")) return false; 
     else if(board[x][y+1].equals("P")) return false; 
     else return true; 
    } 
    public boolean belowAvailability(int x, int y) 
    { 
     if(y-1 < 0) return false; 
     else if(board[x][y-1].equals("1")) return false; 
     else if(board[x][y-1].equals("P")) return false; 
     else return true; 
    } 

    public void printBoard() 
    { 
     System.out.println("The board number " +total+ " is: "); 
     for(int i=0; i< size; i++) 
     { 
      for(int j=0; j< size; j++) 
      { 
       if((i==mX) && (j==mY)) 
       { 
        System.out.print("M"); 
       } 
       else if((i==eX) && (j==eY)) 
       { 
        System.out.print("E"); 
       } 
       else if(board[i][j].equals("1")) 
       { 
        System.out.print("1"); 
       } 
       else if(board[i][j].equals("0")) 
       { 
        System.out.print("0"); 
       } 
       else 
       { 
        System.out.print("P"); 
       } 
      } 
      System.out.println(); 
     } 
    } 
} 

Voici le testeur:

public class MazeTester 
{ 
    public static void main(String[] args) 
    { 
     int size = 11; 
     String[][] board = new String[][] 
      { 
       {"1","1","1","1","1","1","1","1","1","1","1"}, 
       {"1","0","0","0","0","0","1","0","0","0","1"}, 
       {"1","0","1","0","0","0","1","0","1","0","1"}, 
       {"E","0","1","0","0","0","0","0","1","0","1"}, 
       {"1","0","1","1","1","1","1","0","1","0","1"}, 
       {"1","0","1","0","1","0","0","0","1","0","1"},  
       {"1","0","0","0","1","0","1","0","0","0","1"}, 
       {"1","1","1","1","1","0","1","0","0","0","1"}, 
       {"1","0","1","M","1","0","1","0","0","0","1"}, 
       {"1","0","0","0","0","0","1","0","0","0","1"}, 
       {"1","1","1","1","1","1","1","1","1","1","1"}, 
      }; 


     Maze m = new Maze(size, board); 
     m.findPath(); 
    } 
} 

Voici la sortie de courant:

The board number 1 is: 
11111111111 
1PPPPP1PPP1 
1P1PPP1P1P1 
EP1PPPPP1P1 
101111101P1 
10101PPP1P1 
10001P1PPP1 
11111P1PP01 
101M1P1PP01 
100PPP1PP01 
11111111111 
The board number 2 is: 
11111111111 
1PPPPP1PPP1 
1P1PPP1P1P1 
EP100PPP1P1 
101111101P1 
10101PPP1P1 
10001P1PPP1 
11111P1PP01 
101M1P1PP01 
100PPP1PP01 
11111111111 
The board number 348 is: 
11111111111 
1PPPPP10001 
1P1PPP10101 
EP1PPPPP101 
1011111P101 
10101PPP101 
10001P10001 
11111P10001 
101M1P10001 
100PPP10001 
11111111111 

EDIT: J'ajouté si (carte [x ] [y] .equals ("P")) tableau [x] [y] = "1"; au début de findIndex. J'ai également corrigé le problème x < = 0. J'ai mis à jour la sortie à ce que je reçois maintenant (c'est en fait l'impression 348 conseils similaires).

Answer 1

Je mis une estimation partielle à la ligne:

else if(belowAvailability(x,y)) 
{ 
     findNext(x, x-1); 
} 

x-1 doit être y-1

Un autre problème, vous trouverez dans le fait que vous utilisez autre si les blocs . Si vous rencontrez une branche, par exemple

1E1 
101 
1P0 
1P1 

Vous allez essayer d'aller à droite d'abord, puis quand cela échoue lamentablement, il ne tentera pas d'augmenter. Vous pouvez réellement voir que dans la sortie de test,

_._._789_._ 
_..._6_A54_ 
_____5_B23_ 
_._M_4_C10_ 
_..123_DEF_ 
___________ 

numéroté en hexadécimal pour faciliter la lecture. Il pénètre dans le coin inférieur droit, puis reste coincé; N'ayant nulle part où aller, le tableau est imprimé et la récursion se termine sans retour en arrière dans des cases non testées.

EDIT à nouveau. Toujours à la recherche, mais dans la disponibilité gauche/droite, vous avez une autre incompatibilité x/y, et vous ne voulez probablement que refuser la disponibilité lorsque x-1 < 0 (ou y-1); comme le nœud de but est à y = 0. Avec ces changements, et ayant un déclencheur d'impression seulement lorsque x == eX & & y == eY, je reçois la sortie de solutions. Un grand nombre de solutions, mais des solutions. Un fait plus humoristique pour le nombre d'éditions: vous avez gauche/droite et haut/bas en arrière. La coordonnée x spécifie la ligne de l'entrée que vous regardez, et la coordonnée y spécifie la colonne. Il est raisonnablement courant d'utiliser r/c dans des cas comme celui-ci.

Answer 2

Les algorithmes de recherche de chemin standard devraient fonctionner, vous devrez les modifier pour correspondre à votre définition du monde.

Mais les algorithmes A * ou D * fonctionnent plutôt bien. Ils utilisent un graphique, que vous devriez être en mesure de définir à partir de votre définition du monde. (http://en.wikipedia.org/wiki/A *)

L'algorithme de Dijstra devrait également fonctionner pour trouver un chemin (utilise à nouveau un graphique). Il est couramment utilisé pour le routage réseau - mais il fonctionne également pour la recherche de chemin normale.(http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

Fondamentalement, mon approche serait de transformer votre définition de labyrinthe en un graphique (les nœuds sont des «points de jointure», les bords sont les «couloirs») et ensuite utiliser un de ces algorithmes.