Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Werbeanzeige

Nox

Supermoderator

  • »Nox« ist der Autor dieses Themas

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

1

11.09.2007, 14:13

Netzwerk-MemSync Algo

Hi,
ich schlage mich nun seit gut einem Jahr mit Ideen für einen gescheiten MemorySync-Algorythmus rum und bin irgendwann auf eine Lösung gekommen. Das Problem ist nur, dass er schlichtweg zuviel Leistung frisst, aber vielleicht hat ja jemand von euch den rettenden Gedankenblitz.

Nun will ich erstmal die Anforderungen an den Algorythmus erleutern:
-Der Memsync-Algo soll nur in Richtung Server->Client funktionieren
-Es soll nur ein Paket pro Frame und pro Client geschickt werden(Daten sollen also gesammelt werden)
-Das System muss mit mehreren Threads klar kommen(wo da das Problem liegt, erleutere ich noch)
-Es soll möglichst resourcensparend sein

Die aktuelle Lösung sieht wie folgt aus(falls was unverständlich ist, bitte einfach sagen):


Jedes Objekt, was übers Netzwerk geschickt werden soll, wird von einer Klasse DatenElement abgeleitet. Diese hat eine eindeutige ID, um die Objekte übers Netzwerk eindeutig identifzierbar zu machen. Auch hat die Klasse einen Datenbuffer um die serialisierten Daten zwischenspeichern zu können. Dieses Zwischenspeichern muss threadsafe sein, damit der Netzwerkthread, die Daten auch dann sammeln zu können, wenn die anderen Threads gerade ihr nächsten Frame durchlaufen. Wenn sich die Daten im Buffer geändert haben, wird das Attribut Version um 1 erhöht.

Weiterhin gibt es die Klasse MemExServerClient, welche die beim Server angemeldeten Clients repräsentiert, und die Klasse MemExServerThread, von welcher die Klassen mit den Threads abgeleitet werden müssen. Die Verbindung zwischen den Clients und den Threads erledigt die Klasse MemExServer_Thread_Client. Dies ist nötig, weil die Threads die DatenElemente updaten und kein anderer Thread derweile auf die DatenElemente zugreifen darf. Denn bis auf die Datenbuffer der DatenElemente sind weder die Methoden noch die Attribute noch die Struktur der DatenElemente threadsafe. Da aber die Klasse MemExServerClient wissen muss, was der Client an Daten braucht, updaten die Threads auch die MemExServer_Thread_Client. Beim Update wird eine Liste für jeden Client erstellt, welche Datenelemente der Client braucht. Dieses Liste sammelt die Klasse MemExServerClient ein, setzt sie zusammen und vergleicht die eingesammelte Liste mit der Liste von den DatenElementen, die der Client schon hat. Auf Basis dieser Informationen wird dann das UpdatePaket zusammengepackt.

Kurzzusammenfassung:
MemExServerClient muss wissen, welche DatenElemente der Client braucht. Daher sind in MemExServer_Thread_Client Listen gespeichert, die eingesammelt und dann mit der Liste der schon dem Client bekannten Elementen verglichen werden. Die Listen MemExServer_Thread_Client werden einmal pro Durchgang von den Thread geupdatet.

Als Klassenstruktur:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class DatenElement //von dieser Klasse sollen später alle Klassen erben, die übers Netz geschickt werden sollen.

{
    DWORD ID;
        CRITICAL_SECTION Critic;
    Anbindung* DatenAnbindung; 

        size_t Size;
        char* Data;
        unsigned short Version;

    virtual void PerformNetAction() = 0; //hier werden die Daten beim Server serialisiert und beim Client deserialisiert 


    void SetDatas(size_t s, char* datas); //nutzt die CRITICAL_SECTION um die Daten sicher in den Buffer der Klasse zu kopieren. Auch erhöht die Methode, die Version um 1

    size_t GetDatas(char*& datas); //hier wird der Buffer der Klasse in den Pointer kopiert.

}:

class Anbindung //hier registieren sich alle DatenElemente und bekommen eine eindeutige ID.

{
    SecureMap<DWORD, DatenElement*> Elemente;   //eine threadsichere Version von std::map

};

class MemExServerClient : public BasicServerClient //hier werden die Clientdaten gespeichert von den Clients die beim Server angemeldet sind 

