Performancesteigerung Brainstorming Pacman

[Chasmo]

Guten Morgen liebe Java-Community! :smoke:

Da ich zur Zeit an einem kleinen Spiel programmiere, wollte ich hier mal nach konstruktiven Rat fragen / Ideen sammeln.

Das ganze ist eine Art Pacman. Das Problem ist jetzt die KI.
Für die Geister, welche versuchen den "Player" zu fangen, nutze ich einen A*-Algorithmus mittels PriorityQueue. Das ganze läuft auch sehr schnell, jedoch muss der Weg jede Runde neu berechnet werden.
Da das ganze später auch Netzwerkfähig sein soll, wird es nicht zwingend nur einen Spieler geben.

Jeder Geist muss also jede Runde folgendes machen:

• Den Pfad zu jedem Spieler berechnen
• Vergleichen, welcher Pfad der kürzeste ist

Das frisst natürlich Geschwindigkeit wenn man sich ein Szenario mit 10 Spielern und 10 Geistern vorstellt.

Jetzt zu meiner Frage:
Hat jemand von euch Erfahrung mit solch einem Problem oder eine Idee, wie man das ganze etwas cleverer lösen könnte?

Meine erste Überlegung war, das sich der Geist einen Spieler aussucht, den Pfad berechnet und diesen erst abläuft, bis er am Ziel ist. Ist der Spieler nicht mehr dort, wird neu berechnet.
Das führt allerdings zu einer sehr dummen KI :applaus:

Ich bin auf eure Ideenvielfalt gespannt!
MfG Chasmo

 

[SlaterB]

für jeden Geist zu jeden Spieler die genaue A*-Entfernung berechnen bzw. anfangs abschätzen und dann vor allem merken, sowie die Positionen von allen Figuren merken,
nach einer Runde die neuen Entfernungen abschätzen:
für jeden Geist: auf die Entfernung des dichtesten Spielers die eigene Bewegung + die des Spielers absolut drauaddieren, das ist der WorstCase-Fall der maximal vergrößerten neuen Entfernung,
evtl. weniger falls man doch wohl einrechnen kann, dass der Geist schon in die richtige Richtung ging, vielleicht Entfernung gleichgeblieben?
musst du von deinen Beispielabläufen wissen was alles passieren kann

hinsichtlich der anderen Spieler jedenfalls die Geist- + Spieler-Bewegung komplett abziehen, das ist dann die kürzestmögliche Entfernung,
wenn mit diesen Schätzungen immer noch 5-9 Spieler weiter entfernt sind als der eine direkt vor der Nase des Geistes, dann müssen die nicht komplexer neu geprüft werden,

in weiteren Runden immer wieder die gekürzten Schätzungen weiter absenken bis dann irgendwann doch eine Aktualisierung durch A* nötig ist,
mal abgesehen davon dass aus einfachem x/y-Vergleich sowieso immer eine bestimmte Schätzung bekommt

für den Hauptverfolgten kann man überlegen, ob da noch öfter der Weg geprüft wird, vor Wegkreuzungen aber sowieso nicht, oder?
wieviele Runden gibt es eigentlich, 30 pro Sekunde mit jedem Bild neu?

-------

interessant wäre ein größerer Algorithmus, der das ganze Netz betrachtet und gleichzeitig Wege zwischen allen Akteuren bestimmt statt zig mal A* von 0 zu beginnen,
aber ob das so leicht machbar ist..

 

[ice-breaker]

Ich weiß nicht ob es stimmt, aber ich habe mal gelesen, dass der Pacman eine Art Duft absondert, die letzten 5 Positionen haben quasi eine Intensität, die angibt wielange es her ist, dass der Pacman da war.
Und die Geister "irren" mehr oder weniger sinnlos über die Map, bis sie den Duft orten, das soll wohl meist schon recht schnell gehen.

 

[SlaterB]

das klingt natürlich intelligenter und bringt mir auch eine nicht mehr so schwere Idee für den 'größeren Netzalgorithmus',
von allen Pacman-Positionen ausgehen mit, ich übernehme mal, 'Duft' 100, dann die direkten Nachbarknoten 99, dann 98 usw.
das ganze Netz mit Nummern ausgelegen, wenn auf einen Knoten schon eine Nummer aus der aktuellen Runde da ist,
dann überschreiben falls eigene größerer ist, sonst aufhören (mit der Ausbreitung von einem Punkt aus, von den anderen weitermachen),
die Geister müssen dann nur schauen, in welche Richtung die nächstgrößere Duftnote liegt,

