spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Was du vorgeschlagen hast, war A*.
Was ich vorschlage, ist sowas wie z.B. der Minimax-Algorithmus, wobei man das Spiel als eine Art "Brettspiel" betrachtet.

Soweit ich das rauslesen kann wär der glaub ich schon das richtige für dich. Du willst ja wenn ich das jetzt richtig verstehe Punkte für einzelne Aktionen vergeben, von denen dann ausgewählt wird welche Aktion er dann ausführen möchte. Aber du musst dann ja noch herausfinden welche Aktion jetzt die höchsten Punkte hat und das macht der Minimax-Algorithmus dann für dich. Der Algorithmus würde ja erst aufwendig werden wenn du jetzt deutlich mehr Optionen hast zwischen die der Computer auswählen müsste, aber was ich so rauslese hast du ja dann nur 3 Möglichkeiten, geradeaus oder links, rechts abbiegen.


Und um dir vllt etwas überblick über den Zeitaufwand zu geben, ich bastel an einem Rundenstrategiespiel, wobei die Einheiten sich nicht bewegen sie deshalb immer eine feste Positionen haben. Um meiner KI sagen zu können wenn sie angreifen sollen, muss diese durch ca. 3000 Zeilen Code durch, einmal für die Einheiten der Spieler und dann nochmal für die gegnerischen Einheiten. Im Release Modus, braucht das Programm für 500 Runden, mit jeweils 6000 Zeilen Code nichtmal 5 Sekunden. Das könnte also auch flüssig mit 100 Frames laufen.

Dabei denke ich mal das dein Code der KI deutlich kürzer sein wird.


Ich mach das auch mit einer Punktevergabe, zuerst Speichere ich die Daten der 21 Einheiten des Gegners in Vectoren ab sodass ich später einfach darauf zugreifen kann und Ordne sie schon nach Stufen. Dann schaue ich für jede Einheit nach wen sie überhaupt angreifen darf, nach den Regeln die ich aufgestellt habe, was sicherlich die hälfte des Codes darstellt. Um anschließend für die Angriffsmöglichkeiten die Punkte zu ermitteln und anschließend die Einheit anzugreifen die die höchste Punktzahl erreicht hat. Das mach ich momentan noch mit einer for Schleife wo ich einfach jeden Wert überprüfe bis der höchste über geblieben ist. An dem Punkt würde sich für mich im Grunde auch der Minimax-Algorithmus rentieren, kannte den bis jetzt auch nicht, hab einfach so für mich losprogrammiert.

Mit den Minimax-Algorithmus reduzierst du halt die Vergleiche um auf die höchste Punktzahl deiner Auswahlmöglichkeiten zu kommen.


Also wie du schon geschrieben hast, hat gerade ausfahren jetzt z.b. schon Standard mäßig einen höheren Wert. Wenn jetzt z.B. vor dir ein Hindernis festgestellt werden sollte, kannst du nach den Regeln die du dir aufstellt ja dann z.b. mehr Punte für abbiegen rechts erteilen. Wordurch dann diese Aktion ausgewählt wird. Mit der Punktvergabe musst dich halt einfach etwas Spielen, also am besten schon eine Strecke haben wo du das auch immer etwas Testen kannst, wäre doch sehr von Vorteil denke ich. So hab ich das bei mir auch immer gemacht, immer zwischendurch mal geschaut wie wirkt sich das jetzt auf die KI aus, um dann auch gleich sehen zu können wo man evtl. noch nachbessern sollte, weil sie sich noch nicht so verhält wie man es gerne hätte.


Hoffe ich hab nichts falsch verstanden und es hilft dir etwas weiter.

Du wirst ja wahrscheinlich auch die Frames begrenzen, sodurch hast du dann ja auch Zeit um die KI in der Zwischenzeit zwischen den Frames zu berechnen. Ich denke das mein Spiel was ich momentan habe und was im Grunde rundenbasiert ist, auch mit 60 Frames flüssig laufen würde, wenn ich jeden Frame eine neue Runde berechnen würde. Die graphische Darstellung ist bei mir da recht simpel da es 2D ist und braucht deswegen da nicht viel Leistung.

Sollte ich mal testen. *g*


Aber das wirst du ja nicht mal unbedingt brauchen, je nachdem wie schnell deine Fahrzeuge unterwegs sind musst du das pro Sekunde vllt nur 2x oder 4x machen oder auch weniger. Dadurch könntest du die Aufgaben ja auch aufteilen, sodass den einen Frame ein paar Punkte vergeben werden, den nächsten Frame die nächsten Punkte und dann sobald das fertig ist in einem weiteren Frame mit dem Minimax-Algorithmus die höchste Option mit der höchsten Punktzahl bestimmen.

Wenn man weiter geht könnte man da auch noch überprüfen wieviele Zeit bleibt mir jetzt gerade auf diesem PC wo es läuft über und kann das dann dynamisch ja anpassen, wie oft die KI Schritte berechnet werden, jenachdem wieviel Zeit zur Verfügung steht.

Hab das zwar noch nie gemacht, aber sollte nicht so schwer sein. Dazu gibts hier auf der Seite ja auch einen Wiki Artikel, wie man sowas unterbringen kann. Mit Verschiedenen herangehensweisen.

Implementier ruhig mal den Minimax. Das sollte ganz gut laufen. Dann begrenzt du einfach wie weit er in die Zukunft gucken kann. Er muss ja nicht 1000 Schritte im voraus berechnen. Da reicht auch weniger. Wenn dir das ganze dann zu langsam läuft ist das hier eine gute Erweiterung für den Algorithmus. Damit kannst du die Laufzeit dann noch ein bisschen verbessern.

Wir haben den mal in der Uni bei einer Gruppenarbeit implementiert. Da haben wir eine KI für ein Kartenspiel benötigt. Das war für 3 bis keine Ahnung wie viele Spieler Funktioniert also auch bei 4 Spielern. Habe ihn jetzt auch nicht mehr richtig im Kopf und grad ist es mir zu spät zu gucken. Dafür muss ich zu früh raus
Versuch doch vielleicht einfach mal den Algorithmus auf ein einfacheres Spiel anzuwenden. Tic-Tac-Toe ist ein guter Einstieg. Die Logik sollte auch fix implementiert sein. Es reicht ja auch ein einfacher Prototyp und muss kein ausgefeiltes C++ sein. Zu Tic-Tac-Toe findest du vielleicht auch schon fertige Implementationen, wobei es immer so eine Frage ist, ob sich anhand dieser der Algorithmus so super nachvollziehen lässt. Danach musst du einfach davon ausgehen, dass dein Spiel Schrittweise abläuft. Das hat David ja schon ganz gut erklärt. An sich könntest du ja sogar sogen, pro Frame macht jeder nacheinander seinen Zug/seine Entscheidung. Ganz so schnell wird es ja sicherlich nicht laufen, aber du kannst ja einfach davon ausgehen, dass einmal pro Sekunde jeder Fahrer in einer bestimmten Reihenfolge seinen Zug festlegt. Du hast deine 3 möglichen Züge und musst dann entscheiden wie gut die Situation nach diesem Zug wäre. Bei Tic-Tac-Toe machen die Spieler ja auch nacheinander ihren Zug und du kannst den Spielzustand bewerten. Das musst du dann halt versuchen zu übertragen. Das wird sicherlich nicht ganz einfach sein, aber das hat ja auch keiner behauptet ´
Wie gesagt, versuch dich mal an einem einfachen Beispiel und wenn konkrete Fragen kommen helfen wir gerne. Wenn ichs schaffe gucke ich mir den Algorithmus morgen noch mal an. Dann kann ich dir vielleicht auch noch mal genauere Hilfestellungen geben.