Labyrinth

[gogocho]

Hallo zusammen
Also ich muss ein Programm schreiben, dass den kuerzesten Weg in einem 11x11 Labyrinth findet. Der Eingang ist maze[0][1], der Ausgang maze[10][9]. Soweit hab ich:

public class MazeSolution extends Maze {

    boolean[][] wegBisher = new boolean[11][11];
    boolean[][] kuerzererWeg;
    int LengthBesterWeg;
    int zielx=10;
    int ziely=9;
    public static boolean[][] maze;
 void copyfield(boolean [][]src, boolean[][] target){
     for (int i=0; i<src.length; i++){
         for (int j=0; j<src.length; j++){
             target[i][j]=src[i][j];
         }
     }
 }
   public void walk(int x, int y, int curLength){
       draw(x,y,wegBisher,kuerzererWeg);
       if (maze[x][y]==true){
           return;
           //Im Falle von Wand
       }
       if (wegBisher[x][y]=true){
           return;
           //Falls das Feld schon mal durchgelaufen wurde(nicht im Kreis laufen)
       }
       if(curLength>LengthBesterWeg){
           return;
       }
       if (x==zielx&&y==ziely){
           //Falls den Ausgang erreicht wurde
           copyfield(wegBisher, kuerzererWeg);
           LengthBesterWeg=curLength;
       }
       
      
               //Bewegung nach oben
      
               //Bewegung nach unten
      
               //Bewegung nach rechts
      
            //Bewegung nach links
   
   
 public static void main(String[] args){
    boolean[][] maze=Maze.generateMaze();

Es ist noch nicht komplett fertig. Ich kann aber nicht verstehen wie man sich eigentlich bewegen soll, Im Internet habe ich so eine Loesung gefunden (bzgl, der Bewegungen):

if (x > 0) {
            walk(x - 1, y, curLength + 1); //rauf
        } else if (x < wegBisher[0].length - 1) {
            walk(x + 1, y, curLength + 1); //runter
        }
else if (y > 0) {
            walk(x, y - 1, curLength + 1); //links
        } else if (y < wegBisher.length - 1) {
            walk(x, y + 1, curLength + 1); //rechts
        }

Ich bin nicht ganz sicher ob es richtig ist. Sollen die Bewegungen eigentlich beliebig sein?
Danke im Voraus

 

[thorstenthor]

Den kürzesten auch noch... Nicht nur irgendeinen Weg. Dazu gibts schon fertige Verfahren und auch viel egute Bücher, in denen das beschrieben ist. Deine Methode walk muss sich selbst aufrufen, wenn du es relativ kurz formulieren willst.

 

[gogocho]

ja, heute den ganzen tag suche ich, aber eine antwort meiner frage habe ich nicht gefunden..deswegen frage ich hier

 

[Marcinek]

Algorithmus von Floyd und Warshall ? Wikipedia

 

[thorstennn]

ich glaube nicht, dass er diesen Algorithmus sucht. Am ende weiß ich dann lediglich, wie lang ein Weg zweier beliebiger Knoten ist.
Und wie bereits gesagt gibt es ein Buch, das sich hervorragend für diese Aufgabe eignet. Einfach mal Algorithmen eingeben

 

[Marcinek]

Naja man hat die Transisitive Hülle und alle Abstände von allen Knoten.. Ich denke damit lässt sich prüfen, ob man von A nach B kommen kann und wie lange der weg ist.

 

[thorstennn]

Also ich muss ein Programm schreiben, dass den kuerzesten Weg in einem 11x11 Labyrinth findet.

wenn man keine Ahnung hat...

(genauer: es gibt einen Weg raus mit Länge xyz... das hilft ja jetzt viel)

 

[Marcinek]

Wenn es nur einen Weg gibt, dann ist das der kürzeste.


Man muss nicht prüfen, ob es überhaupt einen Weg gibt. Der Algo bietet aber die mögichkeit dazu.

Man kann auch SSSP ALgo nehmen oder generischen kürzeste Pfade Algo. Oder das Backtracking, dass her versucht wird.

Thorsten, was würdest du hier machen?

 

[thorstennn]

Es gibt Bücher nur über Labyrinthe

Die Aufgabenstellung war, dass der kürzeste Weg berechnet werden soll, nicht einfach nur die Länge dieses Weges.

Floyd-Warshall-Algo liefert ein Array, aus dem lediglich ersichtlich ist, wie lang kürzeste Wege zwischen zwei beliebigen Knoten sind.

Er muss mal genauer beschreiben, welchen Ansatz er meint, es nützt ja nichts, eine Fertiglösung zu präsentieren.

 

[gogocho]

ich hab was verpasst eigentlich..also um man den kürzesten weg zu finden, müssen alle wege durchgelaufen werden..also deswegen hab ich die copyfield methode da..und was ich nicht verstehe ist wie soll ich die bewegungen nach rechts usw. machen

 

[Marcinek]

Ist das eine vorgabe von deinem Professor / Lehrer oder deine Idee?

if (x > 0) {
            walk(x - 1, y, curLength + 1); //rauf
        } else if (x < wegBisher[0].length - 1) {
            walk(x + 1, y, curLength + 1); //runter
        }
else if (y > 0) {
            walk(x, y - 1, curLength + 1); //links
        } else if (y < wegBisher.length - 1) {
            walk(x, y + 1, curLength + 1); //rechts
        }

Hier gehst du doch schon runter und hoch und so weiter. Ist das dein code? Hast du Fragen zu dem Code, der da steht?

Außerdem wirst du so eine Endlosschleife produzieren. Die Rekursion wird ewig rauf und runter gehen an den ersten Positionen.

(Sorry, der Link ist ist kaka)

 

[gogocho]

nein, das hab ich im internet irgendwo gefunden, aber ich denke, dass es nicht richtig ist

 

[gogocho]

soll man sich z.b. bzgl. der wände bewegen? z.b.

if (maze[x][y+1]!=true&&wegBisher[x][y+1]!=true)
walk(x,y+1)
//wenn maze[x][y]=true gibts eine wand

if rechts gibts keine wand und das feld noch nicht besucht wurde, geh rechts usw. ?

 

[Marcinek]

Ein guter Anfang. Bitte beachte auch, dass x nicht größer als das Array sein darf, sonst IOOBE

 

[gogocho]

so laeuft. jetzt aufpassen nicht eingeschlossen zu sein und gut