Quadtree und Fragen dazu

1
2
3
4
…
- 5
- 6
- 7
- 8
- 9
- 10
11

Werbeanzeige

furbolg

Frischling

Beiträge: 74

30.10.2012, 14:46

Kleine Ergänzungsfrage (wollte nicht exta ein Topic öffnen)

Welche Vorgehensweise würdet Ihr für ein RTS Game im Stil von C&C Red Alert wählen ?

Ich denke mal Quadtree scheidet aus ?

Sorry falls ich damit den Thread sprenge

Zum Seitenanfang

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

30.10.2012, 14:51

Hängt davon ab für was. Es ist jetzt ja nich so, dass man in so einem Projekt nur eine einzige Datenstruktur für alles verwendet...

m4studios

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

30.10.2012, 14:56

Zitat

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

Beide Konstruktionen hatten etwa 4096 einzelne Quads bzw. genau 4096 Sektoren
In Jeden Quad Passten maximal 16, in jeden Grid Sektot 24.
Simulationsraum 1024^2.
Partikelanzahl 32000
Die Partikel sind bisher nur Vektoren ihre Größe soll in der Physik 1 betragen.

Zitat

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

Die Partikel werden ja aber nicht gleich verteilt sein. Ich gehe dann große bereiche leerer Sektoren durch.

Ich bin bald so weit dann kann ich Nachbarquads finden. Ich mache jetzt den Speedtest.

Bilder zu meinem Projekt: ParSim

Zum Seitenanfang

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

30.10.2012, 14:59

Zitat von »Horus«

Zitat

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

Die Partikel werden ja aber nicht gleich verteilt sein. Ich gehe dann große bereiche leerer Sektoren durch.

Dann machst du was falsch. Wie gesagt: Lauft doch nicht das ganze Grid ab, sondern merkt dir, in welche Zelle jedes Partikel fällt und lauft nur die Partikel durch!? Dein Grid speicherst du in einem ganz normalen, flachen Array, du kannst dir also jederzeit die Nachbarn einfach ausrechnen...

m4studios

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

30.10.2012, 15:09

Sieht gut aus:

Alle Quads neu anlegen und durchlaufen dauert: 15ms

Alle Quads neu anlegen und durchlaufen, sowie alle Nachbarn auflistzen dauert: 31ms

Ein vergleichbares Grid neu anlegen und durchlaufen dauert: 7ms

(wieder 32K Partikel)

Schön einfach der Code

if (IntRect.Intersect(new IntRect(Node.StartPos, new IntVector2(Node.Size, Node.Size)), Rect))

Quellcode

{
if (Node.Full)
{
MarkNodes(Node.LT_Child, Rect);
MarkNodes(Node.RT_Child, Rect);
MarkNodes(Node.LB_Child, Rect);
MarkNodes(Node.RB_Child, Rect);
}
else
{
//magic code goes here
}

}

Ist bestimmt noch Verbesserungswürdig!

LG

Bilder zu meinem Projekt: ParSim

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Horus« (30.10.2012, 15:14)

Zum Seitenanfang

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

30.10.2012, 15:12

Ich versteh diesen Vergleich nicht ganz. Wieso das Grid neu anlegen und durchlaufen? Das geht völlig am Sinn eines Grid vorbei...

m4studios

Zum Seitenanfang

Horus

Treue Seele

Beiträge: 251

30.10.2012, 15:15

Dot, Die Partikel werden sich aber ungleichmäßig verteilen. Ist ein Raster dann immernoch schneller?

Aber natürlich hast du recht, so herum also mit Zeiger aufs Raster in den Partikeln, das klingt vernünftig!
Ich dachte immer daran das ganze Raster in einer Schleife zu durchlaufen

Sorry irgendwie ein ziemlicher Denkfehler

Bilder zu meinem Projekt: ParSim

Zum Seitenanfang

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

30.10.2012, 15:19

Zitat von »Horus«

Dot, Die Partikel werden sich aber ungleichmäßig verteilen. Ist ein Raster dann immernoch schneller?

Wie gesagt, das hängt davon ab. Aber wenn der Speicherverbrauch des Grid akzeptabel ist und niemals zu viele Partikel in die selbe Zelle fallen können, was bei dir wohl der Fall sein dürfte, dann sehr wahrscheinlich ja...

Zitat von »Horus«

Aber natürlich hast du recht, so herum also mit Zeiger aufs Raster in den Partikeln, das klingt vernünftig!
Ich dachte immer daran das ganze Raster in einer Schleife zu durchlaufen
Sorry irgendwie ein ziemlicher Denkfehler

Jo, das ganze Grid durchlaufen geht komplett am Sinn vorbei. Die Tatsache, dass das trotzdem noch doppelt so schnell ist wie der Quadtree, demonstriert schön, wie wichtig Cache Utilization heutzutage ist, die beim Quadtree natürlich völlig im Eimer ist...

m4studios

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

30.10.2012, 15:37

Zitat von »dot«

Die Tatsache, dass das trotzdem noch doppelt so schnell ist wie der Quadtree, demonstriert schön, wie wichtig Cache Utilization heutzutage ist, die beim Quadtree natürlich völlig im Eimer ist...

Das musst du jetzt aber mal erklären, warum bei einem Grid der Cache besser genutzt werden können soll.
Ich könnte das nachvollziehen, wenn man das Grid Zelle für Zelle durchlaufen würde, aber das ist ja wie schon gesagt Schwachsinn.
Also durchläuft man Partikel für Partikel. Partikel N kann räumlich total weit weg von Partikel N+1 liegen, wo bringt mir da der Cache etwas?
Selbst die Partikel, die in der selben Zelle sind, befinden sich im Speicher "verstreut" - schließlich speichert ja jeder Partikel nur einen Zeiger auf seine Zelle, und nicht die Zelle "enthält" die Partikel.

Beachte außerdem, dass er die Nachbarschafts-Suche noch gar nicht eingebaut hat.
(wenn er das hätte, dann gäbe es dort sicherlich einen Vorteil beim Grid, eben wegen des Caches)

David Scherfgens Website | Konzentrationstest Polizei