Muss eine RTS-KI deterministisch/reproduzierbar arbeiten?

[Gipsel]

Weiterführung aus dem Mantle-Thread:
Gipsel, die Sache warum RTS Engines reproduzierbare Ergebnisse bringen sollen wird hier sehr Offtopic. Wir können das gerne in einem anderen Thread weiterführen wenn Bedarf besteht.
Wie gesagt, wüßte ich nicht, wieso das unbedingt so sein muß.

[Botcruscher]

Ein bisschen Input würde mich auch interessieren. Eine berechenbare KI wird in einem(fairen) RTS immer verlieren.

[redfirediablo]

Ich wage mal zu behaupten, dass es darum geht das Spiel im Multiplayer auf den Clients synchron zu halten.

Wenn die Engine deterministisch ist, dann muss quasi nur der Input zwischen den Clients abgeglichen werden (geringe Bandbreite). Ist ja auch der Grund warum Replays von z.B. Starcraft II so klein sind.

Bei einem nicht deterministischen RTS wird es hingegen schwierig das Spiel auf 2 Clients synchron zu halten. Da beide Clients nicht zum gleichen Ergebnisse kommen, müsste z.B. ein Client den "Lead" übernehmen und ALLE Positionsdaten der Einheiten etc. müssten dann in hoher Frequenz zum anderen Client geschickt werden (hohe Bandbreite).

Bei einem Singleplayer RTS wird es wohl wurscht sein aber für MP sollte die Engine bei gleichem Input immer das gleiche Ergebnis liefern.

[Szudri]

Warum? Die Einheiten werden ja auf beiden Clients vom Menschen gesteuert. Anders sieht es aus wenn du 2 Clients hast + AI die eigenständig agiert.
Naja, wenigstens weiß man warum die KI mist ist xD

[Gipsel]

Ich wage mal zu behaupten, dass es darum geht das Spiel im Multiplayer auf den Clients synchron zu halten.Für was hast Du denn da KI? NPCs und Wegfindung?
Und noch nicht mal das muß unbedingt deterministisch laufen (zumindest NPCs könnten auf dem Server simuliert werden oder auch auf einem der Spieler-PCs und dann als Update verteilt werden, wie auch die Bewegungen der einzelnen Einheiten der Spieler, wenn das nicht gerade jeweils etliche tausend sind [dann wird es irgendwann eng mit der Bandbreite]).

Aber wir reden ja hier von RTS. Da gibt es eine Menge grundsätzlicher strategischer Entscheidungen (oder auch taktischer), die nicht gerade in den Micromanagement-Bereich fallen, der ja meinetwegen ruhig deterministisch gemacht werden kann. Aber warum kann ein KI nicht mit Zufallskomponenten darüber entscheiden, ob sie jetzt lieber mehr solche oder solche Einheiten baut, wenn es zwei (oder mehr) mögliche Ziele gibt, welches davon atackiert wird, wann genau z.B. ein Rückzug eingeleitet wird usw. Das sind Sachen, die bei einem menschlichen Spieler nicht streng deterministisch sind, sie müssen es bei einer KI auch nicht sein.

[Demirug]

Zuerst zwei paar Dinge vorweg.

1. Es geht um RTS Engines nicht um RTS Spiele. Man kann ein RTS Spiel natürlich auch mit einer FPS Engine realisieren. Das bringt durchaus ein paar Vorteile aber auch Nachteile mit sich.

2. Die Sache ist primär für Multiplayer wichtig. Beim Singleplayer spielt es nur eine untergeordnete Rolle.

Deterministisch bedeutet nicht zwingend vom Spieler berechenbar. In der Regel treffen auch RTS Engines Zufallsentscheidungen. Das wichtige hierbei ist nur das wenn die Spielsession mit dem gleichen Seed initialisiert wurde es bei gleichen Spielerinteraktionen zum gleichen Ergebnis kommen muss. In der Praxis wird man für jede Spielsession einen neuen Seed (häufig ein Zeitwert) wählen.

