Überprüfen ob n-eck geschlossen ist

Timi-loader · Beiträge: 58 Win XP Delphi 7 Personal

Hallo.
Ich will in meinem Programm überprüfen lassen, ob sozusagen der Weg von einem Eckstartpunkt über beliebige Kurven zum Ausgangspunkt hin ankommt. Dazu habe ich mir auch eigendlich simpel überlegt, prüft er, ob er ein Feld vor gehen kann und solange dies der Fall ist, tut er das und wenn es nichtmehr der Fall ist, d.h. eine Ecke existiert, probiert er in die 2 anderen Richtungen aus (da insgesammt 4 Richtungen und selben Weg zurück soll er ja nicht gehen). D.h. er probiert's dann genauso: Solange Schritt in eine andere Richtung möglich ist, gehe weiter. Wenn nichtmehr möglich, dann ist's 'ne Ecke und probiere die 2 anderen Richtungen aus. U.s.w bis er schließlich am Startpunkt ankommt.
Dann soll er später noch alle Felder, die in diesem Viereck liegen, ermitteln und "füllen" aber das kommt ja danach. Und wenn ebend das Viereck oder Mehreck nicht geschlossen ist, passiert garnichts, sondern er geht aus dieser "Kurvenüberprüf-Prozedur" raus und der Spieler kann normal weiterspielen und seine Felder setzen.

Ich hoffe das war nicht zuviel/zu kompliziert erklärt..
Wenn nötig, würde ich auch meinen Quelltextversuch hier posten, aber da der doch bissl lang ist, dachte ich, verzichte ich erst einmal drauf..

Würd' mich über Lösungsvorschläge sehr freuen, da ich schon ziemlich lang an diesem Problem sitze..

M.f.G.
Timi-loader

alzaimar · Verfasst: Fr 14.10.05 11:59

Will ja nicht pingelig sein, aber an deiner Erklärung wird der tiefe Sinn hinter orthographischen Regeln (Kommas und Rechtschreibung) sehr schnell klar: Es liest sich dann einfach besser.

Hast du ein Spielbrett? Welche Regeln gibt es da? Gibt es sozusagen Hindernisse? Oder wie?

_________________
Na denn, dann. Bis dann, denn.

Timi-loader · Beiträge: 58 Win XP Delphi 7 Personal

Ja, ein Spielbrett hab ich und es gibt auch gewisse Regeln, aber die haben jetzt nichts mit der eigendlichen Fragestellung zu tun.

Und extra für dich

..und andere hab ich nochmal versucht meinen Beitrag oben othografisch besser zu gestalten.

M.f.G.
Timi-loader

jaenicke · Verfasst: Fr 14.10.05 12:27

Du verstehst sicherlich, dass ich bei dieser Schreibweise nicht alle deine Ausführungen gelesen habe, das ist ja fast so schlimm, wie wenn einer mit ner Sauklaue handschriftlich was schreibt. :evil:

Na ja, zur grundsätzlichen Vorgehensweise:
Hier solltest du am besten rekursiv vorgehen. Dazu brauchst du natürlich etwas, wo deine Wege gespeichert sind. Dann fängst du beim Ausgangspunkt an, und rufst für jeden wegführenden Weg eine Funktion auf, die diesen überprüft.
Im Rückgabewert muss dann der Erfolg angegeben werden und zudem muss irgendwo der Weg gespeichert werden.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:

var
  Playground: array of array of array[0..7] of Boolean;

procedure TesteWeg(uPosition: TPoint; uRichtung: Integer; var uWeg: TWeg): Boolean;

  function GetNewPosition: TPoint;
  begin
    case uRichtung of
      0, 1, 7: Result.Y := uPosition.Y - 1;
      3, 4, 5: Result.Y := uPosition.Y + 1;
    end;
    case uRichtung of
      1, 2, 3: Result.X := uPosition.X + 1;
      5, 6, 7: Result.X := uPosition.X - 1;
    end;
  end;

var
  i: Integer;
  tmpWeg: TWeg;
begin
  tmpWeg := uWeg;

  //In tmpWeg den aktuellen hinzufügen

  uPosition := GetNewPosition;
  for i := 0 to 7 do
    if Playground[uPosition.X, uPosition.Y, i] and TesteWeg(uPosition, i, uWeg) then
    begin
      uWeg := tmpWeg;
      Break;
    end;
end;

//In deiner Startmethode:
for i := 0 to 7 do
  if Playground[3, 2, i] and TesteWeg(Point(3, 2), i, myWay) then
    Break;

Das ist ein ganz simples Vorgehen, fertig ist das natürlich noch lange nicht, aber die Idee hilft ja vielleicht.
In einem Array wird gespeichert, in welche der (bei einem quardatischen F>eld mit diagonalen Zügen) 8 nrichtungen man vom aktuellen Feld aus kommt (Richtung[i], Ja odser Nein).
Dann muss man nur vom Anfangspunkt aus alle möglichen R<ichtungen jeweils überprüfen.

//EDIT: Wow, jetzt kann man ja die Fragestellung richtig lesen...

Timi-loader · Beiträge: 58 Win XP Delphi 7 Personal