vielleicht gar zu intelligent, das Absondern auf den letzten Positionen ist bisschen was anderes, da hat man nach vorne etwas Luft zu den Geistern, könnte interessanter sein

 

[Landei]

Zur "Duft-Methode": Antiobjects - Wikipedia, the free encyclopedia

 

[Marco13]

Hm. Für jedes Paar (Spieler-Geist) einen A* laufen lassen wird wahrscheinlich recht schnell ineffizient. Wie ist denn der Graph des Spielfeldes aufgebaut?
Vermutlich wäre es schon bei relativ wenigen Spielern/Geistern effizienter, eine einmalige All-Pairs-Shortest-Paths-Suche durchzuführen. Aus den daraus gewonnenen Informationen können sich dann alle bedienen.

 

[Chasmo]

@Marco13: Die Idee kam mir auch, anfangs die Wege zwischen allen Punkten zu berechnen. Das Problem dabei ist, das sich die Karte zwischenzeitlich verändert. Das liegt daran, das jedes Feld eine gewissen Höhe hat, die der AStar Algo mit berücksichtigt. Die Höhe ist aber immer erst bekannt, wenn der jeweilige Bot darüber gelaufen ist oder direkt daneben steht. Er sieht also anfangs alle Felder mit Höhe 0 an und später merkt er sich die Werte. Dadurch ergibt sich nach einer Weile ein anderer Weg zwischen 2 Punkten.

@All: Das mit dem Duft klingt echt nach einer vernünftigen Idee. Die genaue Position der Gegner sieht der Bot immer nur, wenn er "Blickkontakt" zu dem Gegner hat. Ist das der Fall, wird ihm die Position des Gegner übermittelt. Aktuell speicher ich die bekannten Gegner, die er schon gesehen hat, sowie deren Position und vor wie vielen Runden er die Position gespeichert hat.

 

[bygones]

Ich weiß nicht ob es stimmt, aber ich habe mal gelesen, dass der Pacman eine Art Duft absondert, die letzten 5 Positionen haben quasi eine Intensität, die angibt wielange es her ist, dass der Pacman da war.
Und die Geister "irren" mehr oder weniger sinnlos über die Map, bis sie den Duft orten, das soll wohl meist schon recht schnell gehen.

stimmt... hat der erfinder von pacman erzählt

 

[Der Müde Joe]

Wär dann wohl sowas:
Ameisenalgorithmus ? Wikipedia

Ich weiss nicht ob der AStar da so gut taugt. Dei Viecher gehen ja erst "zielgsteuert" hinter
dem Pacman her, wenn der sich im Umkreis von ein Paar Punkten befindet. So kann man sie
auch wieder verlieren. Ich denke mal das komplette Spielfield zu berechnen ist das nicht nötig.

Die Pheromon Idee ist auch etwa so. Ist der Pacman nahe, so ist der Duft stark und zieht die
Viecher an. Wobei auch hier eine recht begrenze Sichtweite benutzt wird. Das Ding schaut lediglich
ein Paar Punkte weit und der stärkste im Umkreis X zieht. Ich weiss jetzt nicht ob da der AStar noch
taugt. Das Ziel ist ja eingetlich nicht definiert. Sprich: Suche den besten "Duft" im Umkreis von X und
wenn nix da,lauf einfach weiter bzw Ramdom weiter.

 

[Gast2]

The Pac-Man Dossier
Dort steht einiges zu dem wie sich die einzelnen Geister verhalten. Jeder Geist folgt einem anderen Algorithmus und verhält sich dementsprechend anders.

 

[Chasmo]

Das der Astar da nicht mehr benötigt wird ist mir klar. das war auch nur mein erster Ansatz. Also bis jetzt ist die Idee mit den Pheromonen noch die schnellste und beste denke ich. Vielleicht hat jemand noch ganz andere Ideen? Danke schonmal an alle

 

[Der Müde Joe]

>Das der Astar da nicht mehr benötig

Naja. Irgendwas brauchts da schon. Evtl ein DSSP, was ja nichts anderes ist als ein AStar ohne Heuristik, bzw alle Konten sind gleich gewichtet.