Hallöle

Also, wenn ich hier meine komplette Welt habe und die in einen Stream speichern will, kann ich ja schlecht Pointer speichern (logisch). Weiterhin kann ich auch nicht jede Objektreferenz, die ich in einem Objekt vorfinde auflösen und das Objekt nochmal speichern. Schließlich sind zum beispiel bei (aus performancegründen erzeugten) Schiffslisten Schiffe mehrfach vorhanden. Oder Aufträge, die Referenzen auf Schiffe beinhalten. Da kann ich ja schlecht das Schiff nochmal speichern, schließlich muss es ja mit dem Original verknüpft werden.

Folgendes System habe ich bereits erfolgreich bei einem Projekt verwendet: Ich habe einen globalen Manager, der alle bekannten Objekte beinhaltet, verknüpft mit einer ID. Diese ID ist eindeutig, sodass ich sie in den Stream oder so schreiben kann und beim Laden das Objekt daran identifizieren kann. Ich würde dieses System gerne verwenden, da ich diese IDs dann zum beispiel auch beim Netzwerkspiel verwenden kann (nach dem Motto: "Schiffobjekt mit ID [0000-01A7-5A91-BCD7] bitte nach System mit ID [0000-0020-67BD-FF9A] schicken"). Allerdings bin ich hier für gute Alternativen offen. Jedes Objekt könnt hierbei seine eigene ID kennen und anstatt Pointer auf andere Objekte könnte man auch einen Record mit ID und Pointer platzieren, das würde Lookups im Netzwerk ersparen (zumindest auf der sendenden Seite).

Jetzt brauche ich nurnoch ein performantes System um in dieser Liste einen Eintrag zu finden. Man könnte da natürlich eine Art Hashlist aufbauen, wobei ich da gerne ein Konzept für hätte. Ich dachte vielleicht an XOR-en aller Bytes der ID zu einem Byte, 256 Listen erstellen und alle IDs mit dem gleichen Ergebnisbyte kommen in eine Liste. Das dürfte die Lookup-Performance erhöhen (wobei zu hinterfragen bleibt, wieviel 7 xor-Operationen kosten - sollte aber nicht allzu viel sein, im vergleich dazu, was wohl notwendig ist, durch eine (längere) Liste zu iterieren). Ist das gut, oder habt ihr vielleicht eine bessere Idee?

Gruß Lord Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Hashs sind für sowas teilweise gut geeignet. Am besten nimmt man für sowas eine Hashfunktion. Ich habe in meinem aktuellen Pojekt einige Zuordnungen auf String-Basis, und ordne Objekte nach dem Hash der zugehörigen Strings in sowas wie Arrays ein.

Ich weiß ja nicht genau, wieviele IDs und Objekte du so hast etc. , es kommt bei der Wahl einer Hashfunktion auf eine Menge Faktoren an.
Das Objekte, deren ID man hat und über eine Hashfunktion zugreift, nicht mehr existieren, kann man ja per Abfrage herrausfinden (zeigz der Pointer auf was?), Kollisionen kann man auch verhindern, mit unterschiedlichen Strategien.
Ich würde keinen Mischmasch verwenden, und die IDs auf 256 Listen mit "den gleichen Hashes" herrunterrechnen, sondern gleich per Hashfunktion versuchen, den richtigen Eintrag zu nehmen, und eine übliche (funktionierende und schnelle) Kollisionsverhinderung einsetzen. Bei dem "256" Listen und einer schlechten Hashfunktion kann man sich in den Listen auch noch recht lange durchwühlen und hat keinen Vorteil. Listen brauchen zwar vielleicht weniger Speicherplatz, aber auch ein großer Array mit Objekt-Zeigern braucht nicht viel Speicherplatz. Davon ab, wenn man erwartet, dass eh viele Objekte existieren, brauchen die Listen sogar mehr Speicherplatz (da in jedem Element weitere Pointer etc. vorhanden sind), da die Arrays ja gut gefüllt sind.
Insgesamt ist hashen mit Sicherheit schneller als Listen durchgehen, auch mit Kollisionen. Viele Hashfunktionen brauchen nur wenige Rechenoperationen, viele davon sind auf Binärer Basis (paar Bits shiften und XOR und sowas), was sehr schnell geht. Beim Suchen in einer Liste muss man ja beim durchlaufen jedesmal min. einen Vergleich durchführen, und einen Zeiger erhöhen, und oft noch einen Programmzeigersprung durchführen etc., womit man bei 4-5 falschen Listenelementen die man durchläuft schon langsamer als die Hashfunktion ist.
http://www.fantasy-coders.de/projects/gh/html/x435.html ist z.b. eine nette Seite mit vergleichen von verschiedenen Hashfunktionen mit Stärken und Schwächen ( auch Zeitaufwand). Deine IDs kann man dabei bestimmt auch einfach als 1 Byte zeichen auffassen, womit es auch die, die "strings" basieren, verwendbar wären.

