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

1

14.05.2015, 12:22

Beleuchtungsmaschine in 2D-Spiel funktioniert nicht wie gewollt (C++ und SFML)

Hallo zusammen,
vielleicht hat einer von euch mein Projekt schon in den Projektvorstellungen gesehen und so mitbekommen, dass ich zurzeit an der Beleuchtung meines Spiels arbeite.
Wer nähere Informationen zum Spiel haben will kann sich gerne den Beitrag "Dig Deeper - Ein Hobbyprojekt" (Dig Deeper - Ein Hobbyprojekt )
ansehen.
Das Problem ist nun folgendes: Die derzeitige Lichtberechnung ist sehr langsam. Hier der zugehörige Code:


Funktion zum Hinzufügen eines neuen Lichtkreises

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
//fügt eine neue Lichtquelle in Form eines Kreises hinzu
void CLightMachine::AddLightCircle(int _x, int _y, int _radius, Color _color)
{
    //Erstellt ein neues VertexArray in Form eines Kreises mit 92 Vertices
    VertexArray circle(TrianglesFan, 92);

    //Setzt die Position des Mittelpunktes auf der Rendertextur, die die Größe des Fensters +10 hat
    circle[0].position.x = _x - m_ViewX + 10;
    circle[0].position.y = _y - m_ViewY + 10;
    circle[0].color = Color(255, 255, 255, _color.a);

    //durchläuft die einzelnen Vertices
    for (int angle = 1; angle <= 91; angle++)
    {
        //setzt die Position abhängig vom Radius
        circle[angle].position = Vector2f((_x - m_ViewX + 10) + _radius * cos(angle*4*3.1415926535 / 180), (_y - m_ViewY + 10) + _radius * sin(angle*4*3.1415926535 / 180));

        //überprüft auf Kollision des Lichtstrahls mit einem soliden Block
        circle[angle].position = IsLineIntersecting(circle[0], circle[angle], angle*4, _radius);

        //setzt die Farbe
        circle[angle].color = Color(_color.r, _color.g, _color.b, 255);
    }

    //zeichnet den Lichtkreis
    m_lightTexture.draw(circle, BlendMultiply);
}


(Die Variablen m_ViewX und m_ViewY beinhalten die x- und y-Koordinaten der View, also des sichtbaren Bereichs. Da die Rendertextur für das Licht immer auf der Position m_ViewX -10 und m_ViewY-10 liegt müssen diese
Werte entsprechend abgezogen werden um aus der Position in der Gesamtwelt die Position auf der Rendertextur zu erhalten.)

Funktion, die die Kollision eines Lichtstrahls mit einem Block überprüft

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
Vector2f CLightMachine::IsLineIntersecting(Vertex _firstPoint, Vertex _secondPoint, int _angle, int _radius)
{
   //wenn der Lichtstrahl außerhalb der Welt ist: Beende die Funktion und gib 0,0 zurück
    if (_firstPoint.position.y <= 0 && _secondPoint.position.y < _firstPoint.position.y)
        return Vector2f(0, 0);

    //setzt einen Startwert
    int currentRadius = 5;
    int x, y;

    bool is_intersecting = false;
    
    //läuft durch, bis der Strahl kollidiert oder den Radius erreicht hat
    while (is_intersecting == false)
    {
        //setzt die neue Position des Endpunktes abhängig vom derzeitigen Radius
        _secondPoint.position = Vector2f(_firstPoint.position.x + currentRadius * cos(_angle*3.1415926535 / 180), _firstPoint.position.y + currentRadius * sin(_angle*3.1415926535 / 180));

    //berechnet Position des Blockes in der Matrix, den der Lichtstrahl schneidet (Die Blöcke sind in einer Matrix angeordnet mit Seitenlänge 100)
        x = (_secondPoint.position.x - 10 + m_ViewX) / 100;
        y = (_secondPoint.position.y - 10 + m_ViewY) / 100;

        //prüft, ob der entsprechende Block Licht durchlässt, oder nicht
        if (!m_pWorld->isBlockPassable(x, y))
        {
            //berechne Länge des Lichtstrahles, damit er genau einen Block erleuchtet
            int length = 0;
            if ((_angle >= 45 && _angle < 135) || (_angle >= 225 && _angle < 315))
                length = 100 / (abs(sin(_angle*3.1415926535 / 180)));
            else
                length = 100 / (abs(cos(_angle*3.1415926535 / 180)));

            //prüft, ob die Länge des Lichtstrahls den Radius überschreitet und setzt die Länge ggf. auf diesen
            if (currentRadius + length > _radius)
                _secondPoint.position = Vector2f(_firstPoint.position.x + _radius * cos(_angle*3.1415926535 / 180), _firstPoint.position.y + _radius * sin(_angle*3.1415926535 / 180));
            else
                _secondPoint.position = Vector2f(_firstPoint.position.x + (length + currentRadius) * cos(_angle*3.1415926535 / 180), _firstPoint.position.y + (currentRadius + length) * sin(_angle*3.1415926535 / 180));

            //gibt den neuen Endpunkt des Lichtstrahls zurücl
            return _secondPoint.position;
        }

        //kollidierte der Lichtstrahl nicht: erhöhe den Radius um 2 (bzw. 10, wenn schnelle Lichtberechnung eingestellt ist)
        if (m_fastLight)
            currentRadius += 10;
        else
            currentRadius += 2;

        //ist der Lichtstrahl bis jetzt nicht kollidiert, aber der Radius überschritten: gib Ausgangspunkt zurück
        if (currentRadius > _radius)
            return _secondPoint.position;
    }

    return _secondPoint.position;
}


