# collisionDetection



## skappler (27. Mai 2012)

Hallo Leute. 
Ich arbeite an einem Spiel und verzweifle grad and der collisionDetection.
Ich hab zwar eine Idee wie ich es machen will, aber die Implementierung funktioniert nicht. 
Ich berechne die Hitbox des Players im nächsten frame, indem ich die bewegungsvariablen zu den koordinaten addiere, und überprüfe, ob sie sich mit einem anderen Entity oder einer Wand überschneidet. In der update Methode wird der Player dann nur bewegt, wenn die collisionDetection() false liefert.
Hier der entsprechende Code:


```
public boolean checkCollision(){
		
		Rectangle r1,r2;
		int xx = (int) x - Screen.offsetx;
		int yy = (int) y - Screen.offsety;
		int dyy = (int) dy;
		int dxx = (int) dx;

		r1 = new Rectangle(xx + dxx, yy+ dyy, 32 ,32+speed);
		r2 = new Rectangle(xx +dxx , yy + dyy+32 ,32, 32 + speed );
		
		//r1  upper half
		//r2  lower half
		
		for (int x = 0; x < 25; x++) {
			for (int y = 0; y < 18; y++) {
                                // visibleScreen beinhaltet alle Tiles, die sich auf dem Bildschirm befinden
				if ((World.visibleScreen[x][y].getBounds().intersects(r1) ||
						World.visibleScreen[x][y].getBounds().intersects(r2))
						&& World.visibleScreen[x][y].isSolid()) {
					return true;
				}
			}
		}
		
		for(Entity e: World.entities){
			
			if(r1.intersects(e.getUpperBounds())){
				//up up
				return true;
			}
			if(r2.intersects(e.getLowerBounds())){
				// low low
				return true;
			}
			
			if(r1.intersects(e.getLowerBounds())){
				// up low 
				if(yy <= e.getY())
				//	return false;
				return true;
			}
			if(r2.intersects(e.getUpperBounds())){
				//low up
				if(yy + 64 >= e.getY())
				//	return false;
				return true;
			}
			
		}
		
		
		return false;
		
	}
```

Außerdem will ich, dass die Entities sich passend überschneiden (Also wenn ich hinter einem gegner stehe, dass sein Oberkörper meine Beine verdeckt und umgekehrt). Ich sortier dazu die Entities nach y-Koordinate und zeichne sie dementsprechend. Das klappt auch soweit, nur wenn ich unter einem Gegner stehe und mich gerade nach oben bewege, wird der Gegner trotzdem über mir gemalt.

Hier der Code dazu:


```
public void drawEntities(Graphics g){

                // draw ist eine ArrayList vom Typ Entity
                draw.addAll(entities);
		draw.add(player);
		sort(draw);
		
		for(Entity e : draw){
			e.draw(g);
		}

		draw.clear();

}

private ArrayList<Entity> sort(ArrayList<Entity> entities){
		
		Collections.sort(entities, new Comparator<Entity>(){

			@Override
			public int compare(Entity e0, Entity e1) {
				if (e1.y < e0.y) return +1;
				if (e1.y >= e0.y) return -1;
				return 0;
			}
			
		});
		
		return entities;
		
	}
```

Findet ihr logische Fehler oder habt sonstige Verbesserungsvorschläge? Ein Problem, das ich bei diesem Code habe, ist dass ich so die Kollision der Entities nicht prüfe. Ich wollte den Code abwandeln und in die Entity Klasse einfügen.
Ich bin offen für alle Ideen, Ratschläge o.ä.. Ich sitze da jetzt schon so lang dran, dass ich den Überblick langsam verliere. Ich hab auch kein Problem damit, ein ganz neues Konzept zu übernehmen.

Vielen Dank im Vorraus!!


----------



## Marco13 (28. Mai 2012)

Abgesehen von dem 
if (e1.y >= e0.y) return -1;
was 
if (e1.y > e0.y) return -1;
sein sollte, erkennt man daran nicht so viel. Was genau erwartest du als Antwort?


----------



## Spacerat (28. Mai 2012)

Ein logischer fehler könnte sein, dass ein Rectangle nur zwei Dimensionen abdeckt und damit in denem Fall anscheinend nur X- und Z-Achse abdeckt (rein hypothetisch, hab deinen Code nur überflogen) und die Gegner deswegen über bzw. unter dir erscheinen können.
Verbesserungsvorschlag: Wie sieht's denn damit aus, nicht ständig alle BoundingBoxes (Rectangle) der Entities berechnen und sortieren zu müssen, sondern nur die, die aufgrund einer Überschneidung ihrer BoundingSphere dazu in betracht kommen? Denn erst wenn sich zwei Kugeln überschneiden, können sich auch darin befindliche Quader überschneiden, vorher jedoch nicht.


----------



## skappler (28. Mai 2012)

Marco13 hat gesagt.:


