Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Quadtree und Fragen dazu

Werbeanzeige

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

31

30.10.2012, 15:54

OK, Missverständnis ...
Aber Cache ist ein interessantes Thema.
Partikelsimulationen werden ja auch im großen Stil auf Clustern durchgeführt.
Vielleicht könnte man sich mal anschauen, wie die das lösen.
David Scherfgens Website | Konzentrationstest Polizei

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

32

30.10.2012, 15:56

Ich muss zugeben, dass das auch sehr leicht zu missverstehen war. ;)
m4studios

Horus

Treue Seele

  • »Horus« ist der Autor dieses Themas

Beiträge: 251

  • Private Nachricht senden

33

30.10.2012, 16:36

Das Grid wird immer schneller. konntes es auf knappe 5ms pro Frame für den Gridaufbau drücken.


Ich nehme jetzt solche: Listen als Sektoren was meint ihr?
public List<int>[,] Sector;


Momentan wird für jeden Sektor jedes Frame noch .Clear aufgerufen.

Ich werde versuchen, Zellen die ihre Sektoren Verlassen umzusortieren, anstatt alle Sektoren zu "Clearen" in jedem Frame. Da sind noch bestimmt 30% mehr Leistung rauszuholen hoffe ich.

mal sehen :D


Ja Cluster :wacko: Ich bin noch nicht ganz so weit leider.
Aber ich sehe mein Prozessor läuft nie über 50% , Multithreading daran denke ich als nächstes kommt vor den Clustern.

LG
Bilder zu meinem Projekt: ParSim

Horus

Treue Seele

  • »Horus« ist der Autor dieses Themas

Beiträge: 251

  • Private Nachricht senden

34

30.10.2012, 18:40

Mit 32K Partikeln Lässt sich ein Grid mit 16384 Sektoren in ~1,35 ms Updaten.
Partikel pro sektot ~2
Mit 200K Partikeln Lässt sich ein Grid mit 16384 Sektoren in ~7 ms Updaten.
Partikel pro sektot ~12
Mit 320K Partikeln Lässt sich ein Grid mit 16384 Sektoren in ~14 ms Updaten.
Partikel pro sektot ~16
Mit 320K Partikeln Lässt sich ein Grid mit 65536 Sektoren in ebenfalls(!) ~14 ms Updaten.
Partikel pro sektot ~5
Mit 320K Partikeln Lässt sich ein Grid mit 262144 (!) Sektoren in ebenfalls(!) ~14 ms Updaten.
Partikel pro sektot ~1

Die Rechenzeit nimmt einigermaßen linear zu mit der Partikelzahl zu. Die Rasterung hat keinen Einfluss.
Ist mega schnell finde ich.

Es wird jetzt nur upgedated wenn Partikel einen Sektor verlasen und in einen anderen gehen.

Mal sehen wie es sich mit der Iteration gestaltet. Ich würde gerne vermeiden Kollisionen alle doppelt aufzurufen.
Bilder zu meinem Projekt: ParSim

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

35

31.10.2012, 10:58

Zitat von »Horus«

Mal sehen wie es sich mit der Iteration gestaltet. Ich würde gerne vermeiden Kollisionen alle doppelt aufzurufen.

Das kannst du mit einem "Moving Flag" machen.
Dabei merkst du dir die Nummer des Frames, in dem ein Partikel zuletzt auf Kollision geprüft wurde.

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

foreach(Particle p in particles)
{
    foreach(Particle q in spatialDataStructure.enumParticlesAround(p.position, p.radius))
    {
        // Nur dann auf Kollision prüfen, wenn der andere Partikel noch nicht geprüft wurde.
        if(q.checkedForCollisionInFrame != currentFrameNumber)
        {
            // Kollisions-Test durchführen!
        }
    }
    
    // Merken: Dieser Partikel wurde bereits auf Kollision getestet.
    p.checkedForCollisionInFrame = currentFrameNumber;
}

// Später:
++currentFrameNumber;
David Scherfgens Website | Konzentrationstest Polizei

Horus

Treue Seele

  • »Horus« ist der Autor dieses Themas

Beiträge: 251

  • Private Nachricht senden

36

31.10.2012, 12:30

@ Dot,

eine Durchlaufen aller Sektoren (for in for schleife)
VS
ein Durchlaufen aller Partikel und Absuchen der Nachbarsektoren

Ergbnis
Beide hoher Partikeldichte ist ein Durchlaufen aller Sektoren minimal schneller!

