Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Werbeanzeige

shadowstrike

Frischling

  • »shadowstrike« ist der Autor dieses Themas

Beiträge: 24

Wohnort: Wiesbaden

Beruf: Schüler

  • Private Nachricht senden

1

20.12.2010, 20:34

Kollisionserkennung mit der SFML und rotierten Sprites

Hi,

ich sitz grad an einem Algorithmus für Pixelgenaue Kollisionserkennung mit der SFML.
Ich hab mir das Problem in 3 kleinere Funktionen eingeteilt. Die erste prüft, ob überhaupt
eine Bounding-Rect-Kollision stattfindet. Die 2. berechnet dann, aus welcher Richtung
Sprite b mit Sprite a kollidiert. In Funktion 3 wird dann zu Beginn das Rechteck berechnet,
an dem sich die Sprites überschneiden und als letztes wird für jedes Pixel in diesem Rechteck
für beide Sprites der Alpha-Wert geprüft. Sind beide Alphawerte größer als 0, kollidieren
die Sprites. Soweit die Theorie. In der Praxis sieht das ganze dann so aus (Zur Namensgebung:
Das ganze wird für ein Framework entwickelt für mein Entwicklerteam namens Evil Industries):

EvilCollision.hpp

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef EVILCOLLISION_HPP
#define EVILCOLLISION_HPP
//*********************************************************************
//Headerdateien einbinden
#include <SFML\Graphics.hpp>
//*********************************************************************
//Namespace ef (Evil Framework)
namespace ef
{
    //Richtung der Kollision
    enum E_COLLISION_DIRECTION { COLLISION_UPLEFT = 0x00000000,
                                COLLISION_UPRIGHT = 0x00000001,
                                COLLISION_DOWNLEFT = 0x00000010,
                                COLLISION_DOWNRIGHT = 0x00000011,
                                COLLISION_NONE = 0x11111111 };
    //Berechnung der BoundingRect-Kollision
    bool getCollisionRect(sf::Sprite, sf::Sprite);
    //Berechnung der Richtung
    E_COLLISION_DIRECTION getCollisionDirection(sf::Sprite, sf::Sprite);
    //Berechnung der Pixelgenauen Kollision
    bool getCollisionPixel(sf::Sprite, sf::Sprite);
}
#endif


