Optimierung einer SpriteEngine

[igel457]

Hallo.

Wie ihr vielleicht wisst, programmiere ich gerade an einer kleinen 2D Engine.

Ich möchte nun die SpriteEngine optimieren. Das heißt ich möchte die Zeit, die benötigt wird um die Sprites, die gezeichnet werden müssen und mit denen Kollisionen stattfinden sollen, verringern. Ich möchte das mal an einem Beispiel verdeutlichen:
Ich habe z.B. auf einem Spielfeld 3100 Objekte. 100 von den 3100 Objekten prüfen nun jedem Renderschritt ob sie mit einem der anderen 3099 Objekte kollidieren. Das macht also 309900 Überprüfungen pro Frame. Allerdings ist dies ziemlich unnötig, da die Kollsionskontrolle ja eigentlich nur mit den Objekten in nächster Nähe stattfinden soll.

Nun habe ich mir folgendes überlegt:
Ich teile das Spielfeld in kleine Rechtecke mit fester Größe (z.B.: 128*128px) ein. Dann erstelle ich ein dynamisches, 2-Dimensionales Array. Die Array-Elemente sind wiederum Listen.
Also habe ich praktisch festes Gitter mit "Eimern". Die Objekte befinden sich in den Eimern. Bewegt sich ein Objekt, so wandert es von dem einen, in den anderen Eimer. Ist an der Stelle noch kein Eimer vorhanden, wird das Gitter vergrößert (kommt aber eigentlich nicht so oft vor). Möchte nun ein Objekt eine Kollision überprüfen, so muss die Kollision nur mit den Objekten in den benachbarten Gittern stattfinden. Ein kleines Problem bei der Sache war allerdings, dass dynamische Arrays nur bei 0 Anfangen können. Bewegt sich nun ein Objekt über die Grenzen des Gitters hinaus, so müsste ich ja alle Objekte im Gitter verschieben. Deshalb habe ich eine Organisationsstruktur Implementiert, die sich darum kümmert, dass die "Eimer" auch ungeordnet im Gitter verteilt sein können und eine Funktion geschrieben, die den Zugriff dennoch optimiert, indem Sie die "Eimer" auf Wunsch ordnet und damit den Zugriff immens Beschleunigt. (bei 19 Mio. zugriffen von 5s auf 0,5s)

In meinem Spiel CrashPoint hatte ich es so ähnlich gemacht, und das hat die FPS von 50 auf 300 erhöht. Allerdings hatte ich da keine Objekte, deren Koordinaten kleiner als 0 waren.

Puh...

Nun meine Fragen:
1. Fällt einem noch etwas Besseres ein um so etwas zu Optimieren? Ich denke das Quadtrees nicht unbedingt dafür geignet sind (oder irre ich mich?)...
2. Kann sich jemand mal meinen Quellcode anschauen: http://andorra.cvs.sourceforge.net/a...=markup#l_1010

Danke schonmal,
Igel457

[mimi]

etwas spät ich weiß, aber ich bin schon vor einiger Zeit auf diesen Interessanten Beitrag von dir gestoßen und habe einige fragen.

Was Passiert bei dir wenn sich mehrer Objekte Bewegen ?

Ich habe jetzt eine eigene Engine Angefangen die nutzt Intern nur TCanvas und TBitmap....

sie Besteht aus drei Klassen:
TPluto2DEngine
TPlutoSpritmanger
TPluto2DSprite

Wenn ein Sprite gezeichnet wird, löst es ein event aus, das von der Engine aufgefangen wird, und wiederum alle Sprits in allen Spritmangern neuzeichnet.
Damit sich das Programm nicht "Aufhängt" Gibt es bei der Draw Methode einen Default Paramter der besagt das der Event nicht ausgelöst wird.

Damit es zu keinen Grafik Fehler kommt, wird dieser Event ausgelöst.
Weil wenn sich zwei Sprite überscheiden, würde es ja zu einem Grafik Fehler kommen, wenn einer von den Sprite sich Weg-Bewegt.

Der Sprit hat zugief auf die 2DEngine und auf den Spritmanger, jeder Sprit muss einen angehören.

Jetzt gibt es noch eine Imagelist die das alle Grafiken lädt und den eine ID, einen Namen und einem Typ zuordnen z.b. ID=id001 Name=Player1 Typ=Spieler

geht dein ansatzt auch in dieser Richtung ?