Ich benutzte selber FNV, da es bei mir keine zeitkritischen Teile betrifft (nämlich z.B. das nachladen von Graphiken in einem zweiten Thread), und das klappt wunderbar.

Das Stichwort heisst Serialisierung und dabei werden die Pointer aufgelöst.
Ich hab es in C++ wie folgt implementiert.
Ein Pointer wird durch ein 64Bit Datentyp realisiert, wenn man ein 32Bit System hat, dann werden 32Bit von den 64 benutzt und die anderen 32 liegen brach sonnst benötigt er die 64Bit.
Zuerst werden alle Objekte mit ihren Pointer Referenzen in den Stream gespeichert, dann werden die Pointer in Offsets umgewandelt und das ganze in der Datei überschrieben.
Gelesen wird dann die ganze Datei mit einmal in den Speicher, dann werden alle Offsets mit der jeweiligen Objektaddresse addiert und fertig.

Eine Möglichkeit, die durch das ausgeweitete RTTI System, in Delphi/Freepascal vorhanden ist, kann man aber auch nur Properties speichern.
Also alle Properties abfragen und die, die z.B. mit Script* anfangen werden mit Namen und Wert, sowie Klassennamen in die Datei gespeichert und beim Laden wird dann eine Objekt erstellt und die Werte den jeweiligen Propertynamen zugewiesen. Das ist natürlich wesentlich langsamer(wirklich wesentlich langsamer aufgrund der ganzen Stringoperationen) aber dafür Kontrollierbar und Speichereffizienter.

In meinem Scenegraph hatte ich es wiederum anders gelöst, dort habe ich meine Klasse TNode gehabt und dann weitere wie TLightNode und co, neben TLightNode gab es dann TLightData, welches ein record mit den verwendeten Daten war, TLight war nichts anderes als ein Wrapper, welcher TLightData zugreifen konnte und durch die TNode Ableitung mit dem SceneGraph klar kam. Im Prinzip ist TLightData der klassische Datenlayer und TLightNode der Logiklayer. Die Lade- und Speicherroutine wurde in TLightNode und co überschrieben, so dass es TSceneGraph einfach nur alle Kinder durch ist und immer LoadData vom TNode Klasse aufgerufen hatte. Man dann statt LoadData auch noch SaveData einbauen und das gleiche Spiel nur umgekehrt treiben.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Wie viele Objekte hast du den so in deiner Szene? Ich schaffe es mit 20 Vergleichen deine ID aus 2^20 = 1048576 Objekten zu finden, sollte reichen denke ich...genauer ich brauche für n Objekte genau ld(n) Vergleiche. Dabei ist ld(n) = log(n) / log(2), also der Logarithmus zur Basis 2. Sollte schnell genug für deine Anwendung sein.
Darüberhinaus sollte das leichter zu implementieren sein als eine Hashtabelle. Stichwort Binäre-Suche. (Noch besser ist möglciherweise auch die Interpolations-Suche, wenn du von einer Gleichverteilung der IDs ausgehen kannst.)

Einzige Voraussetzung ist, dass die Liste mit den ID-Nummern sortiert ist. Neue Objekte müssen also sortiert eingefügt werden. Das Problem lässt sich dadurch lösen, dass du von vorn herein genug IDs reservierst und irgendwo eine Liste (bzw. besser einen Stack oder Queue) der noch freien IDs verwaltest.

