Speichern von erkundeten Wegen (Graphen)

Hallo miteinander,

ich bin gerade bei einigen Voruntersuchungen für ein Browsergame und dort auf ein Problem gestoßen. Da es so wenig Strategiespiele im Weltraum gibt, wollte ich diese "Lücke" nutzen und selbst in die Richtung entwickeln.

Eine Besonderheit ist die zu Grunde liegende Karte. Hier gibt es zwischen Sonnensystemen vorgegebene Verbindungen (Subraumrouten oder wie man es auch nennen will). Jedes Sonnensystem hat so 2-6 Verbindungen zu anderen Sonnensystemen.  Das ergibt einen tollen Graph, auf dem man dann sehr angenehm Algorithmen wie A* und Kruskal anwenden kann. Soweit so gut.

Das Backend des Spiels soll in Java realisiert werden. Als Datenbank will ich die Graphendatenbank neo4j verwenden - wenn man schon mal perfekte Graphen hat.

Den Graph mit Sonnensystemen und ihren Verbindungen kann ich mühelos anlegen und wunderbar verwalten. Allerdings wäre es schön, wenn ein Spieler nicht alle Systeme und Wege gleich sehen würde. Er soll sich das Wissen schon selbst erarbeiten und die Welt erkunden. Nur wie bringe ich das geschickt in meiner Datenbank unter?

Bei einem Ein-Spieler-System wäre es kein Problem, ich könnte ein Attribut für Wege und Sonnensysteme einführen, welches die Sichtbarkeit angibt und den A*-Algorithmus anpassen. Aber bei einem Mehrspieler-System bin ich da gerade am verzweifeln. Mit Blick auf den A* fällt mir einfach kein guter Weg ein, der die Performance nicht zusammenbrechen lässt.

Habt ihr vielleicht Ideen wie ich das möglichst geschickt umsetzen kann? Über generelle Anmerkungen würde ich mich natürlich auch freuen :)

Vielleicht kann jeder User seinen eigenen Graphen haben der während der Erkundung immer weiter ergänzt wird

Im Großen und Ganzen sehen die meisten Spieler sowieso nur einen kleinen Ausschnitt des gesamten Weltraums?!

Damit sollte sich der Speicherbedarf in Grenzen halten.

Ist ein System 200 Spielern bekannt, würde das bedeuten ich hätte 201 mal das System in der Datenbank. Vom Speicherverbrauch abgesehen wäre es ein riesiger Aufwand da Konsistenz zu wahren.

Bei Einheiten in einem System würde eine Kante des Typs stationiert zwischen Flotte und System ausreichen. Bei Replikation müsste ich dann mehrere hundert Kanten aktualisieren, das ist nicht praktikabel :(

Ich hab keine Ahnung von "Graphen-Datenbanken" ... Darum rate ich einfach nur mit.

Was denn wenn jeder "entdeckte" Planet im User-Graph eine Kante zum "echten" Planeten im Kartengraphen hält? Dann könnte man ziemlich fix herumtraversieren und auch alle stationierten Schiffe finden.

Auf die Idee bin ich noch nicht gekommen, ich hätte damit also praktisch einen "Schattengraph" pro User, der direkt mit dem eigentlichen Graphen verbunden ist. Sichtbarkeit und Wegfindung kann ich dann auf dem Schattengraph erledigen, zentrale Ereignisse auf dem eigentlichen Graphen.

Ich glaube das könnte funktionieren, auch wenn es weiterhin viel Redundanz und Aufwand bedeutet. Sobald ich Zeit hab werde ich auf jeden Fall mal einen Test für die Datenbank schreiben und schauen, wie sich die Lösung so verhält.

Vielen Dank schonmal :) Weitere Ideen sind natürlich immer willkommen. 

Zu den Graphen-Datenbanken: Im Wesentlichen kann man sich vorstellen, das der Graph den man auf Papier zeichnen würde eins zu eins in der Datenbank abgelegt wird. Beliebe Knotentypen (wie zum Beispiel eine Stadt) können über Kanten (Landstraße, Autobahn, Schiene) verbunden werden und Knoten und Kanten können beliebige Attribute haben. 

Die einfachste Lösung wäre es dein Universums-Graphen auf einen ungerichteten Baum zu reduzieren. Dieses ist ist auch leicht durch eine Story zu begründen...mit einem zentralen Hub...vielleicht die gute alte Erde.

