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!

2D Kollision von Bällen

Werbeanzeige

CBenni::O

1x Contest-Sieger

Beiträge: 1 145

Wohnort: Stuttgart

  • Private Nachricht senden

11

24.10.2012, 17:28

Ja, der bewegungsvektor wird in jedem Zeitschritt mit der vergangenen Zeit multipliziert und auf vPos draufaddiert: vPos += vPos+fTime*vVel.

Soo, der Code wie er da steht, erscheint nicht korrekt... Aber ich habe das nicht genauer nachgeprüft. Zu den Berechnungen mit verschiedenen Geschwindigkeiten siehe meinen (vorherigen) Post oben.
Ein kleines bisschen Erklärung: Die Winkelberechnung ist tatsächlich Optional und laufzeittechnisch völliger schwachsinn. Stattdessen berechnet man den Vektor in einem Orthonormalen Vektorraum, der durch die Vektoren VecN und VecDiff aufgespannt wird (Das ist ein "anderes Koordinatensystem", das, wie das "normale" von 2 Achsen aufgespannt wird, die jeweils die Länge(=Einheit) 1 haben. Dies wird durch dot(VecN,VecVel), dot(VecDiff,VecVel) (Beweis siehe Lineare Algebra) berechnet. Daraufhin wird der neue Vektor an VecN gespiegelt (Da wir jetzt in einem neuen Koordinatensystem sind, kommt das einer Negation der 2. Koordinaten gleich). Zu guter letzt muss man den Neuen Vektor wieder zurücktransformieren (durch multiplikation mit VecVel).
Dies lässt sich wie in meinem Code in einer Zeile zusammenfassen.
Soll ich evtl ein Bild dazu malen? :D

Zu der Berücksichtigung von Geschwindigkeiten/Impulserhaltung siehe oben ;) Wenn man mit unterschiedlichen Massen arbeitet, muss man den Impuls berechnen und speichern, statt nur die Geschwindigkeit.
Evtl wäre es besser, wenn du nicht versuchst, den Code vollständig zu verstehen, Mathematische Infos gehen SEHR schnell in die Theorie von Vektorräumen, Orthonormalräumen und Orthonormalen Abbildungen hinein, das geht weit über den Schulstoff hinaus (Ist HM2 oder LA2, wenn ich mich nicht irre?)

Zu deinem Problem: Derart gewaltige Geschwindikeiten treten v.a. dann auf, wenn Objekte sich verkeilen, oder bei divisionen (hier gibt es (k)eine) durch winzige Zahlen dividiert wird. Wenn sie sich verkeilen, siehe oben. Wenn nicht, dann überprüfe mal deinen Normalisierungscode (sofern er von dir stammt)

mfg CBenni::O

PS: Es kann sein, dass ich hier und da kleinere Fehler gemacht habe, habe das so gut wie möglich aus dem Gedächtnis abgerufen, wenn ihr mich denn (höflich) darauf hinweist?
Ein Mitglied der VEGeiCoUndGraSonMaWiGeS Bewegung.
42!
Aufräumen kann jeder, nur das Genie überblickt das Chaos!
Metal will never die!
1. Sppro Gamecontest - mein Beitrag

marfi

Treue Seele

  • »marfi« ist der Autor dieses Themas

Beiträge: 100

Wohnort: Schwerte

  • Private Nachricht senden

12

26.10.2012, 12:30

Also so halbwegs habe ich es jetzt im Griff.
@Benni: Vielen Dank für den Tip mit dem NormalenVektor. Ich hatte vergessen die Nullnummer zu berücksichtigen. So sieht die Funktion jetzt aus.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12

  void CVector2D::normalize()
  {
        int len = GetLength();
            if(len != 0)
        {
            _X  /= len;
                _Y /= len;
            }
            else
                    _X = _Y =  0;
               }