{
    CRITICAL_SECTION Critic;

    SecureList<MemExServer_Thread_Client*> Thread_Client_List;

    void PassNetMsg(const Paket&); //Diese Methode ermöglicht es, empfangene Pakete an die Thread_Clients weiter zu vermitteln

        
    virtual void UpdateClient(void); //Sammelt die Daten von den ThreadClient Instanzen, pakkt das ein großes Paket und schickt dieses ab.


    void RegistrateMemExServer_Thread_Client(MemExServer_Thread_Client*); //hiermit können sich die Thread_Clients in die SecureList eintragen

};

class MemExServer : public BasicServer, public Anbindung
{
     friend void MemExServerClient::UpdateClient(void);
public:
    void RegistateElement(DatenElement* e, DWORD id);
};


class MemExServerThread //Von dieser Klasse sollten die Klassen abgeleitet werden, die einen eigenen Thread haben 

{
    SecureList<MemExServer_Thread_Client*> Thread_Client_List;

    void UpdateAllThreadClients(void); //Diese Methode wird vom Thread aus aufgerufen und updatet alle DatenElemente, die zum Thread gehören

    void RegistrateMemExServer_Thread_Client(MemExServer_Thread_Client*); //hiermit können sich die Thread_Clients in die SecureList eintragen

};


class MemExServer_Thread_Client //Verbindungsklasse zwischen den Threads und den Clients. Ermöglicht den Austausch der Listen(von Thread zum Client) und der Pakete (vom Client zum Thread)

{       
    struct CompareContainer
    {
        DatenElement*   Element;
        unsigned short  Version;

        inline bool operator < (const CompareContainer& c)      { return Element < c.Element; }
        inline operator DatenElement* (void)                    { return Element; }
    };

    struct UpdateContainer
    {
        DWORD ElementID;
        bool Update;

        inline bool operator == (const UpdateContainer& c)      { return ElementID == c.ElementID; }
        inline bool operator < (const UpdateContainer& c)       { return ElementID < c.ElementID; }
    };

    std::list<CompareContainer> OwnElements;
    SecureList<UpdateContainer> UpdateElements;
    
    void CheckDelete(void)              { if(Client == 0 && Thread == 0) delete this; }
    
    virtual void CreateCompareList(std::list<DatenElement*>&) = 0; //wird nur vom Thread aus aufgerufen

    virtual void ProcessNetMsg(const Paket&) = 0; //wird nur vom Client(Empfangsthread) aus aufgerufen


    inline void AddUpdateElements(std::list<UpdateContainer> &list)     {   std::list<UpdateContainer>::iterator it = UpdateElements.lockbegin(); list.insert(list.begin(), it, UpdateElements.end()); 
                                                                            UpdateElements.clear(); UpdateElements.unlock(); }

    MemExServerClient* Client;
    MemExServerThread* Thread;
    bool DeleteIt;


    MemExServer_Thread_Client(MemExServerClient* c, MemExServerThread* t) : DeleteIt(false) { t->RegistrateMemExServer_Thread_Client(this); c->RegistrateMemExServer_Thread_Client(this); }
};



SO...nun ist es so, dass dieses System schwachsinnig ist, weil jeder Thread einmal pro Client all seine DatenElemente durchgehen muss, um die Liste der DatenElemente, die der Client braucht, zu erstellen.
Und das einmal pro Durchgang!
Das heißt Anzahl der DatenElemente * Anzahl der Clients Rechenaufwand und das jeden Durchgang, was eine unglaubliche Verschwendung ist.

Daher hatte ich folgende Idee:
Man muss eigentlich nur was ändern, wenn ein neuer Client hinzu kommt, ein alter Client geht, ein Client seinen Zustand ändert und daher andere DatenElemente braucht, ein neues DatenElement hinzukommt oder ein altes DatenElement verschwindet.
Soweit so schlecht. Nun müssten entweder die Clients auf die DatenElemente verweisen oder die DatenElemente auf die Clients oder beide auf den jeweils anderen. Dies geht entweder nur per IDs, weil Pointer im Falle einer Deallokierung zum Absturz führen würden oder per Zwischenelement. Dies würde aber zu Unmengen von Zwischenelmenenten führen (Anzahl DatenElemente * Anzahl Clients). IDs führen allerdings wiederum zu look-ups und locks der entsprechenden Maps.

