Rekursion stoppt an der falschen Stelle

[asyoulikeit]

Moin miteinander,
ich habe folgendes Problem:
Die Aufgabe lautet, ein Labyrinth zu lösen. Das Labyrinth ist ein 2-D Array, wobei jedes Feld entweder eine Mauer oder ein Weg ist. Das Lösungsprinzip ist mir klar: Ich überprüfe vom Startfeld aus die angrenzenden Felder ob Mauer oder Weg. Den ersten Weg nehme ich und prüfe von da aus von Neuem. Ist das neue Feld ein Randfeld, ist das Labyrinth gelöst. Soweit so gut. Mein Algorithmus tut das auch. Nur sobald er am Rand angekommen ist, macht er weiter :-(. Und besucht alle noch nicht besuchten Felder im Labyrinth und bricht erst ab, wenn er überall war. Hier mein Code zum Lösen des Labyrinths (ich hoffe, der reicht. Das restliche Programm ist ziemlich umfangreich):

    public boolean solve(int x, int y) {
        int aktuellesX = x;
        int aktuellesY = y;

        /* Am Rand angekommen? */
        if (aktuellesX == 0 || aktuellesY == 0 || aktuellesX == this.getXDimension() - 1 || aktuellesY == this.getYDimension() - 1) {
            return true;
        }

        /* Alle Richtungen versuchen */
       
        if (!fields[aktuellesX + 1][aktuellesY].isWall() && !fields[aktuellesX + 1][aktuellesY].isVisited()) {
            fields[aktuellesX + 1][aktuellesY].setVisited(true);
            solve(aktuellesX + 1, aktuellesY);
        }
       
        if (!fields[aktuellesX][aktuellesY + 1].isWall() && !fields[aktuellesX][aktuellesY + 1].isVisited()) {
            fields[aktuellesX][aktuellesY + 1].setVisited(true);
            solve(aktuellesX, aktuellesY + 1);
        }
       
        if (!fields[aktuellesX - 1][aktuellesY].isWall() && !fields[aktuellesX - 1][aktuellesY].isVisited()) {
            fields[aktuellesX - 1][aktuellesY].setVisited(true);
            solve(aktuellesX - 1, aktuellesY);
        }
       
        if (!fields[aktuellesX][aktuellesY - 1].isWall() && !fields[aktuellesX][aktuellesY - 1].isVisited()) {
            fields[aktuellesX][aktuellesY - 1].setVisited(true);
            solve(aktuellesX, aktuellesY - 1);
        }
       
        return false;

    }

 

[JCODA]

Der bisherige Code sieht m.M.n. fehlerfrei aus. Wenn du möchtest schau ich's mir mal insgesamt an. Kannst du dein Projekt als zip-Datei hochladen?

 

[asyoulikeit]

Ich versuch's mal. Der restliche Code ist auch nicht von mir, sondern Vorgabe von der Hochschule. Wir sollten nur die solve() ausprogrammieren.

 

[JCODA]

Okay, ich hatte übersehen, dass die Methode ja etwas zurückliefert. Sobald solve true liefert, sollte man ja nicht weiter die anderen Fälle überprüfen, sondern direkt die Methode verlassen:

Spoiler: Click

public boolean solve(int x, int y) {
        fields[x][y].setVisited(true);
            
        /* Am Rand angekommen? */
        if (x == 0 || y == 0 || x == this.getXDimension() - 1 || y == this.getYDimension() - 1) {
            return true;
        }
        /* Alle Richtungen versuchen */
        if (!fields[x + 1][y].isWall() && !fields[x + 1][y].isVisited()) {
            if(solve(x + 1, y)){
                return true;
            }
        }
        if (!fields[x][y + 1].isWall() && !fields[x][y + 1].isVisited()) {
            if(solve(x, y + 1)){
                return true;
            }
        }

        if (!fields[x - 1][y].isWall() && !fields[x - 1][y].isVisited()) {
            if(solve(x - 1, y)){
                return true;
            }
        }

        if (!fields[x][y - 1].isWall() && !fields[x][y - 1].isVisited()) {
            if(solve(x, y - 1)){
                return true;
            }
        }
        return false;
    }

Achja, ich hab das setvisited(true) an den Anfang der Methode gepackt, dort tut es das gleiche, aber weniger Code 🙂

Hier noch eine Variante mit einer Schleife: (Für manche ist diese nicht so gut lesbar, vermutlich besser nicht abgeben, aber ich finde sie besser 😉 )

Spoiler: Click

public boolean solve(int x, int y) {
        fields[x][y].setVisited(true);

        /* Am Rand angekommen? */
        if (x == 0 || y == 0 || x == this.getXDimension() - 1 || y == this.getYDimension() - 1) {
            return true;
        }
        /* Alle Richtungen versuchen */
        for (int[] direction : new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }) {
            int dx = direction[0];
            int dy = direction[1];
            if (!fields[x + dx][y + dy].isWall() && !fields[x + dx][y + dy].isVisited()) {
                if (solve(x + dx, y + dy)) {
                    return true;
                }
            }
        }

        return false;
    }

 

[asyoulikeit]

Besten Dank, das funktioniert einwandfrei. So was in der Art hatte ich auch ausprobiert, aber wohl an der falschen Stelle 🙂