Jetzt ist das Phänomen des Verschwindens schon mal weg. Aber das anprallen ist nicht korrekt. (Zumindest prallen die Bälle schon mal voneinander ab).
Wenn zwei Bälle in die gleiche Richtung fliegen, wechseln sie die Richtung nach einem Anprall. Aufgrund meiner geringen Vektorkentnisse habe ich jetzt versucht dafür eine Lösung zu finden.
Jetzt ist meistens richtig, aber eben nicht immer. Hier ist mal den Codeausschnitt.

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

   CVector2D N =  Normalize(vecPos2-vecPos1);
   CVector2D O = CVector2D(-N._Y,N._X);

         float mass  = 0.7f;

        float Speed1 = mass * GetLength(Normalize(vec1*N));
        float  Speed2 = mass * GetLength(Normalize(vec2*N));

      // Wenn beide in gleiche  Richtung fliegen
    if((vec1._X /  abs(vec1._X))  == (vec2._X / abs(vec2._X))&&
            (vec1._Y / abs(vec1._Y)) == (vec2._Y / abs(vec2._Y)))
        {
        vec1  =((N*(-2*DotProduct(vec1,N))) - vec1)* Speed2;
            vec2 =((N*(-2*DotProduct(vec2,N)))  - vec2)* Speed1;
        }
        else
        {
        vec1  =((O*(-2*DotProduct(vec1,O))) - vec1)* Speed2;
            vec2 =((O*(-2*DotProduct(vec2,O)))  - vec2)* Speed1;
    }

                            vecPos2 = vecPos1+N*15;


@Benni, wenn ich deinen Code verwende, stimmen die Flugwinkel auch nicht und die Bälle fangen an zu klumpen.

Wenn ich es schaffe, werde ich mal ein Programm hochladen, bei dem mal die verschiedenen Berechnungen umschalten kann.
Vielleicht habe ich aber auch woanders ein Problem. Wie gesagt, eigentlich wollte ich die Recursice dimensional clustering Methode zur Kollisionserkennung prüfen.
[Edit] Komisch mit der Codeformatierung, wie ich das jetzt wieder geschafft habe ... tztztz..

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »marfi« (26.10.2012, 12:35)

CBenni::O

1x Contest-Sieger

Beiträge: 1 145

Wohnort: Stuttgart

  • Private Nachricht senden

13

26.10.2012, 16:59

Mmh, ich werde zusehen, dass ich ein kleines Programm auf die beine stelle... bbl

EDIT: wird eher heute abend oder morgen ...
EDIT2: Ich habe einen schrecklichen Tippfehler gemacht!

C-/C++-Quelltext

 
1
2

v1 = v1*dot(v1,o)-normalize(v1*dot(v1,d))*speed2;
v2 = v2*dot(v2,o)-normalize(v2*dot(v2,d))*speed1;


sollte

C-/C++-Quelltext

 
1
2

v1 = o*dot(v1,o)-normalize(d*dot(v1,d))*speed1;
v2 = o*dot(v2,o)-normalize(d*dot(v2,d))*speed2;

und statt

C-/C++-Quelltext

 
1
2

float speed1 = length(v1*dot(v1,d));
float speed2 = length(v2*dot(v2,d));

sollte es

C-/C++-Quelltext

 
1
2

float speed1 = Math.Abs(v1.DotProduct(d));
float speed2 = Math.Abs(v2.DotProduct(d));

sein!
Ich werde die älteren Posts dahingehend anpassen. Meine Kleine Beispielanwendung funktioniert jetzt.

mfg CBenni::O
Ein Mitglied der VEGeiCoUndGraSonMaWiGeS Bewegung.
42!
Aufräumen kann jeder, nur das Genie überblickt das Chaos!
Metal will never die!
1. Sppro Gamecontest - mein Beitrag

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »CBenni::O« (28.10.2012, 16:26)

marfi

Treue Seele

  • »marfi« ist der Autor dieses Themas

Beiträge: 100

Wohnort: Schwerte

  • Private Nachricht senden

14

28.10.2012, 14:11

Mensch Benni, das klappt ja jetzt ganz hervorragend!! Danke!


Machen die Kollisionspartner bei deiner Anwendung auch manchmal komische Bewegungen?



Ich habe hier mal meine Anwendung hochgeladen.



http://www.sudmix.de/media/Koll_Test.rar

Nicht erschrecken wegen der ganzen dll Dateien, aber ich habe für den Test mein Framework benutzt.

CBenni::O

1x Contest-Sieger

Beiträge: 1 145

Wohnort: Stuttgart

  • Private Nachricht senden

15

28.10.2012, 16:15

Ich muss meinen Code auch nochmal überdenken, in manchen Situationen geschehen komische dinge. bbl.

EDIT: Ok, mist.
Komplett Neuer Ansatz:
Bei der Kollision behalten beide Kugeln ihre Geschwindigkeit entlang des Orthogonalen Vektors bei, die Vektoren entlang der Normalen TAUSCHEN sich: (norm=normalenvektor,normalisiert, orth=orthogonalvektor dazu, automatisch normalisiert)

