Maze Solving Algorithmus?
Hi,
ich will mehrere Algorithmen implementieren, womit ich ein Maze lösen kann. Dabei gehts mir um Geschwindigkeit. Das gesamte Maze ist schon bekannt, also die "Maus" kann von jedem Punkt erfahren ob es eine Wand, oder ein Weg ist.
Derzeit habe ich den Wavepropagation, den Wallfollower und einen Kombi algorithmus implementiert. Der Kombi algorithmus entstand, nachdem ich Rekursion versucht hatte, bis ich gemerkt habe, dass das ja garnicht in C# geht xD
Dann hab ich per While loop einfach immer geguckt welche Richtungen sind möglich und dann halt random eine Richtung gewählt. Wenns deadend ist, halt wieder zurück, bis eine unbesichtigte Zelle kommt. Vllt habt ihr ja eine Idee wie der heißt.
Für mich neuling kling der Wavepropagation algorithmus derzeit am optimalsten, denn er hört auf, sobald das ziel gefunden ist.
Man könnte evtl. den noch Optimieren, indem man an an jeder Kreuzung ein Node setzt.
Der Djiktra klingt für mich als Neuling wie ähnlich des Wavepropagation Algorithmus, zumindest wenn man nicht die Map in nodes (bei jeder Kreuzung) plaziert.
Gibts einen viel schnelleren?
Die Map ist so um die 10k x 10k bis 15k x15k
Evtl auch mehr, wenn ich diese nicht painten würde, sondern nur als byte array lasse. Dauert aber so schon lang genug xD
Generiert wird dieses per Binary Tree derzeit. Dieser ist wenigstens Ultra schnell. Prims algorithmus ist mir zu langsam für diese Größenordnung.
3 Antworten
Schau dir mal den A* Algorithmus an, ich denke der könnte dir weiterhelfen :)
Sollte ich den noch optimieren? Also an jeder kreuzung ein Node, oder so lassen?
Das ist dir überlassen, wenn du mehr Geschwindigkeit brauchst/dich daran versuchen willst, dann auf geht's :D
Da macht man auf die freien Koordinaten im Labyrinth einen Flood-Fill, bei dem man die Ausbreitungsgeschwindigkeit von den einzelnen gefluteten Koordinaten über eine prioritätsgerecht umsortierte Prozeßwarteschlange ausbalanciert. Der Flood-Fill soll sich übrigens nicht wieder an eine bereits besuchte Koordinate ausbreiten. Kam der Flood-Fill ans Ziel, markiert man den Weg der Aufrufe über die noch bestehenden Einträge mit Vorgänger-IDs der Prozeßwarteschlange rückwärts. Das ist zwar nicht das laufzeitschnellste, aber dafür das problemumfassendste Verfahren. Es gehen sogar mehrere Pfade direkt der Länge nach.
bis ich gemerkt habe, dass das ja garnicht in C# geht xD
Hä? Natürlich geht Rekursion mit C#. Genauso wie in jeder anderen Sprache auch.
Dann hab ich per While loop einfach immer geguckt welche Richtungen sind möglich und dann halt random eine Richtung gewählt. Wenns deadend ist, halt wieder zurück, bis eine unbesichtigte Zelle kommt. Vllt habt ihr ja eine Idee wie der heißt.
Sowas nennt sich BackTracking-Algorithmus.
Dann hast Du sie falsch programmiert (= ohne Abbruchkriterium). Das ist kein Markenzeichen von C#, sondern von einer nicht endenden Rekursion und kann Dir in jeder Programmiersprache geschehen.
Nein. Es funktionierte, solange die Distanz sehr gering war. Ging es aber um längere Wege, dann brach er ab.
Laut Recherche optimiert der Compiler nicht für tail recursion.
Nun, natürlich kommt es auf die Rekursionstiefe an dabei. Aber Du könntest Dir mit Trampolining helfen. Es ging mir nur um die generelle Behauptung, dass Rekursion in C# nicht möglich ist. Das stimmt nämlich nicht. Dass sie vielleicht in Deinem Fall nicht die zielführende Lösung ist, steht ja auf einem anderen Zettel.
Jeder rekursive Algorithmus kann aber in einen iterativen überführt werden - und das hast Du ja getan, somit: Kein Problem vorhanden.
Ja klar, dass Rekursion möglich ist ist mir klar. Aber bei 10k x 10k kannst dir ja die tiefe dabei ausdenken 😅
Mit dem wallfollower hab ich so um die 90mio steps und mit wave propagation 11k steps (der path jetzt)
Der klingt gut :D