Längenberechnung mal anders

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

 

sinjin

Betreff: Längenberechnung mal anders

BeitragMo, Aug 22, 2016 4:55
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich bin nicht der beste im Erklären aber na schön. Da ich Spiele mag die ohne Scrolling auskommen habe ich mir gedacht, ich mache ein "Bild" in dem schon alle Längen zum Nullpunkt vorberechnet wurden, das heisst ich brauche nie wieder im Programm die Entfernung zwischen 2 Punkten auf die herkömmliche Art und Weise berechnen (ein Bild deshalb weil 4 Pixel mit Alphakanal braucht genausoviel Speicher!). Ich habe ein Quadrat beliebiger größe (Exponientiell 2, da ich statt Teilen Bitshifting anwende), z.B. kann man die Wurzeln auf den ganzen Bildschirm vorberechnen. Dann dachte ich mir, was ist wenn der Punkt ausserhalb des vorberechneten Bereiches liegt. Nun, dann kann man ein Muster anwenden das sich immer wiederholt. Ich schneide die Linie innerhalb des bekannten Bereiches ab, dann schaue ich wie oft sich dieses Muster wiederholt und addiere die restliche Länge. Mit "Muster" meine ich den bekannten Bereich. Und es wird nicht "gezählt", nur berechnet, ich habe die Variable nur so genannt, weil ich beim Testen eine rekursive Funktion genutzt habe, nun ist hier nichts mehr rekursiv! Ausser die Lowestbit-Funktion, aber die wird auch nur einmal aufgerufen.

Code: [AUSKLAPPEN]
type tsqrt
  field roots#[][]
  field size#,bit%

  method init(siz0%=256) 'power of 2
    size=siz0
    bit=lobit(siz0) '256=bin 0000 0001 0000 0000
'                                    8 7654 3210
'Speicher reservieren
    siz0:+1
    roots=roots[..siz0]
    for local y%=0 until siz0
      roots[y]=roots[y][..siz0]
    next

'Den Speicher mit allen möglichen Längen vorberechnen (Wurzeln)
    for local y%=0 until siz0
      local yy%=y*y
      for local x%=y until siz0
        local s#=sqr(x*x+yy)
        roots[y][x]=s
        roots[x][y]=s
      next
    next
  endmethod

  method asqr#(x#,y#)
    local x1#=x,y1#=y
    local count%
    if (x1>y1) then
'count=die Wiederholungen der maximalen Länge innerhalb eines Musters
      count=int(x1) shr bit
'Die Linie abschneiden
      y1=y1/x1*size
      x1=size
    else
      count=int(y1) shr bit
      x1=x1/y1*size
      y1=size
    endif
'roots[y1][x1]*count   =   die maximale Länge innerhalb eines Musters*Wiederholungen
'roots[y-y1*count][x-x1*count]   =   Die restliche Länge dazu addieren
    return roots[y1][x1]*count + roots[y-y1*count][x-x1*count]
  endmethod
endtype


Ich kann es nicht anders Beschreiben, ich kann es nur visualisieren, was eh immer das Beste ist!

Wenn man folgenden Code nimmt, kommt es geschwindigkeitsmäßig sogar fast an den einen SQR-Befehl in Assembler heran (Vorrausgesetzt man berechnet auch noch A^2+B^2, eventuell kann man den gesamten hier gezeigten Code noch in Assembler optimieren, was keiner mehr verstehen würde).

Im folgenden Beispiel habe ich einfach den größeren Punkt, bzw der Punkt liegt wiederum ausserhalb des vorberechneten Bereiches, auf das kleinere Quadrat (den bekannten Bereich) reduziert. Und ich denke bei diesem Codeschnipsel bedarf es auch keine weitere Erklärung.

Code: [AUSKLAPPEN]
  method asqr2#(x%,y%)
    local a%=1
    if (x>y) then
      a:+x shr bit
    else
      a:+y shr bit
    endif
    return roots[y/a][x/a]*a
  endmethod


Wenn man den ganzen Bildschirm berechnen will dann braucht man nur noch:
Code: [AUSKLAPPEN]
roots[y][x]

Das ist das schnellste! Ich habe mit Absicht X und Y überall vertauscht weil ich weiss, dass die Arrays so besser/schneller berechnet werden, in einigen Fällen ist das so, dass müsst ihr euch selber zusammen suchen wie das funktioniert, das ist hier auch nicht das Thema.

