Pacman Geist Ki

[realodds]

Hallo, ich programmiere gerade Pac Man und bin nun bei dem schlimmsten Part, der Ai, angekommen. Mein Problem ist, dass ja den kürzest möglichen Weg zu Pacman herausbekommen muss, ohne durch Wände zu laufen. Die Wände habe ich mit Lines geklont und das klappt alles, nur wenn der kürzeste Weg durch eine Wand wäre, würde der Geist ewigkeiten gegen die Wand laufen.

public class Ghost1{
    public int movex(boolean inCage, boolean attacking, boolean chase, int pacx, int pacy) {
        if (inCage) {
            if (direction == 0) {
                x += speed;
            } else if (direction == 1) {
                x -= speed;
            }
        } else {
            if (direction == 0) {
                int weg1 = (int) (Math.pow(pacx - x + 1, 2) + Math.pow(pacy - y, 2));
                int weg2 = (int) (Math.pow(pacx - x, 2) + Math.pow(pacy - y + 1, 2));
                int weg3 = (int) (Math.pow(pacx - x, 2) + Math.pow(pacy - y - 1, 2));
//+1, um den Schritt zu "simulieren"
                if (weg1 >= weg2 && weg1 >= weg3) {
                    x += speed;
                }
            }
        }
        return x;
    }
}

(Das gleiche mit der Y Achse, direction = 0 bedeutet rechts, 1 = links, 2 = unten, 3 = oben)
Soweit bin ich jetzt gekommen und jetzt ist das oben erwähnte Problem. Wie würde das am Besten funktionieren?

Wand Probe:

public class Wall{
//    List walls speichert alle Wände
    public boolean isCollaps(List<Point> allpoints){
        boolean collapsed = false;
        for (Point p : allpoints){
            for (Rectangle wand : walls){
                if (wand.contains(p)){
                    collapsed = true;
                }
            }
        }
        return collpapsed;
    }
}

 

[kneitzel]

Evtl. hilft Dir ja https://dev.to/code2bits/pac-man-patterns--ghost-movement-strategy-pattern-1k1a - da ist dann auch eine Implementation dabei ...

 

[realodds]

Nein, das löst das Problem mit den Wänden leider nicht. Trotzdem Danke

 

[mihe7]

Das Problem mit den Wänden, wie Du es bezeichnest, darf gar nicht auftreten können. Aus Sicht des Geistes stellt sich die Frage, welche Bewegungsmöglichkeit am Besten gewählt werden soll. Das Laufen gegen eine Wand ist keine "Bewegungsmöglichkeit".

 

[realodds]

Und wie soll ich das coden? ^^" hört sich gut an, nur alle Möglichkeiten zu testen,ist sicher ein schlechter Weg.

 

[MoxxiManagarm]

Sucht die KI bei PacMan wirklich immer den kürzesten Weg? Dann würde ein Geist dich ja durchweg verfolgen. Ich hatte nicht unbedingt das Gefühl, dass das der Fall ist.

 

[White_Fox]

Wann wurde PacMan programmiert? 80er? Oder doch schon in den 90ern? Da hat auf den schwachbrüstigen Maschinchen ganz sicher noch niemand auch nur im Traum daran gedacht so etwas als KI zu implementieren.

Ich habe von Informatik ja keine Ahnung. Aber wäre es mein Problem, dann würde ich zuerst über Djikstra nachdenken.

 

[kneitzel]

Nein, das löst das Problem mit den Wänden leider nicht. Trotzdem Danke

Sorry, hatte nicht gut genug in den Code gesehen. Der hat da ja tatsächlich nur dumme Ausgaben, so dass da nur die Struktur zu erkennen ist. Da hatte ich eigentlich eine Implementation erwartet.

Ich habe von Informatik ja keine Ahnung. Aber wäre es mein Problem, dann würde ich zuerst über Djikstra nachdenken.

Das wäre auch mein erster Ansatz. generell scheint das eine gern genommene Übungsaufgabe zu sein, da die möglichen Wege relativ einfach und übersichtlich sind. Daher auch mein Ansatz, da einfach online kurz nach einer Lösung zu schauen.

Mit dem von Dir gelieferten Stichwort findet man dann aber auf jeden Fall auch entsprechende Implementationen.

 

[mihe7]

Und wie soll ich das coden? ^^" hört sich gut an, nur alle Möglichkeiten zu testen,ist sicher ein schlechter Weg.

Das Spiel befindet sich zu jedem Zeitpunkt in einem bestimmten Zustand. Grundsätzlich bewegt sich der Geist horizontal oder vertikal, es gibt also max. vier Richtungen. Befindet sich beispielsweise links und rechts des Geistes je eine Wand, reduziert sich die Zahl der Bewegungsmöglichkeiten auf zwei. Die Strategie baucht also nur die Richtungen zu bewerten, die zum jeweiligen Zeitpunkt möglich sind.

Sollte die Strategie in die Verlegenheit kommen, dass mehrere Möglichkeiten gleich wahrscheinlich zum Ziel führen, kann sie eine beliebige (auch zufällige) wählen.

Eine simple Möglichkeit wäre, die Manhattendistanz zu berechnen. Die kürzeste Route erhältst Du dagegen mit dem A-Stern-Algorithmus.

 

[Meniskusschaden]

Wann wurde PacMan programmiert? 80er? Oder doch schon in den 90ern? Da hat auf den schwachbrüstigen Maschinchen ganz sicher noch niemand auch nur im Traum daran gedacht so etwas als KI zu implementieren.

Soweit ich mich erinnere funktionierte der Trick beim Original wohl ungefähr so, dass PacMan auf jeder betretenen Position einen integer-Wert hinterlässt, der bei jedem Tick bis auf 0 dekrementiert wird. So ergibt sich eine verblassende Spur, der die Geister im Verfolgungsmodus nachlaufen können. Dafür braucht man dann kaum Rechenleistung.

 

[realodds]

Sucht die KI bei PacMan wirklich immer den kürzesten Weg? Dann würde ein Geist dich ja durchweg verfolgen. Ich hatte nicht unbedingt das Gefühl, dass das der Fall ist.

Die Geister suchen den kürzesten WEg zu einem Punkt, der aber nicht immer Pacman ist. Bei einem Geist ist dieser zB 4 Felder vor Pac man.

Danke an euch alle

 

[lennero]

Die Geister suchen den kürzesten WEg zu einem Punkt, der aber nicht immer Pacman ist. Bei einem Geist ist dieser zB 4 Felder vor Pac man.

Danke an euch alle

Wenn du mit A* den besten Pfad zum Pacman berechnest, und eine Position vorher stoppst, hast du doch eine der 4 Stellen oder nicht?