Labyrinth kürzester Weg

[Han]

Hallo....tüftle schon eine Weile an dem Problem einen kürzesten Weg durch ein Labyrinth zu finden bin aber bis jetzt noch auf keine Lösung gekommen...
Hier mein Code:

//Liste zur Erstellung der einzelnen Wegpfade
//---------------------------------------------------------
        class Node{
                int x;
                int y;
                Node next;
                Node(int x,int y){
                        this.x = x;
                        this.y = y;
                        next = null;
                }
        }

    class List{
            Node head = null;
            
            void insert(int x, int y){
                    Node p = new Node(x,y);
                    p.next = head;
                    head = p;
            }
   
        void print() {

                  Node p = head;
                  IO.writeLn("Weg:");

                  while (p != null) {
                          IO.write("(" + p.x + "," + p.y + ")");
                          p = p.next;
                  }
           }

    }
        
//----------------------------------------------------------

public class labyrinth{
        
        static int zaehler = 0;
        static List path = new List();
        
        static boolean canExit(char[][] maze, int i, int j, int n){
        
                if(i < 0||j < 0||i == n||j == n) return false; //outside the maze
                if(maze[i][j] != ' ') return false; //bumped against a wall or already visited
                maze[i][j] = '.';
                zaehler++;
                
                if(i == n-1 && j == n-1       //already at the  goal?
                || canExit(maze,i+1,j,n) //can we find the exit if we go down?
                || canExit(maze,i,j+1,n) //can we find the exit if we go right?
                || canExit(maze,i-1,j,n)  //can we find the exit if we go up?
                || canExit(maze,i,j-1,n)){ //can we find the exit if we go left?
                      IO.write("("+i+","+j+")"); //print the field as part of the right way  
                      path.insert(i,j);
                      return true;
                }
          
            return false;
        }
        
        public static void main(String[] args){
                
        
        char[][] maze = {{' ','X',' ',' ',' '},
                         {' ',' ',' ','X',' '},
                         {' ','X',' ','X',' '},
                         {' ','X',' ','X',' '},
                         {' ',' ',' ','X',' '}};
        char[][] maze2 ={{' ','X',' ','X',' ',' ',' '},
                         {' ','X',' ',' ',' ','X',' '},
                         {' ',' ','X','X',' ','X',' '},
                         {'X',' ',' ',' ',' ','X',' '},
                         {' ',' ',' ','X',' ','X',' '},
                         {'X','X',' ',' ',' ','X',' '},
                         {' ','X','X','X','X','X',' '}};
   
   
           canExit(maze,0,0,5);
            path.insert(-1,-1);
                 path.print();
                                      
        }        
}

Der Algorithmus findet einen Weg durch das Labyrinth aber halt nicht den Kürzesten.
Ich weiß dass das mit der Breitensuche funktioniert...
Funktioniert die Breitensuche im Labyrinth so dass ich wenn ich auf einem freien Kästchen stehe zuerst einmal alle Möglichkeiten (also nach unten, rechts, links, oben) durchgehe und da wos geht markiere ich die Stelle. dadurch entstehen sozudagen mehrere "Teams" die nach einem Ausgang suchen und wenn ein Team den Ausgang als erstes gefunden hat ist dies der kürzeste Weg.
...jetzt haperts nur noch mit der Einbindung in Java...

Bitte keine Verweise auf google oder derartiges denn ich hab schon zur Genüge auf google gesucht und nichts Brauchbares gefunden.....

mfg,
Hannes


[/code]

 

[Beni]

Wenn meine Augen das richtig entziffert haben, hast du keine Breitensuche, sondern eine Tiefensuche implementiert.

Eine Breitensuche benötigt eine Queue, das lässt sich nur mit Methodenaufrufen nicht mehr (gut) drastellen.

Wenn ich das mal in Pseudocode darstellen darf:

public class Node{
  private int x, y;
  private Node parent;

