Optimale Wegberechnung einer KI

[Castyll]

Hallo zusammen,

Für meine Seminararbeit will ich nun eine Java-Version von Pacman codieren. So weit läuft alles, nun muss ich jedoch die Ghosts codieren. Wer das Spiel nicht kennt: In der vereinfachten Version gibt es 2 Ghosts. Einer der einfach zufällige Bewegungen im Grid macht und einer der gezielt versucht den Spieler zu verfolgen. Und um letzteren geht es im Moment:
Ich habe mir extra ein mehrdimensionales Array angelegt, welches alle begehbaren Koordinaten abspeichert. Und ich steh grad ein wenig auf dem Schlauch. Wie mach ich es am besten, dass der Ghost den schnellstmöglichen Weg berechnet?
PS: Ich brauche keine Code-Abschnitte aber vielleicht hat ja jemand einen Denkanstoß

 

[Flown]

zB. https://stackoverflow.com/questions/2604022/pathfinding-algorithm-for-pacman

 

[Castyll]

Hallo @Flown
Danke erstmal. Da die Seminararbeit letztendlich für 2. Semester Studenten gemacht ist, habe ich mich entschieden die banalere Version zu machen:

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Meine Frage noch wäre: ich habe eine movePossible Methode, die false returned wenn der Ghost sich nicht in die spezifizierte Richtung bewegen kann. Wenn nun der Spieler nach oben geht, und der Ghost nicht nach oben kann, habe ich mir folgendes gedacht:

while(SpielerBewegtSichNachOben&&GhostKannNichtOben)
Ghost.move(links) //oder rechts falls nicht möglich

Der Ghost bewegt sich solange links (falls möglich wenn nicht rechts) bis nach oben wieder möglich ist und solange der Spieler sich nach oben bewegt. Wenn der Spieler dann eine Richtungsänderung einschlägt, schlägt der Ghost diese auch wieder ein oder landet wieder in einer Schleife wenn dies nicht möglich. Würdest du das auch so machen oder hättest du einen besseren Weg?

 

[Meniskusschaden]

Ich glaube, ich würde das "Geruchsverfahren" einsetzen (ist auch im Link von @Flown enthalten). Das müsste ziemlich einfach zu implementieren sein und man hat auch gleich simple Möglichkeiten, den Schwierigkeitsgrad zu variieren (Intensität des Geruchs bzw. Geschwindigkeit der Geruchsminderung). Außerdem rechne ich mit einem ziemlich plausiblen Verhalten des Geistes (planlos bis er eine Spur findet, danach sehr zielorientiert).

 

[Castyll]

Ok Danke dir. Also im Grunde: ghost macht zufällige Bewegungen bis Pacman in seinen "Geruchsradius" kommt. Dann werden die Bewegungen vom Ghost gezielt: d.h. Er verfolgt Pacman, wird eventuell ein wenig schneller

 

[Meniskusschaden]

Ja, wobei ich keinen echten Radius nehmen würde, sondern einfach einen initialen Geruchswert auf jeder Position speichern würde, die der Spieler betritt. Bei jedem Takt werden dann sämtliche Geruchswerte etwas reduziert. So bilden sich verblassende Spuren auf den Wegen, denen der Geist gezielt folgen kann, weil größere Geruchswerte auf eine frischere Spur hindeuten.

 

[JuKu]

Ja, wobei ich keinen echten Radius nehmen würde, sondern einfach einen initialen Geruchswert auf jeder Position speichern würde, die der Spieler betritt. Bei jedem Takt werden dann sämtliche Geruchswerte etwas reduziert. So bilden sich verblassende Spuren auf den Wegen, denen der Geist gezielt folgen kann, weil größere Geruchswerte auf eine frischere Spur hindeuten.

Das ist echt eine sehr gute Idee!
Ich glaube das wäre auch die sinnvollste Implementation.