Noch einfacher geht es natürlich mit fortlaufenden ID-Nummern. Dann ist die Ermittlung des zugehörigen Pointers einfach nur ein Arrayzugriff. Auch hier müssen natürlich freie IDs irgendwie verwaltet werden.

_________________
Yeah!

Noch ein paar Tipps:

• Es beschleunigt die Sache natürlich extrem, wenn du nicht Strings sondern 32bit Integer als ID verwendest. Ich bezweifle das du mehr als 4 Mrd. Objekte verwalten willst. Um einen String zu vergleichen durchläufst du erstmal den gesamten String, beim Integer ist der Vergleich in der Hardware implementiert.
• Wenn du nicht weißt wie viele IDs du benötigten wirst, reserviere immer so ca. 100 auf einmal. Denn 100 IDs einsortieren dauert nur unwesentlich länger als eine einzige ID einzusortieren. (Du musst ja das gesamte ID-Array neuschreiben)

_________________
Yeah!

Zuallererst einen schönen Dank für die Antworten.

@Merlin:
Okay, ein anderer Hashalgorithmus - gerne. Aber was du mit den Listen gesagt hast verwirrt mich. Wie hält man sich eigentlich eine Hashliste? Bisher habe ich das Konzept immer so gesehen, dass man ein Array braucht, in dem alle (möglichen) Hashes als indicies existieren.

@Tak:
Hmm.. Deine Vorschläge gehen alle extrem aufs Speichern ein (okay, zugegeben der Threadtitel regt auch etwas dazu an), aber ich habe jetzt einen Gefallen daran gefunden, über dieses Referenzsystem auch die Identifikation von Objekten über das Netzwerk abzuwickeln.

@coolcat:
Die Anzahl der Objekte kann ich dir nicht genau sagen, aber es sind schon nicht wenige. Die komplette Welt wird ja darüber verwaltet. Es können also schon mal tausend zusammenkommen denke ich, aber wohl nie mehr als hunderttausend - außer in einem wirklich großen Szenario.
Die IDs sind übrigens Int64, ich mag nur die Darstellung in klammern und mit bindestrichen lieber .
Eine Sortierung der Liste ist sicherlich machbar. Schließlich werden wohl viel häufiger Objekte gesucht als hinzugefügt, sodass das bisschen mehraufwand bei einer von anfang an sortierten Liste wohl kaum ins Gewicht fällt.

Ich denke, aus allem zusammen habe ich folgendes Fazit gezogen:
Ich habe hier ein wenig zu kompliziert gedacht. Coolcat hat es schon wunderbar gezeigt, wie ich das am besten machen sollte. Fortlaufende IDs - warum komm ich auf sowas nicht selber? Am besten wäre es dann wohl, wenn ich zunächst den Index kenne, ab dem keine weiteren IDs reserviert sind (fürs Early Out bei einer Abfrage beziehungsweise beim Hinzufügen) und außerdem einen Stack oder eine Queue wo alle freigewordenen IDs gespeichert sind.
Beim Speichern könnte ich dann zuerst die ID-List mit allen freien Slots speichern (oder die beim Laden wieder automatisch finden) und danach alle Objekte. Mit ein bisschen gefriemel ließe sich sicherlich auch noch eine Tabelle mit einer Zuordnung ID <-> Offset in der Datei erzeugen.
Fürs Netzwerk wäre das dann einfach eine Übertragung der ID und ein lookup am entsprechenden offset... Ich verstehs echt nicht, warum komm ich auf sowas nicht ?
Beim vergrößern der Liste würde ich dann natürlich in Blöcken arbeiten. Das habe ich mir bei solchen Sachen sowieso angewöhnt, weil es einfach schneller ist (und den Speicher nicht so stark fragmentiert).

