FPS geht mit Kollisionsberechnung in die Knie

Was lässt du kollidieren, um jedes Pixel prüfen zu müssen?

Zeige doch mal den Code deiner 2 Schleifen.
Ev. läßt sich da noch was auf unterer Ebene optimieren.

Ansonsten muß man was intelligenteres auf hörer Ebene machen (Boxing)

Also nach der Berechnung der Abstände könntest du zum Beispiel prüfen, ob der Abstand der Pixel ingesamt so gross ist, dass sie gar nichts miteinander zu tun haben können und dann aus dem Schleifendurchlauf rausspringen. Dann könntest du vielleicht mit Vorzeichen rechnen, das würde dir die ganzen Vergleiche in der Art von [code]if (pixel_x[i]<pixel_x[q][/code] sparen.

Als nächstes wären da noch solche Stellen:

[code]
if(pixel_type[i] == 0) {
pixel_y[i] += 1;
}
if(pixel_type[i] == 1) {
pixel_y[i] += 2;
}
if(pixel_type[i] == 2) {
pixel_y[i]+=5;
}
if(pixel_type[i] == 3) {
pixel_y[i]+=3;
[/code]

Warum hast du keine Datenstruktur, in der die Inkremente, die du hier angibst, stehen? Dann könntest du z.B. schreiben

[code]
pixel_y[i]+=pixel_down_inc[pixel_type];
[/code]

Das wäre dann nur eine Zeile, ohne Vergleiche.

Generell gilt: Auf Hardware-Ebene gesehen können if-Abfragen ziemlich teuer werden - Stichworte wären da Execution Pipelines, Instruction Caching und Branch Prediction...

Hi Dennis !

Codeoptimierung finde ich eine sehr spannenden Aufgabe, sie kann den Unterschied zwischen Nicht-Durchführbarkeit des Projektes und Erfolg ausmachen.
Meine Kenntnissse beruhen auf C/C++ Optimierung. Ich denke, aber dass bei Java es ähnlich läuft.

Dein Code ist nicht optimal, ich würde ihn sogar das extrem schlecht bezeichnen - so daß Du noch enormes Potential hast. Pi mal Daumen sind 99.9 deiner Berechnungen während der Laufzeit überflüssig wenn mans umformt.

Jede noch so kleine Rechenoperation kostet Zeit.
So auch
pixsize*2 (wenn pixsize keine Konstante ist)
pixel_X[i] ist eine Operator - die Adresse der Variable zu berechnet werden (&X[0]) + i*sizeof(int) in C

Diese und ähnliche Operationen werden permanent in der inneren Schleife ausgerechnet.

Du solltes alles das was in der inneren Schleife konstant ist nur einmal außen berechnen und in der inneren Schleife verwenden.

int PixsizeMal2 = pixsize * 2
int Pixel_Xi = Pixel_x[i]
etc.

switch verwenden statt die cases mit vielen ifs testen.

Die Logik umbauen:

if(pixel_x[i] < pixel_x[q] && absx < pixsize*2 && absy < pixsize*2)
rechts = false;
if(pixel_x[i] > pixel_x[q] && absx < pixsize*2 && absy < pixsize*2)
links = false;

Diese beiden Ifs enthalten teilweise dieselbe Bedingunge.
Wie java die ifs mit mehreren Bedingungen optimiert weiß ich nicht. In C++ kann man einstellen, das nicht alle Bedingungen getestet werden, wenn die 1. schon nicht stimmt.
Jedenfall würde ich umformulieren

if(absx < pixsize*2 && absy < pixsize*2)
{
if(pixel_x[i] < pixel_x[q])
...........
if(pixel_x[i] > pixel_x[q])
................
}
Also generell so schachteln, so das möglichst früh und möglichst einfach die "großen" Entscheidungen getroffen werden.

if(a && b && c)
if(a && b && d)
===>
if(a && b)
if(c)
if(d)

So allg. betrachtet lassen sich deine 2 Schleifen bestimmt triangulieren und einen factor 2 sparen
D.h.
Kommt für indicees q i bzw. i q nicht dasselbe raus.
int absx = Math.abs(pixel_x[q] - pixel_x[i]);
-------------------------------------------------------------------------------------
Versuche mal die Optimierungen einzubauen.
Da ich auch an Java-Code-Optimierung interessiert bin wäre es nett wenn Du berichtest was das gebracht hat, damit wir auch was lernen.
Deinen neuen Code kannst Du ja dann posten. Ich finden bestimmt noch was zum optimieren.

— geändert am 20.12.2012, 10:24:06

Short-Curcuit Evaluation funktioniert natürlich auch in Java, d.h. nach der ersten zutreffenden Bedingung wird abgebrochen.

@Dennis: Deine for-Schleifen selbst solltest du auf vorab berechnete Variablen umstellen.

Also statt


solltest du schreiben:


Ansonsten wird wohl auch bei jedem Schleifendurchlauf pixel_type.length ausgewertet.

Ansonsten bin ich wie Andreas auf deine Ergebnisse gespannt ;-)

— geändert am 20.12.2012, 10:22:37

Ohne Code kann ich nicht viel dazu sagen!
Vermute aber stark dass Du nicht alles optimiert hast.

Diese kleinen Tips waren erstmal eine Übung um zu lernen wie man auf unterer Ebene schnellen Code entwicklet.

Ich denke den großen Performanceschub bekommst Du erst, wenn Du den Algorithmus grundsätzlich umbaust (andere Logik)
Hab das Ziel im Moment nicht ganz vor Augen - im Moment auch keine Zeit das zu analysieren und daher noch keine Idee.

Die Ordnung in müßte eigenlich nicht größer als O(n^2) sein. Daher wundert es mich, das du bei Erhöhnung der Problemgröße um eine Faktor 2 (1000->2000) 8 mal langsamer wirst. Da stimmt was nicht!
(Beruht deine Geschw. messung nur auf dem gezeigten Code oder ist die Grafikausgabe oder was anderes da mit drin?)

Spontane Idee:
Du könntes die Pixel jeweils nach x und y sortieren O(2 * n*log(n)) - also sehr schnell
Damit könntest Du für die jeweiligen Koordinatenrichtungen die Nachbarschaftssuche extrem beschleunigen. Mußt natürlich eine Indexebene mehr verwalten. Denke aber das es sehr viel bringt. Wie gesagt das Problem ist O(n^2)!
Wenn du die Ordnung drückst und das auch nur für Teile des Codes hast Du gewonnen.

Poste erstmal Deine jetzigen Code - bevor wir die große Lösung angehen.

— geändert am 20.12.2012, 17:48:31

Genau, her damit ;-)