Wie bekomme ich eine Kollisionsbehandlung hin?

Hi Leute :) Ich bin dabei ein kleines Jump&Run in Java zu programmieren und bin nun schon seit geraumer Zeit an der Kollisionsauflösung hängengeblieben. Die Erkennung von Kollisionen habe ich bereits gelöst. Ich habe nun schon das halbe Internet abgesucht, bin aber nicht schlauer geworden. Könnt ihr mir helfen? Ich habe bisher eine HALBWEGS funktionierende Kollisionserkennung hinbekommen.

Gegeben sind mir: -Position des Spielers(px, py), -Größe des Spielers(playerSize), -Pos. der Hitbox(bx, by), -Seitenlänge der Hitbox(boxSize), -Bewegungsrichtung des Spielers(movex, movey), -Zielposition des Spielers ohne Einbezug der Kollision(destx, desty), -Geschwindigkeit des Spielers(vel) --- alles vom Typ "int"

Das Problem: so wie ich das gelöst habe ist die Auflösung fehlerhaft. Wenn ich geradewegs auf die Hitbox zukomme mit einer Geschwindigkeit von z.B. 5 Pixel pro Frame und ich rage bei der Kollision so in die Hitbox hinein, dass der x-Anteil größer ist als der y-Anteil, dann wird es nach y aufgelöst.

Ich wollte in jedem Schleifendurchlauf die Kollision mit allen überlappenden Tiles so auflösen: Mein bisheriger Code:

if(intersect(...)){ //wenn die Kollision mit der aktuellen Box feststeht
int tilex = bx
int tiley = by
                    
int yover = desty + playerSize - by;        //positiv wenn überlappung
int yunder = by + boxSize - desty;      //positiv wenn überlappung
int xleft = xdest + playerSize - bx;        //positiv wenn überlappung
int xright = bx + boxSize- destx;       //positiv wenn überlappung
                    
boolean left = false, right = false, top = false, bottom = false;  

//Überragt der Spieler die obere, untere, linke oder Rechte Seite der Box 
                    
if(desty < by) top = true;
if(desty + playerSize > by + boxSize) bottom = true;
if(destx < bx) left = true;
if(destx + playerSize > bx + boxSize) right = true;
                    
if(top && !right && !left) desty = by - playerSize;
if(bottom && !right && !left) desty = by + boxSize;
if(left && !top && !bottom) destx = bx - playerSize;
if(right && !top && !bottom) destx = bx + boxSize;
                    
if(top && right){
    if(yover < xright) desty = by - playerSize;
    if(yover > xright) destx = tilex + boxSize;
}
if(top && left){
    if(yover < xleft) desty = by - playerSize;
    if(yover > xleft) destx = bx - playerSize;
}
if(bottom && left){
    if(yunder < xleft) desty = by + boxSize;
    if(yunder > xleft) destx = bx - playerSize;
}
if(bottom && right){
    if(yunder < xright) desty = by + boxSize;
    if(yunder > xright) destx = bx + boxSize;
}
}

Meine Frage ist nun: Wie bekomme ich so eine realistische und genaue Kollisionsbehandlung hin (mit destx und desty als Zielpositionen)? Es geht mir dabei nicht um einwandfreies Java, es zählt nur die Logik dahinter (von mir aus auch Pseudo-code).

Vielen Dank im Voraus :)

Answer 1

[phigeek]

Hallo

Das ist eine spannende Frage, die ich selbst auch noch nie im Detail gelöst habe, dennoch habe ich schon starke Vereinfachungen dieser Problematik umgesetzt. Vielleicht helfen Dir einige Überlegungen, die ich selbst auch angestellt hatte. Dein Problem wird damit aber noch nicht gelöst, dazu fehlen einige Infos.

Die Collision Detection, also die Kollisiosnerkennung hast Du bereits gelöst.

Nun hast Du den Exakten Zusammenstoß-Zeitpunkt berechnet (liegt typischrweise zwischen den Frame-Steps; will sagen: Wenn Du alle 1/10 Sekunden eine Collision-Detect ausführst, könnte es ja sein, dass zwei Objekte sich nur gerade dazwischen berühren würden (also weder vorher, noch nachher). Daher gibt es diesen Zeitpunkt zwischen den Frames, wo sich die Oberflächen gerade berühren.)

