C++ objekt einer klasse erstellen die erst später definiert wird

[kiep schmeiling]

Hi,

der Titel kling ziemlich komisch, aber mein Problem ist sehr schwierig auszudrücken, daher bin ich auch mit Google nicht wirklich weitergekommen...

Ich will ein einfaches Spiel Programmieren, ein bisschen ähnlich wie Billard nur mit beliebig vielen kugeln und einem Schläger, den man von diesen "Air-Hockey" Tischen kennt.

Mein großes Problem ist jedoch die Performance, da das Programm so ab ca. Hundert Bällen anfängt zu ruckeln, später wahrscheinlich noch füher, da die Kollisionsabfrage zweier Bälle noch ein wenig genauer (öfter ausgeführt) sein muss.
Ich versuche meine Kollisionsüberprüfungsfunktion (die eine Elementfunktion der Ball-Klasse ist) so gut wie möglich zu optimieren, und habe jetzt gelesen, dass es schneller ist wenn ich sie Inline Definiere, allerdings greift sie auf elemente eines Vectors zu, die erst einige Zeilen weiter im Code Definiert wird, selbst aber hinter der Ball-Klasse stehen muss, weil er wiederum auf sie zugreift (weil er ja aus objekten dieser klasse besteht).
Den ganzen Code kann ich hier unmöglich posten, ich hab glaube ich schon über 500 Zeilen, deshalb grob schematisiert bzw. auszugsweise:

class ball
{
   
void chkkol()
  {   
	  int xdst,ydst; //variablen fuer x und yentfernung  und absolute entfernun hoch 2
	  double dst2;

	  for (int i = 0; i<balls.size(); i++) //alle baelle der rehe nach durchgehen
	   {    
		 xdst=(xpos-balls[i].xpos);    //die x entfernung ist die eigene xposition-die xposition des anderen balls
	     ydst=(ypos-balls[i].ypos);
		 
		 
		 if (xdst && ydst) //nicht auf kollision mit sich sellbst ueberpruefen (wenn x und ydst null sind muss es die eigene kugel sein, null nimmt er automatisch als false
		 {
			 if(xdst<r+balls[i].r && ydst<r+balls[i].r)    //hier wird erst mal ein qudrat um den ball gezogen, dass geht wesentlich schneller, da muss er nicht so viel rechnen, denn in 99,9% aller faele liegt keine kollision vor
			 {
				 dst2=(xdst*xdst)+(ydst*ydst);
			     if(sqrt(dst2)<r+balls[i].r)  //wenn der abstand (satz des phytagoras)der beiden kreismittelpunkte kleiner ist als die beisen radien zusammen...
			     {xspeed=0;yspeed=0;}                                                            //bleibe stehen (nur vorlaeufig)
			 }
		 }
	  }
return;
}

};

std::vector<ball> balls;

class schlaeger
{
//benutzt in elementfunktionen (nicht im Konstruktor) Objekte aus "balls"
};

Ich muss die Klasse vor die Deklaration des Vectors schreiben, sonst spuckt der Compiler einen Fehler aus, benötige ihn aber bereits in der Klasse, da ich auf seine Elemente zugreife. Wie gesagt, bisher hatte ich das Problem gelöst, indem ich die Funktion Outline definiert habe...(Der Vector ist auserhalb der main() funktion deklariert, damit er wirklich global ist...)

Wenn also jemand eine Idee hat wie ich das löse (oder meine chkkol() funktion optimieren kann, denn die wird, bei 100 Bällen, 1000 mal pro Frame aufgerufen) wäre ich sehr dankbar...

 

[tomcat83]

Hallo!

Also ein absoluter Performancekiller dürfte sein, dass du ohne Iterator durch den Vektor läufst. Der Vektor wird nicht als Baum aufgebaut sein, sondern eher als verkettete Liste, sodass der Zugriff auf ein beliebiges Element das Durchlaufen aller elemente vor dem zuzugreifenden Element erfordert. Mit Iterator sollte es schneller gehen:

statt

for(int i = 0; i < balls.size(); i++)
{
    // Irgendwas mit balls[i]
}

versuch mal

for(std::vector<ball>::iterator it = balls.begin(); it != balls.end(); it++)
{
    // statt balls[i] kannst du jetzt *it schreiben, also z.B.
    // int xpos = (*it).xpos;
}

Das sollte deiner Performance einen Schub geben. Besser ist aber, den Vektor zu vermeiden (sofern dieser wirklich eine lineare Liste ist). Wenn die Anzahl der Kugeln bekannt ist, solltest du ein stinknormales C-Array verwenden.

Hoffe das hilft ein wenig!

Gruß,
tomcat83

EDIT: Ach ja, das habe ich ja ganz vergessen...Zu deinem Problem mit der Sichtbarkeit der Klasse ball:

class ball;
std::vector<ball> balls;

class ball
{
   // ...
};

class schlaeger
{
   // ...
};

Ich glaube allerdings nicht, dass die inline-Klausel viel bringt - sie bläht höchstens deinen Code auf.

 

[kiep schmeiling]

