Labyrinth absuchen

[Discman]

Hallo,

und zwar hab ich als Übungsaufgabe das hier bekommen.

Mittels den Regelsätzen links soll ich den Roboter durch das Labyrinth schicken und er soll alle Diamanten holen, meine Frage ist jetzt wie ich an diese Problemstellung systemmatisch rangehen könnte mit Algorithmen. Bei der Überprüfung der Regelsätze werden sie nämlich auf ein unbekanntes Labyrinth angewendet, welches der Roboter dann natürlich auch bestehen soll. Schwierigkeitsgrad soll ein Labyrinth mit Loops sein.

Ich hoffe mir kann da wer weiterhelfen wie ich an die Sache rangehen soll.

Danke schonmal

lg

disc

[Mephisto81]

hallo,

nettes spiel.

du musst dir einfach überlegen auf welche zustände (sprich kombinationen der versperrten wege) der roboter auf seinem weg treffen könnte und ihm dafür eine regel geben. Diese Regeln kannst du ja auf der linken Seite hinzufügen und entsprechend bearbeiten.

Denkansatz:

WENN links versperrt UND rechts versperrt  DANN gehe geradeaus.

WENN links versperrt UND vorwärts versperrt  DANN gehe rechts.

vielleicht hilft dir das ja schon.

gruß

mep

[kingofbrain]

Servus,

sehr schön kannst Du das rekursiv lösen, haben wir im Studium auch gemacht. Vielleicht bekomme ich es noch zusammen (ist noch vor dem ersten Kaffee).

Du hast irgendeinen Startpunkt und schaust in irgendeine Richtung (Nord, Süd, Ost oder West). Jetzt prüfst Du, ob Du in der Richtung, in die Du schaust, eine Wand ist. Ja: Um 90° drehen und schauen Nein: um eins weitergehen und schauen. Die Funktion / Methode, mit der Du schaust, ob frei ist und Dich drehst, rufst Du einfach beim Betreten eines Feldes auf.

Um Loops mit Endlosschleifen zu vermeiden, merkst Du Dir, wo Du schon warst in einem zweidimensionalen Array mit boolean Werten o.ä.

Ich hoffe, das genügt als Anstoss. Wenn nicht, frag einfach, dann such ich heute abend die Aufgabe nochmal raus und schreib den Algorithmus ein wenig schöner raus.

Peter

[Discman]

Vielen Dank für die schnellen Antworten.

@Mephisto81 das ist schon klar, bei so leichten "Situationen" ist es kein Problem.

Ich steig hauptsächlich bei den Statusmöglichkeiten aus und bei den Nummern.

@kingofbrain

Schon klar wie das circa aussehen soll mit der Methode und von "rekursiv" hab ich auch gehört, vielleicht kannst du den Algorithmus wirklich rausschreiben, schadens kanns mir sicher nicht. Das mit den Endlosschleifen ist auch so eine Sache, glaubst du es reicht da wenn ich einfach mit den Zahlen arbeite, man kann ja eine Zahl an einer Kreuzung auf das Feld "malen". So könnte es sich der Roboter vielleicht auch merken wo er war. Nur was mach ich dann wieder mit diesem Status (grün,blau etc)

lg disc

[kingofbrain]

Stop, Du bist schon weg vom Algorithmus. Den interessiert eine Farbe oder eine Zahl nicht.

Du hast ein zweidimensionales Array mit boolean Werten. Dieses Array hat genauso viele "Spalten" wie Dein Labyrinth horizontale Felder und soviele "Zeilen" wie Dein Labyrinth vertikale Felder. Warst Du auf einem Feld schon mal, schreibst Du ins Array an der Stelle true. Damit kannst Du im nachhinein schauen, ob Du dieses Feld schon besucht hast.

Wegen dem Algorithmus. Ich schau heute abend, ob und wo ich das Teil noch habe.

Peter

[Discman]

naja aber die Frage ist doch wie kann ich das abspeichern? Man kann ja die Regelsätze normal mit der Hand schreiben das geht innerhalb des Expertenmodus vom Labyrinth.

WENN-> DANN

(ggg,grün,0)->(0,nach vorn,blau)

Was jetzt soviel heisst wie WENN nach "links/rechts/geradeaus" ein Gang ist und mein Status "grün" und am Boden steht eine "0" DANN schreibe eine "0", "gehe nach vorn" und ändere deinen Status in "BLAU"

also das Beispiel würde jetzt zeigen wieviel Möglichkeiten ich innerhalb eines Regelsatzes hätte.

Nur das mit "true" haut nicht hin ich und ich könnte wie gesagt nur mittels dieser Zahlen bzw. Stats etwas auf dem/in dem Labyrinth selber abspeichern damit ich beim nächstenmal weiss das ich dort schon war und das ich dann halt den "anderen" Weg gehen sollte.

Ach ich Blick bald nicht mehr durch ^^

lg disc

[kingofbrain]

Ich weiss nicht wirklich, was mir Dein letzter Post sagen sollte.

Du bist doch hier im Bereicht "Algorithmen". Da unterhält man sich über das prinzipielle Vorgehen, nicht über die Umsetzung.

Deine Beschreibung hört sich so an, als hättest Du ein konkretes Labyrinth-Programm vor Dir. Nachdem ich das nicht habe und es bestimmt auch nicht kenne, wäre es praktisch, wieder zurück zum Algorithmus zu kommen. Wie Du das dann im konkreten Fall löst, ist ja erst mal wurscht. Wichtig ist, das Vorgehen zu verstehen. Und dabei sind wir ja gerade.

