Weltraum Scene Managment und MMORPG Datenbank

ChrisM

HI,

ich programmiere im Moment an einem online Weltraumrollenspiel.

Für das Scene Managment verwende ich einen Octtree und für die Datenbank verwende ich MySQL, d.h. um genau zu sein habe ich schon angefangen, beides zu implementieren, aber langsam frage ich mich, ob das denn wirklich die beste Lösung ist.

Erstmal wegen des Octtrees, ein statischer Octtree kommt für mich natürlich nicht in Frage, sonst hätte ich viel zu viele Nodes. D.h. wiederum, die Unterteilung wird dynamisch gemacht und ein Node wird bis auf einen Kilometer (oder 10?) herunter immer weiter unterteilt, wenn ein zweites Objekt in ihn eintritt, solange, bis in jedem Node nur noch ein Objekt ist. Natürlich müssen auch wieder Nodes verschmolzen werden, wenn sie von Objekten verlassen werden.

Und wegen der Datenbank bin ich am zweifeln, ob ich wirklich eine richtige Datenbank verwenden sollte, oder nicht einfach die Daten von Hand in Dateien abspeichern und nicht dauernd Datenbankabfragen machen sollte, sondern sie direkt im RAM beim Server halte.

Postet doch mal einfach, was ihr von den beiden Sachen haltet und ob ihr bessere Ideen habt!

ChrisM

Sgt. Nukem

Naja, ich würde schon mit MySQL vorlieb nehmen an Deiner Stelle.
Sonst müsstest Du die ganze Funktionalität, die so etwas rentabel macht, selbst implementieren, d.h. diverse Sicherheiten, COMMIT/ROLLBACK, etc.
Natürlich ist es Dir freigestellt, dafür eine (performante) Abstraktionsebene zu basteln.
Ausserdem bleibt es viel ausbaufähiger... falls später doch mal mehr Leute gleichzeitig aktiv sind.
Zudem: Falls es später mehrere Server gibt die auf EINE DB zugreifen, mußt Du den ganzen Verwaltungsaufwand nicht selber coden.
Vielleicht solltest Du ein ganz simples Interface bauen, und das dann in Deiner "Mini-Datei-DB" implementieren, falls Dir MySQL für den Anfang zu komplex ist.
Falls Du Dich dann nachher umentscheidest, mußt Du spieltechnisch nichts mehr umcoden...

ChrisM

Hi,

ok, MySQL ist vielleicht wirklich besser (und auch schneller) als wenn ich das alles von Hand "emuliere". Würde ein Interface dann für dich z.B. so aussehen?

class DatabaseInterface
{
public:
virtual bool isUserExisting(const std::string& sUsername) = 0;
virtual std::string getUserPassword(const std::string& sPassword) = 0;

virtual Ship loadShip(const std::string& sUsername) = 0;  // wenn ein User online geht von DB -> RAM
virtual void saveShip(const std::string& sUsername, const Ship& ship) = 0;  // wenn er offline geht
// ...
};