Gruß Lord Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Sagen wir du hast ein 64Bit System und 50.000 Objekte, 50000*8=400000Byte ~500KB und noch einmal 4Byte für eine counter Variable, meinst du nicht, dass es vieleicht effektiver ist einfach einen Statischen Array mit 50k Elementen zu erstellen und so mit die maximal höchste Geschwindigkeit zu erreichen unzwar garkeine Prüfung und dafür lieber ein halben MB Speicher zu verbrauchen(vorraus gesetzt es ist ein 64Bit System sonnst die hälfte).
Weil so kannst du einfach den Index als ID verwenden und dank nil/NULL kannst du raus bekommen, ob ein Element noch frei ist.
Das System verlagert die benötigte Leistung in den erstellen und zerstören Funktionen und macht dafür die Zugriffsfunktion sehr Performant.
So kannst du z.B. festlegen, dass die Liste Dynamisch ist und in 1000 Elementen Schritten einfach aufstockt, wenn alle Belegt sind(um doch Speicher zu sparen).
Der zugriff passiert in der Regel mehrmals in der Sekunde, ein Objekt zu zerstören oder zu erzeugen ist unregelmässig und passiert vergleichsweise sehr selten.

Diese Variante benutze ich in meinem SceneGraph mit unter(in den Views).
Ich habe den Szenen Baum als wirklichen Baum und durch Views(aus Datenbanken hoffentlich bekannt), werden nur Teile des Baumes betrachtet, wenn ich ein zugriff mache, dann gehe ich nicht Iterativ über den Baum, sondern direkt über die View per Indexnummer.
Durch das Verschachteln von Views kann man so recht effizient den Baum in benötigte Teile zerlegen(z.B. Nodes die auf Scripte oder Physik auswirkung haben).
Die Aktualisierung der Views passiert über Observer Muster und ist damit überaus Performant.
Ich gebe zu, es war nicht meine Idee, dieses System wird als die nächste Generation der SceneGraphen gehandelt(Datenbank basierende).
Was hat das mit deiner Problematik zu tun ? Wie wäre es mit einer View, UpdateNodesViaNetwork.
Wenn du nun den ganzen SceneGraph kram mal weg lässt und nur eine Liste UpdateNodesViaNetwork hast, worin sich die Objekte selber eintragen, wenn sie sich verändert haben, dann muss garnicht erst gesucht werden. Auf der Gegenstelle kannst du dann die oben erwähnte große Liste benutzen, wo du dann ja per Index(ID) den direkten Zugriff auf das Element hast.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Naja es kommt auch drauf an, ob deine Objekte nicht auch mal z.B. zerstört werden können. Dann ist nichts mehr mit fortlaufend, es sei denn man speichert dann die freien IDs und weist diese dann neuen Objekten zu, falls welche erstellt werden. Eine ggf. sortiere Liste wird durch löschen eines Elements aber sortiert bleiben.
Ansonsten...binäre Suche und Listen hört sich im moment nach etwas overhead an, den man mitschleppen muss. Sollte aber möglich sein. Widersprechen muss ich beim Implementationsaufwand. Eine Hashfunktion selbst ist quasi kein Aufwand, einen Kollisionsalgorithmus (es gibt genug sinnvolle und getestete) auch nicht. Da tuen sich die Verfahren nichts. Geschwindigkeit ist schätzungsweise gleich, wenn der Zusatzaufwand, um in den Listen! eine binäre Suche durchzuführen, nicht zu groß ist (hinzufügen wäre mit dem Hash natürlich schneller, aber wenn man das nur selten macht, ists ja egal).
Ich frage mich da ad hock, wie das ganz genau gehen soll mit der binären Suche. Wie greift man auf das mittlere Listenelement zu, und schaut, ob es größer/kleiner ist? Und weiter? Ich sehe da zusätzlich zu dem Aufwand des Algorithmus, der sich zwar toll liest, einen riesigen KONSTANTEN Aufwand, sich durch die Liste zu arbeiten (bei 100k Listenelementen sich bis in die Mitte zu hangeln, macht keinen Spaß). Man kann nicht annehmen, dass die Listenelemente alle hintereinander im Speicher sind, und deren Position berechnen ( was ja gerade die dynamik einer Liste ausmacht).