> Abgesehen von dem
> if (e1.y >= e0.y) return -1;
> was
> if (e1.y > e0.y) return -1;
> sein sollte, erkennt man daran nicht so viel. Was genau erwartest du als Antwort?



Das mit dem >= war nur eine Idee um ein Problem in den Griff zu kriegen, aber nicht weiter wichtig.
Als Antwort erwarte ich Tipps, Ideen, Vorschläge, alles was mich weiter bringt. Siehe eins unter dir.




> Ein logischer fehler könnte sein, dass ein Rectangle nur zwei Dimensionen abdeckt und damit in denem Fall anscheinend nur X- und Z-Achse abdeckt (rein hypothetisch, hab deinen Code nur überflogen) und die Gegner deswegen über bzw. unter dir erscheinen können.
> Verbesserungsvorschlag: Wie sieht's denn damit aus, nicht ständig alle BoundingBoxes (Rectangle) der Entities berechnen und sortieren zu müssen, sondern nur die, die aufgrund einer Überschneidung ihrer BoundingSphere dazu in betracht kommen? Denn erst wenn sich zwei Kugeln überschneiden, können sich auch darin befindliche Quader überschneiden, vorher jedoch nicht.



Das klingt zwar plausibel, würde es aber nicht die draw Methode um einiges verkomplizieren? Im moment habe ich ja einfach eine Liste, die sortiert wird und dann gezeichnet. Wenn ich nicht immer alle sortieren soll, bräuchte ich dann ja noch eine für die nicht zu Sortierenden und müsste diese vorher aussortieren. Klingt ziemlich verwirrend, vor allem dafür, dass nicht mal die normale collision klappt


----------



## Fu3L (28. Mai 2012)

Ich habs bei Delirium! so gelöst, dass ein Objekt einmal sein Sprite hat und einmal ein "baseRect". Sagen wir, wenn der Figur 50 hoch war, dann war das baseRect nur 20 hoch. So können 2 Figuren sich gegenseitig überdecken, wenn sie korrekt sortiert sind in der Zeichenreihenfolge. 

Bist du sicher, dass du dass nicht einfach falschrum sortierst? Du hast uns den Fehlerfall nur für den Gegner, der über dir ist, geschildert. (Also einmal bitte andersrum sortieren zum Test. Das am Code zu verifizieren fällt so früh schwer^^).
Ein Optimierungsvorschlag: Eine TreeMap nehmen, so wird nur beim Einfügen bzw. Höhenändern einer Figur etwas umsortiert und nicht jedes Mal die ganze Liste geprüft, wo sortiert werden muss. Aber das könnte geringfügig sein, deswegen erstmal zum Laufen kriegen^^

Zur Kollision:
Funktioniert denn die Kollision mit den Welträndern? Das lässt du vollkommen offen.
Zur Kollision der Entities untereinander könnten zum Beispiel brute force und wohl O(n^2) zwei for-Schleifen genommen werden, die beide über die EntityListe iterieren und immer untereinander prüfen. 
Sollte die KI aber von vornherein Kollisionen unter den Entities ausschließen, wäre natürlich nur Player gegen Entities  was auch mit einer Schleife ginge. Hier könnte die TreeMap wieder praktisch sein, weil man nur y-Werte in einem gewissen Intervall betrachten muss.

PS: Zu Delirium könntest du dir den Sourcecode angucken. Aber das ist an vielen Stellen einfach nicht schön, weils unter Zeitdruck und Müdigkeit entstand. (Allerdings ist es bei weitem nicht so zum schämen wie mein letzter Ludum Dare Beitrag, wo ich währenddessen krank war...)


----------



## skappler (28. Mai 2012)

Also die Sortierung stimmt. Hab ich getestet. Es funktioniert auch, außer ich bewege mich geradeaus hoch, wenn ich genau unter dem Gegner stehe. Keine Ahnung warum.
Ich hab ja auch sowas ähnliches wie du mit deinem BaseRect probiert. Jedes Entity hat ein Lower und ein UpperRect (siehe getUpperBounds() und getLowerBounds()). Die Fallunterscheidung klappt dann aber nicht richtig (Untere for Schleife im oberen Code).
Die Kollision mit den Wänden klappt reibungslos (hat mich auch schon EINIGE nerven gekostet). Ich denke daher, dass eben diese Fallunterscheidung Quatsch ist. Wie gesagt ich arbeite da jetz schon so lang dran, dass ich langsam den Überblick verliere und nurnoch sinnlos rumprobiere, deswegen auch der Thread hier. 

Um die KI hab ich mir noch keine gedanken gemacht. Ich wollte erstmal die Kollision zum laufen bringen und dann die KI einfach die Kollision benutzen lassen. Ich hab noch überhaupt keine Erfahrung mit KI, wenn es also einfacher ist das so zu regeln, dass die Gegner erst garnicht kollidieren werd ich das wahrscheinlich so machen, auch wenn ich nicht weiß wie 

