eindeutige ID - Umsetzung

Scarabol

Hi Leute,

also erstma der Rahmen:
Ich hab ein Client und ein Server Programm, der Server schickt dem Client Daten über sich bewegende Objekte und der Client stellt diese dar. Wenn der Client jetzt eine Aktion ausführt, die mit einem der Objekte zu tun hat, schickt er diese Info an den Server zurück. Die Objekte sollen mit einer ID identifiziert werden, damit Client und Server immer wissen, um welches Objekt es gerade geht, wenn sie Informationen erhalten.

Leider komme ich gerade etwas in stocken, wenn es darum geht eine eindeutige ID zu finden. Bisher lasse ich einen Random Wert bilden, da die ID's zwischen 10000 und 30000 liegen sollen, und überprüfe dann in der Liste mit den bisher existierenden Objekten ob diese ID noch nicht vergeben wurde.

Ich finde diese Methode allerdings nicht besonders gut, da sich die Zeit eine ID zu finden sehr stark steigern kann, wenn mehr und mehr Objekte dazukommen...

Gibt es eine Resourcenschonendere Methode an eine eindeutige ID zu kommen?

Gruß
Scarabol

Xebov

Naja du könntest die ID fest vergeben, du wirst ja sicher keine 20000 Objekte haben die sich bewegen und da hin und her geschickt werden. Du könntest die Objekte zB einordnen und einen Pool anlegen der feste ID Bereiche für ebstimte Objekte zuordnet die auch wirklich angezeigt werden sollen. Ich würde nur real wichtige objekte auf diese Weise verwalten, also Spielfiguren oder evtl noch Projektile, alles andere könnte man Clientseitig abbilden da es kaum Nötig ist zB Sprites usw über diesen Weg zu verwalten. Damit würde sich die Zahl der benötigten Objekte stark reduzieren. Als pool könnte man ein unsigned Short nehmen das man über Hex anspricht damit hätte man eine 4Stellige Zahl die sich gut einteilen lässt.

Scarabol

Hmm,

klar ich benutze keine 20.000 Objekte, aber könntest du bitte etwas genauer werden, wie ich so einen Pool benutze?

Ich verstehe nicht ganz wie ich eine unsigned short über hex anspreche?

Die Objekte sind fast alle dynamisch, d.h. Sie sind fast alle Projektile...

Gruß
Scarabol

volkard

Scarabol schrieb:

Ich finde diese Methode allerdings nicht besonders gut, da sich die Zeit eine ID zu finden sehr stark steigern kann, wenn mehr und mehr Objekte dazukommen...

dann bau doch ne datenstruktor, die in O(1) testet, ob die ID schon vergeben ist.
statt random kannste dann auch einfach hochzählen, dann haste die beiden zugriffe in die cuckoo hastable schon wieder drin.
und die hashtable muß ja eh sauschnell sein, um die netznachrichten zu dispatchen.

edit: lass mich raten, die id ist bei dir ein arrayindex. dann nimm doch weiter rand() und sorge einfach dafür, daß der füllstand des arrays nicht 50% überschreitet. das doch schon O(1) mit durchschnittlich gerade mal nur zwei versuchen.

Xebov

Scarabol schrieb:

Hmm,

klar ich benutze keine 20.000 Objekte, aber könntest du bitte etwas genauer werden, wie ich so einen Pool benutze?

Ich verstehe nicht ganz wie ich eine unsigned short über hex anspreche?

Die Objekte sind fast alle dynamisch, d.h. Sie sind fast alle Projektile...

Gruß
Scarabol

Als Hex ansprechen ist ganz einfach 0x0000 - 0xFFFF passen als Hex in ein unsigned Short.

Ein Pool wäre etwa das was Volkard schon sagt, du legst einfach feste Bereiche an, da ja vorausszusehen ist wieviele Objekte man hat, man könnte zB sagen das alels von 0x0000-0x1000 Spielfiguren sind, dann könntest du nach Volkards vorschlag einfach schauen welche Ids gerade Frei sind.

Was die projektile angeht, ich denke nicht das die unbedingt eine ID brauchen fürs netzwerk. Die meisten projektile die man nutzt haben eine feste Flugbahn, eine Gewehrkugel fliegt zB in vielen Spielen einfach geradeaus, smit ist von vornherein klar wo sie hingeht, damit reicht es eig dem client zu sagen da kommt eine Kugel, start an Pos x Flugrichtung y, das wäre es auchs chon, animieren kann der Client sie damit selbst, ob sie trifft doer nicht kann ja der server entscheiden, bzw was sie trifft. Das würde auch deinen netzcode stark entlasten weil du im Grunde nurnoch die Spielfiguren evrschicken müsstest und 2x Infos zu Projektilen.

Scarabol

Hi,

