# 2D Kollisionsabfrage mit beliebig vielen unabhängigen Objekten



## Beichtpfarrer (1. Januar 2005)

Hallo!
Ich bin dabei ein kleines Spiel zu schreiben, in dem sich mehrere Objekte (unbekannter Anzahl) auf dem (in Pixel unterteiltem) 2D-Spielfeld bewegen und sich bei Kollision gegenseitig abstoßen können.

Wie würdet ihr am besten (Rechenkapazität sowie Speicher schonend) vorgehen?


----------



## PixelShader (1. Januar 2005)

Hi,
Du schaust dir zuerst an, ob deine Objekte sich wie simple geometrische Figuren verhalten. z.B. falls du Bälle rumkugeln hast, ist die passendste Figur natürlich Kreis.

Was fur objekte sind das denn, und wie sollen sie sich den verhalten? Ich meine sollen sie fliegen und bei Kollision ihre Richtung ändern, oder stehen, und der Spieler kollidiert mit den rumstehenden Objekten?


----------



## Beichtpfarrer (1. Januar 2005)

Die Objekte sind nicht unbedingt geometrische Figuren, sondern beliebige Pixelformen.
Manche Objekte fliegen durch die Gegend und ändern bei Kollision ihre Richtung, andere sind unbeweglich.
Mir geht es hauptsächlich darum:
Ich lasse ein Objekt sich bewegen, jetzt muss es überprüfen, ob es bei seiner Bewegung gegen etwas stoßen würde und gegebenenfalls eine Referenz auf seinen Kollisionspartner bekommen.
Wie ich das mache, bin ich noch vollkommen frei (ich habe also zb auch noch nicht die Programm-Strukturen geschaffen, in der die Objektdaten gespeichert werden, usw), ich habe zwar schon darüber nachgedacht, aber mir ist keine sonderlich befriedigende Lösung eingefallen.
 Eine Lösung wäre zB für jeden Pixel einen Zeiger auf sein zugehöriges Objekt zu speichern und dann bei der Bewegung eines Objekts alle neu-belegten Pixel auf Durchlässigkeit zu überprüfen, aber das ist eher unschön, oder?

Ahja nochwas: Ich ersuche natürlich keinen fertigen Quellcode (den würde ich so in mein Projekt eh nicht einbringen), sondern ein Konzept


----------



## PixelShader (1. Januar 2005)

> Ich ersuche natürlich keinen fertigen Quellcode (den würde ich so in mein Projekt eh nicht einbringen), sondern ein Konzept


genau das hab ich verstanden  ;-] 



> Eine Lösung wäre zB für jeden Pixel einen Zeiger auf sein zugehöriges Objekt zu speichern und dann bei der Bewegung eines Objekts alle neu-belegten Pixel auf Durchlässigkeit zu überprüfen, aber das ist eher unschön, oder?


sehr unpracktisch, ja. Falls nichts geht kann man auf eine Änliche etwas schönere Loesung zuruckgreifen, bei jeder bewegung eines Objekts x, jedes andere Objekt abtasten und gucken ob sie nicht schon diese Pixel die Objekt x besetzen würde, nicht schon besetzt haben. Muss du keinen so grossen Speicher nehmen, dafur frisst es etwas mehr Leistung.

Nocmal zu geometrischen Figuren.. sehen deine Pixelbilder nicht irgentwie änlich zu z.B. Rechtecken? Es muss nicht unbedingt ein Rechteck oder Kreis sein, das Bild, was da rumfliegt. Aber falls es so auf die umbebung reagiert wie ein Rechteck oder Kreis, oder zumindest verdammt änlich, dannkann man geometrie nehmen. Kollision von Kreisen oder Rechtecken ist nicht weiter schwer.

Falls deine Objekte nicht wie Kreise oder Rechtecke aussehen, dann haben sie wohl viele Ecken und Zacken. Kollisionieren kannst du ja nur mit den am weitesten rausstehenden Ecken, also Speicher einfach fur jeden Objekt eine Array, wo du die am weitesten herausstehenden Ecken alle abspeicherst. Bei jeder bewegung von einem Objekt, guckt es ob nur die Pixel von anderen Objekten besetzt sind, die auf den Strecken die von den hervorstehenden Eckpunkten in bewegrichtung ausgehen mit der Länge des Bewegungschrittes.

Wie du das auch machst, Grundkonzept ist es, dass Jedes zu bewegende Objekt nach alle anderen Objekte durchgeht, und guckt ob diese ihm den Weg versperren. Dass frisst mehr Leistung als die von dir vorgeschlagene Variante, jedoch davon hat man mehr als vom Speicher.


----------



## Beichtpfarrer (2. Januar 2005)

