Ich weiß nicht, wie Du das meinst. Wenn ich 64 Bit brauche, muss die Variable/Speicher ja mindestens 64 Bit abbilden können, also auch mindestens 64 Bit groß sein. Sollte man die Bits auf mehre Variablen verteilen, ist eine weitere Logik notwendig, um die richtige Variable zu ermitteln. Ich werde mir das std::bitset mal genauer angucken, wie das intern arbeitet. Danke für den Link.Chromanoid hat geschrieben:Zum Bitset: Ist die STD-Implementierung da so doof? http://en.cppreference.com/w/cpp/utility/bitset/bitset
Ich denke solche Techniken/Algorithmen lohnen sich wie gesagt erst bei einer bestimmten Anzahl von Elementen. Ich habe nochmal einen Test mit 20 Elementen gemacht, und selbst da ist die std::unordererd_map etwas langsamer, als eine lineare Suche in einem Array oder Liste.Chromanoid hat geschrieben:Zu Map-Zugriff: Ich bin ja kein C++-Entwickler, aber die langen Zugriffszeiten bei der Map wundern mich ein bisschen. Gibt es einen Unterschied zwischen Zugriff über map.find und map[key]? Eigentlich sollte das ja eine Hashcode-Berechnung sein, dann ein Speicherzugriff und ggf. ein, zwei Vergleiche mit weiteren Speicherzugriffen.
Hier meine Messergebnisse mit 20 Elementen:
Array -> 2031 ms
Liste -> 2594 ms
dynamic_cast ->102890 ms
std::unordered_map -> 2907 ms
Ok, ich glaube ich habe es verstanden. Wenn ich jetzt auf einer Karte 240.000 Objekte habe und es gibt 33 verschiedene Komponenten, dann habe ich ein zweidimensionales Array mit der Größe [240.000][33], oder anders ausgedrückt, eine 240.000 * 33 Matrix. Ein Objekt kennt seine Zeile in dieser Matrix und in jeder Spalte steht der Index der Komponente. Also Spalte 0 ist z.B. für die Armor-Komponente, Spalte 1 für die Weapon-Komponente, usw.. Wenn ich jetzt bei einem Objekt wissen möchte, ob und welche Armor-Komponente es hat, gucke ich in der Zeile, die dem Objekt zugewiesen ist, in die betreffende Spalte, bei Armor also Spalte 0. Also KomponenteIndex = Matrix[Objektzeile][KomponentenSpalte]; Da steht dann z.B. -1, für keine Armor, oder halt der Index/Position für die Armor im ArmorArray.Chromanoid hat geschrieben:Zur Matrix: ich meinte eine ziemlich billige Form der Implementierung, die mir so in den Sinn gekommen ist.
1. Ermittle die maximale Anzahl aller Komponenten.
2. Baue einen Array mit ANZAHL_ENTITIES*MAX_ANZAHL_KOMPONENTEN aus 24bit Ganzzahlen -> "Matrix".
3. Pro Komponente halte einen Array aus Stucts mit den komponmentenspezifischen Daten zu allen Entities, die diese Komponente nutzen. In der Struct befindet sich mindestens die Zeilennummer des Entity in der "Matrix". Pro Komponente führe weitere Datenstrukturen, um die Daten geschickt zu verwalten (Quadtree usw.). Komponenten recyclen ihre Entity-spezifischen Datenstrukturen.
4. Wenn ein neues Entitiy angelegt wird, reserviere eine Zeile in der "Matrix" und nutze den Index der Zeile zur Identifikation. Registriere das Entity bei allen gewünschten Komponenten und merke dir die Indizes zu jeder Komponente in der "Matrix" - der Rest der Zeile ist 2^24 oder was auch immer.
Zahlreiche Zugriffsmuster sind damit ziemlich optimal zu erledigen. Man kann in der Matrix und bei den Komponenten Chunking betreiben, um nicht von Anfang an Platz für die maximale Anzahl Entities machen zu müssen.
Welche Vorteile sehe ich da?
1. Eine Komponente muss nicht mehr gesucht werden, entweder sie existiert oder nicht.
2. Ein Downcast ist nicht mehr Notwendig.
3. Ich kann eine Komponte, bzw. das Array, durchgehen, ohne dass ich auf andere Daten achten muss. Also z.B. alle Licht-Komponenten.
Punkt 1 und 2 kann ich auch erreichen, wenn ich die Komponentenliste komplett ändere, bzw. gegen eine Struktur mit Pointern zu allen Komponentenarten ersetze. Oder die Zeile pro Matrix direkt im Objekt gespeichert wird. Durch solche Lösungen wird natürlich Punkt 3 nichtig.
Punkt 3 klingt zwar interessant, aber ich habe bisher keine Situation, wo ich das sinnvoll nutzen könnte. Alle Mechaniken/Systeme, die aufgrund von einer Komponente etwas machen, haben so oder so ihre eigenen zusätzlichen Strukturen.
Die gute alte Downcast-Diskussion... ;-)dot hat geschrieben:Ich würde rein prinzipiell hier das Design hinterfragen; bei Anblick von dynamic_cast/typeid() sollten generell sofort immer erstmal die Alarmglocken läuten. Downcasts, egal in welcher Form, sind in der Regel Symptom eines grundlegenden Problems im Design. Ob du nun dynamic_cast, typeid oder irgendein selbst gebasteltes typeid (denn der Enum ist nix anderes) verwendest, spielt keine Rolle. Das grundlegende Problem ist, dass du Code hast, der nur ein abstraktes Interface kennt, der aber auf einmal wissen muss welche konkrete Implementierung hinter dem Interface steckt. So eine Situation zeigt in der Regel dass das Interface nicht zum Problem passt oder das Problem nicht zum Interface. Implementierungsabhängiges Verhalten sollte hinter einem Interface stecken und nicht davor, wofür bräuchte man sonst ein Interface!?
Die Frage ist, wie löse ich das anders? Die einfachste Lösung wäre, dass jedes Objekt einen Pointer oder Index zu jeder Komponente hat (geht in die Richtung der Matrix-Idee von Chromanoid). Ich rechne aber damit, das ich am Ende über 60 verschiedene Komponenten haben werde. Das bedeutet, jedes Objekt hat 60 Pointer/Indexwerte, von denen dann in der Regel 3 bis 5 genutzt werden, vielleicht auch mal 10, aber 50 werden meist total nutzlos leer sein. Ziemliche Speicherverschwendung aber best Performance und kein Downcast.... wahrscheinlich werde ich das, wenn das Prototypen der Komponenten abgeschlossen ist, mal ausprobieren.
Schönes Beispiel, so ähnlich soll das am Ende ablaufen. :)Chromanoid hat geschrieben:@dot Meinst Du wirklich das Vermeiden von Downcasts bzw. die Nutzung von Typ-IDs, ist bei der Implementierung von völlig beliebigen Spielregeln eine sinnvolle Einschränkung? Hier ein Beispiel: Gib mir alle Entities in Bereich R (Abfrage an Physik-Komponente o.Ä.). Füge allen Entities mit einer Health-Komponente 10 Schadenspunkte zu. Alle Entities, die zusätzlich eine "Eiswesen"-Komponente haben, bekommen die Komponente "Vergiftet" aufgedrückt. Wenn schon die Komponente "Vergiftet" vorliegt, wird der Vergiftungsfaktor verdoppelt. Wenn das Entity eine "Charakter"-Komponente hat und ihr Name mit Z anfängt, gibt's 5 Extraschadenspunkte.
Nochmal Danke für die Antworten, über das Alles werde ich jetzt erstmal in Ruhe nachdenken.