Warum macht man das ganze nun? Das primäre Problem bei einem RTS im Vergleich zu einem FPS ist die hohe Anzahl der Einheiten. Bei einer FPS Engine schickt der Server ständig alle Änderungen an jedem einzelnen Objekt im Level zu allen Clients. Man setzt hier zwar massiv auf Delta Protokolle und zum Teil auch auf Kompression aber bei einem RTS entsteht bei diesem Protokoll entweder eine sehr hohe Datenlasst oder man muss ein sehr kleines Einheitenlimit setzen.

Eine RTS engine verteilt nun nur die Kommandos der Spieler an alle Clients. Auf allen Clients führen dann diese Kommandos zum gleichen Ergebnis. Das Datenvolumen ist viel kleiner und das Einheitenlimit im Prinzip nur dadurch begrenzt was ein Client berechnen kann.

Ein weitere Vorteil der sich ergibt ist das RTS Engines im Prinzip die komplette Technik für Replays schon enthalten. Man muss nur noch den Teil hinzufügen welcher die Kommandos in ein File speichert und dort später wieder herausholen kann.

Man bezeichnet das ganze auch als "Verteilte synchrone Simulation". Gibt allerdings eine Reihe von lustigen Fallen in die man laufen kann die dann dazu führen das es zur Desyncronisation kommt.

[Trap]

Das sind Sachen, die bei einem menschlichen Spieler nicht streng deterministisch sind, sie müssen es bei einer KI auch nicht sein.
Wenn du die Aussage "Aktionen von menschlichen Spielern sind nicht streng deterministisch" belegen kannst, bekommst du dafür ein Nobelpreis.

[Gipsel]

@Demirug:
Okay. Aber das betrifft das Starswarm-Demo nicht, was der Ausgangspunkt war. Die KIs treffen da höchstwahrscheinlich Entscheidungen mit Zufallskomponenten (was sehr wohl möglich ist, wie Du selber schreibst), weswegen die Runs nicht reproduzierbar sind. Du kannst daran nicht ablesen, wie die im Multiplayer die Positionsupdates zwischen den Rechnern machen. Das ist schlicht unmöglich.

[Gipsel]

Wenn du die Aussage "Aktionen von menschlichen Spielern sind nicht streng deterministisch" belegen kannst, bekommst du dafür ein Nobelpreis.
Für Quantenmechanik gab es schon mehrere. :rolleyes:

[Demirug]

@Demirug:
Okay. Aber das betrifft das Starswarm-Demo nicht, was der Ausgangspunkt war. Die KIs treffen da höchstwahrscheinlich Entscheidungen mit Zufallskomponenten (was sehr wohl möglich ist, wie Du selber schreibst), weswegen die Runs nicht reproduzierbar sind. Du kannst daran nicht ablesen, wie die im Multiplayer die Positionsupdates zwischen den Rechnern machen. Das ist schlicht unmöglich.

Natürlich nicht.

Ich erwarte nur eben als Entwickler wenn jemand eine Demo seiner RTS Engine zeigt das diese mindestens einen deterministischen Modus hat. Noch mehr erwarte ich das wenn man sagt das man die erste echte multithread RTS Engine hat.

Im Vergleich zu dem Aufwand für die Mantle Implementierung wäre das ein Witz gewesen wenn es die Engine kann.

Und wie gesagt selbst mit Zufallsentscheidungen müssen die Runs deterministisch sein wenn die Engine mit dem gleichen Seed gestartet wurde.

[Trap]

Es ist sicher auch wesentlich einfacher die KI zu debuggen und tunen wenn man reproduzierbare Ergebnisse in Testläufen hat.

Das allein wäre für mich ein ausreichender Grund um auch bei etwas höherem Aufwand in der Implementierung daran festzuhalten.

[Gipsel]

Es ist sicher auch wesentlich einfacher die KI zu debuggen und tunen wenn man reproduzierbare Ergebnisse in Testläufen hat.Und wenn sie gegen einen Menschen spielt, schmiert es ab? Das muß man schon robuster auslegen.