Und ja, das soll nur als Denkansatz für andere dienen. Ich werde weiter an den Wurzeln forschen, es dauert halt nur immer länger neue Ansätze zu finden. Der Geschwindigkeitszusatz ist enorm, wenn man halt wie gesagt, das ganze Spielfeld (das geht auch mit Tilemaps) in Längen vorberechnet, es braucht nie wieder die Formel SQR(x^2+y^2) berechnet zu werden. Ich weiss nicht genau (darum geht es mir auch gar nicht), aber wenn der Punkt 5-6 mal so weit entfernt ist wie der vorberechnete Bereich kann es zu einem Längenunterschied zu 1 kommen. Es ging mir lediglich darum den SQR-Befehl loszuwerden, bzw gar keine Wurzeln mehr während der Laufzeit zu berechnen.

Xerxes: Was du jetzt mit Stichworten meinst, weiss ich nicht. Kann ich irgendwo Tags machen wie bei Youtube? Wenn du mein Video "offline" nehmen möchtest...haha. Ich mache nur Spass, ich hoffe dir gefällt das jetzt so. Jeder darf meinen Code haben, das wird mich nicht daran hindern weiter nachzudenken. Einen allerletzten Edit noch: Danke, dass du mir in den A...rm getreten hast Very Happy
  • Zuletzt bearbeitet von sinjin am Mi, Aug 24, 2016 22:10, insgesamt 18-mal bearbeitet

Xeres

Moderator

BeitragMo, Aug 22, 2016 19:45
Antworten mit Zitat
Benutzer-Profile anzeigen
Bitte füge ein Erklärung zu dem Code in deinem Beitrag hinzu.
Videos werden offline genommen und Texte ohne Stichworte werden mit keiner Suche gefunden.

Ab welcher Größenordnung macht sich der Unterschied bemerkbar? Also als Abweichung von der normalen Quadratwurzelfunktion und wie viel Zeit gewinnt man dadurch?
Oder auch: Welche Anwendung braucht derartige Optimierungen?
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

sinjin

BeitragMi, Aug 24, 2016 22:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich überlege/programmiere wenn ich geraucht habe, ich erkläre, wenn ich getrunken habe....Zigaretten und Wasser Very Happy ach komm, ich lösche das selbst....

FireballFlame

BeitragMi, Aug 24, 2016 22:59
Antworten mit Zitat
Benutzer-Profile anzeigen
Die lobit-Funktion ist in deinem Code nicht mit enthalten.
PC: Intel Core i7 @ 4x2.93GHz | 6 GB RAM | Nvidia GeForce GT 440 | Desktop 2x1280x1024px | Windows 7 Professional 64bit
Laptop: Intel Core i7 @ 4x2.00GHz | 8 GB RAM | Nvidia GeForce GT 540M | Desktop 1366x768px | Windows 7 Home Premium 64bit
 

sinjin

BeitragDo, Aug 25, 2016 1:10
Antworten mit Zitat
Benutzer-Profile anzeigen
@FireballFlame ich hoffe du kommst in deinem Universum klar, ist es Das worum es geht!!!?! Der schönste zu sein? (Du editierst schneller als ich antworten kann, ich editiere und das bleibt auch!) Naja, für mich nicht. Ich kann es auch noch 1000mal bearbeiten. Aber hast du verstanden was ich gemacht habe? Also hast du den Code verstanden? Wenn ja, bitte poste etwas Code, was mich weiter bringt! Die Lowbit-Funktion habe ich mit dem Comment erklärt! Der sollte auch direkt unter der 8 anfangen.....Ich entschuldige mich, auch gerne mehrfach, dafür, dass ich mich nicht als Mensch fühle. Ganz ehrlich? Das bringt MICH weiter, was mit anderen passiert ist mir egal... habe ich schon beantwortet, sowas bringt mich nicht ab weiter Nachzudenken!
Who is asking????
Code: [AUSKLAPPEN]
function lobit%(src%,ln%=32)
  local b%
  repeat
    if (src&1) then return b
    b:+1
    src:shr 1
  until (b=ln)
endfunction

There it is, that concludes all my wisdom!!!! About this chapter at last! You dont wanna know what I derived from NOTHING!!! lol And I for my own, will think about at least square roots, the code i have done is about triple roots.....but that doesnt concern you nonsoever! sry
 

sinjin