Hi,
vielen Dank, das hat schon mal einiges gebracht!
Ich weiß leider nicht genau, wieviele Bälle es dann sein werden, denn man soll während dem Spiel weitere hinzufügen können.
Dies allerdings nur bis zu einer bestimmten Maximalanzahl (wahrscheinlich ca. 50 Stück).

Wäre es also schneller einen Array mit einer Fixgröße von 50 zu erstelllen und jedem Objekt die Eigenschaft

bool exist;

hinzuzufügen, und dann bei der Kollisionsabfrage voher noch zu überprüfen ob das Objekt "existiert"?

 

[tomcat83]

Hallo,

das mit dem bool wäre eine Möglichkeit. Der Vorteil der Methode wäre, dass das Erstellen "neuer" Bälle dann schnell ginge, also kein Speicher beschafft werden müsste (das kann dauern). Nachteil wäre natürlich, dass der Speicherverbrauch relativ hoch wäre (immer der Speicher von 50 ball Objekten), auch wenn nur wenige Bälle tatsächlich verwendet werden.

Eine andere Möglichkeit wäre, die Bälle dynamisch anzulegen:

// Maximale Anzahl der Bälle
const int maxballs = 50;

// Zeiger auf bis zu 50 Ball-Objekte
ball * balls[maxballs];

// 10 Bälle erzeugen
int existingballs = 10;

for(int i = 0; i < existingballs; i++)
    balls[i] = new ball(...); // Entsprechender Konstruktoraufruf

Dann würde nur der Speicher für 10 Objekte verbraucht. Ich denke aber, deine Methode ist die bessere - aus Performancegründen und weil Speicher einfach mittlerweile in rauen Mängen vorhanden ist (und das ist die Programmierer-Mentalität, die moderne Spiele immer hardwarehungriger werden lässt ).

 

[Green Mamba]

Du solltest dir mal deine Algorithmik genauer ansehen. Du rechnest innerhalb der Schleife mehrfach r+balls.r aus, das ist optimierungsfähig. Zudem berechnest du komplexe Operationen wie eine Wurzel (sqrt), auch das ließe sich vermeiden.
Solche Optimierungen bringen im übrigen ein vielfaches gegenüber solchen Inline-Optimierungen, die nur wenige Sprungmarken weniger als die nicht Inline-Lösung beinhalten.

@tomcat83
Der std::vector hat übrigens bei wahlfreiem Zugriff eine Laufzeit von O(1), daher ist es relativ egal ob man mit einem C-Array oder einem Vector auf diese Weise umgeht.
http://www.cplusplus.com/reference/stl/vector/

 

[tomcat83]

Ach so, ich dachte, STL Vektoren seien verkettete Listen. Also muss es ein automatisch wachsendes C-Array im netten Gewand sein. Dann will ich nichts gesagt haben, danke für die Korrektur.

 

[kiep schmeiling]

Hi,
der wirklich wichtige Teil, ist der in dieser Schleife

for (int i = 0; i<balls.size(); i++) //alle baelle der rehe nach durchgehen
	   {    
		 xdst=(xpos-balls[i].xpos);    //die x entfernung ist die eigene xposition-die xposition des anderen balls
	     ydst=(ypos-balls[i].ypos);
		 
		 
		 if (xdst && ydst) //nicht auf kollision mit sich sellbst ueberpruefen (wenn x und ydst null sind muss es die eigene kugel sein, null nimmt er automatisch als false
		 {
			 if(xdst<r+balls[i].r && ydst<r+balls[i].r)    //hier wird erst mal ein qudrat um den ball gezogen, dass geht wesentlich schneller, da muss er nicht so viel rechnen, denn in 99,9% aller faele liegt keine kollision vor
			 {
				 dst2=(xdst*xdst)+(ydst*ydst);
			     if(sqrt(dst2)<r+balls[i].r)  //wenn der abstand (satz des phytagoras)der beiden kreismittelpunkte kleiner ist als die beisen radien zusammen...
			     {xspeed=0;yspeed=0;}                                                            //bleibe stehen (nur vorlaeufig)
			 }
		 }
	  }

bis zur ersten if-Abfrage, denn das muss (anzahl der bälle ^ 2)*10 mal pro frame ausgeführt werden.
Alles was hinter der zweiten Abfrage steht (der mit dem Quadrat), wird ja nur ausgeführt, wenn die beiden Bälle sehr nahe beieinander sind bzw. sich berühren, und da das nicht so oft vorkommt, kann das ja ruhig ein Momentchen dauern.
Die Wurzel ist somit nicht so schlimm, aber das mit dem "r + balls.r" (bzw. inzwischen "r + it->r") ist sehr interessant.
Die Frage ist, ob es schneller geht eine Variable zu Deklarieren, (ok, das zählt nicht so richtig dazu, weil das ja nur einmal gemacht werden muss), dieser variable einen wert durch eine Rechenoperation zuzuweisen und diesen dann zweimal abzufragen, oder das einfach zweimal auszurechnen. Die eine Rechenoperation kann man ja "Rauskürzen", weil die ja in beiden vorkommt, also ist die Frage:

(Variable neuen Wert zuweisen)+2*(Variable abfragen) < (zwei Variablen abfragen und ihre Werte addieren) ?