PixelShader hat gesagt.:
			
		

> Nocmal zu geometrischen Figuren.. sehen deine Pixelbilder nicht irgentwie änlich zu z.B. Rechtecken? Es muss nicht unbedingt ein Rechteck oder Kreis sein, das Bild, was da rumfliegt. Aber falls es so auf die umbebung reagiert wie ein Rechteck oder Kreis, oder zumindest verdammt änlich, dannkann man geometrie nehmen. Kollision von Kreisen oder Rechtecken ist nicht weiter schwer.


Ok, das müsste ich mir nochmal überlegen. Wie würde zb eine Kollissionsabfrage von Rechteck mit einem Kreis aussehen (sowas geometrisches hatten wir in Mathe noch nicht....)?



			
				PixelShader hat gesagt.:
			
		

> Falls deine Objekte nicht wie Kreise oder Rechtecke aussehen, dann haben sie wohl viele Ecken und Zacken. Kollisionieren kannst du ja nur mit den am weitesten rausstehenden Ecken, also Speicher einfach fur jeden Objekt eine Array, wo du die am weitesten herausstehenden Ecken alle abspeicherst. Bei jeder bewegung von einem Objekt, guckt es ob nur die Pixel von anderen Objekten besetzt sind, die auf den Strecken die von den hervorstehenden Eckpunkten in bewegrichtung ausgehen mit der Länge des Bewegungschrittes.


Das gefällt mir weniger, denn soviel Mehraufwand ist es auch nicht, alle Pixel einer Form, statt nur den äußeren, zu kontrollieren (übrigens wäre die gesamte außenlinie und nicht nur Eckstellen nötig).



			
				PixelShader hat gesagt.:
			
		

> Wie du das auch machst, Grundkonzept ist es, dass Jedes zu bewegende Objekt nach alle anderen Objekte durchgeht, und guckt ob diese ihm den Weg versperren. Dass frisst mehr Leistung als die von dir vorgeschlagene Variante, jedoch davon hat man mehr als vom Speicher.


Ok, das wäre das andere Konzept, das mir eingefallen wäre, sonst gibts keine Möglichkeit?
Also eigentlich sehe ich es so, dass ich generell weniger Leistung als Speicher zur Verfügung habe (wenn man das so vergleichen kann..), lieber ein wenig mehr abspeichern, als alles die ganze Zeit wieder zu berechnen, ist normal mein Grundsatz ;-)
Aber egal, die hier benötigten Ressourcen wären sowieso eher gering (kleines Spiel), mir geht es eigentlich darum, einen schönen Code zu schreiben.


----------



## PixelShader (2. Januar 2005)

> Ok, das müsste ich mir nochmal überlegen. Wie würde zb eine Kollissionsabfrage von Rechteck mit einem Kreis aussehen (sowas geometrisches hatten wir in Mathe noch nicht....)?


Du müsstest nur ein Paar Fälle abdecken. Siehe anhang mit 6 Fällen, (vielleicht könnte man das sogar noch schöner machen, weniger Fälle).



> Das gefällt mir weniger, denn soviel Mehraufwand ist es auch nicht, alle Pixel einer Form, statt nur den äußeren, zu kontrollieren (übrigens wäre die gesamte außenlinie und nicht nur Eckstellen nötig).


Dann scanne deinen Rand und Speichere dejen 10. Pixel als Eckpunk, trotzdem noch, wird die Leistungsaufnahme viel geringer sein als alle Pixel zu scannen.



> lieber ein wenig mehr abspeichern, als alles die ganze Zeit wieder zu berechnen


Falls du speicherst, muss du diesen Speicher auch entsprechend verwalten, also unaktuelle Objekte rauslöschen und neue reinschreiben, bei jeder bewegung. Dies aber benötigt wiederum Leistung. Das Preis/Leistungsverhältniss halt. Du könntest das zwar so noch machen wenn du ein 600x800 Spielfeld hast. Bei grösseren Spielfeldern wird der Speicher knapp.


----------



## Beichtpfarrer (2. Januar 2005)

PixelShader hat gesagt.:
			
		

> Du müsstest nur ein Paar Fälle abdecken. Siehe anhang mit 6 Fällen, (vielleicht könnte man das sogar noch schöner machen, weniger Fälle).


Jaa, das hättest du nicht beachten brauchen, das war gestern spät abends, da konnte ich nicht hinreichend denken  *peinlich* Sich das zu denken erfordert eigentlich wirklich keine große Hirnanstrengung..,



			
				PixelShader hat gesagt.:
			
		

