Clanintern Clanintern Clanintern

Forum

Öffentliche Foren
ZURÜCK
FORUM: Spiele & Computer THEMA: Collision Detection
AUTOR BEITRAG
Crush (White & Nerdy)

RANG Deckschrubber

#1 - 24.02 16:32

Ich arbeite zur Zeit an einem MMO Spieleprojekt mit. Wir haben zur Zeit ein kleines Problem mit der Kollisionsberechnung. Wir haben in einer zweidimensionalen Spielwelt (pixelgenau berechnet) Objekte mit verschieden großen kreisrunden Trefferzone (definiert als Mittelpunkt und Radius) und wollen ermitteln ob diese Trefferzone sich zum Teil in Kreissegmenten (definiert als Mittelpunkt, Radius, Anfangswinkel, Endwinkel) befindet. Das Ganze sollte relativ schnell berechnet werden, da das Ganze serverseitig abläuft (Zur Not könnten wir das Kreissegment auch durch ein gleichschenkliges Dreieck approximieren).

Gibt es hier jemanden mit Geometriekenntnissen, der mir ein paar Tipps geben kann, wie ich das am Besten angehe?

Programmiersprache ist übrigens C++.
falcon][bac

RANG Deckschrubber

#2 - 25.02 00:29

Kann leider keine Komplettlösung geben. Erst mal testen, ob ich das Aussehen der Objekte richtig verstanden hab. so? http://i19.tinypic.com/4c9nnsk.png

Wenn ja, mein erster Ansatz wäre, das ganze in zwei Schritten zu berechnen.
1. Schritt: über das Kreissegment ein Viereck legen, dieses Viereck um den Radius des Kreises vergrößern und Prüfen, ob der Mittelpunkt in dieses Viereck fällt. (so wie im Bild)
dann reicht eine Prüfung wir im Bild angegeben. Je nachdem, ob Du Kollisionen eher horizontal oder Vertikal erwartet, kannst Du die Gleichung so umstellen, dass gemäß lazy evaluation die Auswertung möglich früh abgebrochen werden kann.

2. Schritt Erst wenn diese Probe positiv ist, sollte dann eine genaue Auswertung folgen. Da müsstens zu mal ein paar Tests machen, wie hoch die Wahrscheinlichkeit sein darf, damit sich dieser vorgelagerte Schritt lohnt, oder ab wann es zusätzliche Rechenleistung fordert.

Evtl.Hilft Dir diese Seite weiter: http://www.harveycartel.org/metanet/tutorials/tutorialA.html
In bild 6 wird die Kollision von Viereck auf Kreissegment gezeigt. Sollte leicht auf Kreis anpassbar sein.
Crush (White & Nerdy)

RANG Deckschrubber

#3 - 25.02 14:23

Danke, ich hab das Problem mitlerweile selbst gelöst. Hier die Funktion:

PHP-code:
<?php 
#include <cmath.h>

bool
Collision::circleWithCirclesegment( Point circlePos, int circleRadius,
                                    int segRadius, Point segPos, float segAngle, float segSize)
{
    float targetAngle;

    //calculate distance
    int distX = circlePos.x - segPos.x;
    int distY = circlePos.y - segPos.y;
    float dist = sqrt(distX * distX + distY * distY);

    //if out of range we can't hit it
    if (dist > segRadius + circleRadius) {
        return false;
    }
    //if we are standing in it we hit it in any case
    if (dist < circleRadius) {
        return true;
    }

    //calculate target angle
    if (distX > 0)
    {
        targetAngle = asin(-distY / dist);
    } else {
        if (distY < 0)
        {
            targetAngle = M_PI - asin(-distY / dist);
        } else {
            targetAngle = -M_PI - asin(-distY / dist);
        }

    }

    //Add hit circle
    segSize += asin(circleRadius/dist) * 2;

    //calculate difference from segment angle
    float targetDiff = fabs(targetAngle - segAngle);
    if (targetDiff > M_PI)
    {
        targetDiff = fabs(targetDiff - M_PI * 2);
    }

    return (targetDiff < segSize / 2.0f);
}

 ?>


Das Ganze funktioniert folgendermaßen.

Erstmal wird die Distanz berechnet und geschaut ob der Kreis überhaupt in Reichweite ist.

Dann wird der Winkel berechnet, in dem sich das Kreiszentrum zum Mittelpunkt des Kreissegments befindet und der Winkel zwischen diesem Winkel und dem Winkel Kreissegmentzentrum zum Rand des Kreises.

Ist der Unterschied zwischen Winkel zum Kreis und Winkel des Kreissegments kleiner als die halbe Breite des Kreissegments plus Winkel zwischen Kreiszentrum und Kreisrand, dann schneidet der Kreis das Kreissegment.

Das Ganze ist zwar nicht 100% korrekt an den äußeren Ecken des Kreissegments aber das lässt sich in unserem Fall verschmerzen.
Crush (White & Nerdy)

RANG Deckschrubber

#4 - 28.02 00:01

Ein Anderer aus unserem Projekt hat übrigens folgenden Gegenvorschlag gemacht:
http://wiki.themanaworld.org/index.php/Collision_determination

Das Ganze ist zwar wesentlich komplizierter, dafür können aber die Prozessorzeit aufsaugenden trigonometrischen Berechnungen fast alle gecached werden.
Weasel

RANG Ober0wn3r

#5 - 05.04 18:02

Bei zeitkritischen Sachen würde ich die trigonometrischen Berechnungen sowieso durch vorberechnete Tabellen ersetzen.

Die sqrt kannst du evtl. ersetzen, indem du mit dem Quadrat der Distanz weiterrechnest. Quadrieren sollte schneller sein wie Wurzel ziehen.
ZURÜCK