Algorithmus um (System)Karten zu erzeugen?

[odenter]

Ich hab 100.000 Sterne mit bis zu 10 Planeten,teilweise werden die Eigenschaften schon dynamisch erzeugt/gesetzt.

Allerdings hab ich noch ein anderes schönes Performance Problem, hab schon im Forum zur Engine nachgefragt. Das rendern der 100.000 Sterne, die alle als Sphere dargestellt werden ist hochgradig unperformant. Allerdings kann ich so einfach das angeklickte Objekte bekomme, sind alles sog. Nodes, durch klick auf einen bekomme ich mein internes System-Objekt wo ich dann Name, Beschreibung und Liste der Planeten habe.

Hab schon überlegt quasi ein Bild zu rendern, in dem einzelne Pixel, eben ein Stern sind. Wäre mit Sicherheit deutlich schneller, aber dann kann ich nicht so zoomen wie ich mir das ursprünglich vorgestellt habe. Naja darüber diskutier ich ja auch im Engine-Forum.

[Aramis]

Für so enorm viele Objekte wird es nicht ausreichend sein sie einfach als ganz normale Nodes im 'flachen' Szenengraph zu halten .. das ganze wird dann viel zu langsam, von den Such&Cullzeiten her. Auch das von dir beschriebene Problem nur mit enormem Zeitaufwand (O[n^2]) doppelte Koordinaten herausfischen zu können, deutet auf eine mangelhafte Datenstruktur hin ...

Ein Octree wäre der Klassiker um spatial partitioning in einem 3D-Raum zu betreiben .. ggf. ist eine auf die typische Form einer Galaxis spezialisierte Datenstruktur aber geschickter (nur so als unausgegorene Idee: Spiralarme der Galaxis als erste Ebene, dann jeden Spiralarm nochmals in Untersektoren unterteilen ..).

Zum Rendern: LOD! Alle Sterne die nah genug sind, dass man sie wirklich wahrnimmt als Spheren rendern, mit (von irrLicht vermutlich nicht unterstützem ) Instancing kein Problem von der Grafikleistung her. Entfernte Sterne .. naja, Krishty's Sternenartikel ist die Nobelvariante, nur einzelne Pixel zu zeichnen wird hemmungsloses Flimmern produzieren. Als letzte Optimierung ganze Sektoren in Billboards vorrendern und nur alle paar Frames aktualisieren.

[Despotist]

Und wo genau berechnest du hier einen Abstand? (Stichwort: Subtraktion)

Sorry, muss natürlich

Code: Alles auswählen


return ((a->pos.x - b->pos.x)^2 + (a->pos.y - b->pos.y)^2 + (a->pos.z - b->pos.z)^2)


heißen. Wenn man müde ist sollte man keinen Code raushauen der einem nicht selbst um die Ohren fliegen kann

Darum geh ich jetzt auch ins Bett.

Trotzdem wäre korrigieren besser als nörgeln

@odenter:
Ich hatte dich schonmal auf Infinity Universe geschubst aber du scheinst es verpasst zu haben. Darum hier nochmal ein expliziter Link der einige deiner Fragen adressieren dürfte.

Despotist

[Krishty]

Den Operator ^ gibt es für Floats nicht Ist vielleicht Klugscheißerei, aber einen Thread, warum ^ nicht wie gewollt funktioniert, gibt es alle paar Monate.

Code: Alles auswählen


template <
    typename t_Type
> inline t_Type Square(
    t_Type const & p_Value
) {
    return (p_Value * p_Value);
}

return (Square(a->pos.x - b->pos.x) + Square(a->pos.y - b->pos.y) + Square(a->pos.z - b->pos.z));

& durch & ersetzen.

[odenter]

Das ganze auf einen Octree umzustellen wäre kein Problem, dafür müsste ich nur ein paar Zeilen anpassen.
EDIT:
Problem hat sich beseitig, einfach nur einmal an die Graka senden und rendern, statt 100.000 mal und schon gehts schnell.

Wie ich das suchen nach doppelten beschleunigen kann weiss ich schon, muss dafür allerdings den Code zum erzeugen der Sterne nochmal anpassen, so dass keine floats rauskommen sondern nur Ganzzahlen, diese kann ich dann als Indizes verwenden.
Oder mit ner std::map<intX, std::map<intY, std::map<intZ, System*>>>, dann geht das suchen maximal schnell.

Also die Engine zeigt schon nur Objekte an die man sieht, also weiter entfernte werden nicht gerendert bis man näher kommt, keine Ahnung nach welcher Regel die das machen, hat mich auch nie interessiert ich wollt das ja nur benutzen.
Das ganze nochmal in Sektoren zu zerlegen gefällt mir eigentlich ganz gut, ich denke das ist auch nicht dramatisch.
Das würde auch mein Problem beim rendern der Map erledigen, da ich das dann zwei Stufig machen könnte, alle Sektoren rendern und bei Auswahl eines Sektors eben die enthaltenen Sterne.

Das infinity Universe habe ich auch nur kurz überflogen, 24h pro Tag sind einfach zu wenig. Ich komme eh erst wieder richtig ab Donnerstag dazu was zu machen. Spätestens nächstes Wochenende gucke ich mir das nochmal genauer an.

[odenter]

So hab mal ein bischen rumprobiert und den Code zum erzeugen der Galaxy inkl. Systeme nochmal überarbeitet, um mal ein bischen die Geschwindigkeiten zu testen.