Peter

[Klotzkopp]

Du bist doch hier im Bereicht "Algorithmen". Da unterhält man sich über das prinzipielle Vorgehen, nicht über die Umsetzung.

Schau dir mal die Webseite an, auf die er verlinkt hat. Die Informationen, die er zur Umsetzung des Algorithmus speichern kann, und der Zugriff darauf sind ziemlich eingeschränkt. Das wirkt sich auf die Vorgehensweise aus.

[Discman]

eben das ist ja mein Problem, aber ich bin schonmal dankbar wenn ich den Algorithmus dafür irgendwie verstehen kann und dann mittels diesen Möglichkeiten die Lösung ausarbeite bzw. den Algorithmus anwende...

soll kein Wunsch nach Umsetzung gewesen sein ich weiss schon wo ich hier bin ^^

[kingofbrain]

Ok, das habe ich übersehen, dass Du den Link am Anfang gepostet hast.

Ich habe das Teil eben mal ausprobiert, aber das Regelwerk ist wirklich sehr eingeschränkt. Hier im Büro habe ich keine Zeit, das genauer nachzuvollziehen, aber das als Denkanstoss:

Die Standards sind ja klar. Wenn es nur einen Weg gibt, nimm ihn. Gibt es mehrere Wege, dann geh einfach den ersten und merk Dir, wohin Du gegangen bist. Für das merken kannst Du die Zahlen benutzen. Du musst halt aufpassen, das Du beim zurückkommen aus der Situation und der Zahl schliessen kannst, wohin Du noch nicht gegangen bist. Das ist in meinen Augen der aufwändigste Teil, aber schon lösbar. Mit den Farben habe ich mich jetzt nicht beschäftigt. Mal schauen, wenn ich heute abend Zeit habe, schau ich mir das Teil ein wenig genauer an.

Peter

[Discman]

naja vorallem "wie" das Regelwerk eingeschränkt worden ist stört mich, wobei die Einschränkung ja nicht so schlimm ist man kann mit dem Expertenmodus auch andere Sachen statt den Zahlen in die Gänge "malen" also man sitzt nicht nur fest auf 0-3 bzw. den paar Farben man kann das eigentlich unendlich ausbauen...nur der Überblick wird dann halt bald versagen. Ich schätze aber, dass es bei diesem Labyrinth schon auch etwas mit den Farben auf dem Hut hat also das nicht nur die Zahlen zum Einsatz kommen, wobei ich mich derzeit auf die Zahlen konzentriere.

lg disc

[kingofbrain]

Servus,

ich habe mir das jetzt ein wenig angeschaut, allerdings nicht bis zum Ende. Ich habe folgende Strategie gewählt, die war recht erfolgreich.

Wenn Du an eine Stelle mit mehreren Möglichkeiten kommst, gehe immer nach rechts. So kommt man immer wieder aus dem Labyrinth raus.

Aber richtig interessant wird es erst danach - das ist mir aber zu mühselig, es komplett zu lösen. Deshalb auch nur meine Überlegungen.

Du musst eine Stelle, an der Du mehrere Möglichkeiten hast, Kennzeichnen (Zahl auf dem Boden). Der Zahlwert könnte was mit der Anzahl Möglichkeiten zu tun haben oder aber mit einem Tip, in welche Richtung es geht. Es sollte - wenn man immer rechts abbiegt, so sein, dass man bei zwei Möglichkeiten wieder umdreht (aus einer kam man, in eine ist man schon gegangen), bei drei Möglichkeiten muss der Zahlwert zwei mal verändert werden. Dann habe ich überlegt, was man mit der Farbkennzeichnung machen kann. Ich denke, damit fängt man Loops. Wie, ist mir noch nicht genau klar, da werden die Möglichkeiten mit der beschränkten Art der Regeldefinition auch sehr schnell sehr viel, da ich für jede Farbmöglichkeit jede Barrieresituation erfassen muss. Aber prinzipiell muss ich bei Kreuzungen, wo ich schon an allen Möglichkeiten entlanggegangen bin, mich farbig markieren, wenn ich wieder daran vorbei komme, damit ich bei einem nochmaligen Auftreffen des Platzes merke, dass ich im Kreis gegangen bin. Allerdings kann ich ja auf einem Weg an mehreren Stellen schon farbig markiert haben, und dann wird es in meinen Augen schwierig. Das war auch der Punkt, an dem ich keine Lust mehr hatte.

Vielleicht hilft es Dir. Wenn Du die Regeldefinition hast, wäre ich sehr interessiert.

Viel Spass dabei!

Peter

[Faustenator]

Ich hab damals im Studium auch mal über so eine Aufgabe nachdenken müssen und hab auch noch meine kleine Dokumentation dafür.

Da es sich dabei um ein Labyrinth mit sechs-eckigen Feldern handelt müsstest Du aber ein wenig umdenken, um nicht zu sagen "vereinfachen".

Schau einfach mal hier!

Vielleicht hilfts ja...

mfg. ...

[Faustenator]

Ansonsten hab ich vergessen mal die beiden Begriffe

"Tiefensuche" und "Breitensuche" zu erwähnen.

Das könnte Dir auch noch helfen falls Du noch kein Ergebniss hast...