und hier noch die dazugehörige cpp:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include "EvilCollision.hpp"
//-----------------------------------------------------------
//Kollisionsberechnungen
//-----------------------------------------------------------
bool ef::getCollisionRect(sf::Sprite target1, sf::Sprite target2)
{
    return  (target1.GetPosition().x < target2.GetPosition().x + target2.GetSize().x &&
        target1.GetPosition().x + target1.GetSize().x > target2.GetPosition().x &&
        target1.GetPosition().y < target2.GetPosition().y + target2.GetSize().y &&
        target1.GetPosition().y + target1.GetSize().y > target2.GetPosition().y);
}
//***********************************************************
ef::E_COLLISION_DIRECTION ef::getCollisionDirection(sf::Sprite target1, sf::Sprite target2)
{
    //Tritt keine Kollision auf, COLLISION_NONE zurückgeben
    if(!getCollisionRect(target1, target2))
        return COLLISION_NONE;
    //Die Richtung berechnen
    int Direction = 0x00000000;
    if(target1.GetPosition().x < target2.GetPosition().x)
        Direction |= 0x00000001;
    if(target1.GetPosition().y < target2.GetPosition().y)
        Direction |= 0x00000010;
    return (ef::E_COLLISION_DIRECTION)Direction;
}
//***********************************************************
bool ef::getCollisionPixel(sf::Sprite target1, sf::Sprite target2)
{
    E_COLLISION_DIRECTION CollisionDir = getCollisionDirection(target1, target2);
    if(CollisionDir != COLLISION_NONE)
    {

        //Positionsangaben für das zu testende Rechteck (Nur das Rechteck, in dem sich die Sprites überschneiden, wird getestet)
        float spx, spy, epx, epy;

        //Positionsangaben innerhalb der Sprites
        float t1x, t1y, t2x, t2y;

        //Je nach Richtung das zu testende Rechteck berechnen
        switch(CollisionDir)
        {
        case COLLISION_UPLEFT:
            spx = target1.GetPosition().x;
            spy = target1.GetPosition().y;
            epx = target2.GetPosition().x + target2.GetSize().x;
            epy = target2.GetPosition().y + target2.GetSize().y;
            break;
        case COLLISION_DOWNLEFT:
            spx = target1.GetPosition().x;
            spy = target2.GetPosition().y;
            epx = target2.GetPosition().x + target2.GetSize().x;
            epy = target1.GetPosition().y + target1.GetSize().y;
            break;
        case COLLISION_UPRIGHT:
            spx = target2.GetPosition().x;
            spy = target1.GetPosition().y;
            epx = target1.GetPosition().x + target1.GetSize().x;
            epy = target2.GetPosition().y + target2.GetSize().y;
            break;
        case COLLISION_DOWNRIGHT:
            spx = target2.GetPosition().x;
            spy = target2.GetPosition().y;
            epx = target1.GetPosition().x + target1.GetSize().x;
            epy = target1.GetPosition().y + target1.GetSize().y;
            break;
        }

        //Alle entsprechenden Pixel Testen
        for(float y = spy; y <= epy; y++)
        {
            for(float x = spx; x <= epx; x++)
            {
                //Spriteinterne Positionen berechnen
                t1x = target1.TransformToLocal(sf::Vector2f(x, y)).x;
                t1y = target1.TransformToLocal(sf::Vector2f(x, y)).y;
                t2x = target2.TransformToLocal(sf::Vector2f(x, y)).x;
                t2y = target2.TransformToLocal(sf::Vector2f(x, y)).y;

                //Kollision anhand des Alphawertes an den entsprechenden Stellen testen
                //Sind beide Alphawerte größer als 0, tritt eine Kollision auf

                float a1 = target1.GetPixel(t1x, t1y).a;
                float a2 = target2.GetPixel(t2x, t2y).a;

                if(a1 > 0 &&
                    a2 > 0)
                    return true;
            }
        }

    }
    return false;
}


So. Die ersten Tests hat der Algorithmus auch Problemlos überstanden, mit
subrects, skalierungen, invertierungen um die x oder y achse waren alles kein Problem.
Schwierig wird es jetz mit der Rotation. Wenn ich mindestens ein Rotiertes Sprite an die
Funktion übergebe, hagelt es in der Konsole Meldungen, dass auf bestimmte Pixel nicht
zugegriffen werden kann und die Framerate sackt von (auf meinem Laptop zumindest,
der is in sachen graphik generell ziemlich langsam) 300 auf 0,7 ab. Nachdem ich mit
unterschiedlichsten Berechnungen, TransformToGlobal und TransformToLocal in den
wildesten Variationen herumexperimentiert habe, gehen mir langsam die Ideen aus.
Ich habe hier im Forum auch schon einen Lösungsansatz gefunden: Das rotierte Sprite
in ein neues Rendern. Allerdings habe ich weder in der Image, noch der Sprite-Klasse der
SFML eine brauchbare Funktion gefunden, mit der das realisierbar wäre und in den Tuts auf
der Seite habe ich auch keine Antwort gefunden. In dem Thread, den ich gefunden hatte ging
es leider um DirectX, weshalb ich auf diese Frage keine Antwort finden konnte.

Ich hoffe mal, dass hier irgendjemand einen Lösungsweg oder zumindest einen performant
realisierbaren Ansatz hat, mit dem die Rotation kein Hinderniss mehr für die Kollisionserkennung
darstellt.

Mir kam gerade die Idee, evt. in ein RenderTarget zu rendern, allerdings hat die Klasse sf::RenderTarget
keine Funktionen, die Höhe oder Breite des RenderTargets festlegen. Falls ihr daraus iwas machen könnt
wäre das super, ich bin hier jedenfalls recht ratlos...

mfg
Shadowstrike
Evil Industries - Kaufen Sie jetzt, bereuen Sie später.

Oberon

Treue Seele

Beiträge: 181

Wohnort: Österreich

Beruf: Student

  • Private Nachricht senden

