Strategiespiel: Regionen für Kollisionserkennung

[rapso]

hab ich doch geschrieben

[rapso]

noch wat, die performance scheint garnicht so kritisch zu sein bei dir, immerhin hab ich rendering 4ms und logic 0ms.. aber die framerate bleibt bei 50fps... recht komisch

rapso->greets();

[Gast]

Ja, du hast die alte Version.
Die neue Version hat ne sehr gute Wegfindung, aber ich prüfe da bei vielen Wegpunkten, ob sie miteinander verbunden sind.
Das heißt ich "zeichne" praktisch alle Verbindungen nach, und da wird dann insgesamt mal schnell bis zu 3,4 Millionen mal die Kollisionsprüfung aufgerufen.
Ich hab zwar schon Mittel und Wege gefunden, das zu reduzieren, aber ich muss trotzdem die Kollisionsabfrage noch weiter optimieren. Die Bäume sind kein Problem, die kann ich sehr performant prüfen. Vielleicht kann mir jemand bei den Einheiten noch ein bisschen helfen:

// EINHEITEN PRÜFEN:
	for (int i = 0; i < Unit::MAX_NUMBER; i++)
	{
		// Pointer auf die aktuelle Einheit:
		Unit *pUnitI = &unit[i];

		// Prüfen, ob diese Einheit überhaupt zur Kollision zählt:
		if (IsCollisionUnit(pUnitI, reallyWalk))
		{
			// RADIUS BESTIMMEN:
radius = [...]
			// RADIUS IST BESTIMMT; JETZT AUF KOLLISION PRÜFEN:
			const double distanceX = pUnitI->pos.x - posToGo->x;
			const double distanceY = pUnitI->pos.y - posToGo->y;
			if (abs(distanceX) < radius  &&  abs(distanceY) < radius)
			{
				// Einheiten kollidieren:
[...]
				return false;
			}
		}// isCollisionUnit
	}// for (int i = 0; i < Unit::MAX_NUMBER; i++)

double abs(const double &value)
{
	if (value < 0.0)
		return -value;
	else
		return value;
}

[rapso]

dein source ist schön zum optimieren

als erstes solltest du wissen, dass float reicht. double braucht man eigentlich nicht. cpus rechnen intern standartmässig sowieso mit doubles und deswegen brauchst du dir keine angst um precision machen.

bei float zahlen ist das oberste bit das, was das vorzeichen bestimmt, das solltest du theoretisch mit einem

distanceX = ( ((int*)&distanceX) & 0x7FFFFFF );

vorzeichenlos bekommen, ist sehr viel optimierter eigentlich.

wobei ich mich frage wieso du einerseits mit radius und dann wieder mit den x/y ausmassen rechnest

rechne beide male mit dem radius (bzw mit dem quadratischen radius), das ist fixer und einfacher.

const float distanceX = pUnitI->pos.x - posToGo->x;
const float distanceY = pUnitI->pos.y - posToGo->y;
const float minimumR = pUnitI->Radius + posToGot->radius;

if( (distanceX*distanceX)+(distanceY*distanceY) < minimumR*minimumR)

sorre wegen der codetag-losigkeit, aber irgendwie will das hier nicht klappen.

mag sein dass mein code auf sehr kleinliche dinge eingeht, aber da das wohl so extrem oft aufgerufen wird, kann das einiges bringen... benchmarking ist wohl nötig.

rapso->greets();

[Gast]

So kleinliche Dinge mag ich gern
Das mit float hab ich oft ausprobiert, aber leider war float nie schneller als double, manchmal langsamer. Das mag vielleicht eben daran liegen, dass CPUs nach deiner Aussage mit double rechnen. Vielleicht muss dann ständig gecastet werden, ich weiß es nicht.
Das mit dem quadratischem Abstand brauche ich nicht, weil ich eine rechteckige Kollision verwende. Wahrscheinlich ist "radius" eine unpassende Bezeichnung für die Variable
Ich bestimmte praktisch den x- und den y- Abstand der Einheiten und wenn der Betrag einer der beiden Abstände kleiner als der "radius" ist, dann kollidieren die Einheiten.

Ich hab die Variable radius genannt, weil sie nicht die Länge und Breite der Einheit ist, sondern die halbe Länge/Breite. Praktisch ein "eckiger Radius".

[rapso]

float ist eigentlich nicht langsammer als double, das reinladen passiert beide male in einem takt.
aber mit float kannst du halt so schön casten, dann ist es ein int, hab mich wohl auch versehen

distanceX = *((float)&( ((int)&distanceX) & 0x7FFFFFF ));

so müßte es dann richtig sein... manchma bin ich zu beeilt.

du solltest die kollisionsberechnung nicht so extrem durchführen.

es wäre viel einfacher wenn du ein paar knotenpunkte in der level hättest (grob verteilt) und dir vorher speicherst welcher mit welchem verbunden ist.
anschliessend beim wegfinden müßtest du nur den weg von der einheit zum ersten knotenpunkt finden und dann am ende vom knotenpunkt zu richtigen ziel, aber für den groben weg über die ganze level müßtest du nicht wirklich was aufwendiges berechnen...
"die schnellste berechnung ist die, die man nicht machen muss" ist das motto und vorspeichern von knoten ist oft verwendet und läuft gut.

hilft dir aber bei lokalen kollisionen nicht

was bringt deine radiusberechnung und wieso machst du die nicht für beide elemente der kollision?

rapso->greets();

[Cpp_Junky]

Ich habe sowas änhliches auch schonmal gemacht.
War nur eine Spielerei.
Ich habe für die Regionen eine Klasse entworfen, die alle benötigten Informationen hält. Wenn ich Einheiten bewege mussten diese nur von Region-A nach Region-B umgeschrieben werden.
Es gibt also für jede Region ein Objekt. Jedes Objekt hat die Kennungen der dort befindlichen Einheiten.
Anhand dieser Kennungen kann man dann auf das Einheiten-Objekt referenzieren.
Dort steht dann Position, Energie bla bla usw.
(edit)
Was noch wichtig ist: Sobald eine Einheit bein Bewegen eine Region verlässt, muss diese natürlich ihre Kennung im Region-A Objekt austragen und ins Region-B Objekt wieder eintragen.

Ich glaube mit einem unsichtbaren Grid ist das ganze einfacher - Was spricht dagegen, ein Grid zu verwenden wie z.B bei den ersten beiden C&C teilen ?

[rapso]

(ganz meine rede)

mach WarCraft ja vielleicht auch und nur so fein tesseliert dass man das nicht sofort merkt.
ist das einfachste und schnellste.

rapso->greets();

[Gast]

@Junky: Ja genau, und jetzt würde mich interressieren wie du das gespeichert hast, welche Einheiten in dem Objekt sind

@rapso: Die Wegfindung findet eh nur in einem kleinen Umkreis statt, ist also lokal.

distanceX = *((float)&( *((int*)&distanceX) & 0x7FFFFFF ));

c:\Programme\Microsoft Visual Studio .NET\Projects\StoneAge\main.cpp(2483) : error C2102: '&' requires l-value
Leider blick ich da überhaupt nimma durch, also kann ich den Fehler nicht beheben

[Cpp_Junky]

@Optimizer:
Wie bereits beschrieben habe:
In einem Array werden Kennungen (Jede Einheit hat eine eindeutige) der Einheiten gespeichert die sich in der betreffenden Region aufhalten.
Anhand dieser Kennungen komm ich an die genauen Informationen der Einheiten (Position, aktuelle Aufgabe usw)

[Gast]

Schon klar, aber wie speicherst du pro Objekt mehrere Kennungen? Ach so, du hast in jedem Objekt ein Array oder wie?
Wie sind denn so deine Erfahrungen, lohnt es sich die Karte in Regionen aufzuteilen? Wieviele Einheiten konnte es in deinem Spiel maximal gleichzeitig geben?

[rapso]

du weißt in welchem feld das object ist, das bekommst du anhand der x/y coordinaten raus. und das feld kennt das objekt über z.B. id oder pointer.

selbst wenn es mehrere felder sind, das objekt weiß welche es überdekt.

[Gast]

Ja, meine Frage war nur, wie ich das am besten speicher, welche EinheitEN (Mehrzahl) in dem Feld sind. Ich leg jetzt pro Feld ein Array mit den IDs an, so geht's auf jeden Fall.

[rapso]

in den spielen sind die felder so klein dass eben nicht mehrere einheiten drinne sein können.. physikalischgesagt kann zur selben zeit nur eine materie an einem platz sein.

rapso->greets();

[Gast]

Egal, wie klein du das Feld machst, es können immer zwei Einheiten so da stehen, dass ihre Ränder in das Feld hineinragen - wenn du wirklich double-Ortsvektoren als Koordinaten verwendest. Und das wollte ich unbedingt machen, damit Einheiten praktisch in JEDE Richtung (nicht nur in 8 oder 16) gehen können und dabei immer die selbe Geschwindigkeit haben.
Außerdem find ich es auch nicht sinnvoll, eine Einheit über 50 Felder erstrecken zu lassen.

Ich weiß was du meinst und mir sagen willst - aber ich will kein Grid-basiertes Spiel schreiben.
Wir können uns nächste Woche gerne weiter darüber unterhalten, aber jetzt muss ich in meine Barracks

Das mit den Regionen werd ich mir nochmal genau durch den Kopf gehen lassen... ich hab inzwischen noch ein bisschen was optimieren können und hoffe, nächstes Wochenende eine neue Version hochladen zu können.

[Cpp_Junky]

Optimizer schrieb:

Schon klar, aber wie speicherst du pro Objekt mehrere Kennungen? Ach so, du hast in jedem Objekt ein Array oder wie?
Wie sind denn so deine Erfahrungen, lohnt es sich die Karte in Regionen aufzuteilen? Wieviele Einheiten konnte es in deinem Spiel maximal gleichzeitig geben?

Also, zuerst muss ich mal sagen das ich das ganze auf Grundlage der MFC entwickelt habe - Damit hatte ich die Klasse CObArray zur Verfügung die eigentlich die ganze "Einheiten-Verwaltung" so einfach macht.
Innerhalb des "Regionen-Objekts" sieht das etwa so aus, das es genau ein Objekt des Typs "CObArray" gibt. Dieses Objekt bekommt jeweils die Adresse des Sprite-Objekts zugewiesen dessen Einheit sich in der Region befindet.

/Pseudo

Sprite* pEinheit = new Sprite;

...

// Einheit betritt neue Region

pAlteRegion->pEinheiten.Remove(pEinheit);
pNeueRegion->pEinheiten.Add(pEinheit);

... usw

Es werden also nur Adressen unter den Regionen-Objekten ausgetauscht.
Aber da du höchstwahrscheinlich kein MFC nutzen wirst musst du dir diese Organisation selbst schaffen. Darum sagte ich das mit dem Array und den ID's
Man könnte dann (das ist natürlich nicht so schick wie mit dem Pointer-Array ) immer Index-Werte der Einheiten-Arrays tauschen.

[Gast]

Stimmt, ein Pointer-Array wäre sicherlich sinnvoller...

[rapso]

willkommen back bundeswehr mensch, ist schon ne neue version online?

rapso->greets();

[Gast]

Nein, aber ich hoffe heute noch

Ein paar Probleme muss ich noch lösen.