Aus Deinem Modell gehe ich davon aus, dass Deine Objekte flach sind (eine Z-Achse kommt nicht vor). Das vereinfacht die Realität natürlich sehr. So wie kleine Plättchen, die auf einem Luftkissenbot schweben, ohne Schwerkraft?

Nun geht es an die "Collision response". Schau mal hier:

https://en.wikipedia.org/wiki/Collision_response

Hier spielen Reibung und Drall der Objekte auch eine Rolle. Bei elastischen Stößen bleibt der Gesamtimpuls (Masse * Geschwindigkeit) immer konstant. Ebenso erhält sich der gesamte Drehimpuls. Also die Massen der einzelnen Objekte ist hier ganz wichtig, dieses sehe ich aber in Deinem Code nicht.

Ebenso anzuschauen ist die Reibung zwischen den Objekten. Fällt eine Seife auf den Boden, wird sie im wesentlichen (unelastisch, ohne Reibung) einfach wegrutschen, wohiengegen ein Jonglierball einfach liegenbleibt. Ein Gummiball, wird wie eine Billardkugel zurückgeworfen. Gut illustriert sind die vielen Fälle auch hier: https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects leider nur die Detection, und die hast Du ja schon.

Wenn man nun weiß, welche Kollisionsauflösung Du genau haben willst, und wie weit Du gehen willst, ist die Suche nach dem Algorithmus im Internet auch etwas einfacher. Am einfachsten ist der voll elastische Stoß.

• Behandelst Du nur Rechtecke?
• Behandelst Du auch Konkave Formen?
• Ist die Reibung zu vernachlässigen?
• Drehen sich die Objekte vor und nach dem Stoß?
• Benötigst Du eine Schwerkraft?
• ...

Vielleicht kann ich noch weiter helfen, wenn ich weitere Infos dazu habe.

Comments

[linkman13]

Also ich habe erstmal nicht vor eine physikalisch einwandfreie Kollisionsbehandlung zu simulieren. Ich hatte fürs erste nur vor die Kollisionsauflösung mit zwei Rechtecken so zu gestalten, dass sie nicht mehr überlappen und ich sie wie in Jump&Run´s wie Mario oder Supertux, ect ... weiter bewegen kann. Reibung und Trägheit und so sollten erstmal keine Rolle spielen.

Danke erstmal für deine ausführliche Antwort ;)

Answer 2

[Borgler94]

angenommen der spieler und die box sind mit dem punkt links oben + breite + höhe angegeben

if( (sp.x+sp.w)  >=  b.x  && sp.x<=(b.x+b.w) && 
(sp.y+sp.h)  >=   b.y  && sp.y<=(b.y+b.h) )   {
//collision
}

Comments

[linkman13]

Danke für deine Bemühungen, aber für die KollisionsERKENNUNG habe ich schon eine passende Lösung. Das was ich brauche ist eine KollisionsAUFLÖSUNG.

Answer 3

[KnusperPudding]

Mit Kollisionsauflösung meinst du wohl das Ereignis was passiert, wenn du 'getroffen wirst'.

Nur um mal dein Beispiel zu verstehen:

Ich stelle mir jetzt mal einen Space-Shooter, grob wie SpaceInvaders vor. 

Du selbst hast eine Hitbox von sagen wir mal Beispielhaft: 3x3.

 ___________
| 1 | 2 | 3 |
|___________|
| 4 | 5 | 6 |
|___________|
| 7 | 8 | 9 |
|___________|

Wirst du bei 6 getroffen, willst du, dass sich dieser Teil auflöst?

 ___________
| 1 | 2 | 3 |
|___________|
| 4 | 5 |
|___________
| 7 | 8 | 9 |
|___________|

Nutze die 'Vorteile' die Java als Objektorientierte Orientierte Programmiersprache zu bieten hat:

Erstelle dir eine Klasse was die Aufgabe übernehmen soll:

class CollisionDetector {

   private CollidableElement element;
   private Element obstacle;
   private CollisionBound[] collisionBounds;

   public CollisionDetector(CollidableElement element, Element obstacle ) {
   this.element = element;
    this.obstacle = obstacle;
   checkCollision();
 }

