Backtracking - Wege aus dem Labyrinth [Source online]

[Flips]

Hi.

Das folgende Projekt ist eine Projektarbeit aus dem Informatikunterricht. :coder:
Die Wahl des Themas war den Schülern freigestellt, es sollte nur ein 2D-Array benutzt werden, also sehr anspruchsvoll :wink:

Das Programm ist nun fertig.
Es dient dazu, den Computer rekursiv einen Weg aus dem Labyrinth suchen zu lassen.
Die genaue Vorgehensweise findet ihr als Anhang.
Was da nicht drin steht ist eine neue Funktion, grau sind die besuchten Felder und gelb der aktuelle Idealweg.

Wollte nur mal von euch wissen, wie ihr das Programm denn so findet und ob es bei euch läuft und ob es evtl. Bugs hat die mir noch nicht aufgefallen sind.
Ich weiß, man könnte noch 1000 Sachen einbauen aber das würde den Rahmen des Projekts sprengen und mein Partner der erst seid nem Jahr Delphi lernt (dabei aber sehr erfolgreich ist) muss das ja auch verstehen. :coder2:

Lg und THX,
Flips

Ps: Sind zwei Beispiellabyrinthe dabei, wenn ihr selbst eins macht dann muss dieses an allen Rändern geschlossen (schwarz sein)

Aktuelle Source ist nun auch dabei :-)

[RavenIV]

Cooles Programm.

Hier aber noch ein paar Anregungen:
- Position des Startpunktes frei wählbar
- Labyrinth per Drag&Drop laden (mit der Maus ein Image auf's Programmfenster ziehen)
- Abbrechen der Suche auf Knopfdruck
- Möglichkeit, dass man Wegstücke sperren kann
- Hilfe-Fenster

/edit:
Am Quellcode hätte ich starkes Interesse...

[Flips]

Hi, danke für dein Feedback :thumb: und für das Lob :-)

Werde deine Wünsche morgen einbaunen, nach der Präsentation (geht im Vortrag ja mehr um die Theorie dahinter).
Sobald das fertig ist stelle ich dann auch den Code frei zur Verfügung.

[Larsi]

Muss auch sagen, großes Lob!!! Mich würde der Quellcode natürlich auch sehr interessieren, besonders das mit dem Speed Ding :) :) :) Es kommt aber wenn man ein Labyrinth lädt was falsch von mir gezeichnet wurde ne zugriffsverletzung nach dem gesagt wird dass es nicht möglich ist sollte vielleicht unterbundne werden.

[STS301]

wow, finde ich wirklich toll, trotzdem würde ich mich auch über den Source sehr freuen :thumb:

toll wäre es auch, wenn man gerauszoomen könnte, weil beim großen Labyrinth ist es ziemlich umständlich.

Timer wäre auch lustig, bei mir leuft zur Zeit das große Labyrinth, 10 minuten und hat erst 1%

[Flips]

Zitat:

Zitat von Larsi

Muss auch sagen, großes Lob!!! Mich würde der Quellcode natürlich auch sehr interessieren, besonders das mit dem Speed Ding :) :) :) Es kommt aber wenn man ein Labyrinth lädt was falsch von mir gezeichnet wurde ne zugriffsverletzung nach dem gesagt wird dass es nicht möglich ist sollte vielleicht unterbundne werden.

Danke :-)
Der Unterschied zwischen Speed-Modus und normalen Modus ist eigentlich nur das er im Normalen Modus immer die Ausgabe aktualisiert, im Speed-Modus nur alle 50.000 Schritte ;-)
Prinzipiell kann der Algorithmus das große Labyrinth in ein paar Sekunden lösen (bzw. in dem Fall anzeigen, dass der Ausgang nicht erreichbar ist)

Zitat:

Zitat von STS301

wow, finde ich wirklich toll, trotzdem würde ich mich auch über den Source sehr freuen Thumbs up!