2

22.12.2010, 09:00

Ich hatte ein ähnliches Problem: TransformToLocal bzw. TransformToGlobal sollten es lösen

shadowstrike

Frischling

  • »shadowstrike« ist der Autor dieses Themas

Beiträge: 24

Wohnort: Wiesbaden

Beruf: Schüler

  • Private Nachricht senden

3

22.12.2010, 15:18

genau da liegt ja das problem:

wenn ich mit TransformToGlobal und TransformToLocal arbeite, funktioniert die Kollisionserkennung
zwar prinzipiell, aber die Framerate bricht zusammen (auf unter 1 fps!!) und in der konsole erklärt mein
programm mir, dass die gesuchten pixel nich existieren

evt lass ich den kram mit dem vorberechneten Überschneidungsrechteck und prüfe pixel für pixel, ob
an der momentan geprüften Stelle ein Pixel vom anderen Sprite ist... Is halt bei nicht gedrehten Sprites
n bisschen Performancefressend der jetzigen Methode gegenüber aber wenns nich anders geht dann muss
ichs wohl so machen... und da das thema jetz schon 3 tage existiert und du der erste bist, der antwortet,
geh ich mal davon aus das hier niemand mehr ne elegantere lösung im angebot hat :P

naja danke auf jeden fall trotzdem
Evil Industries - Kaufen Sie jetzt, bereuen Sie später.

shadowstrike

Frischling

  • »shadowstrike« ist der Autor dieses Themas

Beiträge: 24

Wohnort: Wiesbaden

Beruf: Schüler

  • Private Nachricht senden

5

22.12.2010, 16:53

hey danke :D

ma sehn was sich da so draus machen lässt hab keine lust den gesamten code abzukopieren xD
klingt aber auf jeden fall schonma vielverbrechend

EDIT:

Habs gelöst :D is zwar nich die eleganteste lösung aber sie klappt ohne framerate-einbruch:

Hier die leicht veränderte EvilCollision.hpp

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef EVILCOLLISION_HPP
#define EVILCOLLISION_HPP
//*********************************************************************
//Headerdateien einbinden
#include <SFML\Graphics.hpp>
//*********************************************************************
//Namespace ef (Evil Framework)
namespace ef
{
    //Richtung der Kollision
    enum E_COLLISION_DIRECTION { COLLISION_UPLEFT = 0x00000000,
                                COLLISION_UPRIGHT = 0x00000001,
                                COLLISION_DOWNLEFT = 0x00000010,
                                COLLISION_DOWNRIGHT = 0x00000011,
                                COLLISION_NONE = 0x11111111 };
    //Berechnung der BoundingRect-Kollision
    bool getCollisionSphere(sf::Sprite, sf::Sprite);
    //Berechnung der Richtung
    E_COLLISION_DIRECTION getCollisionDirection(sf::Sprite, sf::Sprite);
    //Berechnung der Pixelgenauen Kollision
    bool getCollisionPixel(sf::Sprite, sf::Sprite);
}
#endif


