|
|
|
|
Labyrinth - Backtracking |
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
|
|
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
)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von CDW: 12.12.2003 18:04.
|
|
12.12.2003 18:00 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
|
|
@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
|
|
12.12.2003 18:22 |
|
|
Black Star
Der Pate [Admin]
Dabei seit: 11.12.2001
Beiträge: 2.282
Herkunft: /dev/stderr
|
|
^^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.
__________________
vescere bracis meis
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Black Star: 12.12.2003 18:42.
|
|
12.12.2003 18:35 |
|
|
|
|
|
|