Wobei ich jetzt verwirrt, bin, genau wann du die Zuornung ID<->Objektzeiger z.B. brauchst. Aber ich sehe bei der Listenlösung auch Probleme.

Was auch verloren geht, bei fortlaufenden Nummern o.ä. wäre eine Zusatzinformation in den IDs. Man könnte diese ja z.b. in Bereiche aufteilen, und könnte anhand der ID schon direkt sagen, was für eine Art von Objekt es ist, oder sowas.


@TAK2004
Das mit dem Array ist eine fast Hash-Ähnliche Lösung, nur das der Hash die ID direkt ist ohne Umrechnung. Das Problem dabei ist halt die fehlende Dynamik, wenn man es direkt zuordnet. Man muss beim erstellen/zerstören von Objekten immer noch mitschleppen, welche IDs frei sind und man ist in der Wahl der IDs eingeschränkt. Eine Hashfunktion macht ja nichts anderes, als eine als eine große Quellmenge auf eine kleine Zielmenge zu projezieren. D.h. wenn es 10 Mill. mögliche Ids gibt, und man weiß, es wird nur max. 100k gleichzeitig geben, braucht man halt nur einen kleineren "Array" in der Größenordnung von 100k zum speichern.
Wie man das Speichermanagement realisiert (z.b. Liste mit Arrays, in der jeweils 1000 Objektzeiger passen, und dynamischen ändern der Anzahl der Elemente der Liste, so dass man max. den Speichert für 999 Zeiger zuviel reserviert) ist eher ein konstanter Aufwand und nebensächlich.

@merlinschmidt: Äh...also eine verkettete Liste macht hier wenig Sinn, erstmal ist der Speicheraufwand viel höher, der Speicher fragmentiert und es gibt keinen RandomAccess. Das ist sowohl für die binäre Suche schlecht, als auch für die primäre Tabelle einer auf Hashes basierten Indexstruktur. Eine Alternative wären natürlich Skip-Listen, aber die sind ziemlich fies zu implementieren so das dies eigentlich keiner macht. Daher dachte ich es wäre klar das ich von einem Array rede, sorry falls dies nicht deutlich genug war


Der Aufwand wäre nicht konstant, sondern linear mit der Anzahl der Elemente.


Hm, ne Schleife, vielleicht 5 Zeilen Code? Ich finde der Aufwand für offenes Hashing ist durchaus höher. Wobei du aber glaube ich ich geschlossenes Hashing meinst?


Er braucht sie beim Speichern des Spielstands sowie bei der Netzwerkkommunikation.


P.S.: Der alte Krieg zwischen den Verfechtern der Hash-Algorithmen und denen der Baumstrukturen bricht hier wohl wieder aus.

_________________
Yeah!

Du hast mich wohl falsch verstanden.
oder auch TObject statt pointer ist eh das gleiche.
bzw.


Wenn du ein Element zerstörtst wird es wieder nil,NULL,0 gesetzt und damit ist es frei, da 0 eh auf kein echtes Objekt zeigen kann.
Da Objekt Pascal TObjekte als Pointer auf den echten Speicher handhabt, bleibt die handhabung wie gewohnt und das erweitern um weitere 1k Elemente wäre dann ledeglich ein kopieren von Pointern und nicht ganzen Objekten, denn die liegen irgendwo im Speicher verstreut.
Das erstellen bzw. zerstören einer ID kann man getrost vernachlässigen, da diese Aufrufe wie schon erwähnt nur einmal auftreten und der Zugriff viele male passiert, bevor es sein Ableben feiert. Ich verwende in meiner Implementierung keine Belegungsliste, sondern gehe Element für Element durch, bis ein Freies da ist.
Effektiv wäre hier eine LinkList, also am Start gibt es 1Knoten mit dem Wert Start=0,Count=len,NextNode=nil; später würden dann auch mehrere Knoten geben aber die Anzahl wäre sehr überschaubar.
Der einzige Fall, der mir einfallen würde, wo sehr schnell erstellung und zerstörung aufeinander folgen würde, wären einzelne Partikel aber das macht keiner, diese werden durch oft Emitter genannte Objekte zusammen gepackt(aufgrund genau diesem Verhaltens).

