# Kollision in 2D



## spyboot (24. Apr 2009)

Hi leuts,

Ich arbeite momentan an einen Spiel in dem sich der User zuerst ein Raumschiff zusammensetzt und anschließend ein (kleines) Universum damit erkunden kann.
Klappt soweit auch alles! Nur dass ich jetzt an den Punkt komme wo ich Kollisionen mit bis zu 50 Objekten berechnen muss. Abprallwinkel und resultirende Rotation ist kein Problem da ich schon beim umherfliegen die Auswirkungen jedes angebrachten Antribes auf dass Schiff berechnen musste (Berechnenung des Schwerpunktes/Mittelpunktes durch ein vorher festgelegtes Gewicht und Mittelpunkt jedes Bauteiles). Also ist es auch keine Schwierigkeit die Auswirkung von Kräften durch Angabe des Angriffspunktes, Winkel und Stärke der Kraft zu berechnen.
Da mann das Schiff beinahe beliebig gestalten kann möchte ich nicht einfach das Ding in nen Viereck packen da des ziemlich unlogisch assähe  

Das Problem ist nun eine Effiziente und Ressourcenschonende Lösung zu finden die auch bei vielen Objekten nicht schlappmacht.

Bitte alles verständlich für nen 14 Jährigen Jungen das ich nicht wieder alles im Wiki nachschlagen muss. Danke!


----------



## André Uhres (25. Apr 2009)

Einstieg in die Spieleprogrammierung mit Java
...
Pixelgenaue Kollisionsermittlung
Wie zu Beginn der Kollisionsermittlung beschrieben, ist es sehr ungenau, wenn die
Kollision nur über die Methoden der Klasse Rectangle2D durchgeführt wird. Gerade
wenn man Grafiken verwendet, die relativ viel transparenten Hintergrund enthalten
kann so ein Spiel schnell frustrierend werden...
Lies weiter: http://www.java-forum.org/buecher-tutorials-und-links/14545-tutorials-von-mitgliedern.html


----------



## spyboot (25. Apr 2009)

Hab ich vergessen: Ich hab nen Vollbildframe und zeichne den 20 mal die Sekunde neu.
Ich hatte zuerst daran gedacht über die nicht Transparent bereiche des schiffsbildes ein 20x20 Gitternetz zu legen aber das ist selbst bei kleinen Raumschiffen (ca. 600x600px) noch zu aufwändig für jeden einzelnen errechneten nicht Transparenten Punkt auf eine Kollision zu prüfen.
Außerdem kann das Schiff sich um 360° drehen.


----------



## Evolver (25. Apr 2009)

Berechne dir doch ein java.awt.Polygon, dass den Schiffsumriss einigermaßen genau beschreibt. Analog auch für andere Objekte. Mit getBounds() kannst du dir ein Rechteck geben lassen, welches das Polygon enthält. Du kannst dann die Kollisionserkennung zuerst grob über die Rechtecke machen und wenn Du dort eine potentielle Kollision erkennst, prüfst du es nochmal genauer über das Polygon. Die entsprechenden Methoden sind in Rectangle und Polygon schon implementiert. Sollte auch einigermaßen performant sein.


----------



## spyboot (25. Apr 2009)

@Evolver danke für die gute Idee! Nur leider aufwändig aus dem Schiffsbild nen Polygon zu berechnen wüsste net wie ich das hinkriegen sollte.

Weiß jemand wo ich die Klasse "Sprite" finde?


----------



## spyboot (25. Apr 2009)

Ok hatt sich erledigt die Klasse Sprite hatt er sich selbstgeschrieben werd mich also mal dransetzten und was änliches schreiben. 
danke für eure antworten!


----------



## spyboot (25. Apr 2009)

So hab mir mal aus dem was ich da gelesen hab was gebastelt :


```
public static boolean collision(BufferedImage img1,BufferedImage img2,int x1,int y1,int x2,int y2){
		
		long delay=System.currentTimeMillis();
		
		Rectangle r1=new Rectangle(x1-x2,y1-y2,img1.getWidth(),img1.getHeight());
		Rectangle r2=new Rectangle(0,0,img2.getWidth(),img2.getHeight());
		
		if(r1.intersects(r2)){
				Rectangle inter=r1.intersection(r2);
				int x=0;
				int y=0;
				
				while(x<inter.width){
					while(y<inter.height){
						int rgb1=img1.getRGB(x,y);
						int rgb2=img2.getRGB(x+inter.x,y+inter.y);
						if(isOpaque(rgb1)&&isOpaque(rgb2)){
							
							System.out.println(System.currentTimeMillis()-delay);
							
							return true;
						}
						
						y++;
					}
					y=0;
					x++;
				}
			
			
		}
		System.out.println(System.currentTimeMillis()-delay);
		return false;
	}
	
	
	private static boolean isOpaque(int rgb) {
		int alpha=(rgb >> 24) & 0xff;
		
		if(alpha==0){
			return false;
		}
		
		
		return true;
	}
```