Und hier die .cpp:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "EvilCollision.hpp"
//-----------------------------------------------------------
//Kollisionsberechnungen
//-----------------------------------------------------------
bool ef::getCollisionSphere(sf::Sprite target1, sf::Sprite target2)
{
    //Position anpassen und die Mitte des Sprites an die Stelle 0 | 0 verschieben
    target1.SetPosition(target1.GetPosition().x - target1.GetCenter().x, target1.GetPosition().y - target1.GetCenter().y);
    target2.SetPosition(target2.GetPosition().x - target2.GetCenter().x, target2.GetPosition().y - target2.GetCenter().y);
    target1.SetCenter(0, 0);
    target2.SetCenter(0, 0);

    //Radius der Boundingsphere des ersten Sprites mit dem Satz des Pytagoras berechnen
    float a1 = target1.GetSize().x / 2;
    float b1 = target1.GetSize().y / 2;
    float radius1 = sqrt((a1*a1 + b1*b1));

    //Radius der Boundingsphere des zweiten Sprites mit dem Satz des Pytagoras berechnen
    float a2 = target2.GetSize().x / 2;
    float b2 = target2.GetSize().y / 2;
    float radius2 = sqrt((a2*a2 + b2*b2));

    //Distanz zwischen den Mittelpunkten der beiden Sprites berechnen
    float disX = abs((target2.GetPosition().x + a2) - (target1.GetPosition().x + a1));
    float disY = abs((target2.GetPosition().y + b2) - (target1.GetPosition().y + b1));
    float distance = sqrt(disX*disX + disY*disY);

    if(distance < (radius1 + radius2))
        return true;

    return false;
}
//***********************************************************
ef::E_COLLISION_DIRECTION ef::getCollisionDirection(sf::Sprite target1, sf::Sprite target2)
{
    //Tritt keine Kollision auf, COLLISION_NONE zurückgeben
    if(!getCollisionSphere(target1, target2))
        return COLLISION_NONE;
    //Die Richtung berechnen
    int Direction = 0x00000000;
    if(target1.GetPosition().x < target2.GetPosition().x)
        Direction |= 0x00000001;
    if(target1.GetPosition().y < target2.GetPosition().y)
        Direction |= 0x00000010;
    return (ef::E_COLLISION_DIRECTION)Direction;
}
//***********************************************************
bool ef::getCollisionPixel(sf::Sprite target1, sf::Sprite target2)
{
    if(getCollisionSphere(target1, target2))
    {
        //Jedes Pixel in target1 überprüfen
        for(int x = 0; x < target1.GetSize().x; x++)
        {
            for(int y = 0; y < target1.GetSize().y; y++)
            {
                //Position des Pixels innerhalb von target2 berechnen
                int px1 = target1.TransformToGlobal(sf::Vector2<float>(x, y)).x;
                int py1 = target1.TransformToGlobal(sf::Vector2<float>(x, y)).y;
                int px2 = target2.TransformToLocal(sf::Vector2<float>(px1, py1)).x;
                int py2 = target2.TransformToLocal(sf::Vector2<float>(px1, py1)).y;

                //Befindet sich das Pixel innerhalb von target2?
                if(px2 > 0 && px2 < target2.GetSize().x &&
                    py2 > 0 && py2 < target2.GetSize().y)
                {
                    //Alpha-Werte prüfen
                    int a1 = target1.GetPixel(x, y).a;
                    int a2 = target2.GetPixel(px2, py2).a;

                    //Sind beide Alphawerte größer als 0, tritt eine kollision auf
                    if(a1 != 0 && a2 != 0)
                        return true;
                }
            }
        }
    }
    return false;
}


Und nochmal ne kleine erklärung dazu:

In getCollisionSphere wird das übergebene Sprite als erstes so manipuliert, dass es die "Mitte" des Sprites an die Stelle 0 | 0 verschoben wird, das
Sprite aber an der selben Stelle bleibt. Dann werden mit dem Satz des Pythagoras die Radien der Umgebenden Kreise berechnet. Eine Kollision tritt
auf, sobald die Distanz zwischen den Mittelpunkten der Sprites (Auch wieder Pythagoras, diesmal verwenden wir aber die richtigen Mittelpunkte ;)) kleiner
ist als die addierten Radien.

In getCollisionPixel wird dann, sofern getCollisionSphere true zurückgibt, für jedes Pixel in target1 geprüft, ob sich an dieser Stelle (TransformToGlobal) ein Pixel von target2 (TransformToLocal) befindet. Wenn ja, werden die Alphawerte geprüft und wenn beide Alphawerte größer als 0 sind, also etwas angezeigt wird, haben wir eine Pixelkollision. Hier wird die Funktion sofort beendet, da weitere Berechnungen nur noch Zeitverschwendung wären.

Ich weiß, man soll (zumindest laut meinem Programmierlehrer in der Schule :P) niemals ne forschleife vorzeitig beenden und evt werd ich das iwann nochma fixen aber im mom bin ich erstma froh, dass der kram überhaupt funktioniert :D
Evil Industries - Kaufen Sie jetzt, bereuen Sie später.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »shadowstrike« (23.12.2010, 15:30)


Werbeanzeige

Ähnliche Themen