Ein Baum hätte den Vorteil, dass es zwischen zwei Knoten immer genau einen Weg gibt. Das verringert die Komplexität aller deine Anfragen immens, da ein Spieler, der wissen will, wie und ob er von A nach B kommt dies sehr einfach erfahren kann. Denn:

• eine statische, vorberechnete kürzeste Wege Matrix ist einfach zu erstellen...die Laufzeit zum Finden eines kürzesten Weges liegt damit immer in O(a), mit a = der länge des kürzesten Weges.
• für jeden Spieler muss nur eine Liste der bekannten Systeme gespeichert werden (z.B. serialisiert in der Usertabelle abgelegt

Frage ein User an ob er von A nach B kommen kann, so wird der kürzeste (es gibt ja nur einen) Weg berechnet in O(a) Zeit. Das Ergebnis ist eine Liste von Subsystemen, über die gesprungen werden muss. Diese Liste wird mit den bekannten Subsystemen in der Liste der bekannten Systeme des Benutzers abgeglichen...fertig ist das Ergebnis...entweder kennt er alle Subsysteme, oder nicht.

Desweiteren kann für die Anzeige der bekannten Systeme / der Umgebung des Spielers eine einfache Breitensuche auf dem Baum erfolgen, die Knoten nur zur Worker-Queue hinzufügt, wenn er sie auch kennt...daher wird dieser Algorithmus immer in O(b) terminieren, wobei b die Anzahl der bekannten Systeme ist...auch eine durchaus akzeptable Laufzeit.

Mein grosser Tip ist also für dich: Modelliere dein Universum als ungerichteten Baum und nicht nur als Graphen (jaja...nen Baum ist auch ein Graph) ohne Restriktionen. Das macht dein Problem seeeeeehr überschaubar und leicht beherrschbar. Also... KISS ...

BIs denne...

Maxx

P.S.: Deine Graphenalgorithem in deine Datenbank auszulagern halte ich für eine sehr schlechte Idee...jedenfalls solange, wie du nicht vorher ausgiebig darüber nachdedacht hast, ob du das nicht effizient im Speicher erledigen kannst.

Leider ist dein Vorschlag mit dem ungerichteten Baum nicht hilfreich, weil es ein ganz anderes Prinzip ist. Die Karte verliert an Glaubwürdigkeit und an Dynamik; eigene Routen können nicht mehr errichtet werden, Routen können nicht mehr blockiert werden, verschiedene Routen (kurz und durch Feindesland oder lang und sicher) sind nicht möglich usw. Es passt einfach nicht zum Spielprinzip und schränkt die Möglichkeiten zu sehr ein.

Ich glaube aber du hast mich generell teilweise missverstanden. Da ich keine relationale DB nutze gibt es keine Tabellen, die ganze DB besteht aus Graphen. Die Graphendatenbank ist dementsprechend darauf ausgelegt hochperformant Graphen zu bearbeiten und zum Beispiel Wege zu finden, wobei der A*-Algorithmus selbst in Java implementiert ist und per lazy-select entsprechende Knoten erhält. Auch bei tausenden Knoten ist eine Wegfindung so kein Problem.

Auch wenn es für mich nicht relevant ist, warum verzichtest du auf die erste Normalform und speicherst serialisierte Listen ab?

Original von Phoenix1988

Ich glaube aber du hast mich generell teilweise missverstanden. Da ich keine relationale DB nutze gibt es keine Tabellen, die ganze DB besteht aus Graphen. Die Graphendatenbank ist dementsprechend darauf ausgelegt hochperformant Graphen zu bearbeiten und zum Beispiel Wege zu finden, wobei der A*-Algorithmus selbst in Java implementiert ist und per lazy-select entsprechende Knoten erhält. Auch bei tausenden Knoten ist eine Wegfindung so kein Problem.

Ich schau mir die Sache unter dem Gesichtspunkt der Performance an. Meine Empfehlung ist es zuerst zu evaluieren, ob du dein Universum nicht im Speicher halten kannst und dann darauf deine selbst geschriebenen Algorithmen abzusetzen (sei es nun für kürzeste Wege oder Umgebungssuche). Dieser Vorschlag klammert die Persistenz völlig aus...

Ich hab mir jetzt mal schnell Neo4J angeschaut und gesehen, dass das Ziel ist die Graphen komplett im Speicher zu halten...was bei dir ja sicherlich machbar ist...insofern passt das ja...

Das eine Wegfindung bei tausent Knoten kein Problem ist wage ich mal zu bezweifeln...ausser du peilst nur wenige gleichzeitige Benutzer an. Ich habe in meinem Spiel ebenfalls ständige Suchen auf Graphen für die Gegner-KI zu laufen und das zieht ab einer bestimmten Anzahl gleichzeitiger Zugriffe schon an der Performance...vielleicht mal ein Lasttest mit JMeter laufen lassen. Ich hab allerdings auch keine Ahnung, wie gross der Ausschnitt sein wird, den deine User jeweils von der Karte sehen werden und wie häufig diese Anfragen an deinen Graphen haben...bei mir sind es sehr viele pro Aktion.

Da ich keine relationale DB nutze

Wo speicherst du für einen Benutzer die Anzahl an Schiffen, Produktionsanlagen, Verteidigungsanlagen, ... (was auch immer man so in deinem Spiel produzieren/kaufen kann...)? Ich bin nicht davon ausgegangen, dass das alles als Properties in deinem Graphen hängt...und wenn es doch da drinnen hängt (z.B. wie buhrmi vorgeschlagen hat)...wie gross können diese Daten pro User werden und ist dann immernoch sichergestellt, dass der komplette Graph im Speicher gehalten werden kann...wenn nicht wird neo4j dank des Lazy Loadings krass inperformant (auch trotz LRU Cache, wenn genügend viele Benutzer gleichzeitig online sind)...aber zu dem Thema gibts in der Doku von neo4j ja einiges zu lesen und ich hab auch keine Ahnung, auf was für einer Kiste du dein Spiel laufen lassen willst.

Auch wenn es für mich nicht relevant ist, warum verzichtest du auf die erste Normalform und speicherst serialisierte Listen ab?

Weil man irgendwann merkt, dass die Normalfomen kein so heiliger Gral sind, wie es einem im Studium gepredigt wird....genausowenig wie ACID...besonders, wenn man irgendwann an den Punkt kommt, wo es einfach nur um Performance geht...da sind dann auch Redundanzen wieder ok oder columns mit zusammengesetzten Werten...natürlich nur, wenn man auch weiss, was die Konsequenzen sind..  :)

