JAVA

trémaux’ methode

Die Trémaus' Methode
>Algorithmus zum Lösen eines Labyrinths

-Labyrinth wird durch zweidimensionales Array dargestellt
-Mit einem sogenannten Agenten begeht man das Labyrinth, dieser schaut immer in die Richtung in die man gerade geht(wo sich Links, Rechts, u.s.w. befinden ist also von ihm abhänging)
-Es gibt Wege und Plätze(Kreuzungen)
	-Wege bestehen aus zwei Wänden und zwei angrenzenden freien Feldern(der von dem man kam und der zu dem man geht)
    	-man kann sie einfach entlang gehen
    -Plätze bestehen aus zumindest drei freien angrenzenden Feldern
    	-betrete keinen Weg mit zwei Markierungen
    	-wenn man an einen Platz kommt markiert man den Weg hinter sich den man gekommen ist
        -man scannt die angrenzenden Felder und überprüft ob es schon markierungen gibt
        	-gibt es keine sucht mant sich eine Richtung aus und markiert die Richtung in die man geht
            -ist mindestens eine Richtung schon markiert kehrt man um sofern hinter einem nur eine Markierung ist und markiert den weg beim zurück gehen ebenso
            -sind hinter einem schon zwei Markierungen geht man den Weg mit den wenigsten Markierungen (0 oder 1) und markiert diesen ebenso
            -kommt man an einem Platz an der in jeder Richtung zwei Markierungen oder eine Wand hat, hat man das ganze Labyrinth abgesucht
            
-um die Koordinaten also die Position des Agenten bestimmen und änder zu können, benötigt man ein Richtungssystem unabhängig von ihm
	-hier bieten sich die Himmelsrichtungen an(Nord, Ost, Süd, West)
    		N
           ###
          W# #O
           ###
            S
    -Um die Himmelsrichtungen anpassen zu können müssen wir ihnen Werte geben und diese entsprechend ändern
    z.B.: Labyrinth[y][x]
    	  Nord = 1; Ost = 2; Süd = 3; West = 4;
          startRichtung = 3;
          wenn du rechts gehst: Richtung = Richtung + 1
          wenn du links gehst: Richtung = Richtung - 1
          wenn du geradeaus gehst: Richtung = Richtung 
          wenn du umdrehst: Richtung = Richtung + 2
          	wenn Richtung = 5: Richtung = 1 //wenn man von Süden zu Norden wechseln will
            wenn Richtung = 5: Richtung = 2 //wenn man von Westen zu Osten wechseln will
            
          wenn Richtung = 1: ändereRichtung: y + 1 (geh ein Feld Nord)
          wenn Richtung = 2: ändereRichtung: x + 1 (geh ein Feld Ost)
          wenn Richtung = 3: ändereRichtung: y - 1 (geh ein Feld Süd)
          wenn Richtung = 4: ändereRichtung: y + 1 (geh ein Feld West)
          
//Wenn ich helfen konnte würde ich mich über eine Donation freuen