Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

Distanzberechnungsfunktion - Langsam?!

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC.
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Nitroxis



Anmeldungsdatum: 27.02.2008
Beiträge: 300
Wohnort: Irgendwo...

BeitragVerfasst am: 15.01.2010, 16:42    Titel: Distanzberechnungsfunktion - Langsam?! Antworten mit Zitat

Guten Tag
Ich schreibe zurzeit ein Spiel mit vielen Partikeln und anderen umherfliegenden dingen.
Manche Partikel (nicht alle) haben eine Kollisionsberechnung, da sie mit anderen Objekten zusammenstoßen können.
Wenn die Zahl dieser Partikel > 100 ist, wird das Spiel sehr verlangsamt.
Ich wollte dann mal schauen, woran das liegt, denn eigentlich ist diese Kollisionsberechnung nicht sonderlich komplex oder rechenaufwendig.
Dabei habe ich dann einfach mal die gesamte Kollisionsberechnung auskommentiert, und es war alles ok.
Dann habe ich Zeile für Zeile alles wieder entkommentiert.
Als ich dann den Funktionsaufruf für die Distanzberechnung zwischen Partikel und Objekt entkommentiert habe, wurde es wieder langsam.
Aber warum?!
Hier ist meine Distanzberechnungsfunktion:
Code:
Function GetDistance(ByVal X1 As Single, Y1 As Single, ByVal X2 As Single, Y2 As Single) As Single
   Return Sqr((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)
End Function
Bei der Kollisionsberechnung werden bei jeden Kollisionsfähigem Partikel alle Objekte durchgeschleift.
Ich dachte zu erst es würde daran liegen, aber das war es nicht. Ich habe alle anderen Zeilen entkommentiert außer diese und das Spiel läuft flüssig bei > 100 Partikeln.
Wenn ich jedoch Diese eine Zeile entkommentiere ruckelts.
Das heißt es muss an der Distanzberechnung liegen.
Hier ist der Funktionsaufruf für die Berechnung
Code:
Distance = GetDistance(Particle->Position.X, Particle->Position.Y, Object->Position.X, Object->Position.Y)
Hat jemand eine Verbesserungsidee?
Man könnte die Funktion eventuell in Assembler porten, aber ob das hilft weiß ich nicht
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
MisterD



Anmeldungsdatum: 10.09.2004
Beiträge: 3071
Wohnort: bei Darmstadt

BeitragVerfasst am: 15.01.2010, 19:02    Titel: Antworten mit Zitat

Function GetDistance(ByVal X1 As Single, Y1 As Single, ByVal X2 As Single, Y2 As Single) As Single
Return Sqr((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)
End Function

->

#define GetDistance(x1, y1, x2, y2) sqr((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))


grund 1) freebasic compiler = dumm => macro schneller als mini-function
grund 2) freebasic compiler = dumm => a*a schneller als a^2
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Nitroxis



Anmeldungsdatum: 27.02.2008
Beiträge: 300
Wohnort: Irgendwo...

BeitragVerfasst am: 15.01.2010, 22:15    Titel: Antworten mit Zitat

Edit: Hat sich erledigt
Ist jez min. 10x schneller
Danke happy
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Jojo
alter Rang


Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte

BeitragVerfasst am: 15.01.2010, 23:23    Titel: Antworten mit Zitat

MisterD hat Folgendes geschrieben:
grund 1) freebasic compiler = dumm => macro schneller als mini-function
grund 2) freebasic compiler = dumm => a*a schneller als a^2

gibt inzwischen aber auch naked functions (also ohne funktionsoverhead). ich weiß aber nicht, ob der compiler die auch automatisch benutzt, oder ob das nur mit dem schlüsselwort "naked" geht.
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
micha



Anmeldungsdatum: 09.12.2005
Beiträge: 72

BeitragVerfasst am: 16.01.2010, 04:47    Titel: Antworten mit Zitat

Oft reicht es aber auch wenn man nicht die absolute Distanz berechnet sonder nur dessen Entfernung im Quadraht ausdrückt.