Das Problem ist, dass die while-Schleife bei einem Radius von 100 ohne Kollision 50-mal durchläuft und das für jeden Lichtstrahl (also 91-mal).
Das sind 4550 Durchläufe pro Lichtkreis pro Frame und viele Lichtkreise haben einen weit höheren Radius.
Die Funktion an sich funktioniert, aber aufgrund der starken Performanceprobleme, die offenbar von dieser Funktion herrühren (habe das auch noch mal mit einem Profiler überprüft) sehe ich mich gezwungen
die Kollisionsfunktion neu zu schreiben.

Ich habe das probiert, bin aber gescheitert. Im folgenden die Funktion, die ich nach dem Vorbild dieser Seite (http://www.permadi.com/tutorial/raycast/rayc7.html ) programmiert habe.



Neue Funktion zur Berechnung der Kollision eines Lichtstrahls mit einem soliden Block

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
        Vector2f CLightMachine::IsLineIntersecting(Vertex _firstPoint, Vertex _secondPoint, int _angle, int _radius)
{
    //Wenn der Strahl außerhalb der Welt ist: gib 0,0 zurück
    if (_firstPoint.position.y <= 0 && _secondPoint.position.y < _firstPoint.position.y)
        return Vector2f(0, 0);

    int lastX, lastY;

    Vector2f firstCollisionPoint(-1, -1);
    Vector2f secondCollisionPoint(-1, -1);

    //Berechne Position des Startpunktes des Strahls
    int x = _firstPoint.position.x - 10 + m_ViewX;
    int y = _firstPoint.position.y - 10 + m_ViewY;

    //die Position des ersten Kollisionspunktes
    int xA = 0;
    int yA = 0;
    
    //Der Betrag, der in jedem Schritt addiert wird
    int stepX = 0;
    int stepY = 0;

    //Prüfe Kollision mit Horizontalen nach oben
    if (_angle >= 180)
    {
        //Berechne die y-Koordinate des nächsten Kollisionspunktes, durch den der Lichtstrahl geht
        yA = (y / 100) * 100 - 1;

        //Berechne die x-Koordinate des nächsten Kollisionspunktes, durch den der Lichtstrahl geht
        xA = x + (y - yA) / tan(_angle*3.1415926535 / 180);

        if (yA < 0 || xA < 0)
        {
            firstCollisionPoint = _secondPoint.position;
        }
        //ist der Block solide: speichere diesen Punkt als Kollisionspunkt mit der Horizontalen
        else if (!m_pWorld->isBlockPassable(xA / 100, yA / 100))
        {
            firstCollisionPoint = Vector2f(xA - m_ViewX + 10, yA - m_ViewY + 10);
        }

        //Berechne den Betrag, der in jedem Schritt addiert wird
        stepX = 100 / tan(_angle*3.1415926535 / 180);
        stepY = -100;

    }
    //Prüfe Kollision mit Horizontalen nach unten
    else
    {
        yA = (y / 100) * 100 + 100;

        xA = x + (y - yA) / tan(_angle*3.1415926535 / 180);

        if (yA < 0 || xA < 0)
        {
            firstCollisionPoint = _secondPoint.position;
        }
        else if(!m_pWorld->isBlockPassable(xA / 100, yA / 100))
        {
            firstCollisionPoint = Vector2f(xA - m_ViewX + 10, yA - m_ViewY + 10);
        }

        stepX = 100 / tan(_angle*3.1415926535 / 180);
        stepY = 100;
    }
    



    bool is_intersecting = false;

    if (firstCollisionPoint.x != -1 && firstCollisionPoint.y != -1)
    {
        while (is_intersecting == false)
        {
            //Berechne den nächsten Kollisionspunkt
            xA = xA + stepX;
            yA = yA + stepY;

            if (yA < 0 || xA < 0)
            {
                firstCollisionPoint = _secondPoint.position;
                is_intersecting = true;
            }
            //Prüfe, ob der Strahl nun länger als der Radius ist
            else if (sqrt(pow(x - xA, 2) + pow(y - yA, 2)) > _radius)
            {
                firstCollisionPoint = Vector2f(_firstPoint.position.x + _radius * cos(_angle*3.1415926535 / 180), _firstPoint.position.y + _radius * sin(_angle*3.1415926535 / 180));
                is_intersecting = true;
            }
            //Prüfe, ob der Endpunkt des Strahls in einem soliden Block liegt
            else if (!m_pWorld->isBlockPassable(xA / 100, yA / 100))
            {
                firstCollisionPoint = Vector2f(xA - m_ViewX + 10, yA - m_ViewY + 10);
                is_intersecting = true;
            }
        }
    }


    //das gleiche wird nun mit der Vertikalen durchgeführt, sodass man am Ende einen Kollisionspunkt mit der Horizontalen und einen mit der Vertikalen hat

    //Prüfe Kollision mit Vertikalen nach links
    if (_angle <= 90 || _angle > 315)
    {
        xA = (x / 100) * 100 - 1;

        yA = y + (x - xA) * tan(_angle*3.1415926535 / 180);

        if (yA < 0 || xA < 0)
        {
            secondCollisionPoint = _secondPoint.position;
        }
        else if (!m_pWorld->isBlockPassable(xA / 100, yA / 100))
        {
            secondCollisionPoint = Vector2f(xA - m_ViewX + 10, yA - m_ViewY + 10);
        }

        stepX = -100;  
        stepY = 100 * tan(_angle*3.1415926535 / 180);
    }
    else
    {
        xA = (x / 100) * 100 + 100;

        yA = y + abs(x - xA) * tan(_angle*3.1415926535 / 180);

        if (yA < 0 || xA < 0)
        {
            secondCollisionPoint = _secondPoint.position;
        }
        else if (!m_pWorld->isBlockPassable(xA / 100, yA / 100))
        {
            secondCollisionPoint = Vector2f(xA - m_ViewX + 10, yA - m_ViewY + 10);
        }
        stepX = 100;
        stepY = 100 * tan(_angle*3.1415926535 / 180);
    }



    is_intersecting = false;
    while (is_intersecting == false)
    {
        xA = xA + stepX;
        yA = yA + stepY;

        if (yA < 0 || xA < 0)
        {
            secondCollisionPoint = _secondPoint.position;
            is_intersecting = true;
        }
        else if (sqrt(pow(x - xA, 2) + pow(y - yA, 2)) > _radius)
        {
            secondCollisionPoint = Vector2f(_firstPoint.position.x + _radius * cos(_angle*3.1415926535 / 180), _firstPoint.position.y + _radius * sin(_angle*3.1415926535 / 180));
            is_intersecting = true;
        }
        else if (!m_pWorld->isBlockPassable(xA / 100, yA / 100))
        {
            secondCollisionPoint = Vector2f(xA - m_ViewX + 10, yA - m_ViewY + 10);
            is_intersecting = true;
        }
    }


    //gib den Punkt zurück, bei dem die Länge des Strahls kürzer ist
    if (sqrt(pow(firstCollisionPoint.x - x, 2) + pow(firstCollisionPoint.y - y, 2)) < sqrt(pow(secondCollisionPoint.x - x, 2) + pow(secondCollisionPoint.y - y, 2)))
        return firstCollisionPoint;
    else
        return secondCollisionPoint;

}


Diese Funktion ermittelt die Kollisionspunkte des Strahls mit der Horizontalen und Vertikalen der Matrix und gibt den nähesten zurück.
Bei einem Radius von 100 würde jede while-Schleife 1-mal durchlaufen, da die Felder der Matrix eine Länge von 100 haben.
Leider funktioniert diese Funktion nicht wie gewollt (siehe Bild) und läuft zudem auch nicht schneller (eher noch langsamer)
Meine Fragen sind jetzt: Habe ich einen Fehler in der neuen Funktion?
Gibt es eine bessere Alternative?
Warum ist die neue Funktion nicht schneller?


Licht bei neuer Funktion:


Licht bei alter Funktion:


Ich hoffe ihr steigt durch meinen Code durch, wenn nicht, meldet euch.
Ich freue mich über Rückmeldung.
Danke im Voraus.
Ole

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

14.05.2015, 13:53

Ich blicke da nicht durch (zu unordentlich), aber ich sehe, dass du unnötig Wurzeln ziehst. Wenn §\sqrt{x^2+y^2} \leq z§, dann auch §x^2+y^2 \leq z^2§ für §z \geq 0§. Du hast auch viele Sin/Cos-Berechnungen drin, mit int-double-Konvertierungen, die immer dieselben Ergebnisse liefern, da du nur 360 verschiedene Winkel hast. Da würde sich evtl. eine kleine Lookup-Tabelle anbieten.

Aber wichtig: Benutze einen Profiler, um die genauen Stellen zu identifizieren, an denen die Zeit hauptsächlich verbraten wird.

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

3

14.05.2015, 14:09

Oder erstmal einen Debugger, um durchzusteppen und herauszufinden, warum der Algorithmus falsche Ergebnisse liefert.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

4

14.05.2015, 14:46

@David: Ja, tut mir leid, an der Lesbarkeit meines Codes muss ich definitiv noch arbeiten.
Mit den Wurzeln und sin/cos- Berechnungen hast du natürlich Recht, das werde ich auf jeden Fall schonmal ändern, dankeschön :)
Du meinst also ich soll mir mit einem Profiler nur die eine Funktion angucken? Weil, dass diese Funktion das Problem ist ist sicher (das hab ich mit einem Profiler getestet).
Ist allerdings auch das erste mal, dass ich einen Profiler verwendet habe, war bis jetzt nie nötig (ist mein erstes größeres Projekt).