Welche Option meint ihr wird die bessere sein oder hat vielleicht jemand von euch eine geniale Idee?
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Sicaine

unregistriert

2

11.09.2007, 21:40

Aeh lass doch fuer jeden Client einfach in deinen DataObjects ein Flag setzten. 0 aktuell 1 muss geaendert werden. Sobald die Daten zum Client geschickt werden, wird das bit was zu dem Client gehoert auf 0 gesetzt und der client wird ignoriert wenn das bit auf 0 ist. Alternativ machste halt bei jedem Change des Dataobjectinhalts nen Check wer der Clients das Objekt braucht und setzt es in ne extra queue die halt immer abgearbeitet wird.

Warum sollte der Server wissen welche Objekte der Client hat? Kann er doch eh riechen weil er sie ihm geschickt hat. Alternativ machst halt gelegentlich ein Sync packet zur Sicherheit damit der Client wirklich alles hat was er braucht.

Nox

Supermoderator

  • »Nox« ist der Autor dieses Themas

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

3

11.09.2007, 23:09

Die MemExServer_Thread_Client merken sich ja, welche Objekte schon übermittelt wurden (siehe std::list<CompareContainer> OwnElements). Das ist nötig, damit der Server weiß welche Version der Client von dem Datenobjekt hat. Wenn ich in den DatenElement einen Flag nutzen würde, hätte ich mehrere Probleme.
1. soll das System 100+ Clients unterstützen
2. müsste eindeutige Flag->Client beziehung her, weil häufig sich Clients an- und abmelden
3. woher soll ein DatenElement wissen von welchen Clients es gebraucht bzw nicht gebraucht wird?
ALTERNATIV wenn ich pro Durchgang alle DatenElemente pro Client durchgehen muss um zu sehen ob der Flag gesetzt ist und ob der Client das Objekt braucht. Dann bin ich ja wieder bei Anzahl Clients * Anzahl DatenElemente und das einmal pro Durchgang :-/.

Oder habe ich dich jetzt missverstanden?
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Sicaine

unregistriert

4

12.09.2007, 00:10

Hm dann siehs in nem konkreteren Anwendungsbeispiel. Wenn du viele Clients willst wie bei wow muss der Server halt, immer wenn was passiert, berechnen wer das sehen koennte, wem das interssiert und dann den jeweiligen Personen updaten. Wenn sich spieler1 jetzt ausserhalb des sichtbereiches befindet, dann bekommt er halt nicht mit wie grad jemand ne Tuer aufmacht. Sobald er aber in die Naehe der Tuer kommt, muss er das ja wissen und ihm wirds zugeschickt. Muste halt das ganze in Octrees und co speichern damit du schnell Zugriff auf das zeug hast und schnell weist ob was passiert ist. Es gibt schon nen grund warum es in WoW fast keine bewegbaren gegenstaende gibt.

Nox

Supermoderator

  • »Nox« ist der Autor dieses Themas

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

5

12.09.2007, 10:59

Also um WoW 2 geht es nicht^^. Nur leider können wir bei unserer Struktur nur wenige Elemente von vornherein ausschließen. Darin liegt eines der Kernprobleme.
Aber du hast mich auf eine Idee gebracht. Ich könnte jedem Objekt eine Liste mit auf den Weg geben, die alle potenzielle Spieler einträgt, die das brauchen könnten und diese gebe ich dann in der Struktur nach oben weiter, sodass ich beim obersten Element schon sehe welche Elemente interessant sein könnten. Das wird aber nur beim Auffinden helfen.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Nox

Supermoderator

  • »Nox« ist der Autor dieses Themas

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

6

12.09.2007, 13:19

Habe nochmal ein wenig überlegt und dabei 2 Kernfragen rausgearbeitet:

1. wie stellt man möglichst effizient fest, welcher Client welche DatenElemente braucht
2. wie teilt man dem ServerClient mit, welche DatenElemente sich geändert haben
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Black-Panther

Alter Hase

Beiträge: 1 443

Wohnort: Innsbruck

  • Private Nachricht senden

7

12.09.2007, 19:10

Und was wäre, wenn du jeden Client einfach nur jene Daten sammeln lassen würdest, welche sich auch ändern? Diese werden dann an den Server geschickt, und er aktualisiert sie bei allen anderen Clients (sofern sie i.O. sind). Damit hättest du beide Fragen gelöst (oder hab ich das falsch verstanden?)
stillalive studios
Drone Swarm (32.000 Dronen gleichzeitig steuern!)
facebook, twitter

Sicaine

unregistriert

8

13.09.2007, 02:09

Der Client hat nichts zu berechnen. Der Client kann zu leicht manipuliert werden zudem ja 2 Clients verschiedene Sachen berechnen koennten.

@Nox
1. naja so wie du auch effizient Kollisionen erkennst. Dafuer gibts ja genug algos. Octree und co.

2. Naja probiers aus was in Sachen Overhead akzeptabel ist. Gib jeder eigenschaft ne id und jedem objekt oder sende das komplette objekt oder verwende sowas wien rsyncalgo mit zipkomprimierung. Alternativ guck dir mal WoW an, reengeenier das Protokoll und orientier dich an etwas was funktioniert

Nox

Supermoderator

  • »Nox« ist der Autor dieses Themas

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

9

13.09.2007, 07:53

Es geht wirklich nur um das Verschicken der Serverdaten an die Clients.

Also WoW ist eindeutig kein Maßstab ;) und das Protokoll ist ja eine andere Geschichte als der Algo dahinter :( . Jedes Objekt hat ja schon eine ID und es werden auch immer nur Teile auch schon mit dem aktuellen System verschickt. Das Problem ist halt der Leistungsbedarf.

In Prinzip ist es ja eine Art Schichtenmodell:

1. Transportschicht (TCP) - ist vorgegeben
2. Netzwerkengine (mit zlib usw) - ist soweit in Ordnung
3. DatenElementverwaltung (mit den IDs) -ist auch soweit in Ordnung
4. Feststellen welcher Client welche Daten braucht - es werden immer alle Elemente pro Client und pro Frame durchgegangen -> das ist einfach zu ineffektiv
5. Die Daten sammeln - es wird immer die komplette Verwaltung gelockt ->inakzeptabel
6. Spiel bzw Objekthierachie - auch soweit fertig

Die Frage ist nun wie ich Punkt 4 und Punkt 5 möglichst effizient gestalte.

Beim Datensammeln tendiere ich dazu, dass die DatenElemente eine Möglichkeit bekommen bei einer Änderung die Clients direkt zu benachrichtigen. Also sprich jedem DatenElement eine Liste geben in der die Clients eingetragen sind, die meinen das DatenElement zu brauchen. Bei einem Update meldet das DatenElement dies an alle Clients in der Liste.
Da ich aber keine Pointer nutzen kann (wegen Threading) müsste ich entweder IDs erteilen und ständig die Verwaltungen locken um das Element nachschlagen zu können oder ich mache es über ZwischenElemente. Das bedeutet zwar mehr Speicherverbrauch, ist aber glaube ich den Fall die bessere Lösung.

Beim Feststellen welcher Client welches DatenElement braucht, werde ich wohl eine MultiMap nutzen, die ich dann nur noch einmal pro Frame neu erstellen muss. Immerhin muss ich dann nicht einmal pro Frame und pro Client alle Elemente durchgehen, aber das Wahre ist das irgendwie auch noch nicht :-/

Also immer her mit neuen Ideen, sie können nur hilfreich sein ;)
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Black-Panther

Alter Hase

Beiträge: 1 443

Wohnort: Innsbruck

  • Private Nachricht senden

10

13.09.2007, 09:49

Ich nehme mal an, dass die Clients nur die Befehle für die Änderungen schicken und der Server selbige dann berechnet.
Wieso fängst du nicht alle "Änderungsbefehle" nachdem sie bearbeitet wurden auf, und bufferst alle geänderten Objekte?
Danach musst du halt noch aufpassen, dass auch alle Objekte, welche nur vom Server verändert werden, gebuffert werden.

Somit würdest du dir sparen einen extradurchlauf aller Objekte zu haben, und und die gesamte Verwaltung mit einem schwubs zu sperren (es werden ja sequentiell alle veränderten Daten angehängt und somit nur jenes Objekt gesperrt!)
stillalive studios
Drone Swarm (32.000 Dronen gleichzeitig steuern!)
facebook, twitter

Werbeanzeige