[Browsergame] Separate Kampfberechnung

[glocke]

Hi, ich hatte vor eeeeiniger Zeit mal an einem Browsergame gearbeitet und die dafür notwendige Kampfberechnung in einen extra Thread innerhalb meiner WSGI-Anwendung (habe mit Bottle gearbeitet) gelegt. Leider habe ich mir einige Probleme erzeugt, die ich heute umgehen würde. Da ich im Moment überlege in Zukunft nochmal ein ähnliches Projekt in Angriff zu nehmen, bin ich hier

Eines meiner Probleme war, dass die Kampfberechnung ziemlich rechenintensiv war. Nachdem ich die Kampfberechnung (vor einiger Zeit) aus Neugierde mal komplett analog in C++ implementiert habe, habe ich gemerkt, dass das ganze so extreeeem flott läuft Daher habe ich mich in den letzten Monaten intensiver mit C++11 beschäftigt und bin nun "zurück"

Derzeit überlege ich, wie ich diesen separaten Thread (mittels C++ "innerhalb" der Python-Anwendung) "heutzutage" umsetzen würde. Dabei sehe ich folgende Möglichkeiten:

• C++ einbetten (z.B. via SWIG): Ich baue mir einen Wrapper um die in C++ geschriebene Kampfberechnung. Dabei würde ich die Datenbank via Python ansprechen (Abfragen der bisherigen Spielerdaten, Speichern der modifizierten Spielerdaten).
• C++ als separaten Prozess (als eigenständige Anwendung auf dem Server) laufen lassen: Da ich als Datenbank inzwischen redis ins Herz geschlossen habe (und das eine tolle Publish-Subscribe-Funktionalität) zur Verfügung stellt, würde ich via Python die Kampfberechnung nur noch "auslösen", d.h. in die Datenbank schreiben, dass Kampf XY nun berechnet werden soll. Der separate C++ Prozess würde dann von der Datenbank über das "Auslösen" benachrichtigt werden, kann die Daten abfragen, alles berechnen und die Ergebnisse zurückschreiben.

Habt ihr Erfahrungen in der Richtung? Ich könnte mir vorstellen, dass Variante A (z.B. mit SWIG) "more pythonic" ist; Variante B hat aber aufgrund der "Autonomie" der Kampfberechnung (die sich auf die Art als "Event-Handling" verallgemeinern lässt) auch einen gewissen Reiz. Außerdem muss ich mir kein Interface zwischen beiden Sprachen bauen .. Joa, daher weiß ich gerade nicht welches der "bessere" Weg wäre

Welche Vor- bzw. Nachteile seht ihr für die genannten Varianten? Oder habt ihr noch eine Variante C (oder sogar D ^^) im Kopf?

LG Glocke

[MagBen]

Es gibt noch die dritte Möglichkeit, dass Du mit Numpy in die Nähe der Performance der C++ Implementation kommst.
Bezüglich Deiner zwei Vorschlage halte ich die Swig basierte Lösung für einfacher. In meinen Projekten lagere ich sehr häufig rechenintensive Teile in C++ Modulen aus, die ich mit Swig wrappe, sofern es nicht möglich ist, das ganze mit Numpy zu erledigen.

[DasIch]

Die erste Methode ist weder "mehr pythonic" noch irgendwie einfacher. Die herbei fantasierte dritte Methode mit numpy existiert auch nur wenn man die Kampfberechnung vollständig in Form von Berechnungen mit Matrixen ausdrücken kann, will. Letztendlich würde man aber auch bei einer Python Implementation der Kampfberechnung diese nicht automatisch im selben Prozess wie die Webanwendung laufen lassen.

Du solltest definitiv die zweite Methode bevorzugen. Die beiden Komponenten haben ja vollkommen unterschiedliche Verhalten und Anforderungen. Die Kampfberechnung wird ja im wesentlichen CPU bound sein und wird sich wahrscheinlich nur schwer skalieren lassen. Auf der anderen Seite hast du die Webanwendung die im wesentlichen IO bound ist und die man üblicherweise in mehrere Threads/Prozessen und vielleicht auf mehreren Servern laufen lassen würde.

Dazu kommt dass C++ Code grundsätzlich aus Sicherheitsgründen problematisch ist. Sofern praktikabel ist es daher sinnvoll diesen fern von dem großen Angriffsziel Webanwendung fernzuhalten.

[Sr4l]

@glocke Rein aus Interresse: Könntest du mir kurz das Kampfsystem erklären? Wieviele Einheiten stehen sich gegenüber? Wie viel schaden macht so eine Einheit? Wieviel HP hat sie? So grob erwähnen wie lang Python braucht (Sekunden? Minuten?)?

Es fällt mir gerade schwer mir vorzustellen das es mehr als einige Sekunden dauert.

[glocke]

@glocke Rein aus Interresse: Könntest du mir kurz das Kampfsystem erklären? Wieviele Einheiten stehen sich gegenüber? Wie viel schaden macht so eine Einheit? Wieviel HP hat sie? So grob erwähnen wie lang Python braucht (Sekunden? Minuten?)?

Es fällt mir gerade schwer mir vorzustellen das es mehr als einige Sekunden dauert.

Ich hatte ein RPG-artiges, rundenbasiertes 4 vs. 4 (inkl. KI!) und eine Berechnung dauerte (auf dem Netbook) um die 250-500ms (jaaa Netbook ^^ das sollte eigentlich keine Referenz sein ^^) .. eine analoge C++-Implementierung hat weniger als 1/10 der Zeit zur Berechnung in Anspruch genommen. Sicherlich habe ich bei der Python-Version auch ein paar NoGos eingebaut (ist ja auch schon eine Weile her^^). Aber so die Größenordnung war's

HP und Schadenswerte waren in verschiedenen Größenordnungen und hatten (soweit ich mich erinnere) keinen Einfluss auf die benötigte Zeit. Was Einfluss hatte war die Anzahl der teilnehmenden Charaktere (inkl. ob KI oder nicht).

[jerch]

@Glocke:
Ich schliesse mich DasIchs Einschätzung an. Allein der Skalierbarkeit wegen sollte das nicht innerhalb HTTP-Server-Prozess(-e) laufen. Auch möchte man das Segfault dort nicht sehen, wogegen es bei einem separaten Dienst behandelbar wird. Mit einem der neueren MQ-Protokolle wird auch die Anbindung in C++ zum Nobrainer. Übrigens sind websockets evtl. besser geeignet für das, was Du da vorhast.

Wir hatten mal ein ähnliches Problem mit Heatmap-Generierung in Echtzeit (für Google Maps Overlay). Echtzeit war nötig, da der theoretische Speicherbedarf mehrere PB gewesen wären. Lösung war ein KD-Tree, welcher die Datenpunkte aus der DB sehr schnell mappen konnte. Dies wäre innerhalb eines HTTP-Prozesses undenkbar gewesen (14GB an Zustandsdaten im RAM durch den Baum bei 10Mio. Testeinträgen). Der Dienst hierzu, geschrieben in C++ und angebunden über Unix-Socket, schaffte >8000 Requests/s auf einem i7-2600 im Lasttest (Auslieferung an 256x256 Overlay-Tiles). Das schöne daran, es ist super skalierbar - wenns im Kundeneinsatz nicht reicht, kann man den Dienst auf eine dickere Maschine auslagern oder gar den Baum zerlegen.

Bei einem anderen Projekt (Browserversion als Demo eines Spiels) haben wir die Engine direkt per ctypes eingebunden. Das war sehr einfach möglich, da die Spielebibliothek eine C-API hatte und der Wrapper in 1h geschrieben war. Allerdings ist es null skalierbar und, da die Bibliothek den Spielfortschritt selbst vorhält, auch noch an globale Zustände gebunden, wodurch Multiprozess-HTTP-Server ausscheiden. Da es nur für Demozwecke genutzt wurde, war das kein Problem und der Zeitvorteil überwog die Nachteile.

Edit:
Noch ein paar Tipps - Evtl. macht es Sinn, die anfallenden Daten nicht alle in die DB zu schieben. Der Ansatz, die Kampfberechnung über DB-Trigger zu steuern, klingt erstmal teuer und ist vllt. auch nicht nötig. Hierzu solltest Du Dich fragen, ob Du das wirklich persistent brauchst bzw. welchen Impact die DB an der Stelle hat (DB-Zugriff ist immer teurer als Deine Heapdaten). Zusätzlich noch der Hinweis, dass Du alle Daten vom Client auf Plausibilität prüfen solltest. Gerade bei Spielen wird gerne die Client-Logik unterminiert, um sich einen Vorteil zu verschaffen. Zu guter Letzt - die KI zieht sicher auch einiges an Rechenzeit, evtl. lässt sich mit einem optimierten Suchbaum-Algorithmus da noch was machen. Und falls beim Profiling malloc > 30% der Rechenzeit beansprucht - willkommen im Reich der eigenen Speicherverwaltung. (Wir hatten das Problem bei obigem Spiel mit >60% für malloc, mit Umstellung auf stackbasiert lief die KI dann 6x schneller.)

[glocke]

Noch ein paar Tipps - Evtl. macht es Sinn, die anfallenden Daten nicht alle in die DB zu schieben. Der Ansatz, die Kampfberechnung über DB-Trigger zu steuern, klingt erstmal teuer und ist vllt. auch nicht nötig. Hierzu solltest Du Dich fragen, ob Du das wirklich persistent brauchst bzw. welchen Impact die DB an der Stelle hat

Als DB verwende ich redis, eine In-Memory-DB mit Key-Value-Prinzip. Die verfügt zwar über Möglichkeiten Persistenz zu gewährleisten - aber nicht jeder Write wird nicht immer sofort auf die Festplatte geschrieben (je nach verwendetem Persistenzmodell). Daher sind die Trigger-Sachen relativ flott: Webservice schreibt sie via Socket in die In-Memory-DB, Eventhandler liest sie via Socket aus der In-Memory-DB. Dabei muss ich selbst noch nicht einmal pullen, da Redis' Publish-Subscribe den Listener selber benachrichtigt.