Distance2=xdif*xdif + ydif*ydif

Der Flashenhals ist dabei SQR() besonders bei einigen tausend Partickeln die alle mit einander kollidieren können/sollen/dürfen.

Gerade bei Partickeln reicht oft die Angabe des Radius um Testen zu können ob eine eventuelle Kollision vorliegt.

Partickel1.Radius = 10
Partickel1.Radius2 = Partickel1.Radius*Partickel1.Radius

Partickel2.Radius = 30
Partickel2.Radius2 = Partickel2.Radius*Partickel2.Radius


if Distance2(Partickle1, Partickel2)<(Partickel1.Radius2+Partickel2.Radius2) then Kollision

Micha
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Caran



Anmeldungsdatum: 11.03.2007
Beiträge: 290
Wohnort: Lörrach

BeitragVerfasst am: 16.01.2010, 13:17    Titel: Antworten mit Zitat

MisterD hat Folgendes geschrieben:

grund 2) freebasic compiler = dumm => a*a schneller als a^2

...stimmt aber auch nur teilweise:
Nach einigem Testen ist mir aufgefallen, dass
Code:
x*x + x*x + x*x
meistens etwas langsamer ist als
Code:
x^2 + x^2 + x^2


Allerdings ist
Code:
 (x - y)*(x - y) + (x - y)*(x - y) + (x - y)*(x - y)

um einiges schneller als
Code:
(x - y)^2 + (x - y)^2 + (x - y)^2

_________________
Eine Erkenntnis von heute kann die Tochter eines Irrtums von gestern sein.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Jojo
alter Rang


Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte

BeitragVerfasst am: 16.01.2010, 14:10    Titel: Antworten mit Zitat

micha hat Folgendes geschrieben:
Distanz berechnet sonder nur dessen Entfernung im Quadraht ausdrückt.

Was fürn Draht? lachen
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
28398



Anmeldungsdatum: 25.04.2008
Beiträge: 1917

BeitragVerfasst am: 16.01.2010, 14:29    Titel: Antworten mit Zitat

Alternativ könnte man die Quadratwurzel auch annähern oder die Funktion auf der FPU berechnen lassen (Assembler)...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2529
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 16.01.2010, 19:09    Titel: Antworten mit Zitat

Caran hat Folgendes geschrieben:
Allerdings ist
Code:
 (x - y)*(x - y) + (x - y)*(x - y) + (x - y)*(x - y)

um einiges schneller als
Code:
(x - y)^2 + (x - y)^2 + (x - y)^2

Das Ganze hat einen interessanten Hintergrund (bei FreeBasic sogar dank offenem Quelltext nachprüfbar!): In der Regel arbeitet der "^"-Operator mit zwei Fliesskommazahlen und rechnet intern (kein Witz!) das Ganze als

Code:
' Berechnung y = a ^ b
y = EXP(LOG(a) * b)

womit natürlich relativ teure Reihenfunktionen ähnlich SIN() und COS() zur Anwendung kommen. Man beachte: Auch b wird als Fliesskommazahl erwartet!
_________________
Teste die PC-Sicherheit mit www.sec-check.net
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
Stueber



Anmeldungsdatum: 07.07.2008
Beiträge: 202

BeitragVerfasst am: 16.01.2010, 22:45    Titel: Antworten mit Zitat

Mit "-fpu SSE" sollte es glaube ich auch schneller gehen, hab ich aber nicht getestet.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
28398



Anmeldungsdatum: 25.04.2008
Beiträge: 1917

BeitragVerfasst am: 17.01.2010, 15:36    Titel: Antworten mit Zitat

Ich weiß nicht ob der seit zwei Jahren nicht mehr geupdatete FBC SSE2 unterstützt, aber damit würde es nochmal schneller gehen. Alternativ einfach SSE2 mithilfe von Assembler benutzen.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
croco97



Anmeldungsdatum: 04.11.2005
Beiträge: 260