@Demirug:
Das sind doch zwei verschiedene Dinge. Ich verstehe nicht, warum eine Enginedemo mit dem Match zweier KIs gegeneinander reproduzierbare Ergebnisse zwischen zwei Runs liefern soll. Das hat auch nichts mit RTS-Engine ja/nein zu tun. Was Du als deterministisch meinst, bezieht sich ja nur auf den Playerinput und der Interpretation dieses auf verschiedenen Rechnern im Multiplayer. Dieser Input wird in der Starswarm-Demo aber über eine bzw. zwei Instanzen einer KI bereitgestellt. Selbst wenn die Reaktion auf die Inputs absolut deterministisch ist, kann die die Inputs simulierende KI immer noch nicht reproduzierbar laufen. Und dafür gibt es sogar durchaus gute Gründe, wie ich meine (bzw. außer dem Benchmarkaspekt keinen dagegen). Oder um Dich zu zitieren, was bei der StarSwarm-Demo vermutlich passieren wird:
Deterministisch bedeutet nicht zwingend vom Spieler berechenbar. In der Regel treffen auch RTS Engines Zufallsentscheidungen. Das wichtige hierbei ist nur das wenn die Spielsession mit dem gleichen Seed initialisiert wurde es bei gleichen Spielerinteraktionen zum gleichen Ergebnis kommen muss. In der Praxis wird man für jede Spielsession einen neuen Seed (häufig ein Zeitwert) wählen.Weswegen jeder Run anders aussieht. Hatte ich übrigens hier schon beschrieben (https://www.forum-3dcenter.org/vbulletin/showthread.php?p=10096778#post10096778).

Oder kurz: Deine Vermutung "nicht simulationsstabil" bzw. "eine der schlimmsten Todesünden im RTS Bereich" ist sehr voreilig und nicht durch die verfügbaren Fakten gedeckt.

[Unicous]

Ich möchte auch noch darauf explizit hinweisen, dass das eine Tech Demo ist. Wie die beiden in ihrer Präsentation mehrmals aufzeigen, wollen sie zeigen wo die Reise hingehen kann.

Ab time code 36:20 gibt er dazu auch Auskunft, auf eine Frage die auf Multiplayer abzielt (den genauen Wortlaut der Frage kann man leider nicht verstehen nur die Antwort darauf)

https://www.youtube.com/watch?feature=player_detailpage&v=QIWyf8Hyjbg#t=2180

Ich finde, in die tech demo wird viel zu viel hinein interpretiert und äußert "deterministische" Aussagen getroffen.

Laut meiner Interpretation ist das nur ein Lastesel um zu schauen was die Engine alles verkraftet. Man hat sich von Ironclad (Sins of a Solar Empire) ein paar Sachen zusammengeklaut(oder sich Raumschiffmodelle basteln lassen?) und damit dann geschaut wie die Engine scaled und wo thresholds sind und man war so zufrieden damit und AMD hat sich auch gefreut, was Vorzeigbares zu haben dass sie dann entschieden haben, das zu veröffentlichen.

[redfirediablo]

Nun, das die Demo nicht Simulationsstabil ist, kann daran liegen das dynamisch unterschiedliche Seeds verwendet werden.

Wäre durchaus möglich ABER dieses Verhalten deutet eher darauf hin, dass ein Hauptproblem der Multithreaded RTS Engine weiterhin nicht behoben wurde!!!

Demirug stellt genau diese Vermutung auf, Beweisen kann er es wie gesagt (noch) nicht.

Nochmal zum mitdenken: deterministisch bei gleichem start seed = wenig traffic da nur Spielerinput übertragen werden muss = kleine replayfiles.

Paradebeispiel: SC II

mieserable Kernskalierung weil die KI (u.a. Wegsteuerung und targeting) Singlethreaded ist, dafür Vorteil der einfachen syncro von Clients und kleine replay files. -> sehr gut Multiplayer geeignet

Es gibt ja einen Grund warum die KI Singlethreaded ist. So ist sichergestellt, das der Berechnungsablauf immer gleich abläuft, da die KI Routinen immer in der gleichen Zeitreihenfolge passieren, d.h. alle Einheiten werden immer in der gleichen Reihenfolge losgeschickt (Wenn z.B. 20 Einheiten ein Bewegungsbefehl gegeben wird). Rein optisch laufen diese gleichzeitig los, real werden diese Bewegungen aber für jede einzelne Einheit sequenziell nach einer immer gleichen Logik deterministisch abgearbeitet und erfolgen Zeitversetzt.

Wenn jetzt 2 Threads parallel Userinput in Einheitenbewegung umwandeln dürfen, dann würde in einer idealen Welt immer erst der eine und dann der andere Thread jeweils eine Einheit verschieben, das Ergebnis wäre zunächst immer gleich. Wenn jedoch aufgrund der Systembelastung jetzt plötzlich ein Thread schneller arbeitet als der andere, ergeben sich minimale Unterschiede da die Wegfindung immer auf den aktuellen "Umgebungsvariablen" ergo Einheitenpositionen basiert. Wenn also Thread 1 schon 5 Einheiten verschoben hat, ergibt sich für Einheit 2 aus dem Thread 2 ein unterschiedlicher Laufweg, als wenn Thread 1 nur 2 Einheiten verschoben hätte -> Ergebnis ist ein anderes, bei gleichem Userinput.

Deshalb kann man auch so gut zusätzliche Physikeffekte in RTS einbauen, wenn diese rein optischer Natur sind. Diese haben keinen Einfluss auf den Spielablauf und lassen sich so wunderbar auf viele Kerne verteilen. Es bleibt dabei, entweder jemand findet einen brillianten Weg KI deterministisch Multithreaded zu berechnen, was bisher aber nur Singlethreaded geht. Oder er hat eine brilliante Idee den ganzen Mist FPS artig zu syncen ohne das die Bandbreite durch die Decke geht.

Deshalb auch die Unterscheidung zwischen RTS und FPS. Beim FPS müssen nur die Positionsdaten der Spieler und der beweglichen Levelgegenstände permanent abgeglichen werden. Das sind z.B. maximal 64 Spieler also 64 Raumkoordinaten.

Bei einem RTS mit 10k Einheiten ist es also quasi unmöglich das ganze so wie bei einem FPS zu machen. Also synced man bei einem RTS (bisher) nur den Userinput, es ergibt sich dadurch aber aufgrund der deterministischen singlethreaded KI egal auf welchem Rechner man das ganze Abspielt das gleiche Ergebnis.

Tja und wie im Videolink zu hören ist, hat scheinbar Obsidian eines der beiden Problem gelöst. Entweder das syncen oder die deterministische multithread KI. Ich tippe mal das hier etwas "getrickst" wird.

Sie werden letztlich nicht alles 1:1 syncen sondern wahrscheinlich nur Einheitengruppen als eine große Einheit zusammenfassen (z.B. eine Jägergruppe), ähnlich company of heroes bloß viel größer. Dieser Einheitengruppe werden jetzt Eigenschaften wie z.B. anzahl der noch enthaltenen Jäger zugeordnet. Diese Einheitengruppen (die eigentlich nur eine Einheit sind) kämpfen jetzt miteinander a la civ. Das was der Spieler auf seinem Bildschirm sieht (mit allen tausend Einheiten und Projektilen) ist quasi nur ein grafischer "Physikeffekt" bzw. eine Live Darstellung die in etwa das wiedergibt, was real im Hintergrund berechnet wird. Das heißt also die Darstellung im Detail unterscheidet sich von Rechner zu Rechner, das Ergebnis des Kampfes ist aber immer gleich weil weiterhin Singlethreaded im Hintergrund berechnet. Die Hauptcpulast geht deshalb für die physikalisch pseudokorrekte Darstellung drauf, die aber nur ein optischer Effekt ist.

Ich wette, dass es nicht möglich sein wird, alle Jäger separat zu steuern! Nur Einheitengruppen wie in COH. Das ganze funktioniert natürlich auch nur für Weltraumrts da hier soviel Platz ist, das nicht auffällt, wenn man bei der Kolisionsabfrage trickst und die Einheiten eigentlich gar nicht alle einzeln berechnet bzw. steuern kann. In SC II kann ich ja die Einheiten des Gegner räumlich blockieren, dies wird bei der Obsidian Engine nicht möglich sein.

[Gipsel]

Nun, das die Demo nicht Simulationsstabil ist, kann daran liegen das dynamisch unterschiedliche Seeds verwendet werden.

Wäre durchaus möglich ABER dieses Verhalten deutet eher darauf hin, dass ein Hauptproblem der Multithreaded RTS Engine weiterhin nicht behoben wurde!!!Jumping to conclusions heißt das im Englischen. Das deutet erstmal auf gar nichts hin, womit sich der Rest erübrigt.
Nochmal zum mitdenken: deterministisch bei gleichem start seed = wenig traffic da nur Spielerinput übertragen werden muss = kleine replayfiles.

Paradebeispiel: SC II

mieserable Kernskalierung weil die KI (u.a. Wegsteuerung und targeting) Singlethreaded ist, dafür Vorteil der einfachen syncro von Clients und kleine replay files. -> sehr gut Multiplayer geeignet

Es gibt ja einen Grund warum die KI Singlethreaded ist. So ist sichergestellt, das der Berechnungsablauf immer gleich abläuft, da die KI Routinen immer in der gleichen Zeitreihenfolge passieren, d.h. alle Einheiten werden immer in der gleichen Reihenfolge losgeschickt (Wenn z.B. 20 Einheiten ein Bewegungsbefehl gegeben wird). Rein optisch laufen diese gleichzeitig los, real werden diese Bewegungen aber für jede einzelne Einheit sequenziell nach einer immer gleichen Logik deterministisch abgearbeitet und erfolgen Zeitversetzt.Das geht auch anders und parallel.
Wenn jetzt 2 Threads parallel Userinput in Einheitenbewegung umwandeln dürfen, dann würde in einer idealen Welt immer erst der eine und dann der andere Thread jeweils eine Einheit verschieben, das Ergebnis wäre zunächst immer gleich.Warum sollen die sich abwechseln? Man muß nur sicherstellen, daß das Ergebnis das gleiche ist, unabhängig von der Reihenfolge, was sehr wohl geht.
Wenn jedoch aufgrund der Systembelastung jetzt plötzlich ein Thread schneller arbeitet als der andere, ergeben sich minimale Unterschiede da die Wegfindung immer auf den aktuellen "Umgebungsvariablen" ergo Einheitenpositionen basiert.Feste Zeitschrittgröße und fertig.
Wenn also Thread 1 schon 5 Einheiten verschoben hat, ergibt sich für Einheit 2 aus dem Thread 2 ein unterschiedlicher Laufweg, als wenn Thread 1 nur 2 Einheiten verschoben hätte -> Ergebnis ist ein anderes, bei gleichem Userinput.Da kann man z.B. ein zweistufiges Update machen (im Prinzip analog zur Integration von Bewegungsgleichungen, da spielt die Reihenfolge der Updates keine Rolle mehr; Entscheidungen werden überall anhand der alten Positionen/Geschwindigkeiten getroffen [die deswegen überall identisch sind], im zweiten Schritt dann die Einheiten wirklich bewegt [logisch gesehen alle gleichzeitig, nicht nacheinander]), Kollisionsvermeidung ist ein wenig tricky, aber alles kein wirkliches Problem in meinen Augen. Bei Molekulardynamiksimulationen (wo Tausende bis Millionen Teilchen miteinander wechselwirken und sich bewegen, natürlich multithreaded) funktioniert das ja auch (praktisch durch Trennung der Berechnung der Beschleunigung [Entscheidungen der KI] von den Positions- und Geschwindigkeitsupdates). Ob die Bewegungen durch Kräfte zwischen den Teilchen oder von deren Entscheidungen abhängig sind, spielt für die Reproduzierbarkeit keine Rolle ;).