Bei niedriger Partikeldichte schneidet ein durchlaufen aller Partikel und Absuchen der Nachbarsektoren
merklich besser ab nehme ich an.

Beide Methoden sind immens Langsam! :thumbdown:


Zum Thema Zeiger auf Nachbarsektoren, das dauert länger als die Nachbarsektoren zu berechnen, zumindest in diesem 2D Grid. :thumbdown:


@David
Haut das mit den Moving Flag auch hin, wenn ein Partikel in einem Frame mit mehreren Partikeln zusammenstößt? Er ist dann ja schon abgehackt.
Ich kann ja nicht in jedem Partikel gigantische Arrays anlegen in denen ich abspeicher wann irgendwo ein Kontakt war. ?(
Vielleicht habe ich das auch missverstanden?


Ich verfolge momentan einen etwas anderen Ansatz, erste Tests verlaufen gut.

Ich Liste jeden Partikel in dem blauen Sektor in allen Rot markierten Sektoren



Jetz gehe ich wie folgt vor:


private void PassSectors5()
{
for (int x = 1; x < Config.SectorNumber - 1; x++)
for (int y = 1; y < Config.SectorNumber - 1; y++)
for (int Index1 = 0; Index1 < Grid.Sector[x, y].Count; Index1++)
for (int Index2 = Index1; Index2 < Grid.Sector[x, y].Count; Index2++)
//Physics to come here

}


Was meint ihr dazu?

LG
Bilder zu meinem Projekt: ParSim

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

37

31.10.2012, 12:59

Zitat von »Horus«

Haut das mit den Moving Flag auch hin, wenn ein Partikel in einem Frame mit mehreren Partikeln zusammenstößt? Er ist dann ja schon abgehackt.

Ja, weil Kollision symmetrisch ist. Entweder der andere wurde bereits geprüft (und hat damit die Kollision mit dem aktuellen Partikel bereits entdeckt) oder er wurde noch nicht überprüft und wird es folglich jetzt.
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Horus

Treue Seele

  • »Horus« ist der Autor dieses Themas

Beiträge: 251

  • Private Nachricht senden

38

01.11.2012, 21:37

Ich habe die Flags von Scherfgen umgesetzt, habe jetzt Sektoren, genau so groß wie die Partikel. Maximal passen 4 Partikelzeiger rein.

Sieht alles ganz gut aus. Eine dichte Annsammlung zufällig plazierter Partikel "explodiert"!



Das Material ist irgendwie klebrig elastisch, so wie es eingestellt ist. Aber zur Optimierung werde ich bestimmt nochmal nachfragen. Ob ich dazu einen neuen Thread machen soll ?( Mit einem Quadtree hat das alles nicht zu tun. :P

LG
Bilder zu meinem Projekt: ParSim

Horus

Treue Seele

  • »Horus« ist der Autor dieses Themas

Beiträge: 251

  • Private Nachricht senden

39

02.11.2012, 21:26

Mit 20K Partikeln schafft mein Laptop ~35 FPS ist schon ganz ok aber naja.

Bisher speichere ich in einem 2D int[x,y] Array die Indizes anwesender Partikel. Die Partikel selber befinden sich in einem 1D Array.
In jeden Sektor des 2D Array passen maximal 3 Partikelindizes als int.

Jetzt wurde in diesem Thread von Zeigern gesprochen ist obiges gemeint, so wie ich es schon umgesetzt habe?
Oder ist eher folgendes gemeint? :

Zitat

Um Sicherheit und speziell Typsicherheit zu gewährleisten, unterstützt C# standardmäßig keine Zeigerarithmetik. Mit dem unsafe-Schlüsselwort können Sie jedoch einen unsicheren Kontext definieren, in dem Zeiger verwendet werden können. Weitere Informationen zu Zeigern finden Sie unter dem Thema Zeigertypen.


Irgendwie komme ich nicht weiter, was ich auch anstelle wird es nicht mehr schneller :dash:

LG
Bilder zu meinem Projekt: ParSim

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

40

02.11.2012, 22:44

Zeigerarithmetik ist etwas ganz anderes als Zeiger. Vom Prinzip her sind in C# alles das Zeigertypen, was eine Instanz einer Klasse ist oder per new erzeugt wurde.
Eventuell solltest Du Deinen Code einfach mal als Release kompilieren und "ohne Debug" starten, um zu sehen wie viele FPS es dann schafft. Das ist nämlich meist ein GANZ anderer Wert, als wenn man es als Debug kompiliert hat oder als Debug gestartet hat.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige

Ähnliche Themen