hmm ja ansich versteh ich die herangehensweise nur das ich meine methode nur mit 4 richtungen gemacht hab was allerdings eh irgendwann hätten 8 werden müssen...
..jedenfalls zeig ich jezt einfach mal was ich versucht hab.. vll. findet ihr ja nen fehler:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:

procedure TForm1.vierecksp;
begin
rx:=x1; // + 1;   // wobei x1,y1 die aktuelle position des typ1 ist
lx:=x1; // - 1;
oy:=y1; // - 1;
uy:=y1; // + 1;
probenm:=1;
pruntenm:=1;
prlinksm:=1;
prrechtsm:=1;
testvorbei:=0;  //bisher unverwendet
prrechts;             // fängt einfach mal beliebig mit rechts an zu testen..
if ((rx=x1) and (oy=y1)) or ((rx=x1) and (uy=y1)) or ((lx=x1) and (oy=y1)) or ((lx=x1) and (uy=y1)) then close;
end;

procedure TForm1.prrechts;
begin
if prrechtsm=1 then
begin   while belegt[rx,uy]=4 do
        begin
         rx:=rx+1;
         if ((rx=x1) and (oy=y1)) or ((rx=x1) and (uy=y1)) then close;
        end;
        if belegt[rx,uy]<>4 then
             begin
              prrechtsm:=0;
              if probenm=1 then proben;
              if pruntenm=1 then prunten;
             end;
end;

end;

procedure TForm1.proben;
begin
if probenm=1 then
begin while belegt[rx,oy]=4 do
      begin
       oy:=oy-1;
       if ((rx=x1) and (oy=y1)) or ((lx=x1) and (oy=y1)) then close;
      end;
      if belegt[rx,oy]<>4 then
           begin
            probenm:=0;
            if prlinksm=1 then prlinks;
            if prrechtsm=1 then prrechts;
           end;
end;

end;

procedure TForm1.prlinks;
begin
if prlinksm=1 then
begin while belegt[lx,oy]=4 do
      begin
       lx:=lx-1;
       if ((lx=x1) and (oy=y1)) or ((lx=x1) and (uy=y1)) then close;
      end;
      if belegt[lx,oy]<>4 then
           begin
            prlinksm:=0;
            if pruntenm=1 then prunten;
            if probenm=1 then proben;
           end;
end;

end;

procedure TForm1.prunten;
begin
if pruntenm=1 then
begin while belegt[lx,uy]=4 do
      begin
       uy:=uy+1;
       if ((rx=x1) and (uy=y1)) or ((lx=x1) and (uy=y1)) then close;
      end;
      if belegt[lx,uy]<>4 then
           begin
            pruntenm:=0;
            if prrechtsm=1 then prrechts;
            if prlinksm=1 then prlinks;
           end;
end;

end;

Zur Erklärung:
Den Wert 4 bekommt das Feld dann durch den Spieler gesetzt, da es noch 3 Vorstufen gibt, die aber nicht überprüft werden sollen.
Und die Variablen mit dem Schema [prozedur]m da steht m für möglich, weil ich dachte, dass man nicht mehrfach selbe Richtungen überprüfen sollte, was sonst zu einer Endlosschleife führt... aber irgendwie ists so wies jetzt ist auch zu früh
Und in dem Testfall soll das Programm wenn das Viereck komplett ist geschlossen werden durch close; .

..und mit case of hab ich bei dir schon verstandn ..komme nur net klar wo jetzt der weg überprüft wird..

jaenicke · Verfasst: Fr 14.10.05 14:08

Timi-loader hat folgendes geschrieben:

hmm ja ansich versteh ich die herangehensweise nur das ich meine methode nur mit 4 richtungen gemacht hab was allerdings eh irgendwann hätten 8 werden müssen...
..und mit case of hab ich bei dir schon verstandn ..komme nur net klar wo jetzt der weg überprüft wird..

Nun ja, das hab ich auch nicht eingebaut, ich wollte ja schließlich nur zeigen, wie das rekursiv funktioniert! In TesteWeg musst du natürlich den Rückgabewert, also Result, dementsprechend setzen. Dazu musst du halt prüfen, ob die Position, die man in TesteWeg übergeben bekommen hat, die gesuchte ist, und, falls das der Fall ist, True zurückgeben und aus der Methode rausgehen. (Die Schleife zum weiteren Testen, darf dann natürlich nicht mehr ausgeführt werden!!!)

Sicher hätte ich auch das on the fly hinbekommen und posten können, (on the fly, weil Delphi hab ich im Moment nicht hier), aber ich wollte ja nur die Idee zeigen und nicht das Programm fertig schreiben...

Timi-loader · Beiträge: 58 Win XP Delphi 7 Personal

ich versteh schon, dass du nciht das programm fertig schreiben sollst.. aber genau der teil den du weggelassen hast ist der, der mir fehlt.. und den ich nicht hinbekomme.. und das man das mit den richtungen noch bissl vereinfachen kann ist mir klar.. nur ebend net mit dem "gedachten ablaufen" ..wäre evtl auch nett wenn du dir mal den quelltext von mir anguggst und daran verbesserungen durchführen könntest, da ich nicht unbedingt lust habe noch eine andere methode zu benutzen es sei denn es geht so garnicht wie ich mir das dachte..
mfg
Timi-loader

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme