[Kirgo]

Langsam fängt Rekursion an zu nerfen.


Aufgabe ist es ein vorgegebenes Labyrinth zu erbauen.
Dann es in boolean umzuwandeln wobei die Wände(*) false sind und Gänge(_) true sind.

Das hat auch geklappt, habe auch eine möglichkeit eingebaut das Labyrinth ausgeben zu lassen.

Jetzt müssen wir mit Rekursion durch das Labyrinth durchgehen und den AUsgang finden.
Aber mein Programm gibt immer nur true aus, obwohl er auch false ausgeben müsste (habe den Ausgang blockiert und nochmal probiert.

public class Labyrinth {
	
	// Methode erzeugt ein Labyrinth
	private static boolean[][] createLab(int n){
		char[][]lab=new char[n+1][n+1];
		return fillLab(n, lab);
	}
	
	// Labyrinth wird mit Zeichen gefüllt
	private static boolean[][] fillLab(int n, char[][]lab){
		for (int i=0;i<9;i++){
			for (int k=0;k<9;k++){
				if ((i==0)||(i==8)||(k==0)||(k==8)||(i==2&&(k==1||k==2||k==4||k==6||k==7))||(i==3&&(k==2||k==4))||(i==4&&(k==2||k==3||k==4||k==5||k==6))||(i==6&&(k==2||k==3||k==4||k==6||k==7))||(i==7&&k==4)){
					lab[i][k]='*';
				}
				else{
					lab[i][k]='_';
				}
			}
		}
		lab[1][1]='E';
		lab [n-1][n-1]='A';
		
//Optionale Ausgabe des Labyriths
//		for (int o=0;o<9;o++){
//			for(int p=0;p<9;p++){
//				System.out.print(lab[o][p]);
//				if (p==8)
//					System.out.println();
//			}
//		}
		return booleanLab(lab);
	}

	
	// Zeichen Labyrinth wird durch ein Boolean Labyrinth ersetzt
	private static boolean[][] booleanLab(char[][]lab){
		boolean[][]blab=new boolean[9][9];
		for (int i=0;i<9;i++){
			for (int k=0;k<9;k++){
				if (lab[i][k]=='*'){
					blab[i][k]=false;
				}else{
					blab[i][k]=true;
				}
			}
		}
		return blab;
	}
	
	
	private static boolean findExit(boolean[][]lab, int inI, int inK, int exitI, int exitK){
		int right = inK+1;
		int left = inK-1;
		int down = inI+1;
		int up = inI-1;
		
		if (lab[inI][right]){
			if (lab[inI][right]==lab[exitI][exitK])
				return true;
			else
				findExit(lab,inI,right,exitI,exitK);
		}
		if (lab[inI][left]){
			if (lab[inI][left]==lab[exitI][exitK])
				return true;
			else
				findExit(lab,inI,left,exitI,exitK);
		}
		if (lab[down][inK]){
			if (lab[down][inK]==lab[exitI][exitK])
				return true;
			else
				findExit(lab,down,inK,exitI,exitK);
		}
		if (lab[up][inK]){
			if (lab[up][inK]==lab[exitI][exitK])
				return true;
			else
				findExit(lab,up,inK,exitI,exitK);
		}
		return false;
	}
	
	public static void main(String []args){
		System.out.print(findExit(createLab(8),1,1,7,7));

	}
}

[jabu]

Langsam fängt Rekursion an zu nerfen.

Nicht vorschnell nerven lassen. So schlecht sieht das nämlich nicht aus!

Aber mein Programm gibt immer nur 'true' aus, obwohl er auch 'false' ausgeben müsste

Es sollte an diesem - gar nicht so seltenen - Missgeschick liegen (welches sich in jedem der vier if-Zweige wiederholt):

if (lab[inI][right]){
	if (lab[inI][right]==lab[exitI][exitK]) // ergibt: if (true==true)
		return true;
	else
		findExit(lab,inI,right,exitI,exitK);
}
if (lab[inI][left]){
...

Dieser Vergleich (rot markiert) bezieht sich auf den jeweiligen Wert, welcher mit dem Operator [] (bzw. hier [][]) zugreifbar gemacht wird. Der Wert ist also keine Identität in dem Sinne, dass man etwa ein bestimmtes Objekt erhielte, welches sich vergleichen ließe. Es handelt sich um den an der Position [n][m] gespeicherten Wert, welcher hier entweder false oder true ist (in diesem Zweig immer beide Werte 'true'). Du könntest einfach die Array-Indices vergleichen, falls die Aufgabe so gemeint ist.

Selbst wenn augenscheinlich alles läuft, so wüsstest du immer noch nicht, ob der Algorithmus wirklich dem Pfad folgt. Um das zu überprüfen, würde ich die Ausgabe noch einmal zusätzlich direkt aus der Rekursion heraus erfolgen lassen.


Du solltest dich aber nicht wundern, wenn nach der Korrektur trotzdem Blödsinn herauskommt:

• Der Rückweg funktioniert ebenfalls und zwar mit Priorität nach rechts oder nach unten, was, je nach Aufbau des Labyrinths, eine Endlosschleife ergeben kann, und zwar mit Hin- und Herspringen an der rechten Wand (Problem gelb markiert). Mit einer unteren Wand verhält es sich ebenso, wenn nur die Position darüber frei ist.
• Was ein Kindknoten an seinen Elternknoten per return zurückgibt, wird verworfen. Alle rekursiven Pfade geben 'false' zurück.
• Nachdem der Ausgang gefunden wurde, geht es aufwärts zum Elternknoten, was gut und richtig ist. Aber auch die weiteren Äste werden durchlaufen. Dieses kann erwünscht sein oder eben nicht.

Fertige Lösungen möchte ich nicht verraten, weil man solche Probleme wenigstens einmal selbst durchmessen haben sollte. Du hättest jetzt mindestens vier Probleme zu bedenken, also:

1. Wie erkenne ich, ob der Ausgang erreicht ist (steht dort oben eigentlich schon)?
2. Wie verhindere ich, dass die Rekursion die vorherige Position gegenüber der nächsten freien Position bevorzugt (Oszillation/Endlosschleife verhindern)?
3. Wie bekomme ich im Erfolgsfall den Rückgabewert auch aus verschachtelten Ebenen (Kindkoten) übergeben?
4. Was soll nach der jeweiligen Rückkehr zum Elternknoten geschehen (kann sich mit der Beantwortung der letzten Frage implizit erledigen, muss aber nicht, je nach Aufgabenstellung bzw. Anforderungen)?

Selbst kompiliert habe ich das aber nicht, ist also nur aus der Hüfte geschossen.