@Schrompf
: Das stimmt natürlich, aber manchmal waren offensichtliche Fehler in meinem Code, die andere schnell entdeckt haben. Hätte ich da einen Debugger benutzt hätte ich ewig gebraucht. Darum hab ich gedacht, poste ichs mal hier, vielleicht fällt einem ja schon was auf.

Danke für die Rückmeldung :)

5

15.05.2015, 14:52

Man kann sich da natürlich auch streiten, wie schnell eine einzelne sin/cos instruktion der FPU im Vergleich zu vielen Multiplikationen und Divisionen ist ;)

Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von »Roflo« (15.05.2015, 15:05)


6

15.05.2015, 16:51

Hast ja recht hab da etwas Quatsch erzählt :D
Aber vielleicht könnte man aber mal versuchen, statt auf die CPU auf entsprechende Shader und Buffer zu setzen, um den Lichteffekt zu erreichen.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Roflo« (15.05.2015, 17:06)


7

15.05.2015, 21:08

Also wenn ich das jetzt richtig verstanden hab kann ich die Sinus-/Cosinus- Berechnungen doch so lassen, weil die Grafikkarten die genauso schnell berechnen wie eine Multiplikation bzw. Addition?

Und bezüglich Geschwindigkeit der Lichtberechnung in meinem Code habe ich zumindest bemerkt, dass der neue Code doch nicht langsamer ist als der alte.
Ich habe im Nachhinein das Gefühl, dass die krassen Performanceprobleme (teilweise 1 Frame pro Sekunde) erst nach Verwendung eines Profilers aufgetreten sind.
Kann das sein, das der Profiler mir da irgendwie reingepfuscht hat, oder eher nicht?
Ich verwende AMDCodeXL.

8

15.05.2015, 21:35

Weil ich es noch nirgends gelesen habe (hoffe habe es nicht überlesen :D )

Die Performanceprobleme treten im Release-Modus auf?
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

9

15.05.2015, 21:54

Weil ich es noch nirgends gelesen habe (hoffe habe es nicht überlesen :D )

Ich glaube du irrst dich im Thread ^^

Die Performanceprobleme treten im Release-Modus auf?

Eine gute Frage!

10

15.05.2015, 22:18

@Koshi what the...? versteh nur Bahnhof!

Koschi!

Ich glaube du irrst dich im Thread ^^

Superolelli schreibt ...

...Ich habe im Nachhinein das Gefühl, dass die krassen Performanceprobleme (teilweise 1 Frame pro Sekunde) erst nach Verwendung eines Profilers aufgetreten sind...


Ich bin schon im Richtigen Thread, ich möchte nur wissen ob die FPS von 1 im Release Modus auftreten.
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

Werbeanzeige