PhysicEngine, Fragen zur Datenstruktur

[dmdjt]

Wow, das geht ja schnell! Danke!

Das Problem am Löschen ist, das zwischenzeitlich immer wieder einzelne Elemente gelöscht werden müssen... und dann mit einem neuen Abschnitt im Spiel doch auch wieder eine größere Menge. Das resultiert dann in plötzlichen Rucklern. Ich dachte mir auch, dass ich die Elemente einfach im Array belassen könnte und sie einfach als gelöscht markiere. Ab so steigt dann der Speicherverbrauch unvorhersehbar, wenn ich mich im Spiel hin -und herbewege. Es ist mir irgendwie unsympathisch, wenn ich nicht ungefähr vorhersehen kann, was sich im Hintergrund tut.

Ich hab mir jetzt gedacht, ich lasse einfach einen "Generationszähler" mitlaufen. Immer wenn ein Element in einem Array ersetzt wird, steigt der Zähler an. Referenzen gelten nur für eine bestimmte Generation.

Hat vielleicht Jemand noch eine bessere Idee?

Hat vielleicht Jemand noch eine bessere Idee als meine?

[Namenloser]

Zitat von dmdjt:

Das Problem am Löschen ist, das zwischenzeitlich immer wieder einzelne Elemente gelöscht werden müssen... und dann mit einem neuen Abschnitt im Spiel doch auch wieder eine größere Menge. Ich dachte mir auch, dass ich die Elemente einfach im Array belassen könnte und sie einfach als gelöscht markiere. Ab so steigt dann der Speicherverbrauch unvorhersehbar, wenn ich mich im Spiel hin -und herbewege. Es ist mir irgendwie unsympathisch, wenn ich nicht ungefähr vorhersehen kann, was sich im Hintergrund tut.

Das sollte eigentlich nicht passieren. Du darfst nur nicht neue Elemente immer am Ende des Arrays einfügen (und es ggf. vergrößern). Merke dir die freien Stellen und füge neue Elemente dort ein. Solange es noch irgendwo eine Lücke gibt, darf das Array nicht vergrößert werden.

Dann sollte das Array irgendwann seine maximale Größe erreichen und anschließend nicht weiter wachsen.

Wenn es dir immer noch unsympatisch ist, dass womöglich recht viel Speicher belegt wird, der eigentlich nicht genutzt wird, dann kannst du ja in regelmäßigen Abständen das Array "komprimieren" (bzw. defragmentieren) und zurechtschrumpfen. Wird sich aber wahrscheinlich nicht lohnen.

[dmdjt]

Namenloser, lieben Dank fürs Nehmen meiner Ängste!

Das hab ich nämlich komplett übersehen.

[Aphton]

Bei soetwas zeitkritischem ist das Ändern der Größe eines Arrays (De-Allozieren) kontraproduktiv.. Daher ist es besser, dass man z.B. ein Array mit einer fixen Länge dynamisch anlegt; man merkt sich mit einer Zusatzvariable die "eigentliche" Länge und vergrößert/verkleinert immer um das Doppelte/Halbe, wenn eine Grenze erreicht wird.

Wenn zusätzlich die Reihenfolge der Elemente des Arrays keine Rolle spielen, so kann man das Löschen einzelner Elemente dadurch erreichen, indem man das letzte Element des Arrays dem zu löschenden Element zuweist und die Längenvariable reduziert.

Au0erdem - "x, y, z: Array of Double" ist totaler Quatsch! Bitte nimm den "TPunkt" Datentyp.

[Medium]

Zitat von Aphton:

Au0erdem - "x, y, z: Array of Double" ist totaler Quatsch! Bitte nimm den "TPunkt" Datentyp.

Bei dieser Art der Verarbeitung ist es kein Quatsch. Das wichtigste ist dabei, dass man so schnell wie nur möglich durch alle Punkte durchrauschen kann, und wenn man sich dabei die Dereferenzierung zu Records spart, ist gar nicht mal so wenig gewonnen. Ich hatte mal aus Spaß eine Stoff-Simulation gebaut (ich komm gerade ums Verrecken nicht mehr auf den Namen vom Algo), und bin am Ende ebenfalls bei Arrays für X und Y (war nur 2D) gelandet, und habe die Relationen mittels Pointern hergestellt. Damit war dann auch ein "Kreuz-Verfedertes" Tuch mit 80x80 Vertices noch schnell genug auf dem Core2Duo damals für ~30fps.
Die "saubere" Vorversion mit Kapeslung und allem ganz hübsch in Hochglanz kam da bei weitem nicht hinter her. So lange man nachher nach aussen alles schön verpackt, finde ich es hier ausnahmsweise mal okay die Datentypen dem Zweck unterzuordnen.

[Dejan Vu]

Du kannst dein Record erweitern:

Delphi-Quellcode:

Type
  TDaten = record x,y,z,n : double; del : integer end;

// wenn del= 0 ist, dann ist der record gültig
// ansonsten enthält 'del' den Index des nächsten freien Platzes im Array oder -1
var
  ListenGroesse,
  ersterFreierPlatz : Integer; // = -1 am Anfang, oder wenn es keine freie Stelle gibt

Procedure Initialisieren;
Begin
  ListenGroesse := 0;
  ersterFreierPlatz := -1;
End;

Procedure Loeschen (Index : Integer)
begin
  if Liste[Index].Del != 0 then raise Exception.Create('Platz schon gelöscht');
  Liste[Index].Del = ersterFreierPlatz;
  ersterFreierPlatz := Index;
End;

Function NeuerPlatz : Integer;
Begin
  if ersterFreierPlatz = -1 then begin
    if ListenGroesse = MaximaleListenGroesse then raise Exception.Create('Speicherüberlauf');
    ListenGroesse := ListenGroesse + 1;
    Result := ListenGroesse - 1;
  end else begin
    Result := ersterFreierPlatz;
    ersterFreierPlatz := Liste[Result].Del;
    Liste[Result].Del := 0;
  end
end;

Die Idee von Aphton ist noch einfacher, aber genau dann falsch, wenn Du dir merkten musst, das z.B. am Index #5 eine Kuh ist. Denn wenn die Kuh am Ende der Liste ist und ein Element wird gelöscht (z.B. #2, dann wandert die Kuh ja in das Element #2). Und wenn Du dann später die Kuh suchst, isse wech (bzw. nach #2 gewandert).

[dmdjt]

Im Prinzip scheint sich mir damit alles beantwortet zu haben.

Wenn ich ein Element lösche, dann markiere ich es als gelöscht.
Ich denke, das werde ich mit einem Zeiger machen, der falls nicht gelöscht 0 ist, und ansonsten auf das nächste, belegte Element zeigt. Vielleicht ist das ja nützlich wenn es größere Löcher geben sollte, muss ich testen. Ansonsten einfach nur als gelöscht markieren.
Wenn ein Element neu belegt wird, dann erhöhe ich einen Zähler um verbleibende Zeiger als ungültig zu erkennen. Ein Byte sollte reichen, weil ansich alle Zeiger nach einer Runde einmal verwendet - und damit getestet worden sein müssten
Fragmentierung sollte, glaube ich, kein großes Problem sein. Das bedeutet nur wenn viele Elemente gelöscht wurden einen unnötigen Aufwand - und genau da gibt es weniger zu berechnen - und beim Hinzufügen neuer Elemente. Das wird aber vermutlich auch keine Probleme bereiten.

Jetzt muss ich noch aufpassen, dass ich nicht durch Verwaltungsaufwand langsamer als vorher werde

Aber falls ich irgendwas übersehen haben sollte, oder es weitere Vorschläge gibt, wäre ich natürlich auch unheimlich dankbar!

[dmdjt]

Aphton:

Mir ist klar, wie das aussieht und dass es wirklich, wirklich nicht schön ist. Aber wenn ich die so anlege und nicht in einem Record, scheint es zumindest in meinem Test etwa 10% schneller zu sein.

Delphi-Quellcode:

x,y,z : array of double;
z[i] := x[i]*y[i];

//vs.
a: array of TPoint;
a[i].z := a[i].x*a[i].y;

Anstatt das letzte Element zu verschieben, will ich es ja eh einfach nur als gelöscht markieren und dann beim Erstellen eines neuen Elements neu befüllen und reaktivieren. Davor hatte ich vor Namenlosers Einwand irgendwie ein ungutes Gefühl... aber eigentlich ist es eh ganz klar.
Auf die Art hab ich auch von außerhalb der Engine eine immer gültige Adresse für ein bestimmtes Element und kann dort so tun, als würde ich mit Objekten hantieren.

Dejan Vu:

Danke für die Tipperei!

Vom Prinzip her werde ich es ganz ähnlich aufbauen.

Ich hab weniger ein Problem das ganze umzusetzen, als dass ich mich vor ein paar Problemen beim Design wiedergefunden habe.

Danke übrigens an alle

[dmdjt]

Der Algo hieß ziemlich sicher Verlet Integration

Habs davor einfach per Euler versucht, aber das wird einfach zu instabil. Deswegen muss man Dämpfungen unnatürlich hoch einstellen und alles wirkt wie unter Wasser oder Honig

[Aphton]

Ok, meinetwegen...
Aber in 98% aller Fälle ist das Unfug, da es nicht notwendig ist, solche Optimierungen bereits zu machen. Erst makro, dann micro - vlt habe ich mich beim TE auch nur vertan und er ist auch schon soweit und hat alle Makro-Probleme optimiert..

Edit: Ok, nochmal zurück zu dem; so ganz überzeugt bin ich nicht.
Die Verwendung von Structs/Records sollte in deinem Fall schon schneller sein, wenn man überlegt..:
Array[INDEX] ==> <Größe_Array_Datentype> * Index
--> 3 Multiplikationen schon allein für die Indizierung von x, y und z..
Hätte man stattdessen vergleichsweise ein Record benützt, so hätte man nur 1x Multiplikation für die Indizierung und 2x Additionen für die Offsets im Record/Struct (für x wird nichts addiert, da es sich am Anfang befindet).
Jetzt sagt bloß nicht, dass 1x Mul & 2x Add langsamer ist als 3x Mul
oO

Hab hier kein Delphi zur Hand, deshalb weiß ich leider ned, was der genau für nen Assembler Code ausspuckt, könnte das ganze aber mit C++ testen..