Laden...

WinForms Shape: Kollisionsabfrage - Verbesserungsvorschläge

Erstellt von GeneVorph vor 5 Jahren Letzter Beitrag vor 5 Jahren 2.905 Views
G
GeneVorph Themenstarter:in
180 Beiträge seit 2015
vor 5 Jahren
WinForms Shape: Kollisionsabfrage - Verbesserungsvorschläge

Hallo,

und gleich noch eine Frage:

ich spiele gerade ein bisschen mit den Shapes in WindowsForms rum und habe mir dazu einen beweglichen Kreis erstellt. Zudem gibt es jede Menge stationäre Kreise. Der bewegliche Kreis flitzt lustig in einem Panel hin und her und jedes Mal, wenn er mit einem stationären Kreis kollidiert, ändert er seine horizontale und vertikale Bewegungsrichtung. Klappt soweit alles prima! (übrigens: im Anhang ist ein - nachgestelltes Bild, damit man sich's besser vorstellen kann. Der bewegliche Kreis ist rot, die stationären blau.)

Damit das alles klappt, braucht es eine Kollisionsabfrage. Und die schaut bei mir so aus:

Ich erstelle mit Rectangle meine Kreise.
Dem beweglichen Kreis ordne ich eine public Variable zu (public Rectangle RedCircle).
Die unbeweglichen Kreise packe ich in eine Liste (List<Rectangle>StationaryObjects).
Auf meiner WinForm ist eine Timerinstanz, die alle 100ms feuert und meine CollisionDetection-Methode aufruft. Dort passiert folgendes:



foreach (Rectangle stationaryObject in StationaryObjects)
{
   if (RedCircle.IntersectsWith(stationaryObject))
   {
       OnObjectCollision?.Invoke();
   }
}

Die Methode prüft für jeden unbeweglichen Kreis, ob eine Kollision mit dem beweglichen Kreis stattgefunden hat. Falls das zutrifft, wird ein Event (OnObjectCollision) gefeuert, der die Richtungskoordinaten des beweglichen Kreises ändert. Funktioniert soweit einwandfrei.

Jetzt meine Frage:
Rein von meinem Verständnis her ist diese Lösung nicht so optimal. Mich stört es, dass ich einen Haufen unnötige Abragen mit meiner foreach-Schleife machen muss. Es ist ja immer nur eine Kollision zu einem Zeitpunkt möglich.

Ich hätte schon ein paar Ideen, wie ich mit einer eigenen Stationary-Klasse das Problem angehen könnte, oder wenn ich eine Möglichkeit hätte nach dem Schema :
if (RedCircle.IntersectsWith(typeOf(Rectangle)) -- was natürlich nicht geht.

Leider scheint es, dass ich auf die Methode .IntersectsWith() angewiesen bin.

Hat jemand Ideen, wie ich meine Kollisionsabfrage besser machen / effizienter gestalten könnte?

Vielen Dank schon mal vorweg - ich betrachte mich immer noch als C#-Anfänger, auch wenn ich mittlerweile Code mit Papier und Bleistift schreiben kann. Eine Tatsache, die ich vor allem den Hilfswilligen dieses Forums verdanke.

In diesem Sinne,
Gruß
Vorph

4.931 Beiträge seit 2008
vor 5 Jahren

Wenn du nur genau mit einem Objekt je Timer-Tick eine Kollision auslösen willst, dann breche doch einfach die Schleife mittels break ab.

Für 5 (oder auch einige Dutzend) Objekte lohnt sich eigentlich keine Optimierung.
Wenn du jedoch mehr als einige 100 Objekte jedesmal abfragen müßtest, dann wäre z.B. ein QuadTree (bzw. OktTree für 3D), wie ihn viele Spiele nutzen, sinnvoll.

PS: Für Kreiskollisionen nimmt man eigentlich den Abstand der Kreismittelpunkt (anstatt die Rechteckkollision):


var distance = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // nach Pythagoras
var r = r1 + r2;
if (Math.Sqrt(distance) < r) // bzw. distance < r * r

G
GeneVorph Themenstarter:in
180 Beiträge seit 2015
vor 5 Jahren

Hallo Th69,

Danke für den Hinweis mit dem QuadTree. Kannte ich bisher nicht - ich habe mir aber über deinen Link den Wikiartikel zu Gemüte geführt und hätte jetzt noch ein paar Fragen.

Vorweg, ich habe bestimmt nicht alles verstanden; dazu müsste ich mich tiefer in die Materie einlesen.
Was die Kollisionskontrolle angeht, verstehe ich glaube ich so viel:
Ich müsste mein Panel in ´quadratische Raster zerlegen und statt die Gesamtzahl aller unbeweglichen Objekte abzufragen nur jeweils ein bestimmtes Raster. Jetzt mal grob formuliert.

Es stellt sich mir jetzt aber folgende Frage: wäre das nicht eher sinnvoll, wenn meine Kollisionen in einem polynomischen Verhältnis zueinander stünden?
Also: 100 bewegliche Objekte - würde ich für jedes einen Kollisionsstatus erfragen wollen, wären das 100*100 Abfragen = 10000. Das wäre dann eine Menge Holz. Durch den QuadTree käme ich (laut Wiki) auf O (log n) Abfragen, i. d. Fall also nur 200 Abfragen. (Korrigiere mich bitte, wenn ich falsch liege)

In meinem Fall habe ich ja nur ein Objekt (roter Kreis) der sich bewegt, so dass ich immer nur so viele Abfragen habe, wie ich statische Objekte habe. Oder habe ich da einen Denkfehler?

Gibt es keine Möglichkeit, die stationären Objekte mit einer Eigenschaft oder einem Tag zu versehen, so dass ich für diesen speziellen Fall einfach durch eine if-Abfrage prüfen kann oder bei Kollision ein einzelnes Ereignis auslösen kann?

Vielen Dank für den Hinweis mit der Berechnung für Kreiskollisionen mit dem Kreismittelpunkt. Leuchtet mir ein, ansonsten wird ja das (unsichtbare) Rectangle um den Kreis als Kollisionsbegrenzung herangezogen, was ja nur für die 4 Kreispunkte bei 0°, 90°, 180° und 270° exakt mit dem Rectangle übereinstimmt. (Für Kollisionen mit der Panelbegrenzung aber ausreichend ist?).

Vielen Dank für dein reply,
Gruß
Vorph

4.931 Beiträge seit 2008
vor 5 Jahren

Ja, ich denke, das hast du richtig verstanden.
Bei nur einem beweglichen Objekt ist die Anzahl der Abfragen so groß wie die Anzahl der unbeweglichen Objekte. Wenn du dann doch mehrere bewegliche Objekte haben möchtest, dann multipliziert sich die Gesamtanzahl an Abfragen entsprechend (kann ja sein, daß du das Programm entsprechend ausbauen möchtest und daher der Hinweis auf den Quadtree).

Und zu

Gibt es keine Möglichkeit, die stationären Objekte mit einer Eigenschaft oder einem Tag zu versehen, so dass ich für diesen speziellen Fall einfach durch eine if-Abfrage prüfen kann oder bei Kollision ein einzelnes Ereignis auslösen kann? Dies verstehe ich nicht so ganz. Was gefällt dir denn an dem Vorschlag mittels break nicht?


foreach (Rectangle stationaryObject in StationaryObjects)
{
   if (RedCircle.IntersectsWith(stationaryObject))
   {
       OnObjectCollision?.Invoke();
       break; // <- abbrechen, wenn eine Kollision stattfand
   }
}

(also im Schnitt etwa N/2 Abfragen)

G
GeneVorph Themenstarter:in
180 Beiträge seit 2015
vor 5 Jahren

Dies verstehe ich nicht so ganz. Was gefällt dir denn an dem Vorschlag mittels break nicht?

  
  
Nee, so war das nicht gemeint (ich hab's auch in meinen Code mittlerweile eingebaut) - war lediglich eine Frage, ob ich zwangsläufig immer [b]von[/b] den stationären Objekten aus testen muss (also jedes einzelne abfragen, ob es gerade mit meinem beweglichen Objekt kollidiert), oder ob es eine Art Trigger oder etwas Ähnliches gibt. Ich bin aber mittlerweile selbst auf den Trichter gekommen, dass dann ja trotzdem im Hintergrund immer irgendetwas laufen muss, was den aktuellen Kollisionszustand meiner Objekte überwacht. Womit wir wieder am Ausgangspunkt wären :-)  
  
Aber meine ursprüngliche Frage hat sich damit geklärt - vielen Dank!
G
GeneVorph Themenstarter:in
180 Beiträge seit 2015
vor 5 Jahren

Ah - sollte jemand mal vor demselben Problem stehen, wie ich: ich konnte noch einen Fehler entdecken. Die Idee mit der Formel des Phythagoras die Kollisionsabfrage zu gestalten war für mich unmittelbar einleuchtend - ich hatte dann aber einen Fehler entdeckt:

So funktioniert es nicht:

C#-Code:
var distance = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // nach Pythagoras
var r = r1 + r2;
if (Math.Sqrt(distance) < r) // bzw. distance < r * r

Wenn man mit den x- und y-Koordinaten der Kreise arbeitet, bekommt man dann ein ganz komisches Verhalten. Ich weiß nicht, ob es bei WPF anders ist, aber bei WinForms ist etwas mehr Arbeit notwendig. Der Grund ist folgender:

  • man kann keine Shape "Ellipse" erstellen. Dafür muss man auf ein Rectangle zurückgreifen; d. h. der "Kreis" ist eigentlich ein Rechteck - die obere linke Ecke markiert den Punkt, der die x-Koordinate des gesamten Rechtecks angibt, bzw. die y-Koordinate repräsentiert.

Man muss also folgendes tun:

  1. von den zu vergleichenden Kreisen jeweils die Mittelpunktkoordinaten bestimmen; daran denken, dass der Mittelpunkt der Kreise relativ zur linken oberen Ecke des Rectangles zu ermitteln ist:
var xCenterCircleA = (CircleA.X + (CircleA.Width/2)) //x-Koordinate plus Radius
var yCenterCircleA = (CircleA.Y + (CircleA.Height / 2)) // Entfernung der umschließenden Rechteckseite zu Kreismittelpunkt 

//dasselbe für den zu überprüfenden Kreis
var xCenterCircleB = (CircleB.X + (CircleB.Width/2)) 
var yCenterCircleB = (CircleB.Y + (CircleB.Height / 2))


  1. Nun braucht man die Distanz zwischen x und y-Werten (Betrag)
var xDistance = xCenterCircleA - xCenterCircleB
var yDistance = yCenterCircleA - yCenterCircleB 

//sicherstellen, dass man immer den Betrag der ´Distanz erhält
if (xDistance < 0)
xDistance = xDistance * (-1);

if (yDistance < 0)
yDistance = yDistance * (-1)
  1. Anhand eines pythagoräischen Dreiecks die augenblickliche Distanz ermitteln:
var currentDistance = Math.Sqrt((xDistance * xDistance) + (yDistance * yDistance))

Der Wert von currentDistance repräsentiert den Wert, den beide Kreise mindestens haben müssen, um eine Kollision auszulösen (Berührung in einem Puinkt). Demnach muss die Kollisionsabfrage lauten:


if (currentDistance <= ((CircleA.Width/2) + (CircleB.Width/2))
{
//Kollision!
}

Gruß
Vorph

4.931 Beiträge seit 2008
vor 5 Jahren

Sorry, daß ich das nicht explizit zu dem Code dazugeschrieben habe, aber für mich ist es selbstverständlich, daß x und y in der Formel die Kreismittelpunkte und r die Radien sind.

Daß man dann für die Darstellung noch ein paar mathematischen Berechnungen anstellen muß, ist klar.
Du solltest auch bedenken, daß Kollisionsberechnungen etc. in die Logik-Schicht (s.a. [Artikel] Drei-Schichten-Architektur) gehören, d.h. du eigene Datenstrukturen dafür hast (z.B. eine List<Circle>, wobei Circle dann eine eigene Klasse oder Struktur mit entsprechenden Eigenschaften darstellt).
Und für die UI ist es dann so, daß diese dann aus dieser Datenstruktur die passenden Objekte erstellt (mit evtl. kleineren math. Anpassungen).

Trotzdem schön, daß du so detailliert diese Umrechnung mal hier aufgeschrieben hast (hilft evtl. auch anderen Usern hier).

PS: Dein 2. Punkt "Distanz zwischen x und y-Werten (Betrag)" ist überflüssig, da im nächsten Schritt sowieso das Quadrat genommen wird (d.h. dieses ist immer positiv).

PPS: Aus Performancegründen wird bei deinem Punkt 3 meist auf Math.Sqrt verzichtet, da dies langsamer als die Multiplikation ist (daher in meinem Code als Kommentar: distance < r * r).

G
GeneVorph Themenstarter:in
180 Beiträge seit 2015
vor 5 Jahren

Danke für deine Hilfe und Anmerkungen, Th69!

PS: Dein 2. Punkt "Distanz zwischen x und y-Werten (Betrag)" ist überflüssig, da im nächsten Schritt sowieso das Quadrat genommen wird (d.h. dieses ist immer positiv)

Stimmt 🙂 Da war der Eifer schneller, als mein mathematisches Verständnis 😁

Gruß
Vorph