# Labyrinth



## gogocho (17. Jun 2011)

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 (17. Jun 2011)

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 (17. Jun 2011)

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


----------



## Marcinek (17. Jun 2011)

Algorithmus von Floyd und Warshall ? Wikipedia


----------



## thorstennn (17. Jun 2011)

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 (17. Jun 2011)

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 (17. Jun 2011)

gogocho hat gesagt.:


> 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 (17. Jun 2011)

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 (18. Jun 2011)

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 (18. Jun 2011)

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 (18. Jun 2011)

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 (18. Jun 2011)

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


----------



## gogocho (18. Jun 2011)

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 (18. Jun 2011)

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


----------



## gogocho (18. Jun 2011)

so laeuft. jetzt aufpassen nicht eingeschlossen zu sein und gut


----------

