Labyrinth auf der Basis eines rekursiven Algorithmus

iris_anfänger · 15. Dez 2019

Habe diese Aufgabe fast geschaft. Jedoch nicht ganz richtig.

Code:

public class LabyrinthChar {
    public static void main(String[] args) {
  ............
  }

    public static boolean navigate(char [][] lab, int i, int j){
    boolean weg = true;

    if(i == lab.length-1 || j == lab[0].length-1){
        return weg;
    }else{
        if (lab[i][j+1]== ' '){
            lab[i][j+1]= '*';
            if(navigate(lab,i,j+1)) return true;
        }
        if (lab[i+1][j]==' '){
            lab[i+1][j]='*';
            if(navigate(lab,i+1,j)) return true;
        }
        if (lab[i][j-1]==' '){
            lab[i][j-1]='*';
            if(navigate(lab,i,j-1)) return true;
        }
        if (lab[i-1][j]==' '){
            lab[i-1][j]='*';
            if(navigate(lab,i-1,j)) return true;
        }
        }
        return false;
    }
}

Das Problem, dass die Ausgangsposition soll in der Mitte des Labyrinths sein. Bei mir fängt von [0][0] an. Wie kann ich das ändern?
Ich bedanke mich im Voraus für Bemühen und würde mich über jede Antwort sehr freuen )

mihe7 · 15. Dez 2019

Indem Du beim ersten Aufruf von navigate nicht 0, 0 sondern eben die Mitte angibst.

iris_anfänger · 15. Dez 2019

Dann wird nur das Teil genau ab Mitte ausgewertet

iris_anfänger · 15. Dez 2019

mihe7 hat gesagt.:
Indem Du beim ersten Aufruf von navigate nicht 0, 0 sondern eben die Mitte angibst.

dann bekomme ich "IndexOutOfBoundsException" 😳

mihe7 · 15. Dez 2019

Ja, vielleicht gehst Du zu weit nach links oder oben?

iris_anfänger · 15. Dez 2019

mihe7 hat gesagt.:
Ja, vielleicht gehst Du zu weit nach links oder oben?

vielleicht....

mihe7 · 15. Dez 2019

Ja, wäre halt nicht verkehrt, wenn Du den Fall abfangen würdest 🙂

iris_anfänger · 15. Dez 2019

mihe7 hat gesagt.:
Ja, wäre halt nicht verkehrt, wenn Du den Fall abfangen würdest 🙂

Ist hier falsch?

Code:

if(i == lab.length-1 || j == lab[0].length-1){
        return weg;

mihe7 · 15. Dez 2019

Das ist die Prüfung nach rechts/unten, nicht aber nach links/oben. Deine IndexOutOfBoundsException gibt ja noch an, welcher Index falsch ist. Da steht vermutlich -1.

iris_anfänger · 16. Dez 2019

mihe7 hat gesagt.:
Das ist die Prüfung nach rechts/unten, nicht aber nach links/oben. Deine IndexOutOfBoundsException gibt ja noch an, welcher Index falsch ist. Da steht vermutlich -1.

Ich habe gedacht, dass mit dieser if-Anweisung erfasse ich array komplet von [0][0] bis [9][9]
Wie kann ich dann nach links/oben prüfen? 😵

mihe7 · 16. Dez 2019

Naja, wenn i bzw. j gleich 0 sind, kannst Du nicht auf lab[i-1][j] bzw. lab[i][j-1] zugreifen, da sonst der entsprechende Index -1 werden würde.

Analog: wenn i gleich lab.length-1 bzw. j gleich lab[0].length-1 ist, dann darfst Du nicht auf lab[i+1][j] bzw. lab[i][j+1] zugreifen, da sonst der entsprechende Index zu groß wäre.

Prüfen: mit if.

iris_anfänger · 16. Dez 2019

mihe7 hat gesagt.:
Naja, wenn i bzw. j gleich 0 sind, kannst Du nicht auf lab[i-1][j] bzw. lab[i][j-1] zugreifen, da sonst der entsprechende Index -1 werden würde.

Analog: wenn i gleich lab.length-1 bzw. j gleich lab[0].length-1 ist, dann darfst Du nicht auf lab[i+1][j] bzw. lab[i][j+1] zugreifen, da sonst der entsprechende Index zu groß wäre.

Prüfen: mit if.

Erst Danke für deine Geduld. Wenn ich das richtig verstanden habe, dann soll so aussehen:

Code:

if(i == lab.length-i || j == lab[0].length-j){
        return weg;

Aber jetzt wird der Weg nicht markiert, mit *

mihe7 · 16. Dez 2019

iris_anfänger hat gesagt.:
Wenn ich das richtig verstanden habe, dann soll so aussehen:

Nein 🙂 lab.length-1 war schon richtig. OK, machen wir erstmal den rechten bzw. unteren Rand.

Deine Methode sucht ja prinzipiell vier Richtungen ab: rechts, links, oben und unten. Am Anfang prüfst Du nun, ob Du am rechten und/oder am unteren Rand stehst und falls ja, brichst Du ab. Das ist nicht richtig: wenn Du am rechten Rand stehst kannst Du trotzdem noch nach unten, links und oben gehen.

Du darfst nur dann nicht nach rechts gehen, wenn Du am rechten Rand stehst. Du darfst nur dann nicht nach oben gehen, wenn Du am oberen Rand stehst usw.

Die Prüfung am Anfang kannst Du also erstmal vergessen und

Java:

        if (lab[i][j+1]== ' '){

reicht offensichtlich nicht aus, Du musst hier prüfen, ob j+1 noch zulässig wäre.

Java:

        if (j+1 < lab[i].length && lab[i][j+1]== ' '){

Analog prüfst Du das für "nach unten", natürlich mit passendem i und lab.length.

Fehlt noch oben und links. Wenn Du ganz links stehst, ist j == 0. Würdest Du jetzt auf j-1 zugreifen, bekommst Du natürlich einen Fehler. D. h. Du musst prüfen, ob j-1 noch zulässig wäre. j-1 ist zulässig, wenn j-1 >= 0 gilt, d. h. j >= 1, also j > 0. Es folgt:

Java:

    if (j > 0 && lab[i][j-1] == ' ') {

Analog für "nach oben".

Blender3D · 16. Dez 2019

iris_anfänger hat gesagt.:
Das Problem, dass die Ausgangsposition soll in der Mitte des Labyrinths sein. Bei mir fängt von [0][0] an. Wie kann ich das ändern?

Wenn Du die Problemstellung aufteilst und sprechende Namen vergibst wird alles viel einfacher.

Java:

package maze;

public class MazeChar {
    public final static char WALL = '*';
    public final static char AIM = 'O';
    public final static char MARKED = 'x';
    public final static char FREE = ' ';

    public static boolean navigate(char[][] maze, int x, int y) {
        if (maze[x][y] == AIM)
            return true;
        maze[x][y] = MARKED;
        if (!isRightBlocked(maze, x, y))
            return navigate(maze, x + 1, y);
        if (!isDownBlocked(maze, x, y))
            return navigate(maze, x, y + 1);
        if (!isLeftBlocked(maze, x, y))
            return navigate(maze, x - 1, y);
        if (!isUpBlocked(maze, x, y))
            return navigate(maze, x, y - 1);
        return false;
    }

    public static int getDimX(char[][] maze) {
        return maze.length;
    }

    public static int getDimY(char[][] maze) {
        return maze[0].length;
    }

    public static boolean isBlocked(char c) {
        return c != FREE && c != AIM;
    }

    public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) || isBlocked(maze[x][y + 1]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x == 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) || isBlocked(maze[x + 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y == 0 || isBlocked(maze[x][y - 1]);
    }

}

iris_anfänger · 16. Dez 2019

mihe7 hat gesagt.:
Nein 🙂 lab.length-1 war schon richtig. OK, machen wir erstmal den rechten bzw. unteren Rand.

Deine Methode sucht ja prinzipiell vier Richtungen ab: rechts, links, oben und unten. Am Anfang prüfst Du nun, ob Du am rechten und/oder am unteren Rand stehst und falls ja, brichst Du ab. Das ist nicht richtig: wenn Du am rechten Rand stehst kannst Du trotzdem noch nach unten, links und oben gehen.

Du darfst nur dann nicht nach rechts gehen, wenn Du am rechten Rand stehst. Du darfst nur dann nicht nach oben gehen, wenn Du am oberen Rand stehst usw.

Die Prüfung am Anfang kannst Du also erstmal vergessen und

Java:

if (lab[i][j+1]== ' '){

reicht offensichtlich nicht aus, Du musst hier prüfen, ob j+1 noch zulässig wäre.

Java:

if (j+1 < lab[i].length && lab[i][j+1]== ' '){

Analog prüfst Du das für "nach unten", natürlich mit passendem i und lab.length.

Fehlt noch oben und links. Wenn Du ganz links stehst, ist j == 0. Würdest Du jetzt auf j-1 zugreifen, bekommst Du natürlich einen Fehler. D. h. Du musst prüfen, ob j-1 noch zulässig wäre. j-1 ist zulässig, wenn j-1 >= 0 gilt, d. h. j >= 1, also j > 0. Es folgt:

Java:

if (j > 0 && lab[i][j-1] == ' ') {

Analog für "nach oben".

Vielen Vielen Dank!!!! Eine echte HILFE! 😉 Jetzt habe ich verstanden und es funktioniert!!!!!
Ich bin glücklich. 🙂🙂🙂

Blender3D · 16. Dez 2019

iris_anfänger hat gesagt.:
Vielen Vielen Dank!!!! Eine echte HILFE! 😉 Jetzt habe ich verstanden und es funktioniert!!!!!
Ich bin glücklich

Dann solltest Du @mihe7 auch mit einem Like belohnen. 😉

iris_anfänger · 16. Dez 2019

Blender3D hat gesagt.:

Wenn Du die Problemstellung aufteilst und sprechende Namen vergibst wird alles viel einfacher.

Java:

package maze;

public class MazeChar {
    public final static char WALL = '*';
    public final static char AIM = 'O';
    public final static char MARKED = 'x';
    public final static char FREE = ' ';

    public static boolean navigate(char[][] maze, int x, int y) {
        if (maze[x][y] == AIM)
            return true;
        maze[x][y] = MARKED;
        if (!isRightBlocked(maze, x, y))
            return navigate(maze, x + 1, y);
        if (!isDownBlocked(maze, x, y))
            return navigate(maze, x, y + 1);
        if (!isLeftBlocked(maze, x, y))
            return navigate(maze, x - 1, y);
        if (!isUpBlocked(maze, x, y))
            return navigate(maze, x, y - 1);
        return false;
    }

    public static int getDimX(char[][] maze) {
        return maze.length;
    }

    public static int getDimY(char[][] maze) {
        return maze[0].length;
    }

    public static boolean isBlocked(char c) {
        return c != FREE && c != AIM;
    }

    public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) || isBlocked(maze[x][y + 1]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x == 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) || isBlocked(maze[x + 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y == 0 || isBlocked(maze[x][y - 1]);
    }

}

Blender3D danke. Ich schaue gleich nach 😉

mihe7 · 16. Dez 2019

Blender3D hat gesagt.:
auch mit einem Like belohnen.

LOL. Ich sag mal Danke aber vielleicht klärt mich mal jemand auf: das habe ich nämlich noch nie so richtig verstanden, was man von Likes/Followern, und was es im Social Media Sumpf noch so alles für Kennzahlen gibt, hat.

Das Feedback

iris_anfänger hat gesagt.:
Jetzt habe ich verstanden

ist für mich wesentlich interessanter (und mehr Arbeit, als auf Like zu klicken). Ich nehme die Likes z. B. her, wenn mir ein Beitrag gefällt, ohne dass ich dazu viel schreiben will.

iris_anfänger · 16. Dez 2019

Blender3D hat gesagt.:

Wenn Du die Problemstellung aufteilst und sprechende Namen vergibst wird alles viel einfacher.

Java:

package maze;

public class MazeChar {
    public final static char WALL = '*';
    public final static char AIM = 'O';
    public final static char MARKED = 'x';
    public final static char FREE = ' ';

    public static boolean navigate(char[][] maze, int x, int y) {
        if (maze[x][y] == AIM)
            return true;
        maze[x][y] = MARKED;
        if (!isRightBlocked(maze, x, y))
            return navigate(maze, x + 1, y);
        if (!isDownBlocked(maze, x, y))
            return navigate(maze, x, y + 1);
        if (!isLeftBlocked(maze, x, y))
            return navigate(maze, x - 1, y);
        if (!isUpBlocked(maze, x, y))
            return navigate(maze, x, y - 1);
        return false;
    }

    public static int getDimX(char[][] maze) {
        return maze.length;
    }

    public static int getDimY(char[][] maze) {
        return maze[0].length;
    }

    public static boolean isBlocked(char c) {
        return c != FREE && c != AIM;
    }

    public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) || isBlocked(maze[x][y + 1]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x == 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) || isBlocked(maze[x + 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y == 0 || isBlocked(maze[x][y - 1]);
    }

}

ich erhalte jedoch: ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10

mihe7 · 16. Dez 2019

Das ist ein kleiner Fehler drin: x+1 >= getDimX(maze) und das gleiche natürlich für y.

Blender3D · 16. Dez 2019

mihe7 hat gesagt.:
Ich sag mal Danke aber vielleicht klärt mich mal jemand auf: das habe ich nämlich noch nie so richtig verstanden, was man von Likes/Followern, und was es im Social Media Sumpf noch so alles für Kennzahlen gibt, hat.

Ich selbst stecke in keinem Social Media Sumpf da ich nicht bei Facebook, Twitter und Co bin. Ausnahme ist WhatsApp. Aber auch nur weil ich bei einem Software Projekt mit anderen Programmieren darüber kommuniziert hatte. Ich halte diese Sozial Media Sache für einen gierigen Zeit Vampier, dem sich die Menschen freiwillig hingeben. Das Anzahl vom Like im Forum erachte ich als Hinweis für einen guten Feedbackgeber. Da ich Dich in dieser Richtung schätze und sich die Hilfesuchende selbst als glücklich wegen Deiner Unterstützung bezeichnet hat, hielt ich meinen Anstoß für angebracht. 😉

mihe7 · 16. Dez 2019

Blender3D hat gesagt.:
Ich selbst stecke in keinem Social Media Sumpf

Wer im Java-Forum sitzt, soll nicht mit Steinen werfen oder so ähnlich 😛

Blender3D · 16. Dez 2019

mihe7 hat gesagt.:
Das ist ein kleiner Fehler drin: x+1 >= getDimX(maze) und das gleiche natürlich für y.

Stimmt.
Würde aber die Korrektur so vorschlagen.

Java:

public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) - 1 || isBlocked(maze[x][y + 1]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) - 1 || isBlocked(maze[x + 1][y]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x <= 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y <= 0 || isBlocked(maze[x][y - 1]);
    }

Blender3D · 16. Dez 2019

mihe7 hat gesagt.:
Wer im Java-Forum sitzt, soll nicht mit Steinen werfen oder so ähnlich 😛

lol🙂

mihe7 · 16. Dez 2019

Blender3D hat gesagt.:
Würde aber die Korrektur so vorschlagen.

Tatsächlich würde ich das auch so schreiben - ich dachte nur, dass es für das Verständnis erstmal besser ist, wenn man vorne genauso testet, was hinten ggf. schiefgeht:

Java:

if (x+1 ...) maze[x+1][y]

EDIT: wobei das bei Deiner Methode eh nicht mehr direkt der Fall ist 🙂

iris_anfänger · 16. Dez 2019

Blender3D hat gesagt.:

Stimmt.
Würde aber die Korrektur so vorschlagen.

Java:

public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) - 1 || isBlocked(maze[x][y + 1]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) - 1 || isBlocked(maze[x + 1][y]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x <= 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y <= 0 || isBlocked(maze[x][y - 1]);
    }

Funktioniert, aber nicht ganz richtig: wenn kein ausgang auf erste "Route" gibt, z.B. hier:

Code:

            char[][] maze =      {{'X','X','X','X','X','X','X','X','X','X'},
                                    {'X','X','X','X','X','X','X','X','X','X'},
                                    {'X',' ',' ',' ','X',' ',' ',' ','X','X'},
                                    {'X','X','X',' ','X',' ','X',' ','X','X'},
                                    {'X','X','X',' ',' ',' ','X',' ','X','X'},
                                    {'X','X','X','X',' ',' ','X',' ','X','X'},
                                    {'X','X','X','X',' ','X','X',' ','X','X'},
                                    {'X','X','X','X',' ','X','X',' ','X','X'},
                                    {'X','X','X','X','X','X','X',' ','X','X'},
                                     {'X','X','X','X','X','X','X',' ','X','X'}};

Blender3D · 16. Dez 2019

iris_anfänger hat gesagt.:
Funktioniert, aber nicht ganz richtig: wenn kein ausgang auf erste "Route" gibt, z.B. hier:

Sorry da war ein schwerer Fehler drin. Habe Deinen Code nur refactored ohne zu testen.
Der Fehler liegt am Durchreichen des Ergebnisses mit return.
Hier die verbesserte getestete Variante.
PS. Verwende für die Mauern * und für das Ziel O.

Java:

char[][] maze = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' },
            { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, { '*', ' ', ' ', ' ', '*', ' ', ' ', ' ', '*', '*' },
            { '*', '*', '*', ' ', '*', ' ', '*', ' ', '*', '*' }, { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' },
            { '*', '*', '*', '*', ' ', ' ', '*', ' ', '*', '*' }, { '*', '*', '*', '*', ' ', '*', '*', ' ', '*', '*' },
            { '*', '*', '*', '*', ' ', '*', '*', 'O', '*', '*' }, { '*', '*', '*', '*', '*', '*', '*', ' ', '*', '*' },
            { '*', '*', '*', '*', '*', '*', '*', ' ', '*', '*' } };

Java:

public class MazeChar {
    public final static char WALL = '*';
    public final static char AIM = 'O';
    public final static char MARKED = 'x';
    public final static char FREE = ' ';

    public static boolean navigate(char[][] maze, int x, int y) {
        if (maze[x][y] == AIM)
            return true;
        boolean result = false;
        maze[x][y] = MARKED;
        if (!isRightBlocked(maze, x, y))
            result = navigate(maze, x + 1, y);
        if (!isDownBlocked(maze, x, y))
            result = navigate(maze, x, y + 1);
        if (!isLeftBlocked(maze, x, y))
            result = navigate(maze, x - 1, y);
        if (!isUpBlocked(maze, x, y))
            result = navigate(maze, x, y - 1);
        return result;
    }

    public static int getDimX(char[][] maze) {
        return maze.length;
    }

    public static int getDimY(char[][] maze) {
        return maze[0].length;
    }

    public static boolean isBlocked(char c) {
        return c != FREE && c != AIM;
    }

    public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) - 1 || isBlocked(maze[x][y + 1]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) - 1 || isBlocked(maze[x + 1][y]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x <= 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y <= 0 || isBlocked(maze[x][y - 1]);
    }

}

Blender3D · 16. Dez 2019

Blender3D hat gesagt.:
Hier die verbesserte getestete Variante.

Nicht wirklich ehre verschlechtbessert.

Hier jetzt hoffentlich die Richtige Lösung.

Java:

public class MazeChar {
    public final static char WALL = '*';
    public final static char AIM = 'O';
    public final static char MARKED = 'x';
    public final static char FREE = ' ';

    public static boolean navigate(char[][] maze, int x, int y) {
        if (maze[x][y] == AIM)
            return true;
        maze[x][y] = MARKED;
        if (!isRightBlocked(maze, x, y) && navigate(maze, x + 1, y))
            return true;
        if (!isDownBlocked(maze, x, y) && navigate(maze, x, y + 1))
            return true;
        if (!isLeftBlocked(maze, x, y) && navigate(maze, x - 1, y))
            return true;
        if (!isUpBlocked(maze, x, y) && navigate(maze, x, y - 1))
            return true;
        return false;
    }

    public static int getDimX(char[][] maze) {
        return maze.length;
    }

    public static int getDimY(char[][] maze) {
        return maze[0].length;
    }

    public static boolean isBlocked(char c) {
        return c != FREE && c != AIM;
    }

    public static boolean isDownBlocked(char[][] maze, int x, int y) {
        return y >= getDimY(maze) - 1 || isBlocked(maze[x][y + 1]);
    }

    public static boolean isRightBlocked(char[][] maze, int x, int y) {
        return x >= getDimX(maze) - 1 || isBlocked(maze[x + 1][y]);
    }

    public static boolean isLeftBlocked(char[][] maze, int x, int y) {
        return x <= 0 || isBlocked(maze[x - 1][y]);
    }

    public static boolean isUpBlocked(char[][] maze, int x, int y) {
        return y <= 0 || isBlocked(maze[x][y - 1]);
    }

}

An einem Beispiel erklärt.

Java:

     if (!isRightBlocked(maze, x, y) && navigate(maze, x + 1, y))

            return true;

Falls die Richtung nach rechts nicht blockiert ist und man in diese Richtung zum Ziel navigieren kann gib wahr zurück.
Andernfalls teste an dieser Position die andern Richtungen.

Labyrinth auf der Basis eines rekursiven Algorithmus

Mitglied

Top Contributor

Mitglied

Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

Top Contributor

Top Contributor

Mitglied

Top Contributor

Mitglied

Top Contributor

Mitglied

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Top Contributor

Mitglied

Top Contributor

Top Contributor

Ähnliche Themen