spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Ja, diese schwammige Beschreibung hatten wir schon. Es geht also nur um Partikel, die gegenseitig kollidieren? Dann ist ein regelmäßiges Gitter die beste Datenstruktur. Die Partikel lassen sich super schnell einordnen in O(1) und du kannst in O(1) auf die benachbarten Felder zugreifen. Wozu du da eine rekursive Verschachtelung brauchen würdest und welche Vorteile diese bringen soll, ist mir nicht ersichtlich und Dir scheinbar ebenfalls nicht bewusst.

@BlueCobold:
Ein Gitter wird dann problematisch, wenn die Partikel sehr ungleich verteilt sind.
Partikel, die in der selben Gitterzelle sind, müssen paarweise auf Kollision getestet werden, also O(n²) Aufwand. Bei 1000 Partikeln in derselben Gitterzelle wären das schon 1000*999/2 = knapp 500.000 Tests.
Hier müsste man dann ein sehr feines Gitter wählen, was aber auch den Speicherverbrauch drastisch erhöht. Regionen, die leer sind, wären sehr fein unterteilt.
Der Quadtree passt sich automatisch an die unterschiedlichen Partikeldichten an.

Außerdem gibt es noch das Problem der "Größe der Welt".
Beim Gitter wächst der Speicherverbrauch mit der Größe der Welt (wenn man die Gitterzellen gleich groß lässt).
Der Quadtree dürfte nur logarithmisch wachsen.

Übrigens muss es ja nicht unbedingt ein Quadtree sein, oder?
Beim Photon Mapping (Verfahren für globale Beleuchtung), wo ebenfalls ein sehr ähnliches Problem gelöst werden muss - nämlich beim Einsammeln der Photonen - benutzt man normalerweise einen kd-Baum.
kd-Bäume sind beim Raytracing sowieso sehr beliebt. Schau dir die mal an.
Wenn ich mich nicht täusche, würde bei einem kd-Baum der Speicherverbrauch völlig unabhängig von der Größe der Welt sein, denn die Stelle der Unterteilung kann frei gewählt werden (anders als beim Quadtree).

David, wegen der Komplexität sagte ich ja auch schon, dass die Gitter im Vergleich zur Partikeldichte "klein" sein soll, damit eben nicht so viele reinpassen und somit auch nicht so viele geprüft werden müssen. Klar fordert das viel Speicher, aber 32k Partikel in einem Baum in jedem Schritt zu updaten, das kann nicht schnell werden. Die Partikel sind ja leider nicht statisch, sondern sehr dynamisch. Ob sich das umsetzen lässt, das kann man ohne konkrete Dimensionen nur schwer sagen, aber dazu schweigt er sich bisher ja leider komplett aus. Bei 2.000² Feldern wäre das alles ja kein Akt, bei 2.000.000² sähe das schon schlechter aus.

Das sagt leider gar nichts aus. Die Anzahl der Ebenen des Baum oder die Anzahl Felder des Grids wären relevant, sowie die Info darüber, wie viele Partikel Du momentan maximal pro Feld (egal ob Baum oder Grid) hast. Es macht halt schon einen Unterschied, ob der Baum 10 Ebenen hat und das Grid 2000² mit jeweils nur 3 Partikeln pro Feld oder ob der Baum nur 3 Ebenen und das Grid nur 200² Felder hat mit jeweils 50 Partikeln darin. Ebenso wäre wichtig zu wissen wie groß die Partikel sind und wie groß der gesamte Simulations-Raum. Wenn die Partikel 5cm Durchmesser in einem 3m² Feld haben, dann ist das etwas ganz anderes als 2mm Durchmesser Partikel in einem 100m² Feld oder gar 0.0001mm Durchmesser in einem 2km² Feld. Daraus ergibt sich, welcher Ansatz überhaupt praktikabel wäre.

Versteh ich das richtig, laufst du in jedem Frame alle Zellen des Grid bzw. alle Nodes des Quadtree durch!? Wenn ja, wieso? Speicher deine Partikel in einem normalen Vektor und jedes Partikel enthält Zeiger auf die Zellen/Nodes, in denen es sich befindet. Dann brauchst du zum Updaten nur diesen Vektor durchlaufen und nicht 90% leere Zellen/Nodes...

Wie BlueCobold schon gesagt hat: Hierarchische Struktur vs. Grid ist in dem Fall am Ende einfach ein Laufzeit vs. Speicherverbrauch Trade-off...

Huhu, *hüpf*, hallo!? Eventuell kannst Du ja mal auf meine Fragen eingehen?

Verwend ein einfaches, regelmäßiges Grid. Dann kannst du immer direkt auf jede Zelle zugreifen, genau das ist doch der Punkt!?