PacMan KI

[ViperNeo]

Hallo Leute!

Ich programmiere zurzeit in der Schule das Spiel Pacman noch ganz billig für die Konsole.

Im Moment ist die Aufgabe eine KI zu schreiben die intelligent zum Spieler hinläuft. Spricht auch Wände erkennt sich wege sucht un merkt. Mein Lehrer gab mir den Tip auf ein Backtracking System. Aber ich finde im INternet nichts gescheites darüber. Vielleicht hat ja jemand eine IDee wie man eine solche KI umsetzen könnte oder vielleicht hat ja jemand schon einmal eine KI für Pacman programmiert.

Wäre super cool wenn mir jemadn weiterhelfen könnte!!

Ich arbeite mit Visual C++ .NET

Liebe grüße,
ViperNeo

[CStoll]

Du könntest von der aktuellen Position aus n Schritte in alle möglichen Richtungen "laufen" und dann testen, welcher Weg dich am nächsten zur aktuellen Spielerposition bringen würde - in die Richtung läufst du dann weiter:

int min_dlt = abstand((m_x,m_y),(player_x,player_y))
stack weg
direction opt_dir
gehe(m_x,m_y,max_schritte)

gehe ((int x,int y),int schritte)
  if schritte = 0
    dlt=abstand((x,y),(player_x,player_y))
    if dlt<min_dlt
      opt_dir=weg[0]
      min_dlt=dlt
  for d in (N,O,S,W)
    if istfrei(Nachbar((x,y),d)
      gehe(Nachbar((x,y),d),schritte-1)

[rapso]

naja, den perfekten weg zu finden ist nicht unmögilch, z.b. mit A*. aber das möchte wohl niemand, weil ein spiel bei dem man dauernt verliert langweilig ist.

es reicht wenn an verzweigungen die KI, falls der spieler innerhalb eines bestimmten radius ist, versucht den weg einzuschlagen, der sie näher an spieler bringt.

[thordk]

klar kann man den perfekten weg berechnen, den spieler mittels trajektoren verfolgen und was weiss ich nicht für schweinkrams machen. aber wie gesagt ist es langweilig, bei pacman dauernd zu verlieren

ich würd nen ganz einfachen ansatz wählen. das pacman spielfeld besteht ja aus feldern. eine spielfigur hat an jeder stelle 8 möglichkeiten, sich zu bewegen.

schliesse erstmal alle felder aus, die unmöglich sind. das werden wohl nur diejenigen sein, an denen sich eine wand befindet.

dann berechnest du für jedes feld den euklidischen abstand zur aktuellen spielerposition und bewegst das KI männeken dann auf das feld mit dem geringsten abstand.

diese art der fortbewegung ist für den spieler allerdings sehr leicht zu durchschauen und ausnutzen. er kann die KI in ecken lotsen, aus denen sie nicht mehr rauskommen.

deshalb vielleicht ab und an eine "falsche" entscheidung einschieben.

[Jester]

Den perfekten Weg zu nutzen heißt ja nicht, daß man automatisch gewinnt. Wenn alle drei Geister den kürzesten Weg zu Pacman nutzen bedeutet das ja noch garnix. Man kann dann leicht vor ihnen abhauen. Fies ist es dann, wenn einer den kürzesten Weg nimmt und die anderen die Fluchtwege dichtmachen. Beim Originalpacman gab es daher ja drei Geister mit jeweils unterschiedlichen KIs.

[thordk]

kooperative KI ist aber schon ne größere herausforderung. sollte das gefragt sein, kann man sicherlich auch noch paar tips geben.

[Sgt. Nukem]

Es waren sogar vier IIRC.

[thordk]

grad nochmal geguckt, die meissten pacman klone haben tatsächlich vier.

[Sgt. Nukem]

...weil das Original 4 hatte...

EDIT: Also eins war komplett zufällig, und turnte oftmals immer da rum, wo Du überhaupt nicht warst.
Eins war super-aggressiv, und nahm immer den kürzesten Weg zu Dir der möglich war.
Eins versuchte immer ein zwei Kreuzungen vor (oder hinter?) Dir zu erreichen.

IANAL... äh.. IIRC

[NES-Spieler]

Ich weiß nicht, ob das was nützt, aber auf http://en.wikipedia.org/wiki/Pac-Man#Ghosts steht, wie sich die Geister im Orginal bewegen.