# A*, Array und KI



## javaPanther (14. Feb 2012)

Hallo liebe Leute,
ich bastle derzeit einen Spiel in Richtung Castle Crashers. Über Performance und Darstellung der Sache mache ich mir wenig Sorgen aber ich würde dem geneigten Nutzer gerne eine Möglichkeit bieten eine gelungene KI zu genießen.
Leider habe ich mich bisher zu erfolgreich um dieses Thema gedrückt, da ich weiß wie heftig es ausarten kann. Nachdem ich nun endlich den Bleistift in die Hand genommen habe dachte ich an ein Tilebasiertes System (zumindest für Pathfinding, Positionierung und evtl. Kollision).

Hier nun die Frage: Wie haben die Jungs von CastleCrashers das vermutlich gelöst und welche Vorgehensweise könntet Ihr mir empfehlen? Vor- und Nachteile wären klasse. Aber bitte nichts zu rechenintensives, da es auch auf den Androiden  und möglichst vielen Plattformen verfügbar werden soll.

Mit besten Grüßen und Dank im Voraus!


----------



## Marco13 (15. Feb 2012)

Stichworte wären A*, Array und KI :joke:

Im Ernst: Was sind die Hauptaufgaben der KI? Wie viele Einheiten gibt es? Vielleicht wäre es für dei Performance gut, einen "All Pairs Shortest Paths" durchlaufen zu lassen, und die Einheiten später nur noch auf diese Vorberechneten Wege zurückgreifen zu lassen. Wenn sich die Karte aber zwischendrin ändert, wäre der A* wohl besser. Aber zur KI gehört ja noch mehr als Wege finden (Kenne "Castle Crashers" nicht - irgendein "ganz normales" Tower Defense, vermutlich...)


----------



## javaPanther (15. Feb 2012)

Google verrät, dass es sich bei CastleCrashers um eine Art Sidesscrolling Action Spiel handelt. Die KI soll sich hauptsächlich damit beschäftigen intelligentes Gegnerverhalten zu simulieren. Darunter zählt grob gesagt die Auswahl einer geeigneten Attacke, die Interaktion mit anderen Charakteren, die korrekte Positionierung (A* ?) sowie einem gewissen Zufallsfaktor, damit das ganze nicht vorhersehbar wird.

Die Karte wird sich vermutlich relativ oft ändern, da es auch teilweise bewegliche Gegenstände gibt. Ein Worst Case Szenario liegt bei ca 30 gleichzeitig auf dem Spielfeld agierenden Figuren. der Normalfall werden vermutlich 7-15 Figuren sein.


----------



## Marco13 (15. Feb 2012)

Hm... die Screenshots sehen nicht nach Tiles aus (genau wie der Beegriff "Sidescrolling" nicht danach klingt). Insgesamt ist die Frage (wenn es nicht darum geht, wie man den A* implementiert, sondern wie man eine "Gute KI" macht) etwas zu schwammig...


----------



## Helgon (15. Feb 2012)

Habs mir grad auch angeguckt und ich find, dass das gar nicht danach aussieht, als wäre ein A* notwendig

Sidescrolling ist klar, und "tiles" naja.. eben 2d texturen, aber dabei weniger massig an tiles.

Scheint ja im Xbox store zu sein und dementsprechend XNA

arbeite grad auch damit und kanns nur empfehlen!

a* ist meiner meinung nach aber overkill für das (wonach es aussieht).

Ist doch einfach nur das die mobs (den gegner anvisiern und in die richtung laufen), da muss ja nicht wirklich durch irgend ein labyritnh manivriert werden, könnten genau so gut waypoints oder so sein.

du sprichst ja auch kollision an. mir ist nich klar, ob du es nun "kannst" oder eben nicht, wenn nicht würd ich dir erstmal "spiele basics" ans herz legen, weil ich find ne A* star implementierung trotz anleitung noch sehr kompliziert (für mich zumindest) und unterscheidet sich bei unterschiedlichem aufbau (deiner "tile-engine") doch vllt auch sehr von nem beispiel und da ist nix mit "copy & paste"


----------



## javaPanther (16. Feb 2012)

Danke erstmal für die Antworten. Die Kollisionserkennung und Vermeidung ist bereits implementiert, ebenfalls ein rudimentäres Kampfsystem sowie diverse Effekte. Allerdings strebe ich jetzt ein "intelligentes" Gegnerverhalten an, so dass diese nicht geradeaus auf den Spieler zulaufen sondern eigene Strategien verwenden. Ebenso soll dazu vermieden werden, dass die Gegner an Hindernissen hängen bleiben oder sich anderswo verkanten. Hierfür brauchen sie ja auch eine Pfadvorgabe und für diesen Teil habe ich an A* gedacht (aber nicht zwingend notwendig). 

Aus dem Basic's Alter bin ich vermutlich raus, aber eine gelungene KI wäre Neuland für mich. Außer den vermutlich etwas heftigeren Umsetzungen aus dem Softcomputing wie neuronale Netze.

Eine Umsetzung nach XNA und objective-C sind geplant sobald die Java / Android Version wie gewünscht funktioniert. Das ist auch der Grund weshalb ich Alles selbst gestalten möchte um zu gewährleisten, dass ich es auf allen späteren Plattformen gleichermaßen im selben Look and Feel ausbringen kann.

Falls noch weitere Fragen offen sind beantworte ich diese gerne.


----------