BeitragDo, Aug 25, 2016 1:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Es mag total abwegig sein, bevor jmd antwortet, der einzige dem ich es zuschreibe ist Midimaster, und ich weiss selber nichts über fast-fourier-transformations...Midimaster ist für mich jmd der es auch erklären kann. Ich kann es nicht! (Eventuell kann ich es tun, Time-Streching, dann aber nur auf meine Art) Es geht auch nicht um FastFourierTransformations. Ich nenne meine eigene Erfingung: Feld-Längen-Theorie Very Happy Es mag sein, ich habe nie behauptet, das alles kommt von mir, es kommt alles aus meinem Gehirn, wenn jemand vorher schon mal sowas gemacht hat, ok!!!!! Ich habe aber bisher noch nie gesehen, das jemand die Längen auf diese Weise angewandt hat. Wir arbeiten schließlich alle zusammen, oder nicht? Ich sehe das so, fertig, mögen andere aus dem Code was machen! Und ja, die Musik "spielt" für mich eine grosse Rolle, so ferner glaube ich, das Luftlose-Antriebe mit Ton (Sound) funktionieren werden.

DAK

BeitragDo, Aug 25, 2016 12:35
Antworten mit Zitat
Benutzer-Profile anzeigen
Äh, fehlen hier ein paar Posts? Irgendwie fehlt mir der Kontext zu den letzten beiden Posts. Wo kommt die Fouriertransformation her?

Wie dem auch sei, Back to topic:
Ich find diese Idee der Längenberechnung ziemlich cool. Überraschend, dass sie wirklich schneller ist, als simples quadrieren und wurzelziehen. Hab es noch nicht ausprobieren können, nehm also mal dein Wort für die Geschwindigkeit.

Wenn ich das optimieren will, und es nicht darum geht, die Länge rauszubekommen, sondern nur selbige zu vergleichen (z.B. um zu checken, ob was in Reichweite ist), dann bleib ich bei c^2=a^2+b^2, quadriere also die Vergleichslänge, statt die Wurzel vom Ergebnis zu ziehen. Das ist deutlich schneller. Schaut dann etwa so aus:

BlitzBasic: [AUSKLAPPEN]
If a*a+b*b<=c*c Then


Dann ist man runter auf drei Multiplikationen, schneller wird's dann kaum mehr.
Gewinner der 6. und der 68. BlitzCodeCompo

BladeRunner

Moderator

BeitragDo, Aug 25, 2016 13:19
Antworten mit Zitat
Benutzer-Profile anzeigen
sinjin,
egal was Du da geraucht oder getrunken hast - die Dosierung war falsch.
Das hier ist nicht deine Selbstdarstellungsbühne und sich bei FBF zu beschweren weil er seine Posts editiert obwohl Du selbst von deinen Ursprungspostings nahezu nichts mehr übrig gelassen hast ist schon ein wenig... merkwürdig.

Wenn Du also nun dieser speziellen geistigen Verfassung bist - und das ist ja jetzt nicht zum ersten mal passiert - spar dir bitte das Erstellen von Beiträgen bis sie vorüber ist.

Sieh es als freundschaftliche Aufforderung, aber sei dir auch gewiss dass eine Wiederholung in einer Verwarnung mündet.

Codearchiv: Fertige, funktionsfähige Codes, bitte kommentiert und erklärt. Alles andere gehört hier nicht her. Danke.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI

Stolzer Gewinner des BAC#48, #52 & #92

FireballFlame

BeitragDo, Aug 25, 2016 20:09
Antworten mit Zitat
Benutzer-Profile anzeigen
DAK hat Folgendes geschrieben:
Ich find diese Idee der Längenberechnung ziemlich cool. Überraschend, dass sie wirklich schneller ist, als simples quadrieren und wurzelziehen. Hab es noch nicht ausprobieren können, nehm also mal dein Wort für die Geschwindigkeit.

Cool schon, aber ich habe mal einen simplen Geschwindigkeitstest dafür geschrieben, und wenn man dem Glauben schenken kann, ist sie leider langsamer.

BlitzMax: [AUSKLAPPEN]
SuperStrict
Framework brl.standardio
Import brl.math


Local t:tsqrt = New tsqrt
t.init
GCCollect
Delay 500
GCCollect
GCSuspend
Local val:Double
Local ms:Int = MilliSecs()
For Local i:Int = 1 To 100
For Local x:Int = -500 To 500
For Local y:Int = -500 To 500
val :+ Sqr(x*x + y*y)
'val :+ t.asqr(Abs x, Abs y)
'val :+ t.asqr2(Abs x, Abs y)
Next
Next
Next
ms = MilliSecs() - ms
GCResume

