Autor Beitrag
fidionael
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 232

Win XP SP2, Ubuntu 6.06
Delphi 7 PE, Delphi 3 Prof
BeitragVerfasst: Do 18.05.06 14:37 
Hallo,

ich versuche gerade, zur Übung, ein Pacman-Spiel zu programmieren. Das ist das erste Spiel, in dem es Gegner gibt, also das erste Spiel, in dem ich mir Sorgen um eine KI machen muss.

Nun habe ich mir gedacht, dass die Geister ja nicht allzu intelligent seien müssen, sondern lediglich auf schnellsten Wege zum Pacman laufen. Das hat allerdings nicht so richtig funktioniert, da sie dann immer an Wänden hängen bleiben. Ich habe jetzt etliche Varianten ausprobiert, doch keine führt zum gewünschten Ergebnis.

ausblenden volle Höhe UGhost
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:
87:
88:
89:
90:
91:
92:
93:
94:
95:
////////////////////////////////////////////////////////////////////
// UGhost by Nikolas Jansen                                       //
// This unit contains the types TGhostState and TGhost            //
//                                                                //
// TGhostState: (gsNormal, gsAfraid, gsKilled);                   //
//                                                                //
// TGhost:      (CLASS)                                           //
//   Functions and Procedures:                                    //
//     constructor TGhost.Create(Canvas,1..20,1..20,TDirection);  //
//     procedure TGhost.MakeMove(TField,PacX,PacY,Flee: Boolean); //
//     destructor TGhost.Free;                                    //
//   Properties:                                                  //
//     X, Y: Integer                  READ                        //
//     CurrentDirection: TDirection   READ                        //
////////////////////////////////////////////////////////////////////

// Die Funktion unsigned gibt von einer Zahl lediglich den Betrag zurück, das 
// Vorzeichen wird also ignoriert

// Die Funktion DirIsPossible überprüft im Feld, ob ein Schritt in die gewünschte
// Richtung möglich ist (Resulttyp Boolean)

// Die Funktion InvertedDir invertiert wie der Name schon sagt die Richtung, also ist
// z. B. InvertedDir(dLeft)=dRight

{...}

function TGhost.GetDirection(Field: TField; Aim_X,Aim_Y: Integer) : TDirection;
  function GetDir(X: Boolean) : TDirection;
  begin
    Result:=dNone;
    if X then begin
      if (xCoord-Aim_X>0) and (DirIsPossible(Field,dLeft)) then
        Result:=dLeft;
      if (xCoord-Aim_X<0) and (DirIsPossible(Field,dRight)) then
        Result:=dRight;
    end else begin
      if (yCoord-Aim_Y>0) and (DirIsPossible(Field,dUp)) then
        Result:=dUp;
      if (yCoord-Aim_Y<0) and (DirIsPossible(Field,dDown)) then
        Result:=dDown;
    end;
  end;
begin
  Randomize; Result:=dNone;
  if unsigned(xCoord-Aim_X)>unsigned(yCoord-Aim_Y) then
    if InvertedDir(GetDir(True))<>dir then
      Result:=GetDir(True)
    else
      if InvertedDir(GetDir(False))<>dir then
        Result:=GetDir(False)
      else
        Result:=dNone
  else
    if (GetDir(False)<>dNone) and (InvertedDir(GetDir(False))<>dir) then
      Result:=GetDir(False)
    else
      if InvertedDir(GetDir(True))<>dir then
        Result:=GetDir(True)
      else
        Result:=dNone;
  if Result=dNone then
    Repeat
      Result:=TDirection(Random(4));
    Until (DirIsPossible(Field,Result)) and (InvertedDir(Result)<>dir);
end;