edit: Bin kein Verfechter von Hashlisten oder anderem Dingen, ich bin ein Verfechter von erprobten Techniken auf bestimmte Szenarien ^^.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

bevor ihr hier jetzt die Gräben aushebt .

Ich redete tatsächlich von Arrays, nicht von (verketteten) Listen, bitte entschuldigt die Ungenauigkeit. Außerdem meinte ich bei meinem letzten Post auch keine Ids mehr sondern wirklich Indicies in diesem Array.

Was ich aber dazu gedacht habe, war eine (verkettete) Liste oder ein dynamisches Array, wo ich frei gewordene Indicies speichern kann, damit ich beim Hinzufügen eines Elementes schnell einen unbenutzten Eintrag im Array finden kann.

Wie coolcat schon richtig erfasst hat, ich brauche die Zuordnung um bei der Netzwerkkommunikation und beim Speichern objekte *eindeutig* ansprechen zu können. Ich kann ja übers Netzwerk schlecht Pointer verschicken und schon garnicht in dateien schreiben, denn das wird ja auf jedem System anders sein (noch dazu beim Unterschied zwischen 32 und 64 bit). Oh und wenn du die Tabelle meinst, die ich eventuell in die Datei schreiben wollte, das wäre vielleicht hilfreich für bestimmte Aktionen beim Auslesen, damit man schnell ein Objekt finden kann. Aber nicht obligatorisch.

Nochmal danke für die beteiligung hier. Wenn jemand noch einen Vorschlag hat, der eine höhere Performance als ein Array (evtl. mit zusätzlicher Liste für freie Indicies) erzielt, möge er jetzt sprechen oder für immer schweigen

Gruß Lord Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Ein paar Ideen hab ich noch. In meiner Fontbibliothek muss ich Buchstabeninstanzen anhand deren Charcode ablegen. Ist in etwa vergleichbar wie dein Problem. Dort könnte ich am einfachsten mit einem "Array[0..$FFFF] of blah" arbeiten. Würde ausreichen. Ich hatte mich aber für einen zweigeteilten Weg entschieden. Und zwar ist das eigentliche Array nur ein Array welches Pointer, auf andere arrays, enthalten kann. Der Grund ist einfach. Selbst, wenn ich nur einen Buchstaben habe, dann belegt ein komplettes Array immer volle 256k. So habe ich zwar ein paar sehr sehr kleine Operationen (and, shr bzw if abfrage) mehr allerdings der Speicherverbrauch ist deutlich geringer.

Freiwerdende Indizes. Da würde ich eher eine Liste bevorzugen. Je nachdem wie viel Fluktuation bei den IDs du hast sogar eine Liste aus ID Blöcken und den Speicherverbrauch nicht ausarten zu lassen. Denn dynamische arrays etc müssen bei Bedarf kopiert werden. Was immer unpraktisch ist.

Eventuell solltest du aber auch überlegen ob es nicht sinnvoll wäre die IDs für eine gewisse Zeit lang zu sperren? Nehmen wir mal an du löscht ein Objekt. Damit wird dessen ID in die Liste eingetragen und direkt im Anschluss wird ein neues Objekt erstellt und dieses bekommt die erste ID aus der Liste. Wenn die Liste aber nur eine ID enthält bekommt das neue Objekt genau diese ID wieder zugewiesen. Da es ja auch mit Netzwerk arbeiten soll kann es dort bei der Kommunikation zu Verzögerungen kommen. Wenn also gerade jemand auf das eigentliche Objekt geschossen hat etc., dann wäre es gut möglich, dass du ein Paket bekommst in dem steht "beschieße objekt xyz" nur ist Objekt xyz nicht mehr das Selbe. Von daher kann es sinnvoll sein die IDs für 30 Sekunden zu blocken. Selbst wenn also eine ID frei wäre solltest du innerhalb der 30 Sekunden trotzdem eine neue nehmen. Du würdest so also einen Timestamp pro ID benötigen. Die Liste sollte dann auch chronologisch sein. Wenn also die erste ID zu jung ist werden es alle anderen auch sein. Eine Abfrage und schon weißt du bescheid.