Print val
Print ms + "ms"
Input ""







Type tsqrt
Field roots#[][]
Field size#,bit%

Method init(siz0%=256) 'power of 2
size=siz0
bit=8'lobit(siz0) '256=bin 0000 0001 0000 0000
' 8 7654 3210
'Speicher reservieren
siz0:+1
roots=roots[..siz0]
For Local y%=0 Until siz0
roots[y]=roots[y][..siz0]
Next

'Den Speicher mit allen möglichen Längen vorberechnen (Wurzeln)
For Local y%=0 Until siz0
Local yy%=y*y
For Local x%=y Until siz0
Local s#=Sqr(x*x+yy)
roots[y][x]=s
roots[x][y]=s
Next
Next
EndMethod

Method asqr#(x#,y#)
Local x1#=x,y1#=y
Local count%
If (x1>y1) Then
'count=die Wiederholungen der maximalen Länge innerhalb eines Musters
count=Int(x1) Shr bit
'Die Linie abschneiden
y1=y1/x1*size
x1=size
Else
count=Int(y1) Shr bit
x1=x1/y1*size
y1=size
EndIf
'roots[y1][x1]*count = die maximale Länge innerhalb eines Musters*Wiederholungen
'roots[y-y1*count][x-x1*count] = Die restliche Länge dazu addieren
Return roots[y1][x1]*count + roots[y-y1*count][x-x1*count]
EndMethod
Method asqr2#(x%,y%)
Local a%=1
If (x>y) Then
a:+x Shr bit
Else
a:+y Shr bit
EndIf
Return roots[y/a][x/a]*a
EndMethod
EndType

Ist kein sehr guter Test: nur eine einzige Messung, und das Ergebnis schwankt natürlich, wenn man das Programm mehrfach ausführt. Aber grob geschätzt komme ich im Durchschnitt auf:

Sqr(x*x + y*y): ~1350ms
asqr(Abs x, Abs y): ~5000ms
asqr2(Abs x, Abs y): ~1600ms

Wenn man das verschachtelte roots#[][]-Array in sinjins Code durch ein [,]-Array ersetzt, kann man noch etwas mehr Tempo rausholen, aber an das gute alte Sqr kommt es, auf meinem Rechner zumindest, trotzdem nicht ran.
Ich habe übrigens eine andere Funktion für solche Zwecke, die auf ca. 1100ms kommt, also tatsächlich schneller ist. Dafür ist sie deutlich ungenauer. Wenn Interesse besteht, kann ich die auch mal ins Codearchiv stellen.
PC: Intel Core i7 @ 4x2.93GHz | 6 GB RAM | Nvidia GeForce GT 440 | Desktop 2x1280x1024px | Windows 7 Professional 64bit
Laptop: Intel Core i7 @ 4x2.00GHz | 8 GB RAM | Nvidia GeForce GT 540M | Desktop 1366x768px | Windows 7 Home Premium 64bit
 

Matthias

Betreff: Ungenaue Sqr.

BeitragFr, Aug 26, 2016 17:11
Antworten mit Zitat
Benutzer-Profile anzeigen
@FireballFlame

Genau das suche ich.

Habe mir schon die ganze Zeit gedacht, das eine schnellere Sqr kaum noch geht.
Alledings kann ich mir auch denken das wenn mann es nicht so genau haben will dann müste mann da noch etwas Schnelligkeit raus bekommen.

Es geht um ein Spiel wo Raumschiffe andere Raumschiffe jagen.
Ist das gegneriche Raumschiff weit weg dann kann stark beschleunigt werden, ist es nahe dran muss abgebremst werden.

Da sowieso ständig neu geprüft wird, mus die Entfernug bei weiten Distanzen nicht genau sein.
Nur annähernd.

Mich würde dein Code sehr interessieren.

Mit freundlichen Gruß Matze.
 

sinjin

BeitragSo, Jul 01, 2018 3:20
Antworten mit Zitat
Benutzer-Profile anzeigen
Tja Fireball, ich sagte nie das es schneller sei, nur das es schon nah ran kommt, ohne Assembler Very Happy Aber Danke fürs Feedback Very Happy

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group