----------



## spyboot (25. Apr 2009)

Nun muss ich nurnoch die BufferedImages drehen bevor ich sie übergebe.
Außerdem kann ich später um leistung zu Sparen zb. nurnoch alle 5 Pixel einmal prüfen (25xSchneller).


----------



## spyboot (25. Apr 2009)

Hab grad festgestellt dass das Drehen zum Problem wird:

Ich muss eine Methode schreiben mit der ich ein Image um einen Beliebigen Punkt und einen beliebigen Winkel drehen kann und gleichzeitig dass Bild nicht Abschneide (Ecken weg). Es Gibt jede menge Ansätze im Internet doch die funktionieren nur bei quadratischen Bildern und gehen von einem festem Drehpunkt aus.
Was ich bräuchste wären Ideen zu einer Methode:

BufferedImage rotation(BufferedImage buf, int drehpx, int drehpy,int rotation)

Edit: Problem gelöst doch leider alles sehr unperformant.


----------



## Quaxli (27. Apr 2009)

Vermutlich kannst Du Dein Schiff in 1°-Schritten drehen? Grundsätzlich würde ich das Drehen vorher erledigen, entweder im Image oder rechnerisch. Während des Spiels wäre es zu zeitaufwändig, denke ich und würde in unnötigen Verzögerung resultieren

Es macht natürlich keinen Spaß, 360 Bilder zu berechnen und vorzuhalten. Auf die Schnelle fallen mir folgende Möglichkeiten ein, die ich aber noch nie ausprobiert habe und die auf die eine oder andere Weise "unschön" sind.

1. größere Rotationsschritte, z. B. jeweils 6 Grad, analog zu einer Uhr, würde das Ganze auf 60 zu berechnende Bilder reduzieren. Nachteil wäre hier halt eine eher ruckelige Bewegung bei der Drehung.

2. Hängt davon ab, wie das Bild Deines Raumschiffs aussieht. Berechne die ersten 90° - gibt abhängig von Deiner Schrittweite max. 90 Bilder. Den Rest über horizontale und/oder vertikale Spiegelungen.

Ich vermute aber, ehrlich gesagt, daß beide Vorschläge problematisch sind. Ich war mir nicht sicher, ob ich sie überhaupt hinschreiben soll.  
Grundsätzlich dürfte das ein Problem sein, wenn man nur mit Java2D arbeitet.
Ich würde nochmal über den Vorschlag von Evolver nachdenken und das Raumschiff evtl. nur aus Polygonen bzw. "Bordmitteln" zusammen setzen (man kann Grafikprimitive auch übereinander zeichnen  ).


----------



## Evolver (27. Apr 2009)

Mein Vorschlag war nicht, die Grafik des Schiffs mit Polygon usw. darzustellen, sondern nur Polygon für die Kollisionserkennung zu verwenden. Es sollte eigentlich auch nicht so schwer sein, dieses Polygon zu berechnen, wenn man Schritt für Schritt vorgeht (Umriss des Schiffs graphisch ermitteln, Pixel verallgemeinern (man will ja nciht unbedingt 1000 Polygonecken), aus den verbelibenden "Ecken" das Polygon erzeugen).


----------



## Quaxli (27. Apr 2009)

Ja, das habe ich nicht gut formuliert. Aber Dein Vorschlag hatte mich auf die Idee gebracht, daß es für das neue Problem das Schiff gedreht anzuzueigen evtl. ein Lösungsansatz wäre.


----------



## spyboot (27. Apr 2009)

Ich mache gerade dass mit den Polygonen indem ich alle Punkte des einen Polygon über die Methode inside mit dem anderen abgleiche. Da mann dass Schiff aus mehreren Bauteilen (ca 10-200) zusammensetzt speicher ich in jeder Datei die ein Bauteil beschreibt einfach noch das Polygon bei. Anschließend berechne ich die Kollision einfach für jedes Teil extra und kann dann ziemlich genau den Kollisionspunkt meiner Physik-Engine übergeben.

Achso: ich arbeite sowieso immer mit nem 80° system. Das reicht dass sind nämlich immernoch 20 Positionen pro 1/4 Drehung.


----------