Über solche Optimierungen wie die Tree-Map oder Laufzeitoptimierungen mach ich mir erst Gedanken wenn das System läuft. Hab ich bis jetzt bei allen Teilen des Spiels gemacht und bin mit der Methode ganz gut gefahren. 

Vielen Dank für deine ausführlihe Antwort!

EDIT: Ja hatte ich eh vor mir mal den Code anzusehn  Das mit dem unschönen Code aufgrund des Zeitdrucks kenn ich 
EDIT EDIT: Die Seite wo der Quellcode verlinkt ist, ist down =(


----------



## Spacerat (28. Mai 2012)

Also ich hätte Marcos Tip schon als hilfreich empfunden, schliesslich sprengst du mit deinem Konstrukt ja die CompareTo-Konvention.
Ich weis nicht, wie du deine BoundingBoxes erstellst, in 3D Umgebungen erwies es sich jedenfalls als hilfreich, wenn man diese bei der Übergabe der Vertices in einen VertexBuffer per Min-Max ermittelt - also innerhalb der draw-Methode. Der Durchmesser der BoundingSphere ist die Raumdiagonale der BoundingBox, ihr Radius demnach Raumdiagonale / 2. Der Mittelpunkt der BoundingSphere liegt auf halber Strecke der Raumdiagonalen. Ob nun eine Kollision mit anderen Objekten stattfindet kann man nun zunächst an einer simplen Rechnung festmachen: [c]Distanz Mittelpunkte - in Frage kommender Radien[/c]. Dazu benötigt man keine weitere Liste, ausser jene Spiel-Objekt-Liste, die man eh' schon hat. Ist der errechnete Wert [c]<= 0[/c] kommt es in den nächsten Augenblicken evtl. zu einer Kollision (bzw. hat schon eine stattgefunden wenn die BoundingBoxes der Objekte Ecke an Ecke stehen). Dann kann man die BoundinBoxes (oder besser gleich die ganzen Objekte, die Sphere und Box als Membervariablen mit sich führen) in eine Liste einfügen, über die man genauere Kollisionsuntersuchungen mit weitaus weniger Objekten und damit ebenso weitaus weniger Rechenaufwand anstellen kann. Da muss man nicht mal bei der Box aufhören, man kann auch noch feststellen ob eine Mesh-Kollision (2 Vertices verschiedener Objekte überschneiden sich) stattfindet.


----------



## skappler (28. Mai 2012)

Ich wusste nicht, dass das eine Konvention ist nur < und > zu verwenden. Habs schon wieder entfernt.
Ich verstehe schon, was du meinst. Das ganze ist bestimmt sinnvoll und effizienter, aber ich muss erstmal die Kollisionserkennung an sich vernünftig zum laufen bringen, bevor ich Laufzeitoptimierungen angehe


----------



## Spacerat (28. Mai 2012)

skappler hat gesagt.:


> Ich wusste nicht, dass das eine Konvention ist nur < und > zu verwenden. Habs schon wieder entfernt.


Nee, das hast du falsch verstanden. Nicht die Operationen sind entscheidend, sondern die Tatsache, dass du bei = nicht 0 zurück gegeben hast bzw. dieses wegen >= gar nicht konntest.


skappler hat gesagt.:


> Ich verstehe schon, was du meinst. Das ganze ist bestimmt sinnvoll und effizienter, aber ich muss erstmal die Kollisionserkennung an sich vernünftig zum laufen bringen, bevor ich Laufzeitoptimierungen angehe


Etwas vernünftig implementieren zu wollen ist meistens auch nicht verkehrtl. In diesem Fall aber würde anschliessende Optimierung grössten Teils neu bedeuten, es sei denn, du implementierst von vorne herein so, dass du eine Liste von Game-Objects an einen CollisionDetector übergibst.


----------



## skappler (28. Mai 2012)

Bei Gleichheit wird 0 zurückgegeben? Das stand nirgends wo ich das ganze System nachgelesen habe. Danke!

Ich habe das Ganze doch so implementiert, dass die Kollision eine Liste von Entities bekommt. Der Code oben ist halt nur für den Player mit allen andern Entities, aber wenn der erstmal läuft ist das ja ganz einfach zu modifizieren, um alle Entities untereinander zu überprüfen. Und DORT könnte ich dann das von dir vorgeschlagene System einbauen.
Aber zuerst muss ich das ganze an sich erstmal zum laufen bringen 

EDIT: Natürlich wird bei gleichheit 0 zurück gegeben -.- Steht ja auch so dort  total übersehn


----------



## Fu3L (28. Mai 2012)

http://arkaryx.net/ld22/src.zip

Da liegt die Source Datei, wenn du's spielen willst, einfach das src.zip wegmachen.


----------



## skappler (28. Mai 2012)

Fu3L hat gesagt.:


> http://arkaryx.net/ld22/src.zip
> 
> Da liegt die Source Datei, wenn du's spielen willst, einfach das src.zip wegmachen.



Vielen Dank! Ich werds mal durcharbeiten und sehen was sich draus machen lässt.


----------