BeitragVerfasst am: 17.01.2010, 19:08    Titel: Antworten mit Zitat

"Einfach" ROFL. Ungefähr genauso einfach, wie aus Sicht von funkeld eben mal schnell eine Wohnungsplanungssimulation mit Irrlicht geschrieben...

Hat jemand Lust und Know how, schnelle FP-Grundrechenroutinen unter Zuhilfenahme von SSE2 in einer Lib zur Verfügung zur stellen?

Benutzt der FBC eigentlich SSE und MMX? Wenn ja: Bei welchen Befehlen? Weiss jemand da was drüber?

Vielen Dank und VG!

Croco
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
MOD
Fleißiger Referenzredakteur


Anmeldungsdatum: 10.09.2007
Beiträge: 1003

BeitragVerfasst am: 17.01.2010, 19:30    Titel: Antworten mit Zitat

FB verwendet bei entsprechender Aufrufoption AFAIK SSE2. Näheres lässt sich im Code der fbgfx nachlesen. MMX kommt glaub ich auch zum Einsatz. Einfach mal den Source downloaden und reinschauen.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
OneCypher



Anmeldungsdatum: 23.09.2007
Beiträge: 802

BeitragVerfasst am: 18.01.2010, 10:51    Titel: Antworten mit Zitat

Welche funktion/makro ist denn nun mit welchen compiler-parametern am schnellsten?...
Das Thema interessiert mich auch lächeln
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
MOD
Fleißiger Referenzredakteur


Anmeldungsdatum: 10.09.2007
Beiträge: 1003

BeitragVerfasst am: 18.01.2010, 15:34    Titel: Antworten mit Zitat

Bei Gleitkommazahlen wie Single und Double ist es von Vorteil.
Dazu sollte man mit -fpu SSE compilieren.

Alternativ gibt es auch, was in der deutschen Referenz fehlt, aber ich mich darum kümmern werde, den Befehl Option(). Der wird wie folgt angewendet:

Code:
Declare Function ValueInXmm0 () As Double Option("sse")


Damit lassen sich also einzelne Funktionen optimieren.

edit: Natürlich nicht alternativ sondern zusätzlich, weil Option sonst ignoriert wird.

edit2: Hier jetzt der Referenzeintrag zu Option(): http://www.freebasic-portal.de/befehlsreferenz/option-614.html
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
28398



Anmeldungsdatum: 25.04.2008
Beiträge: 1917

BeitragVerfasst am: 18.01.2010, 18:07    Titel: Antworten mit Zitat

[quote="croco97"]"Einfach" ROFL. Ungefähr genauso einfach, wie aus Sicht von funkeld eben mal schnell eine Wohnungsplanungssimulation mit Irrlicht geschrieben...[quote]
Ich habe nicht von SSE2-Assembler LERNEN sondern von "...ein paar Operationen zusammenpasten...". Und das ist durchaus auch für den durchschnittlichen Programmierer kein Problem.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
dreael
Administrator


Anmeldungsdatum: 10.09.2004
Beiträge: 2529
Wohnort: Hofen SH (Schweiz)

BeitragVerfasst am: 18.01.2010, 21:37    Titel: Antworten mit Zitat

Als Anregung ein kleiner Code für wesentlich schnelleres Potenzieren:

http://beilagen.dreael.ch/QB/INT_POT.BAS

=> im Prinzip könnte man in FB dies intern so umsetzen, wenn das Exponent-Argument vom Typ Integer ist.
_________________
Teste die PC-Sicherheit mit www.sec-check.net
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden Website dieses Benutzers besuchen
Nitroxis



Anmeldungsdatum: 27.02.2008
Beiträge: 300
Wohnort: Irgendwo...

BeitragVerfasst am: 19.01.2010, 00:19    Titel: Antworten mit Zitat

Danke für die viele Hilfe... aber es als Makro zu schreiben hat gereicht Zunge rausstrecken
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC. Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

 Impressum :: Datenschutz