nicht angemeldet
Programm für optimale Baureihenfolge bei RTS Spielen entwickeln
Hallo,
vorweg: Das Thema an sich hat eigentlich nichts mit HTML oder Webentwicklung zu tun, sondern eher mit Algorithmen.
Ich poste es trotzdem mal hier, da hier viele kompetente Leute rumlaufen, und sonst auch viel offtopic gepostet werden.
Einige wissen sicherlich was RTS Spiele sind und wie sie funktionieren.
Man hat mit Resourcen zu wirtschaften (z.B. Gold, Holz, Gas, Mineralien, usw.), und von dem Erwirtschafteten kann man sich Kampfeinheiten, Produktionsgebäude oder andere Sachen (z.B. Erforschungen) kaufen oder man kurbelt die eigene Wirtschaft an, in dem man mehr Arbeitereinheiten baut.
Konkret ziele ich z.B. auf sowas wie Starcraft oder Warcraft ab.
Dabei gibt es eine bestimmte Baureihenfolge. Einheit X kann erst gebaut werden, wenn Gebäude Y gebaut wurde, welches wiederum Gebäude Z als Voraussetzung hat. Alle Bauaktionen kosten Zeit und die Schwierigkeit liegt u.a. darin, die Zeiten optimal auszunutzen, also wenn Gebäude Z gerade fertig gestellt ist, dass dann auch sichergestellt ist, dass man die Resourcen hat um Gebäude Y direkt im Anschluss zu bauen. Andernfalls wäre es nicht optimal.
Nun hab ich mir überlegt, es ist doch viel schlauer und exakter, wenn man sich gewisse Strategien ausrechnen lässt, als dass man sie durch viel Spielen und Erfahrung erlernt und langsam optimiert.
Eine Strategie sei z.B. einfach mal so etwas: 5 Einheiten X, 4 Einheiten Y gebaut und Entwicklung Z erforscht zu haben.
Die Frage ist nun, da es sich um ein Spiel, bei dem es auf die Zeit drauf ankommt, handelt: Welcher Weg führt am schnellsten zu diesem Ziel?
Was ist also die optimalste Baureihenfolge?
Meine Idee war nun, ein Programm zu schreiben, das alle Objekte des Spiels kennt und z.B. o.g. Strategie als Input bekommt.
Gebäude X sei dann z.B eine Klasse mit Eigenschaften für Baukosten, Baudauer und Voraussetzung, um es überhaupt bauen zu können.
Klasse "Arbeiter" hätte weiterhin noch die Eigenschaften, die angibt, wie viel Zeit sie brauchen, um X Resourcen abzubauen.
Das Programm soll dann z.B. entscheiden: Wann baue ich einen Arbeiter, ab wann fange ich an Resource X abzubauen, wann baue ich Gebäude X, ..., baue ich lieber spät 2 Produktionsgebäude (die dafür dann parallel produzieren können) oder lieber früh 1 Produktionsgebäude, um am Ende 5 Einheiten zu haben? usw...
Die grundsätzliche Frage wäre: Wie programmiert man sowas? Also woher weiß das Programm, dass es sich vom Optimum wegbewegt?
Muss man da mit Rekursion arbeiten und einfach alles mal ausprobieren (Brute Force)?
Geht man an das Problem mit genetischen Algorithmen an?
Danke für Ideen + Gruß!
-
Grüße,
ekligste lineare optimierung mit ewigen rekuirsionen :/
mit einem blatt papier bist du schneller dran - wobei wenn du kampfeinheiten komplett ignorierst, und nur arbeiter/gebäuden berücksichtigst, müsste es gehendu brauchst erst die wunshckette der gebäuden - durch rekursion kriegst du die.
dann hast du eine reihenfolge von einheitenbeträgen die nötig sind,
anshcließend rechnest du den schnellsten weg vom knoten zum knoten mit der bedingung n+1 arbeiter n mal durch^^.
kan man aber sicher optimaler löser.
MFG
bleicher -
Hey Christian,
Konkret ziele ich z.B. auf sowas wie Starcraft oder Warcraft ab.
hängt deine ganze Berechnung nicht extrem vom Verhalten des Gegners ab?
Ich mein wenn er einen "Scouter" los schickt und der glücklicherweise 3 deiner Arbeiter erledigen kann, bricht dein Konzept schon zusammen oder du musst neu berechnen. Das zwingt dich aber in eine defensive Lage.Umgedreht, kannst du natürlich auch "scouten" und hast entsprechend weniger Ressourcen um andere Dinge zu erledigen. Dafür hast du mehr offensive Möglichkeiten, die wieder neu berechnet werden müssen.
Nun hab ich mir überlegt, es ist doch viel schlauer und exakter, wenn man sich gewisse Strategien ausrechnen lässt, als dass man sie durch viel Spielen und Erfahrung erlernt und langsam optimiert.
Da liegt aber der Hund begraben, weil sich normalerweise jedes Match anders spielt. Hunderte bis tausende mögliche Spielabläufe inklusive Abstraktionen zu berücksichtigen, ist sicher nicht einfacher, als viel zu spielen und Erfahrung zu sammeln. Daher ist Mensch der Maschine in den meißten Spielen auch klar überlegen.
Die grundsätzliche Frage wäre: Wie programmiert man sowas? Also woher weiß das Programm, dass es sich vom Optimum wegbewegt?
Muss man da mit Rekursion arbeiten und einfach alles mal ausprobieren (Brute Force)?Ja, massenhafte Rekursionen.
Geht man an das Problem mit genetischen Algorithmen an?
Ja. Interessant für dich ist vielleicht auch der Minimax-Algorithmus.
Grüße, Matze
-
Hi,
hängt deine ganze Berechnung nicht extrem vom Verhalten des Gegners ab?
Ich mein wenn er einen "Scouter" los schickt und der glücklicherweise 3 deiner Arbeiter erledigen kann, bricht dein Konzept schon zusammen oder du musst neu berechnen. Das zwingt dich aber in eine defensive Lage.Extrem ist relativ. Es ging mir nur darum, wie ich am schnellsten z.B. einen Dark Templer Drop machen kann, ohne Beachtung des Gegners.
Wenn man Gegner mich bei meinem Plan stört, muss man halt anders spielen, aber es ging hier eben nur um die Theorie.Das Ganze scheint schon ne harte Nuss zu sein. Lineare Optimierung hört sich zwar gut an, aber wenn man sich da etwas einliest, versteht man schnell vor lauter mathematischen Formeln nichts mehr :-(.
Gruß!
-
hängt deine ganze Berechnung nicht extrem vom Verhalten des Gegners ab?
Ich mein wenn er einen "Scouter" los schickt und der glücklicherweise 3 deiner Arbeiter erledigen kann, bricht dein Konzept schon zusammen oder du musst neu berechnen. Das zwingt dich aber in eine defensive Lage.Extrem ist relativ. Es ging mir nur darum, wie ich am schnellsten z.B. einen Dark Templer Drop machen kann, ohne Beachtung des Gegners.
Wenn man Gegner mich bei meinem Plan stört, muss man halt anders spielen, aber es ging hier eben nur um die Theorie.Das Ganze scheint schon ne harte Nuss zu sein. Lineare Optimierung hört sich zwar gut an, aber wenn man sich da etwas einliest, versteht man schnell vor lauter mathematischen Formeln nichts mehr :-(.
Ich kenne zwar Starcraft nicht, aber normalerweise sammeln sich doch die Rohstoffe auch nicht immer gleich schnell, weil die Rohstoffe/Rohstofflager je nach Karte unterschiedlich weit weg sind und sowieso die Wege der Arbeiter nicht immer gleich sind. Das macht solche Spiele ja gerade so spannend ;)
-
Richtig.
Das ist alles schoene Theorie. Real muesstest Du die Karte und ihre Gegebenheiten kennen. Entfernung der Rohstoffe zum Lager, Geschwindigkeit der Arbeiter, Menge der Ressourcen, ... Baut man lieber ein neues Lager in der Naehe der Ressourcen?
Schon ne "Testversion" von Starcraft 2 in den Haenden, was?
Eins ist mal sicher. So gern ich auch SC gespielt habe, SC2 gehoert wieder mal zu den Spielen die ich nicht kaufen werde. Soviel Geld verdiene ich nicht, dass ich mir eben mal, - was soll es kosten? 60 Euro? leisten koennte, selbst wenn ich wollte. Vielleicht spaeter mal. Wenns billiger ist.
--
"Die Diebesgilde beklagte sich darueber, dass Mumm in aller Oeffentlichkeit behauptet hatte, hinter den meisten Diebstaehlen steckten Diebe."
- T. Pratchett-
Tach,
Eins ist mal sicher. So gern ich auch SC gespielt habe, SC2 gehoert wieder mal zu den Spielen die ich nicht kaufen werde. Soviel Geld verdiene ich nicht, dass ich mir eben mal, - was soll es kosten? 60 Euro? leisten koennte, selbst wenn ich wollte. Vielleicht spaeter mal. Wenns billiger ist.
der Preis hätte mich (in diesem speziellen Falle) nicht abgeschreckt, aber ich habe meine schon lange bestehende Vorbestellung letztens wegen der zwingenden Bindung ans Battle.net storniert.
mfg
Woodfighter-
Tach,
Eins ist mal sicher. So gern ich auch SC gespielt habe, SC2 gehoert wieder mal zu den Spielen die ich nicht kaufen werde. Soviel Geld verdiene ich nicht, dass ich mir eben mal, - was soll es kosten? 60 Euro? leisten koennte, selbst wenn ich wollte. Vielleicht spaeter mal. Wenns billiger ist.
der Preis hätte mich (in diesem speziellen Falle) nicht abgeschreckt, aber ich habe meine schon lange bestehende Vorbestellung letztens wegen der zwingenden Bindung ans Battle.net storniert.
Ach das auch noch? Tja. So wird das nix. Irgendwie ueberkommt mich immer mehr das Gefuehl, die Spielehersteller wollen keine Games verkaufen. Aber gleichzeitig isses ja wohl auch so, dass viele Leute sich immer lieber unsinnig ueberall anmelden.
Eigentlich sollte man denken, dass Spiele die z.B. Windows Live benoetigen nicht verkauft werden. Ich kenne auch persoenlich Leute die sehnsuechtig auf ein Spiel gewartet haben um es dann wegen sowas nicht zu kaufen oder installieren. Komischerweise scheint das aber die Masse nicht abzuhalten.
--
"Die Diebesgilde beklagte sich darueber, dass Mumm in aller Oeffentlichkeit behauptet hatte, hinter den meisten Diebstaehlen steckten Diebe."
- T. Pratchett
-
-
-
-
Grüße,
Extrem ist relativ. Es ging mir nur darum, wie ich am schnellsten z.B. einen Dark Templer Drop machen kann, ohne Beachtung des Gegners.
Wenn man Gegner mich bei meinem Plan stört, muss man halt anders spielen, aber es ging hier eben nur um die Theorie.Das Ganze scheint schon ne harte Nuss zu sein. Lineare Optimierung hört sich zwar gut an, aber wenn man sich da etwas einliest, versteht man schnell vor lauter mathematischen Formeln nichts mehr :-(.
lass den kak - linearer ablauf macht nur beim rush sinn, und darktemplars zum rushen - das ist unrrealistisch, deine basis wird wahlweise von zerglings oder panzern überrolt eher du ausreichend von den viehern hast - vor allem gegen zergs bist du in 1-2 tot - die overlords machen die sichtbar, zerglingschwärme sind gegen große dunkle arhone effektiv
MFG
bleicher
-
-