C-/C++-Quelltext

 
1
2
3
4
5
6
7

Vector2 innorm1 = norm * Vector2.DotProduct(vel1, norm);  // vec1-Komponente entlang norm
Vector2 innorm2 = norm * Vector2.DotProduct(vel2, norm);  // vec2-Komponente entlang norm
Vector2 inorth1 = orth * Vector2.DotProduct(vel1, orth);  // vec1-Komponente entlang orth
Vector2 inorth2 = orth * Vector2.DotProduct(vel2, orth);  // vec2-Komponente entlang orth

vel1 = inorth1 + innorm2;
vel2 = inorth2 + innorm1;

Dieser Code ist super schnell ^.^ und er funktioniert einwandfrei (bei mir); Ich muss nichtmal die Position neu setzen, da das nicht mehr (unbedingt) notwendig ist (empfiehlt sich trotzdem).

mfg CBenni::O
Ein Mitglied der VEGeiCoUndGraSonMaWiGeS Bewegung.
42!
Aufräumen kann jeder, nur das Genie überblickt das Chaos!
Metal will never die!
1. Sppro Gamecontest - mein Beitrag

Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von »CBenni::O« (28.10.2012, 16:41)

marfi

Treue Seele

  • »marfi« ist der Autor dieses Themas

Beiträge: 100

Wohnort: Schwerte

  • Private Nachricht senden

16

29.10.2012, 15:49

Also jetzt muss ich doch mal nachfragen J

Hey, der Algo ist noch besser. Jetzt gibt es bei mir nur noch komische Effekte, wenn die Bälle sich 3x hintereinander in der gleichen Richtung berühren. Dann flitzen sie auf einmal los. Ansonsten super gelöst.

Was verstehst du unter Normalenvektor und Orthogonalvektor. Für mich ist das eigentlich das gleiche. Den Normalenvektor erhalte durch das Kreuzprodukt. Bei 2D ist das einfach das vertauschen von x und y sowie das negieren von ehemals y.

Den Ortho hast du genauso erstellt. Bei mir ist „Dein“ Normalenvektor der Vektor zwischen den beiden Positionen und der Ortho halt der Normalenvektor des Differenzvektors.

Noch was anderes, kann es sein, das CGrowableArray von MS etwas langsam ist? Oder liegt das in der Sache der Natur? Ich habe meine Bälle vorher in einem einfachen Array gespeichert und hatte bei 100 Bällen und der bf Methode ca 7 ms jetzt habe ich das 100 fache.

Nun, meine RDC Methode zur Kollisionskontrolle ist auch nicht so schnell, wie ich es erwartet hätte, aber daran kann man arbeiten J Die Zeit halbiert sich gegenüber der BruteForce Methode.

Gibt es eine schnellere Methode als RDC um Kollisionen von > 500 Objekten zu testen?

An meinem Lappy geht bei 500 Bällen nicht mehr viel (5 FPS).

Ich werde später eine neue Version hochladen, dabei kann man RDC und bf umschalten und die Anzahl der Bälle mit einem Slider variieren.

CBenni::O

1x Contest-Sieger

Beiträge: 1 145

Wohnort: Stuttgart

  • Private Nachricht senden

17

29.10.2012, 17:19

500 Bälle sollten funktionieren. ich kenne das CGrowableArray nicht. Mit welcher API/Sprache entwickelst du denn? Kann es sein, dass der renderingprozess nicht der schnellste ist? Ich habe meine testanwendung in C#/WinForms geschrieben und da wird es ab 20 bällen unerträglich langsam; Ich werde mal mit SuspenseLayout() rumprobieren.

Meine Namensgebung ist nicht so doll, normalenvektor heißt der eine, weil er normal zur kollisionstangente steht. ortho ist der andere, der steht orthogonal auf dem normalenvektor, also in richtung der tangente.
Und wenn du immer noch das Problem hast, dass die Bälle verkeilen, dann musst du nach der kollisionsbehandlung noch dafür sorgen, dass die Bälle wieder absoand r1+r2 voneinander haben. z.B.

C-/C++-Quelltext

 
1
2
3

Vector2 mid = (pos1+pos2)/2;
pos1 = mid-norm*r1;
pos2 = mid+norm*r2;


mfg CBenni::O
Ein Mitglied der VEGeiCoUndGraSonMaWiGeS Bewegung.
42!
Aufräumen kann jeder, nur das Genie überblickt das Chaos!
Metal will never die!
1. Sppro Gamecontest - mein Beitrag

marfi

