---

Geschrieben von SirSteffiMiles am 12.12.2003 um 08:34:

  Labyrinth - Backtracking

Haben die Aufgabe ein LAbyrinth zu programmieren, aus dem eine Maus herausfinden soll...
Naja, da ich absolut kein Plan von gar nichts habe, hab ich schon das erste Prob beim einfachen erstellen des LAbyrinths mit einem StringGrid.
Kann mir jemand helfen??

---

Geschrieben von CDW am 12.12.2003 um 18:00:

 

am einfachsten wäre es mit Rekursion zu realisieren (wenn ich dein Begriff "backtracking" richtig verstehe... musst du denn auch die Maus progen oder solls einfach ein Labyrint sein, (nach zufallsprinzip erstellt) ?.
Dann:

Zitat:

LAbyrinths mit einem StringGrid.

Delphi ist zwar nicht so mein Ding, aber als Tipp: immer die Oberfläche(GUI) vom eigentlichen Programm trennen. Ich würde das vielleicht so realisieren:

ein zweifaches Array:

Labarray: array[1..MAX_FELDER, 1..MAX_FELDER] of boolean;

so und dann sagst du: true=wand, false=keine Wand;
ich weiß jetzt nicht ob dein Programm den Labyrinth erstellt oder du/user...
aber Labyrintzeichnen wäre dann auch kein großes problem: einfach dann für jedes "true" einen strich zeichnen (mit einer forschleife dein Array durchlaufen)
Wie du es zeichnest, bleibt dir überlassen... man kann (wenn ich mich recht an delphi erinnere) doch einfach eine Fläche zum zeichnen reservieren und bilder über bild.bla.left:=bla und bild.bla.top:=bla plazieren. Eine primitive Zeichnung wäre dann mit Punkten oder Srichen, wo dann jeder Pixel einen Wert des Arrays darstellt (sieht etwas klein aus)

PS: hatte zwar eine Woche Delphieinführung in den Projekttagen, aber die Rechner waren einfach zu neu (halbes Jahr Info als Theorie vorher, weil die Rechner net da waren ), man sagte uns dass das Netzwerk net stabil läuft, also mussten wir es ja austesten (ab dem zweiten Projekttag - UT-Massenspiele -Härtetest bestanden )

---

Geschrieben von Black Star am 12.12.2003 um 18:06:

 

Ein boolean-array reicht nicht, wenn ich mir das richtig ueberlege.
Du brauchst fuer jede Zelle mindestens 4 Zustaende, besser 8. Und zwar mindestens untere Wand da/nicht da und rechte Wand da/nicht da.
Auf diese Weise laesst sich das Labyrinth beschreiben. Ein wesentlich groesseres Problem ist es ein sinnvolles Labyrinth zu generieren.

Die Sache mit der Maus ist dann in der Tat sehr einfach via Rekursion zu loesen, indem du die Maus von jeder Zelle aus in jede moegliche Richtung gehen laesst, und dann wieder und wieder, bis entweder eine sackgasse erreicht ist, oder du den Weg gefunden hast.

---

Geschrieben von CDW am 12.12.2003 um 18:22:

 

@blackstar: ich meinte damit: True=Block, FALSE=kein Block

Zitat:

.................... ........... .... ... ... ............... ........ ..... .... . .. ... ........ .....................

lässt sich etwas schlecht darsellen, aber im Prinzip einfacher als 8zustände zu verwalten .
Und hier ein einfacher Wegfindealgo:

gehe_grade_aus;
wenn_abzweigung dann: Merke Stelle, gehe nach rechts
wenn_wieder_ an_der_selben_stelle_raus dann biege NICHT ab, sondern gehe weiter.
Wenn_sack_gasse_dann_drehe_um;

usw.
erinndert mich irgendwie an Nicki

---

Geschrieben von Black Star am 12.12.2003 um 18:35:

 

^^ok wenn das Labyrinth aus Bloecken oder Weg, statt aus Waenden besteht, ist das echt einfacher, aber dein Algorithmus ist ja jetzt iterativ oder?

Da coded man sich bestimmt einen bloeden und rastet 75mal aus, weil dauernd Bloedsinn rauskommt.

Ich wuerd das ganz radikal per Rekursion machen, wo bei man an die Funktion uebergibt, wo man gerade steht, wo man herkommt, und welchen Weg man bis dahin hinter sich hat (von mir aus auch als String mit Feld-indizes (nur fuer die Ausgabe des Endergebnisses))
Dann macht man ne Schleife, die die Richtungen durchlaueft und fuer den Fall, dass da ein Weg ist, ruft die Funktion sich selbst wieder auf.
Die Abbruchbedingung ist 1) Sackgasse, oder 2) Ziel. Ausserdem muss man in dem Weg-String checken, ob man da schon mal gewesen ist, weil man sonst im Kreis laeuft, und dir die Rekursion um die Ohren fliegt.

Mit der Rekursion laesst sich das bestimmt elegant in 15-20 (max 30) Zeilen loesen.
Iterativ waere man vielleicht tagelang beschaeftigt und sehr frustriert.

[EDIT]
Wobei ich zugeben muss, dass das quasi geschummelt ist.
Die Maus "teilt" sich an jeder Gabelung und "stirbt", wenn sie in einer Sackgasse ist, oder ihren alten Weg kreuzt.
Aber das ist die schnellste Methode den richtigen Weg zu finden.