Kleine künstliche Intelligenz

MrBambi

Angenommen man würde eine Art "Pakman" nachprogrammieren, wie würdet ihr die Sache mit der künstlichen Intelligenz umsetzten. Also quasi woher wüssten die Gegner welchen Weg sie nehmen dürfen (sie können ja nicht durch Wände) und woher wissen sie welcher Weg der kürzeste ist?

Auserdem: Wie würdet ihr verhindern dasder Spieler selbst einfach durch Wände geht?

C++ Forumbot

Dieser Thread wurde von Moderator/in Arcoth aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

die simpelste Lösung wäre wohl ein 2d Array vom Typ int.
Der Benutzer wählt die Richtung, in die er sich bewegen möchte. Dann wird im Array geschaut ob der Spielzug ok ist - also ob dort keine Mauer ist.

struct Position
{
 int x;
 int y;
};

struct Richtung
{
 int x;
 int y;
};

// Position von einem Spieler und einer künstl. Intelligenz
Position spieler,kuenstlicheIntelligenz;

// du befüllst das Array folgendermaßen: 0 bedeutet: Mauer, 1 bedeutet: Weg
const int Mauer=0,Weg=1;
int spielfeld[breite][hoehe];

// in vom Benutzer eingegebene Richtung fortschreiten
MoveOn(spieler,richtung); // MoveOn addiert einfach die x/y Werte von Position und Richtung
// prüfen ob keine Mauer am Weg
if(spieldfeld[spieler.x][spieler.y]==Mauer) 
{
 // Zug rückgängig machen weil dort eine Mauer ist, MoveBack subtrahiert die Werte
 MoveBack(spieler,richtung);
}

Soweit die Logik damit sich der Spieler fortbewegen kann.
Die künstliche Intelligenz (KI) kannst du ähnlich anlegen: es wird geschaut, wie das Labyrinth in der Umgebung der KI aussieht. Ist in eine Richtung ein Weg und keine Mauer, so wird diese Richtung gewählt und mittels MoveOn() in die Richtung fortgeschritten. Die Richtung wird solange beibehalten, bis eine Mauer im Weg ist. Dann wird wieder eine passende Richtung gesucht - und weiter gehts.
Wenn mehrere Richtungen möglich sind, kannst du aus den möglichen Richtungen zufällig auswählen. Angenommen es gibt zwei mögliche Wege: Weg 0 und Weg 1. Dann erzeug eine Zufallszahl und nimm sie modulo Weganzahl - und das Ergebnis ist dann der gewählte Weg: random()%2 => 0 oder 1.

Um kürzeste Wege in Irrgärten zu finden gibt es verschiedene Algorithmen, such dazu im Internet mal nach "solve maze algorithm" oder so ähnlich.

Skym0sh0

Ist es nicht bei Pacman so, dass sich die bösen Geisterchen abhängig von den Bewegungen des Benutzers bewegen (sofern möglich)? Ich meine da mal was gehört zu haben...

MrBambi

Es diente ja nur als Beispiel.

Mechanics

Ich würde bei Pacman nicht von einer KI sprechen, das ist ja wirklich trivial. Den kürzesten Weg zu finden ist Standard, z.B. mit A*. Zu verhinden, dass man durch Wände läuft ist in dem Fall sowieso nicht der Rede wert.

Die Geister könnten schon mal systematisch die beiden Fluchtausgänge versperren.
Ob sie durch Wände können, oder nicht, kann man von Wahrscheinlichkeiten abhängig machen. Aber wieso sollten sie nicht durch Wände gehen, sind doch Geister?
Unterschiedliche Wahrnehmungsfelder für nah und fern wären nicht so schlecht.
Da die Labyrinth-Bilder spiegelbildlich angelegt sind, könnte man Wegstrecken(berechnungen) schlicht aus einer Tabelle auslesen (für eine begrenzte Anzahl an Wegpunkten).
Mit Funkkontakt auf "Sichtweite" (so wie die Soldaten in Oblivion, haben alle super Funkkontakt, falls man mal beim Stehlen erwischt wird. Das ist echt künstliche Intelligenz, nämlich ziemlich unrealistisch) könnte man einen Jagdmob machen.
Da die einzelnen Hälften auch nochmal spielgelbildlich sind, also in Wahrheit Viertel, könnten sich die Geister daran ( grob) orientieren, in welchem Viertel der Pacman gerade herumräubert.

