Moin Moin

Ich arbeite gerade an der neuen Version meines Browsergames.
Bevor ich unprofessionelle Entscheidungen treffe, dachte ich mir, dass ich doch mal nachfrage

Problemstellung:
- Truppen o.ä. soll von A nach B kommen
- wenn andere Truppen den Weg kreuzen muss bekannt sein wann und wo
- wenn ein Spieler auf ein gebiet "schaut" muss man wissen ob da gerade Truppen sind
- wenn ein Haus gebaut wird o.a. Hindernisse entstehen muss der Weg geändert werden

Anforderungen:
- speicherschonend
- schnell
- MySQL als Datenbank (wenn es besser ist kann natürlich auch in Dateien gespeichert werden)
- Cronjob alle 5min (kann geändert werden)

Schon vorhanden:
- A* Algorithmus zur Wegfindung
- Umlaufen von Hindernissen (zum Zeitpunkt der Berechnung)
- zu sehen hier: Beispiel (Beim neu Laden wird automatisch neu berechnet)

Ansätze:
Ich könnte jetzt natürlich bei jedem Seitenaufruf alle Wege neu berechnen - Kollisionen zu diesem Zeitpunkt bemerken und abarbeiten - müsste somit nur Start, Ziel, Startzeit, Geschwindigkeit speichern.
Das ist natürlich rein von der Leistung her nicht zu machen.
Anderer Ansatz wäre den gesamten Weg jeder Einheit in der DB (oder einer Datei) zu speichern - und bei jedem Wegpunkt die Zeit dazu - neu berechnet werden müsste dann beim Bau eines Hauses (sofern die Koordinaten des Hausbaus sich auf dem Weg befinden) oder beim Losschicken anderer Einheiten (sofern die Wege sich kreuzen).
Auch wäre es vllt möglich zur die Wegpunkte der nächsten 5min zu speichern und dann immer vom letzten Wegpunkt aus neu zu berechnen (Cronjob).

Also, was denkt ihr? Es gibt ja schon unzählige (auch andere Anwendungen als Spiele) wo Wege gespeichert werden müssen - wie wird das da gemacht?


Dankö für eine anregende Diskussion

lenny

ps: Programmiersprache ist PHP - aber das ist ja nebensächlich, daher in diesem Forum.

Damit wir dich nicht ganz enttäuschen, fange ich jetzt mal an mit dir zu reden. Am praktischsten wäre doch, wenn du den Ausgangspunkt und den Zielpunkt sowie die Geschwindigkeit deiner Truppen für jede Truppe/Bewegung speicherst. Die genaue Position kannst du doch dann jedes Mal neu berechnen, was doch keine großen Ressourcen frisst.

Wenn ich Start, Ziel, Startzeit und Geschwindigkeit speichere - dann muss ich bei jedem Gebäudebau, Truppenverschieben, Monsterbewegung - einfach bei allem - die Route von jeder Einheit neu berechnen die gerade unterwegs ist.

Denn bei meinem Spiel schickt man die Truppen nicht los und sie sind irgendwann da (ala ogame, stämme etc.) sondern die Truppen kann man auf der Karte sehen - wo genau sie sich gerade befinden - auf der Karte angreifen, ihnen eine Mauer in den Weg stellen etc.

Und bei jeder Aktion den A* durchlaufen zu lassen nur um zu schauen ob genau auf diesem Feld wo gerade etwas gemacht wird gerade ein Trupp ist frisst dann doch zuviele Ressourcen

ps: danke für deine antwort - nu fühle ich mich net mehr so allein

Vielleicht könntest du beim Erstellen einer Truppenbewegung alle Hindernisse vorausberechnen und die IDs der einzelnen Objekte speichern. Wenn eins dieser Objekte sich verändert, dann speicherst du diese und berechnest es für die betroffenen Truppenbewegungen die Daten neu. Somit hast du nicht jedes Mal den Aufwand alles neu zu berechnen.

Also beim Start alle Gebäude, Truppen etc. die im Weg stehen berechnen ist nicht möglich - da ja nichts im Weg steht - der A* läuft ja um alles rum - ich könnte natürlich alles +-5quadrate drum rum nach Objekten absuchen und diese Abspeichern - aber das ist ja dann eine noch größere Datenmenge (und Berechnungsaufwand) als nur den Weg zu speichern.

Wenn ich allerdings den ganzen Weg speicher (z.B. 1000 spieler, jeder 3 Truppenbewegungen über 20 quadrate = 1000*3*20 = 60.000 datensätze à RoutID,x,y,timestamp) ist das dann nicht auch ein wenig viel für eine MySQL innoDB?
Der Vorteil wäre, dass ich beim Bau eines Gebäudes etc. nur schauen müsste ob x,y in der Tabelle vorhanden ist - und wenn ja dann ab dem vorherigen Schritt der Route die Route neu berechnen.

Was ist mit der dritten Möglichkeit? (immer nur ~5 Schritte speichern und dann neu berechnen)

Was mein Problem mit dem vielen Speichern ist, ist dass du verdammt viele Anfragen, Löschungen und Aktualisierung an deine Datenbank senden musst. Bei meiner ersten Methode hast du den Vorteil, dass es deine Datenbank kaum belastest, denn die Rechenarbeit kannst du zwischen PHP und MySQL aufteilen. Versuch mal das als Grundgedanken zu nutzen und darauf einen effizienten Algorithmus zu bauen. Vieles kannst du nämlich über JOINs und verschachtelte Querys lösen. Und Ansichten (VIEWs) kann ich auch nur empfehlen.