  // Länge des Weges, der Knoten ohne parent ist der Start
  private int length(){
    if( parent == 0 )
      return 0;
    else
      return parent.length() + 1;
  }
}

public Node search( int[][] maze, int x, int y ){
  Queue<Node> queue = new Queue<Node>();
  Node[][] nodes = new Node[ maze.length ][ maze[0].length ];
  
  nodes[x][y] = new Node( x, y, null );
  queue.add( nodes[x][y] );

  while( !queue.isEmpty() ){
    Node node = queue.tail(); // erster Knoten in der Queue
    if( node.isExit() )
      return node;  // ein Ausgang

    Node next = testGo( maze, nodes, node, node.x+1, node.y );
    if( next != null ){
      nodes[node.x+1][node.y] = next;
      queue.add( next ),
    } 

    if( // für die anderen 3 Richtungen ){...}
  }
}

private Node testGo( int[][] maze, Node[][] nodes, Node parent, int x, int y ){
  if( x/y ist ausserhalb des Feldes )
    return null;

  // da war noch niemand
  if( nodes[x][y] == null ) 
    return new Node( x, y, parent );

  // da war schon jemand, aber der Weg dorthin ist nicht optimal
  if( nodes[x][y].length() > parent.length() ) 
    return new Node( x, y, parent );
  
  // von hier aus geht es nicht nach x/y
  return null;
}

Die Breitensuche sucht in "Kreisen" um den Start, und ersetzt bereits gefundene Teilwege durch bessere, wenn sie bessere findet.

 

[bygones]

musst du das selber implementieren ?

es gibt im netz gute Implementationen von Dijkstra bzw. A* die dir diese Aufgabe - v.a. effizient - abnehmen....

 

[mic_checker]

Zu A* gibts auch was hier im Forum - von Illuvatar:

http://www.java-forum.org/de/viewtopic.php?t=5540

Falls du zu Dijkstra nichts findest kannst du den ja auch selber implementieren...aber da solltest du auf jeden fall was finden.

 

[Han]

Hallo...danke für die Antworten...aber im Buch steht bei der Aufgabe dabei dass mit nur geringen Aufwand sich dieses Tiefenverfahren in einen Algorithmus umwandeln lässt der einen kürzesten Weg findet...Wie schaut dass aus ohne gleich fast alles zu ändern?
mfg,
Hannes

 

[mic_checker]

Der Code von oben war gegeben (bzw. so ähnlich) und du sollst anhand von wenigen Modifikationen den kürzesten Weg rausfinden ?

Zum Dijkstra kannst du dir auch mal das anschauen. Falls du nichts findest, ich hab irgendwo noch eine Implementierung vom Dijkstra hier rumfliegen....könnte die dir dann zuschicken.

 

[Guest]

Hmm, wenn du diesen Algorithmus nur gering abändern sollst würde ich anstelle der Queue einen Stack benutzen.

Der Unterschied zwischen Breiten-und Tiefensuche ist die Art der Eingabe der Ecken. Also, anstelle der Queue einen Stack.

 

[KS]

Hallo Gast...

Ich habe mal einen Vortrag über Labyrinte gehalten. Hierbei habe ich folgende super Site gefunden:

http://www.mazeworks.com/mazegen/index.htm

Dort hat es ein Applet zu diesem Thema und auch der Code kann heruntergeladen werden.

Cheers
Christian

 

[Han]

Hallo...also muss ich für jeden neuen Weg den ich finde wieder eine eigene Liste erstellen, die Punkte die nicht zum neuen Weg gehören weglassen und dann wieder weitersuchen...zum Schluss zähle ich die Punkte in meinen Listen und die kürzeste Liste ist dann der 'Sieger'.
...Wenn das nicht wenig zu ändern ist dann weiß ich auch nicht.....
Denn alleine dass mir die Methode alle Punkte anschaut muss ich schonmal fast alles im Quellcode ändern oder?
mfg,
Hannes