> Dann scanne deinen Rand und Speichere dejen 10. Pixel als Eckpunk, trotzdem noch, wird die Leistungsaufnahme viel geringer sein als alle Pixel zu scannen.
> 
> Falls du speicherst, muss du diesen Speicher auch entsprechend verwalten, also unaktuelle Objekte rauslöschen und neue reinschreiben, bei jeder bewegung. Dies aber benötigt wiederum Leistung. Das Preis/Leistungsverhältniss halt. Du könntest das zwar so noch machen wenn du ein 600x800 Spielfeld hast. Bei grösseren Spielfeldern wird der Speicher knapp.



Ok, ich überlegs mir, danke für deine Hilfe, ich werde es jetzt wirklich so machen, wie von dir vorgeschlagen, alle Objekte auf Kollision überprüfen, statt ein Pixelraster zu speichern (scheint sinnvoll argumentiert, was du da schreibst *g*)
Was mich noch interessieren würde: bei ellypsenförmigen Objekten (sowas hatten wir jetzt noch wirklich nicht in Mathe), wie kann man hier crachs mit Rechtecken/Kreisen abfragen?

Mfg


----------



## PixelShader (2. Januar 2005)

nochmal zu


> (sowas geometrisches hatten wir in Mathe noch nicht....)?


 Ich glaube nicht dass wir sowas überhaupt mal in Mathe machen...   
-----
Eigentlich ist eine gute Ellipse etwa so definiert: alle Punkte mit der Selben Summe von Abschtanden zu 2 Punkten.
Wie du schon gemerkt hast, bei Kreisen muss man nur die Abschtande berechnen, egal ob du auf Kollision mit Kreisen oder Rechtecken prufst. Um am Mittelpunkt zu bleiben, ich weiss zwar nicht ob das geometrisch richtig ist, aber ich wurde diese annaherung bevorzugen: Man nimmt den Mittelradius, und in Abhangigkeit vom winkel addiert man einen Cosinus(winkel*2); na? Mal etwas anschaulicher: siehe Anhang
So kannst du eine Ellipse wie einen Kreis behandeln, da du auch den Radius vom Mittelpunkt kennst.  ;-)


----------



## Beichtpfarrer (2. Januar 2005)

lol.. ich blick gar nix...
Naja 10. Klasse und unser Mathelehrer ist (dergleiche wie letztes Jahr) nicht unbedingt ein Held, macht sowieso nur die Hälfte des Stoffs und Cosinus und dergleichen haben wir noch nicht behandelt.
Kannst du das ganze bitte nochmal ausführlicher erklärn?


----------



## PixelShader (2. Januar 2005)

> Naja 10. Klasse


auch





> und unser Mathelehrer ist (dergleiche wie letztes Jahr) nicht unbedingt ein Held, macht sowieso nur die Hälfte des Stoffs und Cosinus und dergleichen haben wir noch nicht behandelt.


Habt ihr unseren Mathelehrer oder wie   

also, Sinus und Cosinus sind zur Winkelberechnung im rechtwinkligen Dreieck in Trigenometrie da. Doch kann man diese schöne Funktionen auch "mishandeln", (was ich ständig auch mache) Diese Kurve der Funktionen lässt sich in der Praxis auf vieles übertragen. siehe Anhang.
Ich benutze die Cosinuskurve um den Unterschied zwischen einem Kreis und einer Ellipse darzustellen. Bei 0 Grad gibt Cosinus eine 1 zurück. bei 180 eine -1, und bei 360 wieder eine 1.
Siehe vorheriger Post->Anhang->diff. Re ist der Radius der Elipse, da es aber viele unterschiedliche radien gibt, unterscheden wir zwischen ihnen mithilfe des Winkels a. diff wird mit cos(a*2) multipliziert, da cos einen Maximalwert von 1 hat, wird diff*cos(a*2) einen Wert von diff haben. Die Ellipse hat bei a=0 Grad kleineren Radius als der Blau gemalte Kreis und zwar um diff also (Blauer_Kreis_Radius)-diff=(ElipseRadius). Bei a=90 dagegen ist der EllipsenRadius um diff grösser. Genau diese grösser-kleine-veraenderung beschreibt diff*cos(a*2).


----------



## Beichtpfarrer (2. Januar 2005)

Ok, danke jetz hab ichs geblickt... man man man, du bist'n Genie oder...
..ich mein, ich gelte ja in meiner Schule schon als Genie... aber du erst...


----------



## revelation (2. Januar 2005)

> Ok, danke jetz hab ichs geblickt... man man man, du bist'n Genie oder...
> ..ich mein, ich gelte ja in meiner Schule schon als Genie... aber du erst...



lol


----------



## Kachelator (3. Januar 2005)

revelation hat gesagt.:
			
		

> lol



He, damals kannte ich den Kram auf noch nicht (10. Klasse).


----------