procedure TGhost.MakeMove(Field: TField; Pac_X,Pac_Y: Integer; Flee: Boolean);
begin
  with Canvas do begin
    Brush.Color:=clBlack; FillRect(rect(25*(xCoord-1),25*(yCoord-1),
                                        25*(xCoord-1)+25,25*(yCoord-1)+25));
  end;
  Field.DrawCell(xCoord,yCoord);

  if not Flee then
    if State=gsKilled then
      dir:=GetDirection(Field,Field.GhostSpawn.X,Field.GhostSpawn.Y)
    else
      dir:=GetDirection(Field,Pac_X,Pac_Y)
  else
    dir:=GetDirection(Field,Field.GhostSpawn.X,Field.GhostSpawn.Y);

  case dir of
    dUp: dec(yCoord);
    dDown: inc(yCoord);
    dLeft: dec(xCoord);
    dRight: inc(xCoord);
  end;

  if Flee then
    Draw(gsAfraid)
  else
    Draw(gsNormal);
end;


Vielleicht kann mir ja hier jemand helfen? Schonmal vielen Dank im Vorraus.
Balmung der blaue Gott
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 52

WinXP

BeitragVerfasst: Do 18.05.06 16:54 
Hi,

Ich glaube ich habe deinen Quelltext nun einigermaßen verstanden, trotzdem wäre es nett deine Idee auf Deutsch (/von mir aus englisch) zu formulieren und das Problem das du hast auch.
Ich vermute dass sich deine Geister begeistert auf dich stürzen, wenn du dich in ihrer Reihe befindest, ob nun ein Stein irgendwo dazwischen ist oder nicht.

Ich würde das so machen:

Nach jedem Move eine Schleife benutzen um falls sich Pacman in der gleichen Zeile befindet wie der Geist (sowas wie Pac_X = Gs_X) zu überprüfen ob zwischen ihnen keine Wand ist.

Falls keine Wand dazwischen ist, kann man eine Variable Ziel (= Eigenschaft von Ghost) mit der X Koordinate von Pacman gleichsetzen. Nun lässt man Ghost auf diese x Koordinate zulaufen (z.B. mit Hilfe der Variable Direction).

Statt nur die Zeile, sollte man natürlich auch die Reihe wie oben überprüfen.

Außerdem würde ich um die Geister nicht all zu planlos in der Gegend rumlaufen zu lassen nach jeder durch Zufall bestimmten Direction zufällig eine RichtungsDauer (wieder als Eigenschaft) bestimmen, die der Ghost die Richtung beibehält (natürlich nur bis er Pacman sieht oder eine Wand vor ihm liegt). Die Zahl sollte auch den Wert 0 annehmen können, da der Geist sonst in eine Sackgasse kommen kann.

Also, wenn ich noch was zum Quelltext sagen darf:
-Flee als Eigenschaft von TGhost definieren (weniger Parameter)
-x bei GetDir() mit einer aussagekräftigeren Variable ersetzen (z.B. PacInXrow/PacInYrow ... naja oder so ähnlich)
fidionael Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 232

Win XP SP2, Ubuntu 6.06
Delphi 7 PE, Delphi 3 Prof
BeitragVerfasst: Mi 09.08.06 22:33 
Auch wenn dieser Thread schon einen meterlangen Bart hat, möchte ich - für Interessierte - nun doch mal offen legen, wie ich das Problem letztendlich gelöst habe.

Meinen Grundgedanken im obigen Quelltext habe ich beibehalten, lediglich die Ausarbeitung ist eine andere (ich habe mich ein wenig von dem Backtracking-Prinzip inspirieren lassen).

Der folgende Quelltextschnipsel kann verwendet werden, um ein Objekt zu einer bekannten Zielkoordinate durch ein Labyrinth laufen zu lassen (z. B. Geist zum Pacman). Es wird nicht immer ein Weg gefunden, aber die Erfolgschancen sind ganz gut und das Prinzip ist sehr leicht verständlich.

Wer Pacman programmiert und sich an dieser Stelle fragt, wie man mit dieser KI einen fliehenden Geist programmiert, dem sei als Hinweis gegeben, dass man die vorgeschlagenen Richtungen (Prior) auch invertieren kann.