Treue Seele

  • »marfi« ist der Autor dieses Themas

Beiträge: 100

Wohnort: Schwerte

  • Private Nachricht senden

18

29.10.2012, 21:55

Achso, dann habe ich es doch richtig verstanden :)



Also es kleben keine Bälle mehr zusammen. Und wenn ich jetzt die RDC Funktion aktiviere, kann ich auf meinem PC 500 Bälle bei 30 FPS tanzen lassen.
Ab und zu rutschen die Bälle aneinander vorbei, das sieht noch etwas komisch aus, aber ansonsten ist es so richtig gut. Danke nochmal!



Ich programmiere mit der DX9 Api und c++. An der Renderfunktion liegt es nicht, wenn ich die Bälle ausschalte, wird es nicht schneller. Aber meine RDC Funktion scheint noch zu langsam. Die Zeit wird nur halbiert, eigentlich müsste es schneller sein. Aber jetzt wo die Bälle so schön kollidieren, kann ich an der Geschwindigkeit arbeiten :)
In meiner Anwendung kann man zwischen brute force und RDC wechseln, die Ballanzahl mit dem Slider in der Mitte varieren und die Bälle wegschalten.



http://www.sudmix.de/media/Koll_Test_V1.1.rar



Marfi



EDIT: Bei 350 Bällen wird die Zeit mit RDC doch geviertelt. Es darf nicht so viele Kollisionen geben, sonst wird auch RDC etwas langsamer. Die Zeit für die Prüfung an sich ist aber doch schon ganz passabel.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »marfi« (29.10.2012, 22:01)

CBenni::O

1x Contest-Sieger

Beiträge: 1 145

Wohnort: Stuttgart

  • Private Nachricht senden

19

30.10.2012, 08:48

