000
10.04.2002, 17:21
Prefect
|
Hallo zusammen, wird mal wieder Zeit für was Interessantes hier ;)
Datenstrukturen sind natürlich auch eine allgemeine Codingfrage, aber es paßt doch recht gut ins Gameprogramming rein.
Also, das Subject dürfte ja schon einen Großteil gesagt haben. Immer wieder tauchen Partikelsysteme als Schlagwort auf, und sowohl von TTT als auch von mir (im Rahmen von direktem Surfacezugriff unter SDL) gibt's ein Tutorial zu Partikeln. Wir haben dabei beide allerdings nicht viel Wert auf die dazugehörigen Datenstrukturen gelegt, und beide eine Linked List verwendet.
Linked List mag vielleicht auf den ersten Blick nett aussehen (man hat z.B. keine Obergrenze der vorhandenen Partikel), ist aber sicher nicht die beste Form, um eine Liste von Partikeln zu speichern, besonders da man andauernd Heapfunktionen in Anspruch nimmt.
Eine andere klassische Methode sind natürlich statische Arrays, aber die sind relativ inflexibel.
Naja, ich hab ein kleines C++-Programm geschrieben, das sozusagen ein Framework für die Implementation von Partikelsystemen (allerdings ohne Grafik ;)) bereitstellt. Dieses Programm enthält die simpelste Implementation, nämlich eine Linked List.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
/*
Partikel haben folgende Eigenschaften:
- origin: momentane Position
- velocity: Geschwindigkeit in Einheiten / Sekunde
- timeout: verbleibende Lebenszeit in Sekunden
- type: Zeiger auf eine beliebige Struktur, die z.B. das Sprite enthalten könnte
*/
/*
Abstraktes Partikelsystem
*/
class ParticleSystem {
public:
virtual ~ParticleSystem() { }
virtual void Clear() = 0;
virtual void Render(float frametime) = 0;
virtual void Add(void *type, float time, const float *origin, const float *velocity) = 0;
};
/*
Jedes Partikelsystem soll die gleiche Logik zur Bewegung der Partikel verwenden.
timeout wird vom PS selbst gehandhabt, da es eng mit dem Algorithmus zum Löschen
von Partikeln verknüpft ist.
*/
template<class T>
inline void ParticleLogic(T *part, float frametime)
{
part->vel[2] -= (981 / 2) * frametime; // Gravitation
part->origin[0] += part->vel[0] * frametime;
part->origin[1] += part->vel[1] * frametime;
part->origin[2] += part->vel[2] * frametime;
part->vel[2] -= (981 / 2) * frametime; // Gravitation
}
/*
Gleiches gilt für's "Rendern"
*/
#define MAXRENDER 1000000 // Cache stressen
struct rendering {
float origin[3];
void *type;
} render[MAXRENDER];
int renderidx = 0;
template<class T>
inline void ParticleRender(T *part)
{
/*
render[renderidx].type = part->type; // geht verdammt auf den Cache
memcpy(render[renderidx].origin, part->origin, sizeof(float)*3);
renderidx = (renderidx + (int)part->timeout + 3) % MAXRENDER;
*/
}
/*
Linked List-Implementation
*/
struct llparticle_t {
llparticle_t *next;
float timeout;
float origin[3];
float vel[3];
void *type;
};
class ParticleLL : public ParticleSystem {
private:
llparticle_t *m_pParticles;
public:
ParticleLL() { m_pParticles = 0; }
~ParticleLL() { Clear(); }
void Clear() {
llparticle_t *part;
while(m_pParticles) {
part = m_pParticles;
m_pParticles = part->next;
free(part);
}
}
void Render(float frametime) {
llparticle_t *part, **pnext = &m_pParticles;
while(*pnext) {
part = *pnext;
part->timeout -= frametime;
if (part->timeout <= 0) {
*pnext = part->next;
free(part);
continue;
}
ParticleLogic(part, frametime);
ParticleRender(part);
}
}
void Add(void *type, float time, const float *origin, const float *velocity) {
llparticle_t *part = (llparticle_t *)malloc(sizeof(llparticle_t));
part->type = type;
part->timeout = time;
part->origin[0] = origin[0];
part->origin[1] = origin[1];
part->origin[2] = origin[2];
part->vel[0] = velocity[0];
part->vel[1] = velocity[1];
part->vel[2] = velocity[2];
part->next = m_pParticles;
m_pParticles = part;
}
};
/*
Hauptprogramm:
Läßt eine gefakte Gameloop laufen
*/
void SpawnParticles(ParticleSystem *psys, float frametime)
{
static float delay = 0;
int i, count;
float origin[3], vel[3];
delay -= frametime;
if (delay > 0)
return;
count = 100;
for(i = 0; i < count; i++) {
origin[0] = i*i + i; //blahblah
origin[1] = 724 / (i+1);
origin[2] = 15 + i;
vel[0] = 235;
vel[1] = 0.245;
vel[2] = i*5;
psys->Add(0, (3000 + rand() % 1500) / 1000.0, origin, vel);
}
delay += 0.150;
}
int main(int argc, char **argv)
{
ParticleSystem *psys;
int tstart, tend, ticks, count;
psys = new ParticleLL;
count = 500000;
tstart = time(0);
for(ticks = 0; ticks < count; ticks++) {
if (!(ticks % 1000)) {
putc('.', stdout);
fflush(stdout);
}
SpawnParticles(psys, 0.01);
psys->Render(0.01);
}
puts("");
tend = time(0);
delete psys;
printf("%i ticks in %is\n", count, tend - tstart);
}
Ein paar Anmerkungen:
- der Unterschied zwischen optimierten und nicht optimierten Builds ist generell ziemlich groß, wohl vor allem weil der Compiler in nicht optimierten Builds u.U. alles andere als optimalen Code erstellt (was natürlich das Debuggen erleichtert, aber...)
- wer ParticleRender auskommentiert kann sich auf lange Laufzeiten einstellen; der Code killt den Cache wohl komplett und sorgt dadurch für Ärger...
- es wird wohl alles andere als eine realistische Umgebung für ein Partikelsystem simuliert...
Es scheint in einer RL-Implementation sinnvoll
a) Partikel nach Sprite zu sortieren und
b) ein Vertexarray pro Spritetyp aufzubauen und es in einem Schlag zu Rendern; auch wenn das Array jedes Mal neu aufgebaut wird hat es, wie es aussieht, vom Caching her Vorteile. Vielleicht könnte man ja sogar das Partikelarray selbst als Array "mißbrauchen" ;)
Aber eigentlich ging es mir ursprünglich um die eigentliche Datenstrukturen. Wie gesagt, ein statisches Array streßt den Heap nicht so sehr, hat dafür aber eine feste maximale Anzahl an Sprites.
Vielleicht fällt euch ja was besseres ein :)
cu,
Prefect
--
Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.
|
.