Edit:
Und zur Steuerbarkeit einzelner Schiffe: Na klar ginge das. Die haben alle eine eigene kleine KI (agent), dem Ziele vorgegeben werden können. Normalerweise folgen sie der Formation und feuern z.B. nur individuell. Aber es spricht doch nichts dagegen, ein einzelnes kleines Schiff irgendwas getrennt angreifen zu lassen. Das einzige, was man irgendwann schlußendlich limitieren muß, ist die Anzahl der Nutzereingaben (also Zielvorgaben) für die einzelnen Einheiten bzw. Agents. Ein Mensch schafft ja maximal eine Handvoll pro Sekunde (wofür man vermutlich Koreaner sein muß), was man z.B. auch für die "globale" KI als Limit festlegen könnte. Die Berechnung der ganzen Agents würde ja auf allen Rechnern dupliziert (weswegen bei gleichen Eingangsdaten immer das gleiche rauskommen sollte), lediglich der "Nutzerinput" bzw. Entscheidungen der "globalen KI" müssen übertragen werden.

[Demirug]

Oder kurz: Deine Vermutung "nicht simulationsstabil" bzw. "eine der schlimmsten Todesünden im RTS Bereich" ist sehr voreilig und nicht durch die verfügbaren Fakten gedeckt.

Das eine nicht simulationsstabile RTS Engine eine Todesünde ist ist ein Fakt.