Es gibt auch einen haufen kleinerer Optimierungen, bsp: das quadrat der summe berechnen, damit testen ob der abstand so klein ist dass es eine Kollision gab, danach (wenn es eine kollision gab) die wurzel ziehen und den normalenvektor damit normalisieren. Du sparst dir dadurch beinahe ALLE wurzelberechnungen (nur alle frames ein,zwei, wenn zwei kugeln kollidieren. Der naive ansatz berechnet sogar 2 wurzeln, wenn 2 Kugeln kollidieren...

EDIT: btw, bei deiner anwendung sehe ich die bälle nicht... Im log steht:

Quellcode

 
1
2
3
4
5
6
7
8
9
10

D:\Eigene Dateien\Downloads\Koll_Test_V1.1\Koll_Test
../EoD_Debug/media/hud/arrow.png : Invalid data
D:\Eigene Dateien\Downloads\Koll_Test_V1.1\Koll_Test
../EoD_Debug/media/hud/arrow.png : Invalid data
D:\Eigene Dateien\Downloads\Koll_Test_V1.1\Koll_Test
..\media\boid.png : Invalid data
D:\Eigene Dateien\Downloads\Koll_Test_V1.1\Koll_Test
..\media\Grid.png : Invalid data
D:\Eigene Dateien\Downloads\Koll_Test_V1.1\Koll_Test
..\media\Boid.png : Invalid data

(media/Boid.png und Grid.png existieren)
EDIT2: ich musste media einfach ein Verzeichnis nach oben schieben (../)
EDIT3: Der renderinsprozess macht schon einiges aus... Bei 500 Bällen hab in ~40-50 FPS mir zeichnen, 80-90 ohne; Das sollte schneller möglich sein (da du immer dasselbe Zeichnest).
Und manchmal scheinen sie sich doch noch in einander zu verhaken... Da stimmt was mit deinen "Abstand wiederherstellen" code evtl nicht. Oder haben die Kugeln vielleicht keine chance, sich einmal zu bewegen, bevor sie weider auf Kollision geprüft werden? Darf ich mal deinen finalen Code sehen (Gerne auch per PM)
EDIT4: Und dein Programm stürtzt nach einiger zeit (ca 10 minuten oder so) ab.
mfg CBenni::O
Ein Mitglied der VEGeiCoUndGraSonMaWiGeS Bewegung.
42!
Aufräumen kann jeder, nur das Genie überblickt das Chaos!
Metal will never die!
1. Sppro Gamecontest - mein Beitrag

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »CBenni::O« (30.10.2012, 09:35)

marfi

Treue Seele

  • »marfi« ist der Autor dieses Themas

Beiträge: 100

Wohnort: Schwerte

  • Private Nachricht senden

20

01.11.2012, 15:23

Also der "finale" Code ist relativ einfach.

Update wird vor dem rendern aufgerufen

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

void CBall_Object::update(float fElapsedTime)
{

    
    CVector2D vecPos = GetvecPosition();


    if(m_vecVelocity._X > ballNS::MAX_VEL)
        m_vecVelocity._X = ballNS::MAX_VEL;

    if(m_vecVelocity._Y > ballNS::MAX_VEL)
        m_vecVelocity._Y = ballNS::MAX_VEL;

    
    
    vecPos  += (m_vecVelocity * fElapsedTime);

    

    if(vecPos._X < 0)
    {
        vecPos._X = 1;
        
        m_vecVelocity._X = -m_vecVelocity._X;
    }

    if(vecPos._X > 1000)
    {
        vecPos._X = 999;
        m_vecVelocity._X = -m_vecVelocity._X;
    }

    if(vecPos._Y < 0)
    {
        
        
        vecPos._Y = 1;
        m_vecVelocity._Y = -m_vecVelocity._Y;

    }

    if(vecPos._Y > 700)
    {
    
        
        vecPos._Y = 699;
        m_vecVelocity._Y = -m_vecVelocity._Y;
    }

    SetvecPosition(vecPos);
}


Danach läuft die Kollisionskontrolle und speichert die Kollisionen in den Objekten.

Diese werden dann durchlaufen und verschoben.

Danach erst gerendert.

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

void CPhysics::CircleCollision( CVector2D& vec1, CVector2D& vec2, CVector2D& vecPos1, CVector2D& vecPos2, bool bRigidBody, float fElapsedTime )
{
    // Vebindungsvektor (normiert):
    
    CVector2D N = Normalize(vecPos2-vecPos1);
    CVector2D O = CVector2D(-N._Y,N._X);

    float mass = 0.9f;

    /*
    vec1 = O*DotProduct(vec1,O)-Normalize(N*DotProduct(vec1,N))*Speed2;
    vec2 = O*DotProduct(vec2,O)-Normalize(N*DotProduct(vec2,N))*Speed1;
    */
    CVector2D innorm1 = N * DotProduct(vec1,N);  // vec1-Komponente entlang norm
    CVector2D innorm2 = N * DotProduct(vec2,N);  // vec2-Komponente entlang norm
    CVector2D inorth1 = O * DotProduct(vec1,O);  // vec1-Komponente entlang orth
    CVector2D inorth2 = O * DotProduct(vec2,O);  // vec2-Komponente entlang orth
    
    vec1 = (inorth1 + innorm2)*mass;
    vec2 = (inorth2 + innorm1)*mass;

    CVector2D mid = (vecPos1+vecPos2)/2;
    vecPos1 = mid-N*6;
    vecPos2 = mid+N*6;
    
    //vecPos2 = vecPos1+N*13;
}


So sieht es in der renderfunktion aus

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

    QueryPerformanceCounter(&timeStart);        // get starting time
    m_rdc.run(m_pPairs, &m_arrBalls,X_AXIS,Y_AXIS,bBruteForce);
    QueryPerformanceCounter(&timeEnd);        // get end time
    
    for (int i=0; i< m_nBallCount; i++)
    {
        m_pBallObj = (CBall_Object*)m_arrBalls.GetAt(i);

        if(m_pBallObj)
        {
            
            if(m_pBallObj->GetbCollide())
            {
                m_EnemyObj->m_nCount++;

                //m_pBallObj->Intersection(*m_pBallObj);
                if((m_pBallObj)&&(m_pBallObj->GetpKollPartner()))
                    m_pPhys->CircleCollision(m_pBallObj->m_vecVelocity, ((CBall_Object*)m_pBallObj->GetpKollPartner())->m_vecVelocity,m_pBallObj->GetvecPosition(), m_pBallObj->GetpKollPartner()->GetvecPosition(),true,fElapsedTime);
                
            }


            
            if(GetGameApp()->m_bBallsVisible)
                GetGameApp()->CallGrafikDevice()->CallSpriteManager()->Render(GetGameApp()->m_uTextureID[2],M3DVector(m_pBallObj->GetvecPosition()._X, m_pBallObj->GetvecPosition()._Y,0));
        }


Oder was wolltest du genau sehen?

Das es bei dir abstürzt, liegt daran das die rdc Funktion ein Speicherleck hat :) Und das in einer recursiven Funktion. Sorry!

Werbeanzeige

Ähnliche Themen