Wegfinden auf einem Schachbrett

kraizee · Verfasst: Di 10.05.05 15:18

Hallo Leute!

Ich bastel gerade an einem Spiel herum, das an sich ziemlich banal zu sein schien, als mein Chef mir die Aufgabe übertrug, dass sich aber langsam zur Tortur steigert: Es geht darum, in einem Feld ( 9x9 ) gleichfarbige Steine nebeneinander zu kriegen, bei fünf oder mehr löst sich die Reihe auf und es gibt Punkte.

Ich hab es mit der Hilfe des Ex-Azubis geschafft, allerdings haben wir noch ein ziemlich großes Problem:

Wenn man einen Stein bewegt, sucht sich das Programm rekursiv seinen Weg, um den Stein von A nach B zu bewegen. Meistens findet es auch den direkten Weg. Bei komplizierten Konstrukten allerdings macht der Stein dann fürchterliche Umwege und latsch auch mal quer über's Feld... Nicht wirklich schön.

Das Theater ist folgendes: Das Programm vergleicht Start- und Zielkoordinaten und bestimmt daraus die Richtung, in die es zuerst prüfen soll, ob der Weg denn frei ist. Jeffe hat gesagt: "Vergleiche die KOs und gehe zuerst in die Richtung, die 'größer' ist" ( also gehe zuerst den längeren Weg ). Und das habe ich versucht umzusetzen. Bisher leider mit null Erfolg.

Ich habe zwar eine Abfrage, um das zu prüfen, aber das war es auch schon.

Hat schon mal jemand von euch etwas ähnliches programmiert?

Ich nutze zwei Funktionen, anders wollte es einfach nicht:
1.) Checkpath
2.) SubCheckPath

Die SubCheckpath sieht bis jetzt für die neue und alte Version gleich aus:

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:

function TFormMain.SubCheckpath(const aCol, aRow, aColParam, aRowParam, myTargetCol, myTargetRow: Integer): Boolean;
var
  myActualStone : TmyPlayStones;
  myActualCol,
  myActualRow : Integer;
begin
  // solange KOs des Steins + Richtung im Spielfeld sind...
  if (aCol + aColParam in [0..8]) and (aRow + aRowParam in [0..8]) then begin
    // ...ist der zu prüfende Stein = KO + Richtung
    myActualStone := myPlayground[aCol + aColParam,aRow +  aRowParam];
    // wenn der zu prüfende Stein ein leeres Feld ist...
    if (myActualStone = psEmpty) then begin
      // dann setze meinen Stein auf das leere Feld...
      myActualCol := aCol + aColParam;
      myActualRow := aRow + aRowParam;
      // ...und prüfe die neuen angrenzenden Felder
      Result := CheckPath(myActualCol, myActualRow, myTargetCol, myTargetRow);
      // wenn die angrenzenden Felder leer sind (der Weg also frei ist)...
      if Result then begin
        // ...dann setze die Weglänge um eins herauf und..
        SetLength(myWay,High(myWay) + 2);
        // ...schreibe das zuletzt geprüfte Feld auf
        myWay[High(myWay)] := (myActualCol * 9 + myActualRow);
      end;

    end else Result := false; // if myActualStone = psEmpty then...
  end else Result := false; // if (aCol + aColParam in [0..8]) and (aRow + aRowParam in [0..8]) then...
  // zum Schluss mache noch den alten Stein weg
  myPlayground[aCol, aRow] := psEmpty;
end;

TmyPlayStones sind eigentlich nix weiter als Farben, aber wir haben halt Steine selbstdefiniert, anstatt "nur" die Farben zu verwenden.

Die alte Version der CheckPath ist der Horror :oops:

:

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:

function TFormMain.CheckPath (const myStartCol, myStartRow, myTargetCol, myTargetRow : Integer) : Boolean;
var
  aCol,
  aRow,
  vertParam,
  horzParam,
  myActualPos : Integer;
begin
  aCol := myStartCol;
  aRow := myStartRow;
  // wenn die Start- und Zielkoordinaten übereinstimmen, dann ist Result = true
  Result := (myStartCol = myTargetCol) and (myStartRow = myTargetRow);

  myActualPos := myStartCol * 9 + myStartRow;
  // wenn result = false ist UND die aktuelle Position noch nicht geprüft ist...
  if not Result and (not IsValueInArray(myActualPos, myCheckedFields)) then begin
    // ...dann erweitere die Liste der geprüften Felder um 1...
    SetLength(myCheckedFields, High(myCheckedFields)+2);
    // ... und füge die aktuelle Position hinzu
    myCheckedFields[High(myCheckedFields)] := myActualPos;

    if (myStartCol < myTargetCol) then begin // Ziel ist rechts
      if (myStartRow < myTargetRow) then begin // Ziel ist unterhalb
        Result := SubCheckpath(aCol, aRow, 1, 0, myTargetCol, myTargetRow) or // nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol, myTargetRow) or // nach unten prüfen
                  SubCheckpath(aCol, aRow, -1, 0, myTargetCol, myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol, myTargetRow);  // nach oben prüfen
      end else if (myStartRow > myTargetRow) then begin // Ziel ist oberhalb
        Result := SubCheckpath(aCol, aRow, 1, 0, myTargetCol, myTargetRow) or // nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol, myTargetRow) or  // nach oben prüfen
                  SubCheckpath(aCol, aRow, -1, 0, myTargetCol, myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol, myTargetRow); // nach unten prüfen
      end else begin // Ziel ist in derselben Zeile
        Result := SubCheckpath(aCol, aRow, 1, 0, myTargetCol,myTargetRow) or //nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol, myTargetRow) or  // nach oben prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol, myTargetRow) or // nach unten prüfen
                  SubCheckpath(aCol, aRow, -1, 0, myTargetCol, myTargetRow); // nach links prüfen
      end; // if (myStartRow < myTargetRow) then...
    end else if (myStartCol > myTargetCol) then begin // Ziel ist links
      if (myStartRow < myTargetRow) then begin // Ziel ist unterhalb
        Result := SubCheckpath(aCol, aRow, -1, 0, myTargetCol, myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol, myTargetRow) or // nach unten prüfen
                  SubCheckpath(aCol, aRow, 1, 0, myTargetCol, myTargetRow) or // nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol, myTargetRow);  // nach oben prüfen
      end else if (myStartRow > myTargetRow) then begin // Ziel ist oberhalb
        Result := SubCheckpath(aCol, aRow, -1, 0, myTargetCol, myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol, myTargetRow) or  // nach oben prüfen
                  SubCheckpath(aCol, aRow, 1, 0, myTargetCol, myTargetRow) or // nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol, myTargetRow); // nach unten prüfen
      end else begin // Ziel ist in derselben Zeile
        Result := SubCheckpath(aCol, aRow, -1, 0, myTargetCol,myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol, myTargetRow) or  // nach oben prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol, myTargetRow) or // nach unten prüfen
                  SubCheckpath(aCol, aRow, 1, 0, myTargetCol,myTargetRow); //nach rechts prüfen
      end; // if (myStartRow < myTargetRow) then...
    end else begin // Ziel ist in derselben Spalte
      if (myStartRow < myTargetRow) then begin // Ziel ist unterhalb
        Result := SubCheckpath(aCol, aRow, 0, 1, myTargetCol,myTargetRow) or // nach unten prüfen
                  SubCheckpath(aCol, aRow, -1, 0, myTargetCol,myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 1, 0, myTargetCol,myTargetRow) or //nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, -1, myTargetCol,myTargetRow); // nach oben prüfen
      end else if (myStartRow > myTargetRow) then begin // Ziel ist oberhalb
        Result := SubCheckpath(aCol, aRow, 0, -1, myTargetCol,myTargetRow) or // nach oben prüfen
                  SubCheckpath(aCol, aRow, -1, 0, myTargetCol,myTargetRow) or // nach links prüfen
                  SubCheckpath(aCol, aRow, 1, 0, myTargetCol,myTargetRow) or //nach rechts prüfen
                  SubCheckpath(aCol, aRow, 0, 1, myTargetCol,myTargetRow); // nach unten prüfen
      end; // if (myStartRow < myTargetRow) then...
    end; // if (myStartCol < myTargetCol) then...
  end; // if not Result and (not IsValueInArray(myActualPos, myCheckedFields)) then...