Dann gibt's nur ein Problem, was ist z.B., wenn ich einen neuen User erstellen will und dazu prüfe ich, ob's den Namen schon gibt. Was ist jetzt, wenn er rein zufällig zwischen dem Schonvorhanden-Check und dem eigentlichen Eintragen von einem anderen Server (aber vorerst wird's ja nur einen geben), der auch auf die DB zugreift, erstellt wird? Hier ist das zwar unwahrscheinlich, aber es könnte in anderen Situationen auftreten.

Sozusagen ist die DB dann nicht threadunsafe, sondern mehrereserverunsafe.

Kann man da mit SQL-Transactions oder so das verhindern?
Und was ist der beste Weg, um eine Datenbank anzusteuern und (blöde Frage), was ist die beste Datenbank?

Was haltet ihr vom Octtree?

ChrisM

TheTester

also ich find ja oracle als datenbank ganz doll *gg*, und odbc wäre wohl der einfachste weg anfragen an eine DB zu stellen...

tschööö

tt

Sgt. Nukem

TheTester schrieb:

also ich find ja oracle als datenbank ganz doll *gg*

Jo, und vor allem so preiswert...

Naja, Du mußt halt aus der "Eintragen"-Methode eine atomare Operation machen...
D.h. währenddessen dürfen keine anderen Eintragungen machen.

Beste Datenbank?! Naja, da hier eh alle nur auf OpenSource stehen gröhlen wohl eh alle nur "MySQL"...
Wundert mich ernsthaft, daß als erstes ORACLE kam... :xmas1:

Wieso nimmst Du für den Anfang nicht erstmal TLiteDB, die schreibt AFAIK einfach in eine Textdatei, Du kannst sie aber schon SQL-like ansteuern...?!

ChrisM

Hi,

ok, danke. Ich werde dann mal morgen nach Sylvester anfangen, die Datenverwaltung zu implementieren.

Nur mit dem Octtree... desto öfter ich darüber nachdenke, desto mehr beschleicht mich der Verdacht, dass meine dynamische Variante eines Octtrees keine gute Idee ist.

ChrisM

Sgt. Nukem

ChrisM schrieb:

Nur mit dem Octtree... desto öfter ich darüber nachdenke, desto mehr beschleicht mich der Verdacht, dass meine dynamische Variante eines Octtrees keine gute Idee ist.

Hmmm... naja. Da kann ich Dir leider nicht wirklich bei helfen... Hab' selber zu wenig Erfahrung mit Scene-Managment.
Aber auf die alten Hasen rapso und TGGC ist sicher Verlaß...

Viel Erfolg weiterhin für Dein Projekt.
Um ehrlich zu sein, hab' ich ja, als ich Dich das erste Mal davon im Projekte-Forum hab' schwafeln sehen, gedacht, das ist wieder so einer, der ist am Anfang mega-motiviert, aber das Projekt endet rupp-zupp in der Mülltonne...
Naja, da das nun schon eine Weile her ist, und Du hier immer noch ernsthafte Fragen zur Implementierung stellst, hat sich diese düstere Vorahnung von mir doch in ziemliche Zuversicht gewandelt...! Bleib' dran...!

:xmas1:

ChrisM

Hi,

naja, dann wart' ich mal auf einen Post von den beiden. Das Problem ist ja weniger die Implementierung vom Octtree an sich, sondern nur die Frage, ob Suchoperationen nach Objekten in einer bestimmten Entfernung noch schnell genug bleiben, wenn die Entfernung zu groß wird. Und solche Suchen müssen regelmäßig durchgeführt werden, oder soll der Planet erst 10km vor dem Spieler auftauchen?

ChrisM

PS: Ich hab von Anfang an gewusst, worauf ich mich da einlasse, aber es geht voran...

TGGC

Sorry, aber ich sehe hier keine echte Frage. Und um eine bessere Idee für dein "Scene Managment" zu haben, weiss ich einfach zu wenig über die Anwendung.

Bye, TGGC

ChrisM

Hi,

die Frage ist, ob jemand eine bessere Lösung kennt...

Und die Anwendung ist folgendes: Es geht um ein Weltraumspiel, in dem tausende von Objekten (auch kurzlebige wie Schüsse/Torpedos), die u.a. Schüsse, treibende Objekte, natürlich Schiffe, Stationen, Planeten usw. irgendwie auf dem Server verwaltet werden müssen. Kollisionsabfrage muss dabei möglichst schnell möglich sein, ebenso das Bewegen von Objekten (also ohne neue Memoryallokation bei jeder Bewegung -> würde zur Lags führen). Außerdem müssen schnell alle Objekte ermittelt werden können, die in einer bestimmten Entfernung zu einem anderen Objekt (nämlich ein Spieler, der auf neue sichtbare Objekte getestet werden soll) liegen.

Falls es als Information hilft: Intern wird jede Position in eine Sektorangabe (eine Sektorlänge = 1km) und eine Position innerhalb dieses Sektors aufgeteilt.

ChrisM

TomasRiker

Kleine Anmerkung: Octree mit einem "t".

ChrisM

Hi,

hmm... kommt der nicht von Oct für Acht (weil acht Childs pro Node) + Tree für Baum? Also müssten es zwei Ts sein...

Du hast aber wahrscheinlich trotzdem recht, Google findet für ein T viel mehr Ergebnisse

ChrisM

Sgt. Nukem

ChrisM schrieb:

Hi,

hmm... kommt der nicht von Oct für Acht (weil acht Childs pro Node) + Tree für Baum? Also müssten es zwei Ts sein...

Du hast aber wahrscheinlich trotzdem recht, Google findet für ein T viel mehr Ergebnisse

ChrisM

Tja, man kann ja Octet auch mit Oc abkürzen...

Ein 6-astiger Baum hört sich toll an: Sextree!

Oder 3: Triptree

..., Triple, Quadruple, Quintuple, Sextuple, Septuple, Octuple, ... - wie geht's weiter!?

TGGC

Ich würde da glaube ich gar keinen Baum benutzen. Wie groß ist ein Schiff im Vergleich zu einem Sektor?

BTW: September, Oktober, wie gehts weiter?

Bye, TGGC

ChrisM

Hi,

die Größe eines Schiffes kann eigentlich beliebig sein, d.h. von zehn Metern bis so vielleicht ein km (also genau ein Sektor). Ist das wichtig? Ich speichere ja eigentlich nur die Mittelpunkte.

ChrisM

PS: Es gibt auch einen unären Baum: Die einfache linked list!

TGGC

Dann würde ich die Kantenlänge mal so ungefähr vertausendfachen und jeden Sektor einzeln betrachten. Soll das eigentlich Echtzeit sein und was genau ist in der DB drin?

ChrisM

Hi,

ja, aber wenn ich die Sektoren so viel größer mache, dann hab' ich wieder ellenlange Listen für jeden Sektor und der Server wird zu langsam.

Wobei Kollisionsabfrage das kleinste Problem ist, denn da kann man ja bei jedem Fehlschlag speichern, wie lang es mindestens dauert, bis eine Kollision stattfinden könnte.

Soll das eigentlich Echtzeit sein

Klar.

was genau ist in der DB drin?

Vorerst nur die Accountdaten wie Name, Passwort und Position, Lagerraum (Inventar) usw. aller ausgeloggten Spieler. Denn die, die eingeloggt sind, werden natürlich im RAM des Servers gehalten, ich kann ja nicht zehn Datenbankzugriffe pro Sekunde und Spieler oder machen...

ChrisM

TGGC

Achso, aber ellenlange Sektorlisten werden nicht langsam? Und was wirklich aufwendig ist, ist doch grad der Sektorwechsel, grade wenn diese in einem Baum sind. Ein Server kann ohnehin nur eine bestimmte Anzahl Spieler verwalten, egal wie genau du es machst. Also machste ein Sektor so groß, das er von einem Server noch ordentlich bearbeitet werden kann und verteilst die dann (evtl. dynamisch). So würde ich das angehen. Sektorwechsel würde ich gar nur über "Sprungportale" erlauben.

Bye, TGGC

ChrisM

Hi,

nein, Sprungportale wollte ich vermeiden. Davon, dass sie im Vergleich zum restlichen Spiel wirklich physikalisch unmöglich sind, ist es auch langweilig, wenn man großen Strecken in wenigen Sekunden zurücklegen kann.

Aber so aufwendig, wie du schreibst, ist der Sektorwechsel gar nicht. Die Objekte werden reference counted gespeichert, d.h. es muss kein Speicher umkopiert werden, sondern nur einige Male im Baum runterrekursiert (geiles Wort) werden, solange, bis es keine weiteren Nodes mehr gibt. Dort wird dann der Smart Pointer eingefügt und im alten Node gelöscht.

ChrisM

TGGC

Du hast ja nach einer besseren Lösung gefragt. Aber wenn dein Spiel sonst "physikalisch möglich" ist, dann wird es wohl ohnehin keiner spielen.

Weder Sektorwechssel noch Kollisionsabfrage sind dein Problem, was denn?

Bye, TGGC