toll wäre es auch, wenn man gerauszoomen könnte, weil beim großen Labyrinth ist es ziemlich umständlich.

Auch danke :-)
herauszoomen könnte man echt machen, wobei dem natürlich auch grenzen gesetzt sind (1 Pixel pro feld is minimum ;-) ).
Im Source gibts ne Konstante mit der man die Minimalgröße bestimmen kann, wenn man die auf 1 setzt dann sollte das dann wie ein zoom out wirken.

Zitat:

Timer wäre auch lustig, bei mir leuft zur Zeit das große Labyrinth, 10 minuten und hat erst 1%

Entweder du hast den Speed-Modus aus oder dein PC ist nicht sehr schnell^^
achso, die Prozentzahl muss bei erreichen des Ziels nicht 100% sein, sie gibt nur an wieviel prozent der begehbaren flächen schon abgegrast worden sind.


Code kommt direkt morgen mittag :-D

[STS301]

naja, der Speedmode war halt nicht On.

*freu* auf morgen

kann man das auch irgendwie einstellen, dass er nicht immer den selben Weg nimmt?

[geofranz01]

Auch von mir ein großes Lob :thumb: . Echt super!

Was mir noch aufgefallen ist:
-Wenn du das Fenster vergrößerst, sollte das Labyrinth auch größer werden. Und die Parameter-Box sollte rechts ausgerichtet werden.
-evt. noch eine Zoom-Funktion wie erwähnt oder kleine Vorschau (zur Übersicht) wäre cool.

EDIT: BUGS:
-Während dem Resetten und Laden Application.processmessages wäre nicht schlecht. :wink:
-Wenn ich mit dem Maus hoch-scrolle wird die horizontale Richtung immer zurückgesetzt.

Am Quellcode hätte auch ich Interesse :wink:

mfg,
geofranz

[Flips]

Zoom-Funktion ist jetzt eingebaut, Application.ProcessMessages hatte ich mal drin aber habs warum auch immer wieder rausgenommen :gruebel: jedenfalls danke, dass du mich daran noch erinnert hast :thumb:

Zitat:

kann man das auch irgendwie einstellen, dass er nicht immer den selben Weg nimmt?

Jaein, könnte machen, dass er bei einem zweiten Durchlauf versucht an ner Kreuzung wo er beispielsweise links gegangen ist einfach dann einfach mal nach unten weiter geht, gute Idee!
Bzw. das er alles durchprobiert und dann den schnellsten Weg anzeigt. Das ist keine schlechte Idee, thx :-)

[dominikkv]

Noch nen Bug: wenn man noch keine Map geladen hat und dann Reset klickt und den Öffnen-Dialog abbricht ist der Start-Button enabled! Mit entsprechender Fehlermeldung beim klick:

Zitat:

---------------------------
Project1
---------------------------
Gleitkommadivision durch Null.
---------------------------
OK
---------------------------

[Flips]

Sehr gut, danke dir!!!! :thumb:

[STS301]

um alle aufmerksam zu machen

DER SOURCE IST DA!!! *freu*

[DP-Maintenance]

Dieses Thema wurde von "Dax" von "Freeware" nach "Open-Source" verschoben.

[Flips]

So, hab mal die aktuelle Source (mit der ich die Präsentation gehalten habe) online gestellt.
Sollte evtl. noch jemand Interesse an der Präsentation haben (dadurch wird die Funktionsweise noch klarer), kann ich diese auch hochladen.

[jmit]

Hallo,

wirklich super, sehr gutes Programm. :thumb: :thumb:

Was mich noch interessieren würde: Wie erstelle ich ein neues Labyrinth als Bitmap?

Gruß Jörg

[Flips]

Danke :-)

Also ich weiß von Gimp, das es Labyrinte rendern kann.
Allerdings benötigen die ein wenig Nachbearbeitung, da die Ränder nicht schwarz sind und das ganze nicht komplett durchgängig ist.
Aber im Prinzip reicht schon Paint.
Vielleicht schreib bald auch mal ein Programm, welches Labyrinte erstellen kann :-)

[busybyte]

Da kann ich mich nur anschliessen,sehr gute Arbeit und vielen Dank für den OpenSource.
Bugbericht:

Delphi-Quellcode:

procedure TForm1.FindeWeg(x,y,i:integer);
begin
.
.
.
//alt
//Delay(StrToint(edtDelay.Text));
//neu
Delay(StrTointdef(edtDelay.Text,1));

Im Anhang noch ein Bitmap das auch funktioniert,mittelgroß ohne Ausgang

[busybyte]

Bugreport:
Wenn in eine laufende Wegsuche ein neues ungültiges Labyrinth geladen wurde
kam es zu einer Zugriffsverletzung,ein erster Lösungsansatz:

Delphi-Quellcode:

Procedure TForm1.FindeWeg(x,y,i:integer);
begin
//Wenn Ausgang gefunden / Programm beendet -> Breche alle Rekursionstiefen ab
if gefunden or Application.Terminated then
    Exit;

//Schritte insgesamt
inc(c);
//Rekursionstiefe
inc(i);

//Wenn Verzögerung an: Exakte Ausgabe mit Delay
if Form1.rbtnVz.Checked then
  begin
    Ausgabe(i, x, y);
    Delay(StrTointdef(edtDelay.Text,1));
  end
//Im Speed-Modus nur alle 50000 Schritte malen -> sonst speed-modus zu langsam
else
 if (c mod 50000) = 0 then
   Ausgabe(i, x, y);

//EDIT
while Length(Feld)<1 do
begin
gefunden:=True;
exit;
end;
//

Feld[x,y] := 2;
letzte.X := X;
letzte.Y := Y;

if (Ziel.X = X) and (Ziel.Y = Y) then
  begin
    MessageDlg('Ziel gefunden!',mtInformation,[mbOK],0);
    Ausgabe(i,x,y);
    sg.Invalidate;
    gefunden := true;
    Exit;
  end
else
  begin
    feld[X,Y] := 3;
//Edit if Feld[x+1,y] = 1 then
    if not gefunden and (Feld[x+1,y] = 1) then
      FindeWeg(x+1,y,i);

//Edit if Feld[x,y+1] = 1 then
    if not gefunden and (Feld[x,y+1] = 1) then
      FindeWeg(x,y+1,i);

//Edit if Feld[x-1,y] = 1 then
    if not gefunden and (Feld[x-1,y] = 1) then
      FindeWeg(x-1,y,i);

//Edit    if Feld[x,y-1] = 1 then
    if not gefunden and (Feld[x,y-1] = 1) then
      FindeWeg(x,y-1,i);

    if not gefunden then
      feld[X,Y] := 2;
    if (i = 1) and not gefunden then
      begin
        Fehler(3,fFehler);
        sg.Invalidate;
        Ausgabe(i,x,y);
        Application.ProcessMessages;
      end;
  end;
end;

[Flips]

Danke, den ersten Post hab ich übernommen (kannte den Befehl noch gar nicht :-) ),
auch danke für den 2. Post und die Möglichkeit das zu lösen.
Da ich das Programm aber noch morgen meinem Lehrer schicke muss, mache ich es mir etwas einfacher und deaktiviere einfach den "Laden" Button während eine Wegsuche läuft ;-)

[Edit]Das Beispielbild mit der Erde ist cool, sowas hatte ich noch gar nicht getestet :-D[/Edit]

[xZise]

Eine Frage: Wodurch sind die Start/Ziel Koordinaten definiert?

MfG
xZise

[Flips]

Start durch nen roten Pixel und Ziel durch nen grünen Pixel (clLime -> $0000FF00)
Wenn mehrere rote / grüne Pixel da sind wird der, der zuletzt abgearbeitet wurde genommen, also der der am weitesten unten links liegt ;-)