end;

Und mit der neuen bin ich noch nicht sehr weit gekommen, da ich nicht wieder anfangen will, so einen ewig langen Aufruf-Block zu bauen:

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:

function TFormMain.CheckPath (const myStartCol, myStartRow, myTargetCol, myTargetRow : Integer) : Boolean;
var
  aCol,
  aRow,
  distCol,
  distRow,
  myActualPos : Integer;
begin

(* alles platt gemacht *)

  distCol := myStartCol - myTargetCol;
  distRow := myStartRow - myTargetRow;

// welcher Abstand ist größer?
  if abs(distCol) > abs(distRow) then begin
    // wenn distCol < 0 ist, dann liegt das Ziel rechts
    if distCol < 0 then begin
      // parameter für "nach-rechts-gehen"
    end else begin // wenn distCol > 0 ist, dann liegt das Ziel links
      // parameter für "nach-links-gehen"
    end;
  end else begin
    // wenn distRow < 0 ist, dann liegt das Ziel oben
    if distRow <0 then begin
      // parameter für "nach-oben-gehen"
    end else begin // wenn distRow > 0 ist, dann liegt das Ziel unten
      // parameter für "nach-unten-gehen"
    end;
  end;
end;

Falls sich jemand von euch das ganze Theater hier durchgelesen hat, wäre ich ihm/ihr wirklich sehr dankbar, wenn dazu ein paar Posts mit Tipps oder eine radikale Alternative kommen würden.

Thanks in advance,
Kraizee.

Moderiert von Gausi: Code- durch Delphi-Tags ersetzt.

_________________
if not Signature.Checked then Signature.Checked := True end else begin
Signature := 'Wat n Quatsch' end;

alzaimar · Verfasst: Mi 11.05.05 20:54

So... Den Code habe ich mir nicht angesehen....

Was würde ich also tun?
Ich denke, Du kannst ziemlich billig den 'MinPath' - Algorithmus ansetzen. Das klappt. Dieses Verfahren findet den kürzesten Weg in einem Graphen. Ein Graph G ist definiert durch eine Menge von Knoten K, die durch Kanten E (edges) verbunden ist. Man kann die Kanten auch noch gewichten (z.B. Entfernung), aber hier ist das egal, weil die Entfernung immer konstant ist.
Dein 9x9 Brett ist ja eigentlich ein Graph von 81 Knoten, wobei jeder Knoten mit seinen Nachbarn über Kanten verbunden ist. Da Du einige Steine auf dem Brett hast, musst Du also von den Kanten und Knoten einige wegstreichen. Dann setzt Du den 'minimum Path' Algorithmus an (der ist recht flott) und fertig.

Ich habe ihn im Büro, sonst würde ich ihn posten, aber: ich denke Du findest hier was www.nist.gov/dads/. Eine wunderbare Site zum Schmöckern. Wenn man auf Algorithmen steht....

kraizee · Verfasst: Mi 18.05.05 08:47

Hey, vielen Dank für die Hilfe!

Damit sind wir schon ein gutes Stück weiter gekommen und wenn das ganze dann funktioniert, poste ich den Code nochmal hier, und schließe das Problem als "gelöst" ab...

Schanke dön,
kraizee.

_________________
if not Signature.Checked then Signature.Checked := True end else begin
Signature := 'Wat n Quatsch' end;

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme