Strategiespiel: Regionen für Kollisionserkennung

Ich möchte, um die Kollisionserkennung zu optimieren, die Karte in Regionen aufteilen. Jetzt hab ich mir dazu ein paar Gedanken gemacht.

- Soll ich für Einheiten speichern, in welcher Region sie sind oder für Regionen speichern, welche Einheiten da drin sind? Ich habe mich für letzteres entschieden. Dann ruf ich nämlich einfach nur alle Einheiten der Region ab und teste die Kollision.

- Einheiten, die an den Grenzen einer Region sind, müssen auch in die benachbarte Region aufgenommen werden. Auch ein Grund, warum ich mich für die zweite Lösung entschieden habe.

- WIE soll ich das speichern? Ein Array von Regionen? Ein 2dimensionales Array für die Karte? Und wie speichere ich eine variable Anzahl von Einheiten pro Region?

- Das wichtigste ist, dass die Lösung schnell ist. Die Kollisionserkennung ist nämlich verdammt performance-kritisch bei mir.

Ich brauch ein paar Anregungen und Gedanken von euch, weil sowas will gut geplant werden

rapso

ich glaube, normalerweise haben die strategiespiele relativ hochauflösende 2d-arrays und in jedem eintrag des arrays kann sich nur eine einheit befinden, manchmal braucht eine einheit oder ein gebäude auch mehrere felder. ich glaube sowas ist sehr performant, wenn auch nicht speichersparrend, aber was soll's, 2048*2048 felder wären ok für eine große level und hätten 16mb bei pointer, oder du machst indicies von 16bit und hast 8mb. die kollision zu prüfen ist dann je relativ simpel, einfach prüfen ob in dem arry an der stelle ein NULL-pointer ist oder ein pointer auf eine einheit.

rapso->greets();

ps. entweder ist deine hp irgendwie tod, oder wirklich leer...?

Das Problem ist, dass meine Einheiten an beliebiger Position stehen können und nicht auf Feldern. Es können also immer zwei Einheiten mit ihren Rändern in ein einzelnes Feld hineinragen.
Die Koordinaten der Einheiten bestehen aus
{
double x, y;
}

EDIT: Die Hp ist wirklich so leer, ich hab jetzt erstmal nur ne Möglichkeit zum uploaden gebraucht.

rapso

also bei Dune2000 schaut das so aus, als ob sich die einheiten, bevor sie sich irgendwo hin bewegen, immer erst diese positionen regestrieren. das bedeutet, sie stehen vielleicht auf 1|1 und setzen sich erst in bewegung zu 2|2, wenn die position frei war und dann stellen sich sich quasi virtuell schon auf 2|2 und während dessen bewegt sich dann "der panzer" erst dorthin.

das erkennt man manchmal daran, dass sobald eine einheit sich in bewegung setzt, die andere eventuell schon auf deren alte position rollt und die sprites sich überdecken.

sonst würde ich an deiner stelle genauso handel mit den bereichen, aber anstatt die kanten zu prüfen ob die einheit noch mit den einheiten im nachbarreckt kollidiert, würde ich zweilmal das array mit den bereichen anlegen. das zweite dann um 0.5|0.5 verschieben, sodass das center jedes bereichs aus dem zweiten array an einer kreuzungsstelle der bereiche aus dem ersten array ist.

dann die einheiten so einteilen, dass die in dem bereich der beiden arrays sind, zu dem center sie den kleinsten radius haben. somit könnte es vielleicht garnicht passieren, dass eine einheit mit den objekten im nachbarbereich kollidiert.
dann könntest du auch eine doppelt verkettete liste benutzen um die objekte in die bereiche einzufügen. du müßtest also nich im voraus arrays anlegen.
das einteilen der einheiten in die bereiche wäre auch relativ einfach, da sie ja nur in einen der nachberbereiche gehen können, deren kreuzung im center des aktuellen bereichs sind.

vielleicht kannst du die bereiche auch anders erstellen als mit zwei arrays, aber das scheint mir sehr simpel.

rapso->greets();

ps. nette "tank rushes" in deinem spiel

Dune2000 ist hier kein Maßstab, weil sich dort die Einheiten in Grids bewegen. Das war in meinem alten Game auch noch so, das war auch kein Problem.
Hier jedoch müsste man sich mehr an Warcraft III oder StarCraft orientieren.
Das mit den Arrays muss ich jetzt mal prüfen, mir wäre es aber trotzdem irgendwie lieber, wenn ich die Map in sagen wir mal 100x100 Regionen aufteilen könnte und pro Region dann speichern kann es sind die Einheiten
1, 7, 12, 22, 19
drin, und dass ich bei Bedarf z.B. Einheit 7 entfernen kann oder Einheit 15 hinzufügen.
Mit welchen Mitteln könnte man sowas am besten realisieren?

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();

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();

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();

@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)

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.

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();

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.