In echt würde ich bei einem eindeutigen Labyrinth, also mit genau einem Weg, einfach mit der rechten Hand immer an der Wand entlang laufen. Das habe ich vor Jahrzehnten auch mal programmiert.
Die möglichen Algorithmen unterscheiden sich gar nicht so sehr danach, ob man den kürzesten Weg finden will. Und: Es gibt massenhaft verschiedene davon.
Manche können keine "Rundgänge" (sondern jede Verzweigung führt entweder in eine Sackgasse oder ans Ziel), viele können keine Gänge, die breiter als ein "Kästchen" sind und manche gehen davon aus, dass sie das "ganze Labyrinth auf einmal" sehen können (was möglicherweise als "Cheat" betrachtet werden kann) weil sie Sackgassen suchen und dann "rückwärts" auffüllen, bis nur noch die Wege, die zum Ziel führen, übrig bleiben.
Der einfachste dürfte wohl das "Rechte-Hand-Verfahren" sein: Geh' nur irgendwohin, wo "in Blickrichtung rechts von dir" eine Wand ist (Das biegt im Prinzip an Abzweigungen einfach "rechts ab"). Hat dein Labyrinth aber Rundgänge, läßt es sich damit fast sicher nicht lösen.
Der wohl am häufigsten verwendete Algorithmus ist "rekursives Backtracking" (Pseudocode):
bool solveMaze(Maze & maze, Point start) {
if (maze.isOutside(start))
return true;
if (maze.isMarked(start))
return false;
maze.markSquare(start);
for (Direction dir = NORTH; dir <= WEST; dir++) {
if (!maze.wallExists(start, dir)) {
if (solveMaze(maze, adjacentPoint(start, dir))) {
return true;
}
}
}
maze.unmarkSquare(start);
return false;
}Das löst auch Labyrinthe mit "im Kreis-laufen", die die Rechte-Hand-Lösung nicht lösen kann. Kann aber je nach Größe ziemlich viel Stack-Space brauchen und stößt bei Labyrinthen, die breitere Gänge oder größere Freiflächen haben, auf Probleme (weil es sich "selber den Weg abschneiden" kann)
Beliebige Wegfindungsprobleme z.B. einfach um Hindernisse herum, aber auch Labyrinthe, löst man heutzutage typisch mit dem "A*-Algorithmus", der kann auch den kürzesten Weg finden.
Hi,
Grundlagen:
https://en.wikipedia.org/wiki/A*_search_algorithm
https://en.wikipedia.org/wiki/Maze-solving_algorithm
Rosettacode wurde ja schon empfohlen. 
Have fun,
Maurice
Ein grundsätzliches Problem hier ist aber, wie ein Labyrinth als Datenstruktur dem Programm zur Verfügung gestellt wird.
Ein grundsätzliches Problem hier ist aber, wie ein Labyrinth als Datenstruktur dem Programm zur Verfügung gestellt wird.
Der Einfachheit halber am besten mit einem zweidimensionalen Array. Eine "1" ist eine Wand, eine "0" ein Weg. Das hat auch den Vorteil, dass man in der Struktur schön rumkritzeln kann (z.B. mit einer "3"), um schon begangene Wege zu markieren.
Schönes Beispiel in C++ gibt's hier
D.h. aber, dass jede "Zelle" 4 Elemente des Arrays nutzt und dass man ungültige Daten eingeben kann, wie z.B. ein Weg versetzt sich um eine Zeile oder Spalte.
Als Eingabeformat wäre es aber schön, da es auch als .BMP Bild (unkomprimiert) darstellbar ist
bei "Pascal" und "Labyrinth" fällt mir immer sofort "Niki" ein: https://de.wikipedia.org/wiki/Niki_%E2%80%93_der_Roboter
Irgendwann in den 80er war Niki Teil des Informatikunterrichts und der Einstieg in Turbo Pascal - mit IBM XT und DOS.
Niki hat den Ausgang aus dem Labyrinth immer gefunden
Schöne Erinnerung
Sun's "xmaze" ist so ein Standarddemo gewesen. Die Sourcecodes dafür gibt es bestimmt - find nur gerade nix.
Mal abgesehen dass der "C" Beispielcode auf Rosettacode natürlich kein "C" ist (auch wenn es da so beschrieben ist), sondern "C++", hat wohl Turbo C++ 1.01 auch große Probleme mit der Sourcecode-Datei.
Irgendwas stört das "inline" und das "static" Statement. Wahrscheinlich ist der Beispielquelltext (siehe Anhang hier) nur mit Gnu C(++) kompilierbar, aber dann sollten diese Banausen auf Rosettacode das auch hinschreiben.
Die wchar_t glyph[] Zuweisung muss für MS-DOS (weil kein Unicode) sowieso noch angepasst werden, schaut man sich das Textfile unter Windows 10 an, sieht das perfekt aus, nimmt man MS-DOS, sieht man nur Hyroglyphen, für die Syntax-Prüfung zur Compilationszeit sollte das aber keine Rolle spielen.
Schade, wäre schön wenn's unter Turbo C++ (oder Borland C++) auch lauffähig gewesen wäre 
In echt würde ich bei einem eindeutigen Labyrinth, also mit genau einem Weg, einfach mit der rechten Hand immer an der Wand entlang laufen. Das habe ich vor Jahrzehnten auch mal programmiert.
Genau so kenne ich das. Ich habe das gerade vor ein paar Monaten mal programmiert. Eigentlich ging es mir um die Erzeugung eines Labyrinths, aber dann habe auch gleich noch den Solver programmiert. Ist ja nach der Rechte-Hand-Regel eher trivial.
Ich habe das mal als Video angehängt. Dass da rote Punkte stehen bleiben, ist keine Absicht. Ich war nur zu faul, die wegzuoptimieren.
Leider darf man kein mp4-Anhängen. Deswegen musste ich es zippen.
Wirklich schönes Video. Muss aber das weiterhin bspw. als C Quellcode haben....
Damit kann ich leider nicht dienen und der C#-Code mit Windows-GUI ist eher aufgebläht und unübersichtlich. 
Der Rosetta-Code läuft mit den Änderungen bzgl. der Grafik-Zeichen, dem Auskommentieren der INLINE statements, dem Verändern der STATIC Anweisung, dem Setzen von DOUBLE_SPACE auf 0, dem Hinzufügen der "randomize" Funktion und einer Ausgabe am Schluß zur Weglänge eigentlich ganz prima unter DOS:
Im angehängten ZIP hier befindet nicht nur der modifizierte Source-Code sondern auch die kompilierte, ausführbare Datei (man braucht ANSI.SYS !).
Ich hab's mit Turbo C++ 3.0 geändert, denke man kann es auch mit der Turbo C++ 1.01 kompilieren.
Auch die Ausgabe ist relativ elegant, da man alles in einem Array vorab berechnet/setzt, und dann komplett Wände des Labyrinths und gefundener Weg in einem ausgibt. Könnte man natürlich auch so ändern, dass der Weg zum Schluß erst gezeichnet wird.
