PhysicEngine, Fragen zur Datenstruktur

[dmdjt]

Hallo liebe Leute!

Ich lese schon einige Jahre hier mit und kam eigentlich nie wirklich dazu etwas zu erfragen, weil sich durch einiges stöbern praktisch alles klären lässt.
Jetzt hab ich mich hinreißen lassen ein kleines Spiel zu programmieren, das zu einem gewissen Teil auf einer PhysicEngine (nur Feder-Masse-Dämpfung) aufbauen soll.

Die Engine selbst hab ich schön objektorientiert aufgebaut und funktioniert auch ungefähr so, wie ich es mir erwartet habe.

Nur zu langsam um ein ganzes Spiel darauf basieren zu lassen. Selbst wenn es nur 2D ist.

Jetzt möchte ich sie umbauen und mich um die Daten selbst kümmern - möglichst ohne Flexibilität zu verlieren.

Die Daten liegen dann etwa in der Form im Speicher:

Delphi-Quellcode:

x,y,z: array of double;
//alle Werte mit dem gleichen Index gehören zu einem Objekt

Soweit, so gut. Auch Löschen ist zuerst einmal kein Problem, weil die Reihenfolge in der ich durchiteriere, eigentlich egal ist.

Ich möchte aber, dass sich mehrere Objekte Koordinaten teilen können.
Eine Feder muss die Koordinaten einer Masse lesen können, um die Kräfte berechnen zu können.
Außerdem brauche ich eine Liste von Kräften, die an einer Masse angreifen (Schwerkraft, verschiedene Federn,...).
Ich hab also haufenweise Querverweise.
Und genau da wird das Löschen von Elementen zu einem riesigen Problem:
Lösche ich irgendwelche Koordinaten aus dem Array, zeigen alle auf Koordinaten nach diesen zeigende Elemente auf einen falschen Index.

Ich würde es gerne vermeiden, alle Pointer zu kontrollieren, ob sie angepasst werden müssen.
Statt einfachem Löschen und Neuaufbauen aller Arrays würde ich so oder so einfach das zu löschende Element durch das letzte ersetzen. Dann zeigen auch praktisch alle Pointer auf die richtige Stelle im Array.
Aber die Pointer, die vorhin auf das letzte Element gezeigt haben, müssen geändert werden... und möglicherweise noch existierende Pointer auf das gelöschte Element müssen auch entfernt werden.
Das Problem mit dem letzten Element würde ich mit einem Referenzzähler und einer "Nachsendeadresse", einem Pointer auf die neue Position lösen. Wenn die Nachsendeadresse <> nil ist, werden die Pointer aktualisiert und der Referenzzähler dekrementiert. Ist der Zähler bei 0, wird das Element gelöscht oder als gelöscht markiert.

Ich weiß nur nicht, wie ich die Pointer die noch auf das gelöscht Element zeigen, entfernen kann?!

Denke ich da überhaupt zu umständlich und gibt einen einfach Weg für die ganze Geschichte?

Oder bin ich überhaupt komplett auf dem Holzweg?

Ich wäre für so ziemlich jede Anregung dankbar!

(P.S:
Natürlich hab ich auch Listen ausprobiert. Aber die scheinen doch DEUTLICH langsamer als Arrays zu sein

[mkinzler]

Ich würde einen Record für einen Punkt erstellen und dann einenn Array/eine Liste dafür erstellen.

Delphi-Quellcode:

type
  TPunkt = Record
    x,y,z,n: Double;
  end;

var
  Punkte : Array of TPunkt;

Und die Flächen verweisen dann auf Punkte und Objekte bestehen aus Flächen.

[Namenloser]

Hi, ich würde erst mal einen Profiler hernehmen, um zu schauen, was überhaupt genau der Flaschenhals ist. Nicht, dass du viel Energie in die Optimierung der falschen Stelle investierst.

Arrays sind in der Regel eine gute Wahl, wenn es um Performance geht.

Falls das Löschen und anschließende Updaten der Referenzen wirklich der Flaschenhals ist, dann würde mir spontan die Lösung einfallen, einfach beim Löschen Lücken im Array zu lassen, statt sie direkt wieder zu füllen. Das Array wird dann zwar etwas fragmentieren, aber so schlimm ist das nicht. Wenn ein neues Element eingefügt wird, dann wird es einfach in die erste freie Lücke eingefügt.

[dmdjt]

Danke für die schnelle Antwort!

Mit Rrecord hab ich es schon probiert. Da brauchen die Zugriffe im Schnitt 10% länger.

Außerdem löst das mein Problem mit dem verschobenen Index leider nicht

[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.