Partickelcode

Janko

Ich habe mir schon öfters Tutorials über Partickel angesehen und die Partickel wurden immer in einem Array gespeichert. Warum macht man das nicht in einer Linked_List. Es wäre viel praktischer?
Partickel einfügen, löschen oder auch umgruppieren ist so doch viel leichter und teilweise sicherlich schneller.
Was sind eure Erfahrungen?

[ Dieser Beitrag wurde am 04.05.2003 um 17:34 Uhr von Janko editiert. ]

Ich wüsste gar nicht für was man die normalerweise "einfügen, löschen oder auch umgruppieren" sollte. Das sind doch eher Ausnahmefälle würde ich sage....

TomasRiker

Meistens arbeitet man mit mehreren tausend Partikeln. Die Reihenfolge, in der sie gezeichnet werden, spielt kaum eine Rolle, da ein einzelner Partikel meistens sowieso kaum sichtbar ist (die Masse macht's).
Eine Linked-List wäre da doch denkbar ungeeignet. Man müsste doch für jeden neuen Partikel neuen Speicher reservieren und alten Speicher bei jedem "gestorbenen" Partikel wieder freigeben.
Dann lieber ein ausgeklügeltes Array-System... man merkt sich z.B. immer, wo der erste freie Partikel-Array-Eintrag liegt und muss dann nicht mehr lange herumsuchen. Und man merkt sich den mit dem höchsten Index, um beim Bewegen und Rendern nicht eine größtenteils leere Liste durchzugehen.

[ Dieser Beitrag wurde am 04.05.2003 um 17:49 Uhr von TomasRiker editiert. ]

Janko

@<ORDNUNG>
Na umgruppieren um sie je nach ihrem Aufenthaltsort in Sektoren einzuordnen. 2 Probleme gehen dadurch besser:

Frustum cullen-> zuerst vom Sektor und falls der im Sichtfeld ist dann die Partickel zeichnen; und nicht jedes Partickel einzeln prüfen ob es im sichtfeld liegt..
Wenn die Partickel kollidieren sollen, statt bei der Kollision jedes Partickels mit jedem zu überprüfen ob sie eine ähnliche Position haben einfach nur alle Partickel im gleichen Sektor prüfen.
-----
Und wie willst du ein Partickel aus einem array löschen?
alive=false
und dann in der schleife
if (!partickel[loop].alive)
continue;
Ne das ist umständlich und besonders dauert es unnötig
-----
Außerdem kann ein array nur eine begrenzte Anzahl von Partickeln haben
-----
Und das mit dem einfügen ist bei einigen Problemen auch sinnvoll.
Wie willst du folgenden code realisieren.
/* Sobald ein Partickel gegen eine Wand fliegt zerbarstet es in 10 weitere kleinere Partickel*/

Bei mir sieht der Code einfach so aus.
for (int loop=0; loop<10; loop++)
Neu(&uLinked_List.PNachfolger)->Init(klein_Partickel,ort);
loeschen();

Du müsstest das so machen
1. Möglichkeit
/* setze die Werte des Partickels auf 0 und Suche ob noch irgendwo im array für 10 andere Partickel Platz ist, wenn nicht dann lass es für den Rest bleiben*/
2. Möglichkeit wenn man einen extra array erstellt
Partickels [loop].weiterePartickel=New CPartickel[10];
/* Wenn dann alle 10 Partickel zerfallen sind, werden sie gelöscht und bei Partickels [loop] endlich alle Werte auf 0 gesetzt

-------

Konnte ich dich überzeugen <ORDNUNG> oder habe ich dich falsch verstanden.

Janko

Dann lieber ein ausgeklügeltes Array-System... man merkt sich z.B. immer, wo der erste freie Partikel-Array-Eintrag liegt und muss dann nicht mehr lange herumsuchen. Und man merkt sich den mit dem höchsten Index, um beim Bewegen und Rendern nicht eine größtenteils leere Liste durchzugehen.

Das setzt aber voraus das alle Partikel gleich lang leben.

japro

Original erstellt von Janko:
**
Und wie willst du ein Partickel aus einem array löschen?
alive=false
und dann in der schleife
if (!partickel[loop].alive)
continue;
Ne das ist umständlich und besonders dauert es unnötig
**

super argument...
den aufwand den das programm beim durchlaufen der list machen muss hebt sowas locker wieder auf (pointer derferenzieren etc).
und zum cullen... da die partikel eh nur recht klein sind wird da auch nicht so der haufen rechenzeit zum darstellen benötigt... in der zeit in der du einen partikel neu eingeordnet und gecullt hast haste ihn schon 3 mal gezeichnet...

Janko

In sektoren sortiert wird es vielleicht 3 mal insgesamt
gezeichnet aber 24 mal in der Sekunde. Ich denke mal schon das es sich lohnt. Besonders bei langlebigen partikeln.
(berichtigt mich bitte)

TomasRiker

Warum überhaupt Partikel sortieren? Und wonach? Ich bin mir recht sicher, dass jegliche Sortiererei die Performance nur schwächt und sie nicht erhöht.

Kane

Wie wäre es, wenn man einmal eine Liste von Partikeln und einmal eine
Liste von Pointern auf ungenutze Partikel hätte?

Wenn man mehr P. braucht als da/frei sind, erzeugt man halt noch ein paar.
Stirbt ein P. löscht man ihn nicht aus dem Speicher, sondern fügt seinen
Pointer in die "Leichen"-Liste hinzu.
Wenn man dann wieder ein paar Partikel braucht, checkt man erst die Leichen-Liste.

naja... hast schon recht, dass zum Teil dynamische Sachen besser sind. Aber ich hab ja auch nichts anderes behauptet.... Nur dass das halt eher Ausnahmefälle sind. Ich glaube die wenigsten brauchen so komplexe Partikel. Normalerweise reichen halt die Arrayteile.
Trotzdem kann ich mir auch nicht vorstellen, dass das mit sortieren etc. am Ende wirklich schneller läuft...

TomasRiker

@Kane: Ob das wirklich nötig ist? Man kann während man die Liste der Partikel durchgeht, um sie zu rendern oder zu bewegen, sich schon merken, wo der erste freie Partikel ist, oder wo überhaupt aktive Partikel sind. Da kann man sich beim nächsten Partikel schon die Suche sparen. Ich glaube so eine Extraliste für "Leichen" würde auch schon einiges an Aufwand bedeuten. Man muss ja aus dieser Liste auch was löschen können und dann haben wir das gleiche Problem wieder.

TGGC

Die Leute sind eben alle einfach zu doof 'ne verkette Liste zu benutzen und nehmen deswegen immer Arrays. Die haben halt noch nie über die Performance nachgedacht, geschweige denn das mal probiert und verglichen. Die müsste man echt alle mal zum ZFX schicken ;).

Stefan Zerbst

Hi,

wenn man sein Array mit Partikeln durchläuft und dabei einen entdeckt, der seine Lebenszeit beendet hat, dann kopiert man den letzten Eintrag des Arrays an diese Position und reduziert den Zähler. Kein Aufwand für dynamisches Speichermanagement, keine Extralisten usw.

for (blablablupp)
{
   if (pPartikel[i].fLife <= 0.0f)
   {
      if (i==(m_iPartikels-1))
      {
         m_iPartikels--;
      }
      else 
      {
         pPartikel[i] = pPartikel[m_iPartikels-1];
         m_iPartikels--;
         i--;
      }
   }
   else
   {
   // update / render partikel i
   }
}

Ciao,
Stefan

[ Dieser Beitrag wurde am 05.05.2003 um 11:21 Uhr von Stefan Zerbst editiert. ]

TomasRiker

Jo, so hab ich's auch gemacht

Janko

@Stefan Zerbst
Das ist eine gute Idee, aber:

pPartikel[i] = pPartikel[m_iPartikels-1];

Aber braucht das nicht viel Zeit ein Partickel zu kopieren?
Ein Partickel besteht ja schon mindestens allein aus 7 Zahlen(3×Ort und 3×Geschwindigkeit, Lebenszeit) und zusätzlich noch die anderen Werte.

Dagegen geht das Löschen doch schneller? Man muß nur
1)Vorgänger auf Nachfolger verlinken
2)Nachfolger auf Vorgänger verlinken
3)Den Speicher den das Partickel einnahm als freigeben erklären.
---

Okay vielleicht sollte man mal eine grundlegende Frage klären.
Wie lange dauert das Speichererstellen/freigeben im Vergleich zu einer Zuweisung? hat da wer eine Ahnung

[ Dieser Beitrag wurde am 07.05.2003 um 17:47 Uhr von Janko editiert. ]

Original erstellt von Janko:
Partickel

Kannst du nicht die korrekte Schreibweise benutzen?! Ich muss da immer an Pickel denken!

Janko

Lol klar
"Partikel"

Kane

Nicht löschen, in die Leichen-Liste(bzw. Liste von Pointer auf Leichen) damit.

japro

man kann jetzt so lang darüber diskutieren wie vile es kostet partikel zu verscheiben und so. aber hauptargument gegen listen ist in meien augen das es länger geht eine liste zu durchlaufen als ein array weils einfach aufwendiger ist... und das durchlaufen der liste muss ja ziemlich oft geschehen...

Stefan Zerbst

Hi,

das ständige dynamische Allokieren und Deallokieren von Speicher würde ich nie zur Laufzeit vorziehen. Natürlich kann das Kopieren eines Partikels auch Zeit kosten aber eine Liste linearen Speichers kann schneller durchlaufen werden (weiterschieben des Pointers statt [ i ] Zugriff) als eine verkettete Liste.

Am sinnvollsten ist sicherlich eine verkettete Liste auf einem statischen Speicher, was aber wieder eine eigene Klassenimplementierung voraussetzt.

Für einfache Programme ist die Array Version vorzuziehen, da man keinerlei Setup-Aufwand hat.

Ciao,
Stefan