Dann sollte man für die freien IDs einfach einen fi-fo nehmen (z.B. ne Liste dessen Anfang und Ende man kennt, und entsprechend pushed und popt... oder -zumindest bei c++- einfach ein entsprechendes Template nehmen ).
Der liefert einem immer die "älteste" freie ID. Da ja prinzipiell einige mehr IDs zur Verfügung stehen, als es Objekte geben darf (ansonsten hat man bei neuerstellung von Objekten eh Probleme) würde das schon reichen, und man kann auf eine weitere Abfrage verzichten.



Naja du hast halt selber, ich sage dann mal "ausversehen" Liste geschrieben vorher. In manchen Fällen, besonders beim Programmieren, muss man sich ja schon präzise ausdrücken. Insbesondere sind die Unterschiede zwischen Liste und Array ja schon gewaltig. Woher soll man wissen, was einer meint, wenn es nicht das ist, was er schreibt .

Der Konstante Aufwand ist sowas wie worst-case. Man hat eine Maximale Anzahl Objekten=Konstante. Also O(maximale Objekte), wenn man das als Variablen ansieht natürlich O(n).

Implementationsaufwand: beides so gering, dass es egal ist. Da ich beides schonmal geschrieben habe, ist das halt mein Erfahrungswert.

Ich glaube nicht, dass ein Krieg ausbricht. Wie man seine Daten verwaltet, kommt einfach auf ein paar Faktoren an, wie man sie sortiert haben möchte, wie oft man zugreift, oder ändert, oder löscht, sowie wieviel Speicherplatz/Rechenzeit man zur Verfügung hat. Die Informationen waren am Anfang ja nicht da, weswegen unterschiedliche Methoden zum lösen des Problems vorgeschlagen wurden.

FiFo wäre natürlich gut geeignet aber auf keinen Fall kann ich da alle möglichen verbleibenden IDs speichern. Bei 2^32 möglichen IDs (Integer), wäre das eine viel zu große liste. Ich kann da nur diejenigen Speichern, die als "aus der Reihe" als frei bekannt sind. Also die mitten drin stecken. Das ist denke ich auch sinnvoll. "freie IDs"-Blöcke sind gut geeignet denke ich, weil einige Objekte ja mit anderen zusammenhängen und sofort hintereinander erzeugt werden. Beispielsweise eine Einheit, die vom "Blueprint" direkt mit Ausrüstung erzeugt wird. In dem Fall belegt sowohl Einheit als auch Ausrüstung jeweils eine ID. Da ist es hilfreich, wenn ich beim Freigeben gleich einen kompletten Block markieren kann bzw dann halt hintereinander den "freie IDs"-Block vergrößern (ist ja dann nur eine Inc-Anweisung). Diese Liste wäre dann am besten geordnet, nach Blockbeginn. Und die letzte Änderung am Block (für jede ID wäre hier nicht unbedingt möglich) kann ich da ja gleich mitspeichern. Denn Lossy hat natürlich recht, es kann im Netzwerk immer zu Verzögerungen kommen. Obwohl das bei mir dank Rundenbasiertheit nicht ganz so dramatisch ist, ist es denke ich immernoch angebracht. Schließlich kann das ja nicht nur durch Spielerbefehle sondern auch durch Serveraktionen (Schwarze Löcher oder sonstige asozialitäten) passieren.

Lossy, ich stimme dir zu. Ein dynamisches Array, wo ich dann wiederum konstante Blöcke reinpacken kann, ist glaubich ne gute idee. Wird wahrscheinlich auch dem Speichermanager besser gefallen als das andere (mal eben nen neuen Platz für nen 5000 mal ein Pointer großen bereich zu finden, ist bestimmt kein Spaß ). Da ja mit der verketteten Liste der freien ID-Blöcke auch die Suche wegfällt, muss ich mir darum auch keine Sorgen mehr machen.

Danke nochmal für all die Tipps

Gruß Lord Horazont

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb