Kollisionsabfrage

[Nova]

Hallo,

Ich programmiere gerade ein 2D Spiel.
Bisher hab ich ein 2-Dimensionales Array genommen und dort alles gespeichert:
0: frei
1: Landschaft
1000: Flugzeug 1
2000: FLugzeug 2
1xxx: Geschosse etc. von Flugzeug 1
2xxx: Geschosse etc. von Flugzeug 2

So konnte ich auch wunderbar eine Kollisionserkennung machen, einfach Pixelweise abgefragt ob an einer bestimmten Stelle etwas ist und dementsprechend was es ist reagiert.

Die Flugzeuge, Landschaft etc. existierten auch nur als Sammlung von Koordinaten, sprich jedes Pixel wurde einzeln gezeichent.
Leider wird das langsam zu rechenintensiv, vor allem das Zeichnen der einzelnen Pixel kostet viel Zeit.

Ich habe sowohl hier im Forum als auch in einigen Tutorials gelesen das in der Regel Bilder verwendet werden und dann mit getBounds() und intersects() geprüft wird ob es Überschneidungen gibt.
Bilder würde mir auch besser gefallen, jedes einzelne Pixel zu erstellen wird mit der Zeit echt nervig und sieht nicht so gut aus wie ein Bild.
Flugzeuge, Geschosse und vor allem die Landschaft sind aber nunmal nicht rechteckig, d.h. diese Art von Kollisionserkennung ist viel zu ungenau.

Ich habe schon ein paarmal gelesen das man die Pixel des Bildes einzeln vergleichen kann und nur wenn 2 nicht-transparente Pixel überlappen ist es eine Kollision. Wie das funktioniert hab ich aber noch nicht gesehen und ich denke das dürfte auch sehr rechenintensiv sein, oder?
Zumindest bräuchte ich ein Rectangle das die Fläche der Überschneidung entspricht damit ich mich auf einen Teil der Pixel beschränken kann, vielleicht könnte man auch nur 3x3 Blocks aus Pixeln vergleichen oder so?!?


Lange Rede kurzer Sinn:
Wie bekomme ich eine vernünftige Kollisionserkennung (so auf 3-5 Pixel genau sollte es schon sein) hin die nicht zu rechenintensiv ist?



mfg
Nova

 

[0xdeadbeef]

Da gibt es verschiedene Ansätze.

Wenn Du pixelgenaue Kollisionsabfrage brauchst, dann prüfe halt zuerst, ob die Rechtecke sich überschneiden, bzw. ob ein Schuß (wenn der nur einen Pixel groß ist) in einem Flugzeug-Rechteck liegt. Falls dem so ist, kannst Du immer noch pixelgenau prüfen. Dazu brauchst Du auch kein bildschirmgroßes Array, sondern nur Arrays für alle Objekte (Flugzeuge usw). Außerdem muß nur in dem Rechteck geprüft werden, das der Schnittbereich der beiden Rechtecke ist.

Viele Spiele machen das aber viel billiger ohne pixelgenaue Abfrage: sie benutzen einfach ein Rechteck, daß in den meisten Fällen den Großteil des Sprites abdeckt. Ist zwar nicht 100% genau, reicht aber in vielen Fällen völlig.

Falls ein einfaches, nicht rotiertes Rechteck nicht reicht, könntest Du auch mit rotierten Rechtecken bzw. Polygonen arbeiten. Dann wird es allerdings ein wenig komplizierter.

 

[Nova]

Danke, das bringt mich schonmal weiter.

Also Pixelgenau muss es nicht sein, es sollte halt ungefähr passen, halt so das man im Normalfall nicht merkt das z.B. der Schuss eigentlich daneben gegangen wäre.
Die Geschosse bestehen aus mehr als 1 Pixel, so ca.10-100 Pixel je nach Typ des Geschosses.

