nicht angemeldet
Hallo kai,
Das Problem scheint mir zu sein, dass Dein Graph, auf dem Du Suchst, unnötig groß ist.
Dein Startpunkt A ist z.B. eingeschlossen von Wasser und es gibt nur an einer Stelle, um weiter zu kommen. Die Frage ist nur, wie findet man diese.
Meine Überlegung ist nun folgende:
Es gibt erstmal zwei Möglichkeiten:
1. Das Ziel ist auf geradem Weg erreichbar, kann also vom Startpunkt aus "gesehen" werden. In dem Fall ist diese Sichtlinie bereits die Lösung.
2. Es liegt ein Hindernis dazwischen. In diesem Fall kannst Du rechts oder links vorbei, es ist also absolut sinnlos, alle Wege dazwischen überhaupt in Betracht zu ziehen, was Dein Algorithmus bislang aber tut.
Ich würde nun versuchen, nicht auf dem Graph der Kartenfelder zu rechnen, sondern immer von einem Knoten ausgehend zu prüfen, ob das Ziel schon direkt erreichbar ist und wenn nicht, als nächste Knoten nur die Felder betrachten, die an sichtbaren Ecken von Hindernissen liegen.
Ersteres ist einfach. Man prüft einfach den direkten Weg zum Ziel.
Wenn man nun auf ein Hindernis stößt, kann man diesem entlang laufen bis zu einem rechten und linken Eckpunkt. (Eckpunkte erkennt man daran, dass man nicht weiter nach rechts (bzw. links) gehen kann)
Wenn man nun so einen Eckpunkt gefunden hat, muss man wieder den direkten Weg vom aktuellen Startpunkt aus überprüfen. Ist diesr Weg frei, hat man einen Eckpunkt gefunden und man kann an diesem in Sichtrichtung weiter das nächste Hindernis suchen. Liegt ein anderes Hindernis davor, ist der Eckpunkt nicht sichtbar und die Eckpunkte des Hindernisses davor müssen gesucht werden.
Das zu programmieren dürfte etwas aufwendig sein. Außerdem muss man sich noch überlegen, wie groß Ecken sein sollen, damit man sie als solche erkennt. Man könnte hier mehrere Felder gemeinsam betrachten, um nicht schon kleine, unbedeutende Wellen der Ränder von Hindernissen als Eckpunkte zu erkennen.
Außerdem sollte man wohl nicht alle sichtbaren Ecken für einen Ausgangspunkt sofort bestimmen, sondern immer nur so weit nach Ecken suchen, dass man die Ecke findet, die anhand der Heuristik am besten ist.
Der Algorithmus wird dann nach wie vor zuerst in die lila Bereiche hineinlaufen, aber er wird sehr viel weniger Knoten betrachten müssen, um festzustellen, dass es keinen Weg gibt.
Grüße
Daniel