Damit der Spieler nicht selbst durch Wände geht? Im Grunde genommen, verhält er sich wie auf Schienen, dass sollte nicht so schwer einzurichten sein. Hier gibt es aber spezielle, längst bewährte Techniken.

Diese Art von Fragen sind aber in der Abteilung Spieleprogrammierung -> http://www.c-plusplus.net/forum/f7 etwas besser aufgehoben.
Zu diesem Stichwort (bzw. "Sprites" o.ä) entdeckt man z.B. auch gleich
http://zfx.info/viewtopic.php?f=26&t=777

Richtig nett wäre, wenn die einzelnen Geister unter sich einen Highscore ausmachen, wer den PacMan wie oft und wie schnell gefangen hat, und irgendwie diesen Wettbewerb pflegen. Die Geister müssten etwas für gute Hiscores bekommen, was untereinander Neid auslöst oder so ähnlich...

volkard

Mechanics schrieb:

Den kürzesten Weg zu finden ist Standard, z.B. mit A*.

Man braucht nur die paar Kreuzungspunkte zu nehmen, kann fix alle Abstände berechnen und in einem 2d-Array speichern. Schnellsten Weg von A mach B berechnen ist dann schlichtes Ausprobieren der vier Möglichkeiten (zwei Nachbarkreuzungspunkte von A mal zwei NKZ von B). Dann können die Monsta locker in jedem Schritt den schnellsten Weg zum Spieler neu wählen und der Prozessor langweit sich trotzdem zu Tode.

92 schrieb:

Richtig nett wäre, wenn die einzelnen Geister unter sich einen Highscore ausmachen, wer den PacMan wie oft und wie schnell gefangen hat, und irgendwie diesen Wettbewerb pflegen. Die Geister müssten etwas für gute Hiscores bekommen, was untereinander Neid auslöst oder so ähnlich...

Da drängt sich doch sofort ein genetischer Algorithmus auf. Warscheinlich wird, wenn einfach nur der Spielerkillende Geist alle Punkte kriegt, stets der am fittesten sein, der schnurstraks zum Gegner läuft. Kein Teamwork.

Das könnte man beheben, indem alle Geister im Team Punkte kriegen, je schneller der Spieler erlegt wurde, desto mehr. Dann könnten sich Symbiosen ergeben.
Oder vielleicht besser, der GA läuft nicht mit Einzelgeistern, sondern mit ganzen Teams. Die Einzelgeister sind dann sozusagen Organe, denke, dann werden sich schneller Speizalisten wie Absperrer, Killer und Verwirrer rausbilden.

volkard schrieb:

Oder vielleicht besser, der GA läuft nicht mit Einzelgeistern, sondern mit ganzen Teams. Die Einzelgeister sind dann sozusagen Organe, denke, dann werden sich schneller Speizalisten wie Absperrer, Killer und Verwirrer rausbilden.

Das denke ich auch (und assoziiere schon wieder gewisse Scharfschützen und Panzerfaustgeile Einzelkämpfer http://de.wikipedia.org/wiki/Z_(Computerspiel) ). Man könnte den Geistern noch etwas mehr Möglichkeiten gönnen, sowas wie Mimikry oder Psychoterror (unheilsschwangere Musik, überlaute Gibauf-Propaganda, Religionsgesänge, aufdringlich anzügliche Werbung und so Sachen).
Aber ein Schritt nach dem anderen...das hier ist auch eine ganz nett gemachte Einstiegsanleitung:
http://www.heise.de/ct/artikel/creativ-08-291532.html bzw.
http://www.heise.de/ct/projekte/machmit/asteroids/wiki/BeginnersGettingStarted