Ein Problem ist auch das z.B. das Flugzeug sich in 360 Schritten drehen kann, sprich das Bild müsste ggf. auf dem Bildschirm gedreht dargestellt werden. Dazu gibt es zwar eine Graphics2d Methode die aber viel Rechenzeit beansprucht (zumindest bei meinen Versuchen war das viel zu lahm für ein flüssiges Spiel), außerdem kann ein Rechteck ja nicht "schief" liegen, zumindest hab ich keine entsprechenden Winkelangaben oder so in der Javadoc gefunden, wa liefert getBounds() denn dann überhaupt für ein Rechteck?
Oder sollte man aus dem einen Bild gleich beim Programmstart die 359 anderen Bilder berechnen und abspeichern, sodass man dann immer das entsprechende Bild nimmt ohne nochmal rotieren zu müssen? (vielleicht könnte man es auch auf 180 bilder beschränken, so groß sind die Unterschiede ja nicht bei 1°)
Ich hab das bei meiner "Pixelsammlung" auch so gemacht, beim Programmstart wurden aus der einen "Darstellung" die 359 anderen berechnet und in einem Array gespeichert => es muss im Programm nix mehr berechnet werden weil alle möglichen Darstellungen schon beim Start berechnet wurden.
Vielleicht könnte man sich auch in einer Liste oder so zu jeder Darstellung merken welche Pixel nicht transparent sind um so noch schneller auf Kollision testen zu können?
Oder ist das alles viel zu kompliziert gedacht und es geht auch viel einfacher?

Die kollisionserkennung Flugzeug/Flugzeug bzw. Geschoss/Flugzeug wäre damit wohl machbar, aber ine Frage ist auch wie ich das bei der Landschaft machen soll? Das wäre dann ja im Prinzip 1 Bild das den ganzen Bildschirm bedeckt (bzw. das "Spielfeld" ist mehrere Bildschirme groß, d.h. mit scrollen)...
Da hätte ich ja dann immer 100% Überlappung, sprich es müsste immer jedes Pixel verglichen werden...
Ich könnte mir natürlich beim Programmstart wieder in einem rießen 2-Dimensionalen Array alle Positionen von Pixeln merken die nicht transparent sind, und dann wie bisher immer vergleichen... Gut, wäre immer noch besser als bisher, weil ja immer ganze Bilder statt einzelner Pixel gezeichnet werden, sprich das zeichnen ginge schneller, aber die Kollisionserkennung zur Landschaft wäre immer noch genau wie bisher...


Polygone hab ich mir auch schonmal angeschaut, aber ich hab keinen Plan wie ich an so ein Polygon komme, und eine Methode die Überschneidung zwischen 2 Polygonen testet hab ich auch nicht gefunden in der Javadoc...


Ich bin eigentlich nicht so der Graphikfreak, mir geht es mehr um die Physik und KI, es muss nicht alles graphisch 100% perfekt sein, aber die Kollisionserkennung sollte schon brauchbar sein.


mfg
Nova

 

[Nick H.]

das mit den Polygonen kostet aber auch sicher viel rechenzeit
ich halte die Idee pixelgenau zu prüfen, falls sich die Rechtecke überschneiden besser
dann kannst du dir auch überlegen bei welchen du das nun brauchst und bei welchen du doch normale Rechtecke nehmen kannst
und dann kannste das ganze noch in mehrere große Rechtecke einteilen, damit immer nur die in einem Rechteck untereinander geprüft werden müssen
und nicht alle Objekte im ganzen Spiel, damit sparste auch ne Menge

die einzelnen Bilder ürde ich gar nicht im Spiel drehen, sondern direkt gedreht speichern
dann kannst du auch die Qualität höher machen
aber alle 360° zu nehmen halte ich für sinnlos
40 oder so sind eigentlich je nach größe schon zu viel

 

[Lim_Dul]

Wenn Rechtecke zu ungenau sind, kann man sich auch überlegen, ob sich alle Objekte durch einen Kreis darstellen lassen. Dann muss man nur den Abstand der Mittlelpunkte der jeweiligen Kreise vergleichen.

Das ganze hakt aber, wenn man eine Kollisionsabfrage zwischen Rechteck & Kreis hat, das ist dann wieder Arbeit. Wenn man das aber ausschliessen kann, dann gingen Kreise. Da hat man mit Objektdrehungen keine Probleme.

 

[Nick H.]

Kreise sind auch oft gut
man kann ein Objekt aus mehreren Rechtecken zusammensetzen
dann kann mans schon genauer machen und muss nicht gleich alles auf den Pixel machen

 

[Nova]

Hier mal ein Screenshot:
Bild1

Man sieht das Spiel im Splitscreen-Modus, die Flak schießt die gelben "Geschosse" ab, die roten Striche Geschosse aus einem Maschinengewehr sein. Die Landschaft beschränkt sich momentan noch auf den grauen "Boden" unten.
Ein Flugzeug besteht aus 135 Pixeln, die Geschosse aus 6 bzw. 35 Pixeln.
Das läuft auch so weit auf einem Athlon 2500+ mit >30 Bildern pro Sekunde, wenn aber die KI viel arbeiten muss und viele Schüsse auf dem Bild sind ruckelts manchmal schon (ca.15 fps).

Dadurch das man von der Seite draufschaut ist das Flugzeug recht länglich, sodass auch ein Kreis nicht ausreicht, auch wenn ein Schuss eine Flugzeughöhe unter dem Flugzeug vorbeigehen müsste gäbe es eine Kollision...
Mit mehreren Rechtecken oder Kreisen für jedes Objekt gibts auch Probleme, nämlich mit der Flugrichtung, da müsste ich ja auch die Rechtecke drehen (was wohl nicht geht?!?) bzw. für jede Flugrichtung den realtiven Mittelpunkt der Kreise neu berechnen. Hat auch den Nachteil das ich für jedes neue "Objekt" neue Rechtecke/Kreise von Hand festlegen muss.

Da Kollisionen Flugzeug/Flugzeug bzw. Geschoss/Flugzeug aber vergleichsweise selten vorkommen würde das wohl schon gehen mit dem Pixelweise vergleichen. Momentan ist ja auch nicht die Kollisionserkennung das Problem obwohl ich IMMER bei JEDEM Objekt prüfe ob es eine Kollision gibt bzw. bei beweglichen Objekten auch ständig etliche Pixelpositinen verändern muss, sondern eher das zeichnen jedes einzelnen Pixels (es ist schon ein gewaltiger Unterschied ob ich z.B. ein 400x400 Pixel Rechteck komplett mit drawRect() zeichne oder jedes einzelne Pixel ersteres geht in 1ms oder so, letzteres geht schon fast in den Sekundenbereich...), so müsste ich ja nur selten überhaupt vergleichen und wenn dann nur im Überlappungsbereich, sollte also kein Problem sein.
Ich könnte auch einfach andere Bilder nehmen wenn später weitere Flugzeugmodelle, Geschosse etc. hinzukommen sollten und es würde funktionieren ohne das ich irgendwas am Programm ändern müsste, einfach Bilder austauschen/hinzufügen und fertig. Man könnte vielleicht auch noch einen "Weichspüler" drüberlaufen lassen damit man die Treppcheneffekte nicht mehr so sieht...
Würde mir eigentlich schon recht gut gefallen wenn das so funktionieren würde.
Das Problem ist aber die Landschaft, da diese ja dann praktisch ein riesiges Bild wäre wo sich alles drauf abspielt => man hätte immer 100% Überlappung zwischen Landschaft und allen anderen Objekten, sprich es müsste immer jedes Pixel verglichen werden, oder ???:L
Oder sollte man einen kompromiss eingehen und zumindest für die Landschaft von Hand Rechtecke festlegen ???:L


mfg
Nova