   private void checkCollision();

   public boolean isCollided(){...};

   public CollisionBound[] getCollisions() { ... }
}

Eine Klasse, in der du ausschließlich die Kollision behandelst: Du gibst dein Element, das ich jetzt als CollidableElement betitelt habe hinein, führst dort die Prüfung durch, ob es eine Kollision gab (oder nicht) und stellst diese Information dann nach außen hin bereit via: isCollided();

Während deiner Prüfung, ob eine Kollision statt gefunden hat, gehst du ja sicherlich die einzelnen Punkte durch: Zwischen deinem Element, was 'schaden nehmen' kann und dem Gegenstand, der den Schaden 'verursacht'. Entsprechend wird es also irgendwann eine 'Schnittmenge' geben.

Diese Schnittmenge Kannst du in einem einfachen Objekt, was ich hier bei dem Beispiel als CollisionBound betitelt habe, speichern. Hierbei gehe ich davon aus, dass die Klasse CollisionBound zwei Eigenschaften hat: int x,y;

Entsprechend stellst du bei deiner Kollision im oberen Beispiel fest: An Koordinate: x = 3, y= 2  (Sichtbare Zelle: 6) hast du eine Kollision. Diese Information kannst du über getCollisions() abgreifen und entsprechend drauf reagieren: in dem du diese Zellen entsprechend 'entfernst' oder rot färbst. Hierbei gehe ich davon aus, dass du eine Methode in deiner Klasse hast, die ich jetzt mal als "damage" bezeichne.

CollidableElement spaceship = ...;
Element obstacle = ....

Collisiondetector detector = new CollisionDetector(spaceship, obstacle);

if (detector.isCollided()) {
   for (CollisionBound bound : detector.getCollisions()) {
    int damageCoordinateX = bound.getX();
    int damageCoordinateY = bound.getY();
    spaceship.damage(damageCoordinateX, damageCoordinateY);
 }
}

Comments

[linkman13]

Ich bedanke mich für deine Bemühungen, aber das habe ich leider nicht damit gemeint. Mein Anliegen ist einfach nur ein Algorithmus, der mir die Koordinaten von dem Objekt liefert, nach der Kollisionsbehandlung. Also so, dass ich (das Objekt) auf Blöcken laufen kann, ohne durch sie hindurchzufallen/-laufen - also dass ich mein Objekt auf eine Mauer zulaufen lassen kann, ohne dass es weiterläuft - also, dass sich Objekt und Box nicht überlappen. Wie wenn man in Super Mario gegen eine Wand springt/läuft und nicht weiterkommt. Das ist es, was ich nicht verstehe, wie ich das anstellen soll. Nur die grundlegenden Physics :), die jedes Jump&Run benötigt.

[KnusperPudding]

@linkman13

Aber auch genau dieses Prinzip lässt sich auch hierüber umsetzen. Nur dass es kein Spaceship sondern ein Mario und eine Pipe wäre.

if (detector.isCollided()) {
   for (CollisionBound bound : detector.getCollisions()) {
    int damageCoordinateX = bound.getX();
    int damageCoordinateY = bound.getY();
 ....
 }

an dieser Stelle: Du prüfst ob eine Kollision statt findet und hast als Information: Die

Schnittmengen-Koordinaten

.

Mit: 

CollidableObject mario = ....;

würdest du ja sicherlich seine Hitbox abgreifen können.

Bei deiner Hitbox hättest du zwei X Koordinaten: min und max (für Links und rechts).

int marioLeft = mario.getHitboxPosition().getMinX();
int marioRight = mario.getHitboxPosition().getMaxX();

Durch Subtrahieren der Absoluten Werte kannst du relativ schnell feststellen, von welcher Seite die Kollision statt gefunden hat:

if (Math.abs(marioLeft) - Math.abs(bound.getX()) <  (Math.abs(marioRight) - Math.abs(bound.getX())

somit erhälst du die Distanz von der Linken und der rechten Seite der Hitbox zur Kollisions-Koordinaten. Auf der Seite auf der der Abstand geringer ist, ist die Kollision.

Mit dieser Information kannst du dann jedenfalls auf die Kollision reagieren, wie: Im Falle der Kollision rechts, die Figur um ein Pixel nach Links verschieben.