Ich bin davon ausgegangen, das nur eine Liste von Ids gespeichert wird und Abfragen wie: "Kennt Benutzer A das System a73h?" oder "Welche Benutzer kennen das System a73h?" nicht relevant sind, ich also diese Daten nicht in strukturierter Form in der Datenbank brauche, weil ich eh wenn dann immer alle (für einen Benutzer) brauche. Ansonsten würde es halt ne weitere Relation für deinen User geben.

Wenn du alternativRouten und Blockierungen als Requirements hast, dann kommt man natürlich an nem vollen Graphen nicht vorbei...das mit neo4J gefällt mir, besonders, dass die gängigen Algorithmen gleich mitgeliefert werden in der Graph-algo Komponente.

Bis denne...

Maxx

Ich weiß das alle Empfehlungen wie Normalisierungen und dergleichen nicht in Stein gemeißelt sind. Da ich im Data Warehouse/Business Intelligence-Bereich tätig war/bin, kenne ich das gut. Du sagst ja selbst, man muss die Konsequenzen kennen und ohne das Konzept und den Einsatzzweck zu kennen, kann man doch die Konsequenzen nicht abschätzen. Aus Performance-Sicht hast du Recht, aber es passt nicht alles zum Einsatzzweck :)

Schiffe werden eher rar sein und entsprechend wertvoll. In der DB werden sie auch als Knoten dargestellt. Bisher bin ich mit der Performance auch sehr zufrieden, obwohl ich es nur begrenzt unter Last testen konnte. Wenn das Spiel realisiert werden würde, sieht der Plan vor neo4j komplett in-memory zu betreiben. Entsprechend sind ein paar GB Hauptspeicher auch vorgesehen.

Auf jeden Fall schon mal danke für die Anregungen, ich werde mir JMeter sicher anschauen.