ausblenden volle Höhe 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:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
interface

{ ... }

type
  TFeld = (Hindernis, Leer, Ziel);
  TRichtung = (Rechts, Links, Unten, Oben);

  TSpielfigur = record
    X,Y: Smallint;
    Richtung: TRichtung;
  end;

  TGUI = class(TForm)
    { Komponenten }
  private
    Labyrinth: Array[0..23,0..15] of TFeld;
    Spielfigur: TSpielfigur;

    MeinZiel: TCoord;

    procedure BewegeSpielfigur;
  end;

{ ... }

implementation

{ Initialisierung der Variablen, grafische Darstellung, etc. }

procedure TGUI.BewegeSpielfigur;
var Veraenderung: Boolean;
    Prior: Array[0..3] of TRichtung;

  function Betrag(x: Integer) : Integer;
  begin if x < 0 then Result := -x else Result := x; end;

  function Frei(x,y: Smallint; dir: TRichtung) : Boolean;
  begin
    Result := False;
    case dir of
      Rechts:
        if (x+1 < 24) and (Integer(Labyrinth[x+1,y]) > 0)
        then Result := True;
      Links:
        if (x-1 > 0) and (Integer(Labyrinth[x-1,y]) > 0)
        then Result := True;
      Unten:
        if (y+1 < 16) and (Integer(Labyrinth[x,y+1]) > 0)
        then Result := True;
      Oben:
        if (y-1 > 0) and (Integer(Labyrinth[x,y-1]) > 0)
        then Result := True;
    end;
  end;

  function Invert(dir: TRichtung) : TRichtung;
  begin
    if Integer(dir) mod 2 = 0 then
      Result := TRichtung(Integer(dir)+1)
    else
      Result := TRichtung(Integer(dir)-1)
  end;

  procedure Bewege(dir: TRichtung);
  begin
    case dir of
      Rechts: inc(Spielfigur.X);
      Links: dec(Spielfigur.X);
      Unten: inc(Spielfigur.Y);
      Oben: dec(Spielfigur.Y);
    end;
    Spielfigur.Richtung := dir;
  end;

begin
  Veraenderung := False;

  with Spielfigur do begin
    // Stellt zunächst die Prioritätsreihenfolge der vier Richtungen fest
    if Betrag(MeinZiel.X - X) > Betrag(MeinZiel.Y - Y) then begin
      if MeinZiel.X > X then Prior[0] := Rechts
      else Prior[0] := Links;
      if MeinZiel.Y > Y then Prior[1] := Unten
      else Prior[1] := Oben;
    end else begin
      if MeinZiel.Y > Y then Prior[0] := Unten
      else Prior[0] := Oben;
      if MeinZiel.X > X then Prior[1] := Rechts
      else Prior[1] := Links;
    end;
    Prior[2] := Invert(Prior[1]); Prior[3] := Invert(Prior[0]);

    // Prüft der Reihe nach ob die Richtungen frei sind und geht sie, wenn
    // hierfür die aktuelle Richtung nicht invertiert werden muss
    if (Frei(X,Y,Prior[0])) and (Richtung <> Invert(Prior[0]))
    then begin Bewege(Prior[0]); Veraenderung := True; end
    else if (Frei(X,Y,Prior[1])) and (Richtung <> Invert(Prior[1]))
    then begin Bewege(Prior[1]); Veraenderung := True; end
    else if (Frei(X,Y,Prior[2])) and (Richtung <> Invert(Prior[2]))
    then begin Bewege(Prior[2]); Veraenderung := True; end
    else if (Frei(X,Y,Prior[3])) and (Richtung <> Invert(Prior[3]))
    then begin Bewege(Prior[3]); Veraenderung := True; end;

    // Falls noch kein Zug gemacht wurde wird die Richtung invertiert
    if not Veraenderung then Richtung := Invert(Richtung);
  end;
end;

{ ... }


Vielleicht hilft es ja jemandem. Mfg