Genauso ist es ein Fakt das diese Demo keinen Modus hat der simulationstabile Ergebnisse liefert.

Natürlich kann man daraus jetzt nicht zwingend schließen das die Engine es nicht kann. Es gibt aber auch eigentlich keinen guten Grund keinen entsprechenden Modus einzubauen wenn man die Möglichkeit hat.

[Skysnake]

Zuerst zwei paar Dinge vorweg.

1. Es geht um RTS Engines nicht um RTS Spiele. Man kann ein RTS Spiel natürlich auch mit einer FPS Engine realisieren. Das bringt durchaus ein paar Vorteile aber auch Nachteile mit sich.

Sehen wir denn bei StarSwarm ein RTS Spiel/Eingine?


2. Die Sache ist primär für Multiplayer wichtig. Beim Singleplayer spielt es nur eine untergeordnete Rolle.

Sehen wir denn ein Multiplayer "Spiel"?


bla
Und genau hier machst du wie Gipsel schon richtig gesagt hast einen kolossalen Fehler in meinen Augen. Du nimmst einfach an, dass die "Engine" homogen ist. Wenn man keinen gleichen Ablauf in der Demo sieht, ist die Engine nicht deterministisch. Das ist nen klassischer Logikfehler ala Es reget -> die Straße ist nass und die Straße ist nass -> es regnet ;)

