Labyrinth-Pfad-Finder in Java

Question

Ich versuche, das Labyrinth mit Rekursion zu lösen. Im folgenden Codeabschnitt ist MazeCoord ein vom Programmierer erstellter Typ, der einen Koordinatenort speichert. Das Format ist MazeCoord (int x, int y). Mein Programm, wenn es jetzt kompiliert wird, erreicht einige Teile der Methode und ignoriert die andere und sagt daher in allen Fällen "Kein Pfad gefunden" und speichert nur den Startort in dem LinkedList mazePath. Es gibt einen auskommentierten Teil in der search() Methode, das war eine andere Art, wie ich es ausprobierte, aber ich bin mir ziemlich sicher, dass es falsch ist und nicht die Art, es zu tun.

Jede Hilfe wird geschätzt.

Rekursion Code:

/** Gibt den Weg durch das Labyrinth. Das erste Element ist der Startort und das letzte Element ist der Ausgangsort. Wenn kein Pfad vorhanden war oder vor der Suche aufgerufen wird, wird eine leere Liste zurückgegeben.

@return das Labyrinth Weg */

public LinkedList<MazeCoord> getPath() { 
     return mazePath; 
} 

/** Finden Sie einen Weg durch das Labyrinth, wenn es einen gibt. Der Client kann auf den über die Methode getPath gefundenen Pfad zugreifen. @return ob der Pfad gefunden wurde. */

public boolean search() { 
     currentLoc = new MazeCoord(startLoc.getRow(), startLoc.getCol()); 
     visitedPath = new boolean[mazeData.length][mazeData[0].length]; 

     mazePath=new LinkedList<MazeCoord>(); 

     if(hasWallAt(startLoc) || hasWallAt(endLoc)){  
     return false; 
     } 
     else{ 
      mazePath.add(currentLoc); 
      return appendToSearch(currentLoc.getRow(), currentLoc.getCol()); 
     } 

     /** 
     System.out.println("try1"); 
     mazePath.add(new MazeCoord(startLoc.getRow(), startLoc.getCol())); 
     boolean searchResult = appendToSearch(numRows()-1, numCols()-1); 

     System.out.println("test: " + searchResult); 
     System.out.println("test2: row, col --> " + (numRows()-1) + " , " + (numCols()-1)); 
     System.out.println("test3: wallValue:" + hasWallAt(new MazeCoord(numRows()-1,numCols()-1))); 

     if(searchResult){ 
      System.out.println("try2"); 
      mazePath.add(new MazeCoord(numRows()-1, numCols()-1)); 
     } 
     return searchResult; 
     */ 
    } 

/** Helper-Funktion für die Suche() Methode, die die tatsächliche Rekursion durchführen wird den Pfad durch das Labyrinth erhalten @param die Zeile für den currentLoc @param col der Spalte Zeile für die currentLoc @return iff einen Pfad wahr ist verfügbar */

private boolean appendToSearch(int row, int col) { 


     //Check if within the maze 
     if((row - 1 < 0) || (col - 1 < 0) || (row + 1 > numRows()) || (col + 1 > numCols())){ 
      return false; 
     } 
     //Check if the position is the exit location 
     if(row == endLoc.getRow() && col == endLoc.getCol()){ 
      mazePath.add(new MazeCoord(row, col)); 
      return false; 
     } 
     //Check for Wall 
     if(hasWallAt(new MazeCoord(row, col))){ 
      return false; 
     } 
     //Check if the position has already been visited 
     if(visitedPath[row][col]){ 
      return false; 
     } 
     //If all pass --> add to visitedPath 
     visitedPath[row][col]=true; 

     //Check to the Right 
     if(appendToSearch(row, col + 1)){ 
      mazePath.add(new MazeCoord(row, col + 1)); 
      return true; 
     } 
     //Check Downwards 
     else if(appendToSearch(row + 1, col)){ 
      mazePath.add(new MazeCoord(row + 1, col)); 
      return true; 
     } 
     //Check to the Left 
     else if(appendToSearch(row, col - 1)){ 
      mazePath.add(new MazeCoord(row, col - 1)); 
      return true; 
     } 
     //Check Upwards 
     else if(appendToSearch(row - 1, col)){ 
      mazePath.add(new MazeCoord(row - 1, col)); 
      return true; 
     } 
     return false; 
    } 

Answer 1

zunächst einmal möchte Ich mag Sie this link vorzuschlagen, die dort eine der häufigsten Wegfindung Algorithmen erklärt.

Ein kurzes Tutorial, dem Sie auch folgen können, finden Sie here Meiner Meinung nach wird dieses Tutorial gut zu Ihren Anforderungen passen, da es ein Raster als Beispiel nimmt.

Es ist nicht erforderlich, eine rekursive Funktion zu verwenden, um einen Pfadfindungsalgorithmus auszuführen. Was Sie tun könnten, könnte sein, zwei Listen zu halten: eine von bereits 'checked' Zellen/Kacheln und eine andere von denen, die noch nicht haben.

Nacheinander werden Sie von dem Punkt beginnen, wo Sie den Pfad beginnen soll und wird für alle Zellen/Fliesen überprüfen, die von diesem Punkt zu erreichen, wie:

void addCells(Point current) { 
    // Left 
    if (emptyAndNotChecked(current.x-1,current.y)) // Checking for walls here 
     cellsToCheck.add(new Point(x-1,y)) // Adding this cell to the list 
    // Right 
    if (emptyAndNotChecked(current.x+1,current.y)) 
     cellsToCheck.add(new Point(x+1,y)) 
    // Top 
    if (emptyAndNotChecked(current.x,current.y+1)) 
     cellsToCheck.add(new Point(x,y+1)) 
    // Bottom 
    if (emptyAndNotChecked(current.x,current.y-1)) 
     cellsToCheck.add(new Point(x,y-1)) 
} 

Wo emptyAndNotChecked() nur, ob die überprüft Die angegebene Position ist keine Wand und wurde noch nicht überprüft. Natürlich können Sie auch eine Diagonalprüfung durchführen!

An dieser Stelle möchten Sie die nächste Zelle/Kachel finden, von der Sie weitere Zellen hinzufügen möchten, indem Sie alle "unchecked" Zellen/Kacheln markieren und auf jedes der a "Gewichte" anwenden "Funktion, die Ihnen die beste Zelle/Kachel für ein bestimmtes Ziel gibt, könnte eine grundlegende Implementierung dieses:

float weight(Point current,Point end) { 
    return Math.sqrt(Math.pow(current.x-end.x,2)+Math.pow(current.y-end.y,2)); 
} 

diese Funktion ermöglicht es Ihnen, die am besten geeignete Zelle/Fliese zu navigieren zu finden, das es einmal gefunden (die mit dem niedrigsten Gewicht), Sie bewegen sich zu diesem und rufen die erste Funktion erneut auf, um weitere Zellen/Kacheln hinzuzufügen.

Sie stoppen, wenn die Zelle/Kachel, an die Sie sich bewegt haben, das Ziel ist, oder wenn Sie addCells() anrufen, fügen Sie keine neue Zelle/Kachel hinzu.

Natürlich ist dies nur eine grundlegende Möglichkeit, dies zu tun, und es gibt eine Menge Verbesserungen, die angewendet werden können. Hoffe das ist hilfreich!