also was die "Projektile" treffen, entscheidet der Client, dass lässt sich auch erstmal nicht ändern, aber indem ich die Bereiche kleiner mache und mehrere ID Bereiche anlege kann ich die Zeiten erstmal reduzieren, danke dafür.

Vielleicht geht es ja sogar noch flotter, mal schauen...

Ich hatte gerade die Idee einfach die Speicheradresse zu benutzen, diese kann nur einmal vergeben sein. Problem ist das die Daten von Server und Client sehr wohl die gleiche Speicheradresse haben können, also hänge ich noch vorne eine 1 oder 0 dran für Server oder Client und dann sollte es gut sein...

Funktioniert das?

Wie ermitell ich die Speicheradresse eines Klasse bzw. einer Variabel?

Wie kann ich die Adresse aus einem String auslesen und wieder mit meiner Variablen auf dem Server vergleichen?

Gruß
Scarabol

Xebov

Scarabol schrieb:

also was die "Projektile" treffen, entscheidet der Client, dass lässt sich auch erstmal nicht ändern, aber indem ich die Bereiche kleiner mache und mehrere ID Bereiche anlege kann ich die Zeiten erstmal reduzieren, danke dafür.

Naja die projektile solte man im Idialfall so gestalten: Der Client der schießt sagts dem Server, der Server sagt es allen Clienten und entscheidet ob das projektil trifft oder nicht, das shcützt 1. vor manipulation und sorgt 2. dafür das das Projektil überall das gleiche tut, sonst könnte es in einigen Clienten treffen und in anderen nicht.

Scarabol schrieb:

Ich hatte gerade die Idee einfach die Speicheradresse zu benutzen, diese kann nur einmal vergeben sein. Problem ist das die Daten von Server und Client sehr wohl die gleiche Speicheradresse haben können, also hänge ich noch vorne eine 1 oder 0 dran für Server oder Client und dann sollte es gut sein...

Funktioniert das?

Naja ichw eis nicht so recht, Speicheradressen sind nicht so toll, ein Hex Wert ist zB eindeutig, bei ner adresse ist das sone Sache. Werte anhängen ist auch sone sache bei nem Hex Wert geht das nicht 0x ist die Identifikation für Hex, da darfste nix dran machen.

Das einfachste verhalten wäre aus meienr Sicht wenn die Spielwelt ansich schon eindeutige IDs hat für Objekte und der Rest vom Server verwaltet wird, dh ein Client meldet sich an, der server weist der Spielfigur eine ID zu und sendet die ID weiter, damit wäre jedes Objekt eindeutig Identifiziert.

Scarabol schrieb:

Wie ermitell ich die Speicheradresse eines Klasse bzw. einer Variabel?

Mit dem & Operator, wies bei zeigern funktioniert.

Scarabol

Xebov schrieb:

Das einfachste verhalten wäre aus meienr Sicht wenn die Spielwelt ansich schon eindeutige IDs hat für Objekte und der Rest vom Server verwaltet wird, dh ein Client meldet sich an, der server weist der Spielfigur eine ID zu und sendet die ID weiter, damit wäre jedes Objekt eindeutig Identifiziert.

Das ist ja das Problem, der Server hat eine Menge Daten und müsste mehrere Listen (ich sag nicht hunderte aber einige) durchsuchen nur um an eine geeignete ID zu kommen...

Kann ich einen Pointer speichern, ohne zu wissen worauf er zeigt? Bei Basic waren das immer schöne long Werte soweit ich weiß

Gruß
Scarabol

Xebov

Scarabol schrieb:

Das ist ja das Problem, der Server hat eine Menge Daten und müsste mehrere Listen (ich sag nicht hunderte aber einige) durchsuchen nur um an eine geeignete ID zu kommen...

Wieso einige Hundert? Das verstehe ich nicht ganz, nehmen wir an du machst dir nen Pool auf, einen für Figuren udn einen für Projektile, dann müsstest du im Zweifel ja immer nur den nächsten freien Platz suchen von deienr Aktuellen position ind er Liste aus, das wäre eine Liste und eine Suche, die im Zweifel auch nicht so sehr lang wäre, gerade bei Objekten mit eienr Kurzen lebensdauer könnte es passieren das du nichtmal scuhen musst sondern der nächste Listenplatz fast garantiert immer frei wäre.

Scarabol schrieb:

Kann ich einen Pointer speichern, ohne zu wissen worauf er zeigt? Bei Basic waren das immer schöne long Werte soweit ich weiß

Naja wenn du nen Zeiger erstellst zeigt er irgendwo hin. Wenn du dem Zeiger ne Adresse zuweist die auf irgendwas zeigt haste das Problem du weist nicht auf was er zeigt, ist es das angenommene Objekt, ein anderer Teil des Programms oder etwas anderes wofür du ne Access Violation kassierst, das is ein Zweischneidiges Schwert.

