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