Also Galaxy wird zerhackt in Sektoren, die jeweils eine bestimmte Anzahl Sterne haben sollen. (Später für das rendern der Map)
Lange Rede kurzer Sinn ich benötige jetzt 48 Sekunden um um bei einer Eingabe von 1.000.000 Sternen, wobei ein Stern 10 Planeten enthalten soll) 100489 Sektoren mit jeweils 10 Sternen zu erzeugen und jeder Stern enthält 10 Planeten.
Also werden 1.004.890 Sterne erzeugt und 10.048.900 Planeten.
Der Speicehrverbrauch geht dafür nur einmal auf knapp 600 MB hoch, ist die Liste der schon vorhandenen Positionen.
Da dies allerdings nur Testcode ist, muss ich jetzt wohl aufpassen bei den Eigenschaften die ich meinen Sternen und Planeten gebe, also vielleicht nicht ein 32 Bit Int für einen Wert sondern einen 32 Bit Int für 32 Werte.

Werde den Testcode nun so abändern, das nur die Positionen erzeugt werden und das Objekt selbst (also Sternen-System inkl. Planeten) tatsächlich lazy initialisiert wird. So dürfte der Speicherverbrauch nochmal deutlich absinken.

[Krishty]

Ein paar Tipps für geringeren Speicherverbrauch am Rande:

Falls du noch XP nutzt, aktiviere den Low-Fragmentation-Heap.

Ein besonderer Allocator für die ::std::maps könnte die Effizienz enorm steigern, wenn du schon vorher weißt, wieviele Sterne und Planeten du erzeugst.

Achte auf das Alignment der Klasse, d.h. sortiere die Elemente der Größe nach oder trickse mit #pragma pack. Das kann manchmal genauso viel bringen wie Bit-Fields.

Falls deine Planeten virtuelle Funktionen enthalten, sind das schon 40 MB allein für die vftables. Da könnte ein anderes Dispatching-Verfahren vielleicht was rausholen – kA, ob es dir die 7 % wert sind.


Schon Ideen für das Rendern weit entfernter Sterne?

[odenter]

Hier auf der Arbeit habe ich noch ein WindowsXP (32Bit) zuhause habe ich ein Windos 7 (64Bit). Werde mir das mit dem Heap trotzdem mal angucken.

Ansonsten bin ich jetzt bei ~16 MB Speicherverbrauch.
Dafür erzeuge ich nun natürlich auch kaum noch was, sondern nur noch die Anzahl der Sektoren, diese werden mit Ihren Koordinaten (0,0), (0,1), (0,2) usw. in meine

Code: Alles auswählen


std::map<int, std::map<int, Sector*>> _sectorList;


geschrieben.
Und alle sichtbaren Sektoren werden halt just in Time initialisiert, genauso wie dann auch die Planeten. Muss nur noch Code zum speichern/laden bauen.
Ich werde die Sternen-Karte erstmal in 2D rendern, so brauche ich dann nur die Sektoren rendern in dem man sich befindet und die angrenzenden. Damit ist das Problem erstmal weg.

Sollte dann später, falls ich mal Lust habe, aber auch relativ leicht auf 3D umstellbar sein, so wie der Code aktuell ist.
So mach nun Feierabend und muss zur Mathe Nachhilfe (ich hasse Mathe).

[odenter]

So das Problem das da mal war ist keins mehr.

Nur zur Info für alle die sich hier rege beteiligt haben.
Ich zerlege die Galaxy nun in Sektoren (Test-Screenshot) im Anhang. Verbindungen zwischen den Systemem wird es nicht mehr geben. Es gibt einfach verschiedene Jumpdrives mit unterschiedlichen maximal Entfernungen.

Rendern werde ich nun nur eine Handvollsektoren (im Screenshot sind noch mehr), nämlich diejenigen die in Reichweite liegen, diese werden auch entsprechend initialisiert. Die Galaxy/Sektoren-Karte wird nun also doch 3D statt 2D.

[Loebl]

Wenn ich dich richtig verstehe sollen
1. alle Sterne irgendwie miteinander verbunden werden (man kommt von jedem beliebigen punkt via Route zu jedem anderen beliebigen Stern)
2. nicht zu lang
3. nicht überkreuzen

Ich hatte mal was ähnliches, hab dann aber umkonzipiert und bin übers drübergucken nicht hinausgekommen.
Vielleicht hilft dir das weiter?
http://de.wikipedia.org/wiki/Delaunay-Triangulation

[eXile]

Wenn ich dich richtig verstehe sollen
1. alle Sterne irgendwie miteinander verbunden werden (man kommt von jedem beliebigen punkt via Route zu jedem anderen beliebigen Stern)
2. nicht zu lang
3. nicht überkreuzen

Ich hatte mal was ähnliches, hab dann aber umkonzipiert und bin übers drübergucken nicht hinausgekommen.
Vielleicht hilft dir das weiter?
http://de.wikipedia.org/wiki/Delaunay-Triangulation

Eine Delaunay-Triangulation ist 1. keine Triangulation minimaler Länge, und 2. nur eine Triangulation - vielleicht will man ja sowas wie Vierecke im Wegenetz haben, etc. Meiner Meinung nach lediglich als Ansatz verwendbar, danach müsste man viele Verbindungen zufällig wieder löschen, und "lange" Verbindungen (kreuzungsfrei) wieder hinzufügen.

[exploid]

http://www.jongware.com/galaxy1.html

[dronus]

Eine Delaunay-Triangulation ist 1. keine Triangulation minimaler Länge, und 2. nur eine Triangulation - vielleicht will man ja sowas wie Vierecke im Wegenetz haben, etc.

Eine Triangulation minimaler Länge ist NP-hart. das möchte man lieber nicht in Spielen haben ...sowas scheints in Office schon genug zu geben :-]
Ich denk Delaunay sieht für den Betrachter angenehm und plausibel aus. Man kann dann ja contentbasiert Linien löschen, z.B. wenn Sternenvölker im Clinch liegen ...