Scarabol

Naja die Variabeln sind doch auch nur Konstanten die beim Programmstart durch Speicheradressen ersetzt werden oder? Das heißt ja das der Pointer den Wert dieser Konstanten enthält, also die Speicheradresse und die kann ja nicht sooo unterschiedlich sein, höchstens hex oder int oder sowas...

Gruß
Scarabol

Xebov

Naja doch untershciedlich schon, wenn ich dich richtig verstehe willst du die adresse der Variable auf dem Server nehmen und an den Client schicken, und sowas geht in die Hose, den die Variablen landen ja im RAM wo Platz ist und das ist unberechenbar.

Scarabol

Ist ne RAM Adresse nicht immer 6 oder 8 Zeichen lang?

Gruß
Scarabol

hellihjb

wenn ich dich richtig verstehe willst du die adresse der Variable auf dem Server nehmen [...] sowas geht in die Hose, den die Variablen landen ja im RAM wo Platz ist und das ist unberechenbar.

Die Speicheradresse bleibt fuer die Lebensdauer des Objektes konstant und eignet sich darum sehr gut als ID.

Scarabol

Juhu,

endlich einer der mir zustimmt, hast du auch ne Idee wie ich die Adresse verwenden kann?

Kann man da vielleicht was mit Struktur Union machen?
Dann müsste ich ja nen Pointer erhalten der auf mehrere Typen zeigt/zeigen kann?

Gruß
Scarabol

hellihjb

Kann man da vielleicht was mit Struktur Union machen?

Wenn Du unbedingt verschiedene Objekt-Typen unterscheiden musst, kannst Du einfach von einer Basisklasse erben die solche Funktionalitaet bereitstellt:

class Object
{
public:
  enum Type { Thing, Enemy, Projectile, ... };

  Object(Type type) : mType(type)
  {
  }

  Type getType() const
  {
    return mType;
  }

private:
  Type mType;
};

class Projectile : public Object
{
  Projectile() : Object(Object::Projectile)
  {
  }

  void explode()
  {
  }
};

Object *obj= new Projectile();
if (obj->getType()==Object::Projectile)
{
  Projectile *p= (Projectile*)obj;
  p->explode();
}

Eleganter ist jedoch ein gemeinsames Interface fuer alle Objekte bereitzustellen und jeweils mit sinnvoller Funktionalitaet zu ueberschreiben.

Christoph

Scarabol schrieb:

Ist ne RAM Adresse nicht immer 6 oder 8 Zeichen lang?

Falls du mit "Zeichen" "Bytes" meinst: Auf 32-Bit-Rechnern ist eine Speicheradresse in der Regel 4 Bytes groß, auf 64-Bit-Rechnern aber schon 8 Bytes.

Xebov

hellihjb schrieb:

wenn ich dich richtig verstehe willst du die adresse der Variable auf dem Server nehmen [...] sowas geht in die Hose, den die Variablen landen ja im RAM wo Platz ist und das ist unberechenbar.

Die Speicheradresse bleibt fuer die Lebensdauer des Objektes konstant und eignet sich darum sehr gut als ID.

Ja aber da er auch von Zeigern sprach hatte ich eher das Gefühl das er mit der Adresse vom Server auf die Stelle im RAM das Clients zugreifen will, deswegen hate ich das geschrieben.

hellihjb

mit der Adresse vom Server auf die Stelle im RAM das Clients zugreifen

Muesste aber jedem klar sein dass das nicht geht

Scarabol

Nein, nein, das die Speicheradressen auf beiden Systemen unterschiedlich sind ist mir klar, ich will die Adresse nur als Zahlenwert benutzen, um das Objekt eindeutig zu identifizieren...

Stimmt auf einem 32 bit System sind die Adressen 4 byte, dann sollte es doch möglich sein, die Adresse von einer beliebigen Variabeln in einer signed long zu speichern und dann mit sprintf in einen String zu "drucken" und an die Clients mit nem WinSocket zu verteilen, oder?

Gruß
Scarabol

Xebov

Ja das ginge, müsstest halt das Problem mit den 4 und 8Bytes lösen. In einen String würde ichs allerdings nicht drucken, damit wird die variable nur unnötig lange und du brauchst sie ja nur für einen Vergleich, was am Ende genau drin steht ist ansich ja egal. Wenn dus so machen willst würde ich direkt das int oder long verteilen.

Scarabol

hmm,

soweit ich weiß kann man Programme doch immer nur entweder für 32 bit ODER für 64 BIT compilieren, also währe das ja nur eine Compiler If Frage um das "Problem" zwischen 4 und 8 byte zu lösen, aber ich schaffs nicht das int bzw. long auszulesen, wie geht das?

Gruß
Scarabol