Wir wissen doch gar nicht, welche Entropiequellen es gibt.

Es ist ne Demo zwischen zei Computergegnern.

Da kann der Seed am Anfang immer neu gesetzt werden -> immer anderes verhalten
Die "Nutzer" Eingaben können bei (einer!) der KIs einen seed haben um einen echten User zu simulieren -> immer anderes verhalten

Wir wissen rein gar nichts darüber, wie die Engine im Detail arbeitet, und wo Entropiequellen sind und wo eben nicht. ;)

Natürlich nicht.

Ich erwarte nur eben als Entwickler wenn jemand eine Demo seiner RTS Engine zeigt das diese mindestens einen deterministischen Modus hat. Noch mehr erwarte ich das wenn man sagt das man die erste echte multithread RTS Engine hat.

Im Vergleich zu dem Aufwand für die Mantle Implementierung wäre das ein Witz gewesen wenn es die Engine kann.

Und wie gesagt selbst mit Zufallsentscheidungen müssen die Runs deterministisch sein wenn die Engine mit dem gleichen Seed gestartet wurde.
Wenn alle! Zufallszahlenwerte einen gesetzten Seed Wert haben muss der Run deterministisch sein!

Da reicht aber schon irgendwo in einer verschissenen Zeile Code nen vergessener Seed und aus die Maus.

Ich vermute ja mal stark, das man für den "Benchmark-Modus" einfach nen Bit irgendwo noch setzen müsste damit es deterministisch abläuft und gut ist, wenn keine Bugs drin sind.

Wahrscheinlich wurde aber irgendwo geschusselt, die Demo musste aber raus, und man hat noch genug anderes Zeug zu tun, daher hat das sooooo was von keine Priorität.

[redfirediablo]

Molekulardynamiksimulationen (wo Tausende bis Millionen Teilchen miteinander wechselwirken und sich bewegen, natürlich multithreaded) funktioniert das ja auch (praktisch durch Trennung der Berechnung der Beschleunigung [Entscheidungen der KI] von den Positions- und Geschwindigkeitsupdates). Ob die Bewegungen durch Kräfte zwischen den Teilchen oder von deren Entscheidungen abhängig sind, spielt für die Reproduzierbarkeit keine Rolle ;).


Hmm, ich kenn mich ganz gut mit FEM aus. Ich weiß zwar nicht ob für Fluiddynamik oder Partikelsimmulation ähnlich gerechnet wird aber bei der FEM vermeidet man das Problem indem man diskrete Zeitschritte verwendet und alles schön klein aufteilt. Berechnet wird dann das Element basierend auf den im Zeitschritt zuvor ermittelten Zustandsgrößen (der Umgebung), unabhängig wie sich die Elemente darum herum während des aktuellen Zeitschrittes verändern.

Das ganze ist aber natürlich sehr rechenintensiv und gleichzeitig verwendet man sehr kurze Zeitschritte (bei einer expliziten Berechnung, Implizit gibt es keine echte "Zeit" aber das ist ein anderes Thema)

Man könnte also deterministisch rechnen indem man in zeitlich definierten Abständen für ALLE Einheiten gleichzeitig die neuen Wege berechnet UND Sie währenddessen anhält bzw. eine optische Interpolation der Bewegung vornimmt und diese anschließend korrigiert.

Statt also einmal den Weg vorzugeben und nur über "If" oder ähnliches hin und wieder zu prüfen, ob die Einheit festhängt, muss ständig in kurzen Zeitabständen die Wegfindung für ALLE Einheiten GLEICHZEITIG berechnet werden und während dieser Zeit stehen keine genauen Bewegungsinformationen zur Verfügung.

Das ganze wäre zwar Multithreaded und deterministisch, würde aber insgesamt den Rechenaufwand deutlich erhöhen und gleichzeitig diesen zeitlich sehr ungleichmäßig verteilen -> keine Lösung des Problems!

Meine Theorie lautet: StarSwarm wird im Hintergrund wie gehabt mit wenigen Einheiten(gruppen) deterministisch und singlethreaded berechnet. Das was man "sieht" ist einfach nur eine fancy Repräsentation des ganzen für den Spieler mit einer nicht deterministischen Multithreaded Simulation. Ähnlich einem Rundenstrategiespiel, bei dem während eines "Kampfes" von zwei Einheiten eine Animation abgespielt wird.

[Skysnake]

Ne, der Ansatz ist schon richtig. Du musst "nur" noch ne segmentierung machen.

Die Wegfindung einer Einheit wird ja nicht durch alles auf der Map beeinflusst, sondern nur durch Ereignisse in einem gewissen Umfeld. Das wars dann auch und reduziert massiv die benötigte Rechenleistung. Sowas in der Art macht man z.B. auch bei n-Body Gravity. Da unterscheidet man danach, wie weit etwas von einem entfernt ist. Ist es weit weg, werden viele Partikel als einer angesehen. Die in kurzer Entfernung (relativ zu Masse btw) werden genau berechnet. Die Rundungsfehler sind vernachlässigbar, wenn man es richtig macht.

Und bzgl Zeitschritten. Das sind nicht viele. Du musst ja "nur" die FPS als Iteration nutzen und fertig.