Linked List

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

LordArtus

Betreff: Linked List

 BeitragSo, Sep 02, 2007 14:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi ,

warum ist die Function.1 nur 20% schneller als Function.2 ?
Die Function.1 sollte theoretisch ca.80% schneller sein.

Code.1
Code: [AUSKLAPPEN]

Function Collision(b:Enemy)
   If EnemyList.Count()>1
      Local link:TLink=ListFindLink(EnemyList,b)
      Local e:Enemy
      While link<>EnemyList.LastLink()
         link=link.NextLink()
         e=Enemy(link.Value())
         If b.posx=e.posx And b.posy=e.posy
            If b.x-e.x<enemywidth And b.x-e.x>-enemywidth And b.y-e.y<enemyheight And b.y-e.y>-enemyheight
               'ListRemove(EnemyList,b)               
            EndIf
         EndIf
      Wend   
   EndIf
End Function


Code.2
Code: [AUSKLAPPEN]

Function Collision(b:Enemy)
   If EnemyList.Count()>1
      For Local e:Enemy=EachIn EnemyList
         If b.posx=e.posx And b.posy=e.posy
            If b.x=e.x And b.y=e.y
            ElseIf b.x-e.x<enemywidth And b.x-e.x>-enemywidth And b.y-e.y<enemyheight And b.y-e.y>-enemyheight
               'ListRemove(EnemyList,b)               
            EndIf
         EndIf
      Next
   EndIf
End Function


Hauptschleife
Code: [AUSKLAPPEN]

   For Local e:Enemy=EachIn EnemyList
      Collision(e)
      testcounter=testcounter+1
   Next


Hat jemand eine Idee was ich bei der Function.1 falsch mache ?

MfG

LordArtus
 

Dreamora

 BeitragSo, Sep 02, 2007 15:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Warum sollte sie schneller sein?
Dafür gibts keinen Grund

Vor allem wenn du eh planst listremove zu nehmen was ziemlich sinnfrei ist, denn Listremove muss IMMER durch die Liste iterieren zum entfernen.

Ob du For - Each oder manuelle Link Iteration nimmst macht keinen Speed Unterschied oder keinen ders Wert wäre sich den extra aufwand zu machen wenn man nicht was mit den links machen will sondern nur mit den Werten.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

LordArtus

 BeitragSo, Sep 02, 2007 16:02
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi Dreamora,
wenn Du die Funktionen näher betrachtest , braucht die Funktion 2 , fast doppelt so viele Durchläufe als Funktion 1 um alle Objekte in der Liste auf Kollision zu überprüfen , also theoretisch müsste es 100% schneller sein (ich habe einfach 20% geschwindigkeitsvorteil abgezogen) , deshalb habe ich 80% geschrieben.
Bsp. EnemyList hat 1000 Objekte , Funktion 1 macht 500500 Überprüfungen , Funktion 2 macht 1000000 Überprüfungen.
Das komische ist , habe aber einen 20% Geschwindigkeitsvorteil.Etwas bremst die Funktion 1.

MfG

LordArtus

p.s. Das mit ListRemove habe nur zum Testzwecken eingebaut.

LordArtus

 BeitragSo, Sep 02, 2007 16:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Ok , hab etwas gefunden , die Zeile ist ne ziemliche Bremse:

Code: [AUSKLAPPEN]

While link<>EnemyList.LastLink()


so ist es schneller:

Code: [AUSKLAPPEN]

Local endlink:Tlink=EnemyList.LastLink()
While link<>endlink


Bei jedem While durchlauf suchte der Interator den Link neu.
Aber trotzdem ist es jetzt noch zu langsam , ist etwa bei 50% Geschwindigkeitsvorteil.

MfG

LordArtus

LordArtus

 BeitragSo, Sep 02, 2007 17:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Ok , Problem gelöst , jetzt ist sogar 110% schneller.

Funktion 1.
Code: [AUSKLAPPEN]

Function Collision(b:Enemy,link:TLink)
   If EnemyList.Count()>1
      Local endlink:TLink=EnemyList.Lastlink()
      Local e:Enemy
      While link<>endlink
         link=link.NextLink()
         e=Enemy(link.Value())
         If b.posx=e.posx And b.posy=e.posy
            If b.x-e.x<enemywidth And b.x-e.x>-enemywidth And b.y-e.y<enemyheight And b.y-e.y>-enemyheight
               'ListRemove(EnemyList,b)               
            EndIf
         EndIf
      Wend   
   EndIf
End Function


Hauptschleife:
Code: [AUSKLAPPEN]

   Local link:TLink=EnemyList.FirstLink()
   For Local e:Enemy=EachIn EnemyList
      Collision(e,link)
      link=link.NextLink()
      testcounter=testcounter+1
   Next


MfG

LordArtus

p.s. Dreamora , manuelle Link Interation ist doch irgendwie schneller als For EachIn Wink

BladeRunner

Moderator

BeitragSo, Sep 02, 2007 19:56
Antworten mit Zitat
Benutzer-Profile anzeigen
Dennoch hätte kein Triple sein müssen. Das nächste mal tut es ein Edit. 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

LordArtus

 BeitragSo, Sep 02, 2007 21:54
Antworten mit Zitat
Benutzer-Profile anzeigen
Mit dem Edit vergesse ich es immer wieder , sorry , war keine Absicht.

MfG

LordArtus
 

Dreamora

 BeitragMo, Sep 03, 2007 10:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Wozu machst du dieses absurde Konstrukt eigentlich?

Schau dir Mal CollideImage und CollideRect an, vor allem den letzten, optionalen Parameter mit dem Objekt

Und mach dann Mal einen Benchmark deines Constructs da dagegen.

Dann wirst du verstehen warum ich meine "absurdes Konstrukt"


Den aufwand den du dir da machst musste man sich unter BlitzPlus und Blitz3D machen, unter BlitzMax ist er sinnfrei bis aktiv Performance vernichtend.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

LordArtus

 BeitragMo, Sep 03, 2007 20:08
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi,
also entweder verstehe ich nicht richtig die Funktion von CollideRect , oder CollideRect ist um einiges langsamer (habe CollideRect eingebaut und es ist , sage und schreibe ca.20mal langsamer.Mit CollideRect 8 FPS ohne 175 FPS)

Kurze Erklärung zum Code : Alle Objekte sollen miteinander kollidieren (ist etwas bugy , aber es geht nur um die Geschwindigkeit der Kollisionsüberprüfung)
Hier ein Beispielcode (ohne CollideRect):
Code: [AUSKLAPPEN]

SuperStrict
SeedRnd MilliSecs()
SetGraphicsDriver GLMax2DDriver()
Global EnemyList:TList=New TList

Const GX:Short=1280 ' horizontal resolution   
Const GY:Short=1024 ' vertical resolution

Const enemywidth:Int=10
Const enemyheight:Int=10

Const enemylimit:Short=500

Type Enemy

   Field x:Float,y:Float,xx:Float,yy:Float,direction:Short,speed:Float,posx:Byte,posy:Byte
   
   Method Move()
      If xx=Null
         xx=Sin(direction)*speed
      EndIf
      If yy=Null
         yy=Cos(direction)*speed
      EndIf       
      If x>GX-enemywidth+speed Or x<speed
         xx=-xx
      EndIf
      If y>GY-enemyheight+speed Or y<speed
         yy=-yy
      EndIf
      x=x+xx
      y=y+yy
      posx=x/(GX/10) ' only for Collision
      posy=y/(GY/10) ' only for Collision
   End Method
   
   Method Draw()
      DrawOval x,y,enemywidth,enemyheight ' Enemygraphic
   End Method
   
   Function Create:Enemy()
      Local e:Enemy=New Enemy
      e.direction=Rand(0,359) ' direction in degrees
      e.speed=Rnd(2.0,5.0)
      Local i:Byte
      Repeat
      i=True
      e.x=Rnd(e.speed,GX-enemywidth+e.speed)
      e.y=Rnd(e.speed,GY-enemyheight+e.speed)
      If EnemyList.Count()>0
         For Local ee:Enemy=EachIn EnemyList
            If e.x=ee.x And e.y=ee.y
            ElseIf e.x-ee.x<enemywidth And e.x-ee.x>-enemywidth And e.y-ee.y<enemyheight And e.y-ee.y>-enemyheight
               i=False
               Exit
            EndIf
         Next   
      EndIf
      Until i=True
      EnemyList.AddLast(e)
   End Function
   
End Type

Function Collision:Int(b:Enemy,link:TLink,i:Int)
   If EnemyList.Count()>1
      Local endlink:TLink=EnemyList.LastLink()
      Local e:Enemy
      While link<>endlink
         link=link.NextLink()
         e=Enemy(link.Value())
         If b.posx=e.posx And b.posy=e.posy
            If b.x-e.x<enemywidth And b.x-e.x>-enemywidth And b.y-e.y<enemyheight And b.y-e.y>-enemyheight
               b.xx=-b.xx ' only for
               e.yy=-e.yy ' this test           'ToDo blabla Physik etc
               i=i+1      ' collision counter
            EndIf
         EndIf
      Wend   
   EndIf
   Return i
End Function

For Local i:Int=1 To enemylimit

   Enemy.Create()
   
Next

Graphics GX,GY,32

Local a:Int=MilliSecs()
Local fps:Short=0
Local z:Short=0

Local testcounter:Short=0
Local colcounter:Int=0

While Not KeyHit (KEY_ESCAPE)

   If a+999<MilliSecs()
      a=MilliSecs()
      fps=z
      z=0
   EndIf
   
   Cls
   
   Local link:TLink=EnemyList.FirstLink()
   For Local e:Enemy=EachIn EnemyList
      e.Draw()
      colcounter=colcounter+Collision(e,link,0)
      e.Move()
      link=link.NextLink()
      testcounter=testcounter+1
   Next
   
   DrawText "FPS : "+fps+" Enemys : "+testcounter+" Col.Detect : "+colcounter,0,0
   
   Flip 0
   
   testcounter=0
   
   z=z+1 ' counter for FPS
   
Wend


Wo würdest du CollideRect einbauen ?

Die Zeile überprüft in der Funktion Collision() auf Kollision.(Objekt b mit Objekt e)
Code: [AUSKLAPPEN]

If b.x-e.x<enemywidth And b.x-e.x>-enemywidth And b.y-e.y<enemyheight And b.y-e.y>-enemyheight


Das ist etwas buggy (Richtungswechsel bei Kollision , hatte keine Lust , es physikalisch korrekt umzusetzen , deshalb verhaken sich manchmal die Objekte ineinander.Die Zeilen kann man auch auskommentieren.):
Code: [AUSKLAPPEN]

b.xx=-b.xx ' only for
e.yy=-e.yy ' this test


MfG

LordArtus
  • Zuletzt bearbeitet von LordArtus am Mo, Sep 03, 2007 20:20, insgesamt 2-mal bearbeitet
 

Dreamora

 BeitragMo, Sep 03, 2007 20:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Bei collide XX überprüft man explizit keine binären Kollisionen (a mit b oder b mit a)
Man prüft nur: Kollidiert a?
Wenn ja erhälst du einen Objekt Array zurück der die Objekte enthält mit welchem es kollidiert.


Wenn bei dir das ganze langsam wurde hast du vermutlich mit Clear Collision nach jedem Zeichnen alles wieder gelöscht und damit das gesamte Kollisionssystem ausgehebelt.
In dem Falle: Im Beginner Board von BM hats nen Sticky Thread.
Da ist der Link zu Assaris tutorials.
Schau dir die 3 Kollisionstutorials Mal an Smile


Dein Code ist natürlich auch gut, taugt aber nur solange du nicht viele a mit vielen b auf Kollision testen musst, sonst ist er einfach nur noch übelst langsam. Sprich du müsstest dir nen SceneGraph implementieren.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

LordArtus

 BeitragMo, Sep 03, 2007 20:18
Antworten mit Zitat
Benutzer-Profile anzeigen
Hab schon gelesen Dreamora.

MfG

LordArtus

p.s. Was ist ein SceneGraph ?
 

Dreamora

 BeitragMo, Sep 03, 2007 20:43
Antworten mit Zitat
Benutzer-Profile anzeigen
Prinzipiell ist ein SceneGraph eine Verwaltungsstruktur die dafür sorgt, dass du Tests nur mit Objekten machst, die dafür überhaupt in Frage kommen könnten und nur Objekte aktualisiert und gezeichnet werden die aktuell überhaupt aktiv sind (aktiv sind normalerweise jene die im Bild sind sowie in einem gewissen Bereich um das Bild).
Als Beispiel: Wenn du rechts oben auf eine Kollision prüfst ist es Quatsch mit Objekten links unten auf Kollision zu testen, denn das kann eigentlich nicht eintreten im Normalfall.


Das ist etwas, was du mit dem BM Kollisionssystem schonmal prinzipiell machen kannst, denn es testet nur lokal auf Kollision, nicht mit allem. Deswegen hat es auch die 2 Operationen "Kollision schreiben" und "Kollision lesen" sowie viele verschiedene Layer um dies zu tun, so dass sich total unterschiedliche Kollisionstypen nicht gegenseitig reinpfuschen.
Ich kenne für das Kollisionssystem nur einen Fall der "ungünstig" ist:
Dieser Fall tritt ein, wenn alle mit allen kollidieren können, nicht nur 2 oder 3 Gruppen gegenseitig aber nicht untereinander (zb Raketen vom Spieler mit dem Gegner oder ein Mauspointer mit vielen Gadgets).

Mit mehreren Gruppen ist das deswegen kein Problem weil du alle Objekte der Gruppe A zb in einen Layer schreibst, während Objekte der anderen Gruppen nur Kollision lesen, aber keine Schreiben. Das geht in Windeseile.

Speziell wenn man Layer nur neu zeichnet, wenn sich überhaupt etwas geändert hat, gewinnt man unmengen an Rechnenzeit. Diese Optimierung kannst du natürlich bei dir auch integrieren.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

LordArtus

 BeitragDi, Sep 04, 2007 20:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi,
erstmal danke für die Tipps und Erklärungen.
Hab etwas rumprobiert und das ist das Ergebnis:

Code: [AUSKLAPPEN]

SuperStrict
SeedRnd MilliSecs()
SetGraphicsDriver GLMax2DDriver()
Global EnemyList:TList=New TList

Const GX:Short=1280 ' horizontal resolution   
Const GY:Short=1024 ' vertical resolution

Const enemylimit:Short=1000

Global EnemyImg:TImage=LoadImage("C:\Dokumente und Einstellungen\LordArtus\Desktop\Meine BMAX Progs\EnemyTestImg1.jpg")
Global enemywidth:Int=ImageWidth(EnemyImg)
Global enemyheight:Int=ImageHeight(EnemyImg)

Type Enemy

   Field x:Float,y:Float,xx:Float,yy:Float,direction:Short,speed:Float
   
   Method Move()
      If xx=Null
         xx=Sin(direction)*speed
      EndIf
      If yy=Null
         yy=Cos(direction)*speed
      EndIf       
      If x>GX-enemywidth+speed Or x<speed
         xx=-xx
      EndIf
      If y>GY-enemyheight+speed Or y<speed
         yy=-yy
      EndIf
      '-----------------------------------
      If CollideImage(EnemyImg,x,y,0,1,0)
         xx=-xx
         yy=-yy
      Else
         CollideImage(EnemyImg,x,y,0,0,1)
      EndIf
      '-----------------------------------
      x=x+xx
      y=y+yy
   End Method
   
   Method Draw()
      DrawImage EnemyImg,x,y ' Enemygraphic
   End Method
   
   Function Create:Enemy()
      Local e:Enemy=New Enemy
      e.direction=Rand(0,359) ' direction in degrees
      e.speed=Rnd(2.0,5.0)
      Local i:Byte
      Repeat
      i=True
      e.x=Rnd(e.speed,GX-enemywidth+e.speed)
      e.y=Rnd(e.speed,GY-enemyheight+e.speed)
      If EnemyList.Count()>0
         For Local ee:Enemy=EachIn EnemyList
            If e.x=ee.x And e.y=ee.y
            ElseIf e.x-ee.x<enemywidth And e.x-ee.x>-enemywidth
               If e.y-ee.y<enemyheight And e.y-ee.y>-enemyheight
                  i=False
                  Exit
               EndIf
            EndIf
         Next   
      EndIf
      Until i=True
      EnemyList.AddLast(e)
   End Function
   
End Type

For Local i:Int=1 To enemylimit

   Enemy.Create()
   
Next

Graphics GX,GY,32

Local a:Int=MilliSecs()
Local fps:Short=0
Local z:Short=0

Local testcounter:Short=0

While Not KeyHit (KEY_ESCAPE)

   If a+999<MilliSecs()
      a=MilliSecs()
      fps=z
      z=0
   EndIf
   
   Cls
   
   For Local e:Enemy=EachIn EnemyList
      e.Draw()
      e.Move()
      testcounter=testcounter+1
   Next
   
   DrawText "FPS : "+fps+" Enemys : "+testcounter,0,0
   
   Flip 0
   
   testcounter=0
   
   z=z+1 ' counter for FPS
   
   ResetCollisions()
   
Wend


scheint das gleiche zu tun (bin aber noch nicht ganz sicher) und ist etwa 80% schneller.

Änderungen :

-meine Funktion Collison() ausgeschaltet
-bei der Methode Move() das eingebaut:

Code: [AUSKLAPPEN]

      If CollideImage(EnemyImg,x,y,0,1,0)
         xx=-xx ' only for Test
         yy=-yy ' only for Test
      Else
         CollideImage(EnemyImg,x,y,0,0,1)
      EndIf


So wie ich CollideImage() verstehe , erstell es beim Schreiben des gleichen Layers eine interne Liste , die erst bei ResetCollisions() , gelöscht wird.Hoffe verstehe es richtig.Oder wird der Layer in meinen Objekt abgespeichert (wäre etwas komisch aber naja , es könnte auch so sein) ???

MfG

LordArtus

p.s. Blöd finde ich , dass die Erklärungen zu den Befehlen (oder Funktionen) bei BMax-Help so spärlich sind.

Edit: Code etwas sauberer gemacht
 

Dreamora

 BeitragMi, Sep 05, 2007 9:18
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja mehr oder weniger stimmt das.
Aber nur mehr oder weniger, denn das Kollisionssystem ist um einige Stufen mächtiger:

1. Die Reihenfolge mit der du Dinge reinschreibst bleibt erhalten, du erhälst also damit eine Tiefensortierung. Wenn du A,B,C reinschreibst und dann etwas damit kollidiert, wird im Array den du vom Kollision lesen zurück erhälst ebenfalls A,B,C in der Reihenfolge sein.

2. Du kannst beim Schreiben der Kollision eine Objektreferenz mit übergeben. Diese Referenz wird dann beim lesen im Kollisionsarray stehen! Da muss nicht zwingend TImage drin stehen. Ich empfehle daher einen "Kollisionsgrundtyp" zu erstellen der da genutzt wird, damit du weisst, nach was du das Object das du im Array hast casten musst um es zu verwenden. Abstrakte Methoden zb lassen da grüssen Smile

3. Du musst Arrays nur dann Resetten wenn sie sich ändern. Aber es gibt vermutlich auch Layer die sich nie oder nur sehr selten ändern (der Kollisionslayer einer Tilemap wär so ein Fall zb, wenn dein Spiel im Zelda Stil ist mit "Räumen").
Deswegen kann man selbst auswählen in welchen Layer man schreibt und vor allem in ResetCollisions welche Layer man löschen will!


Ich hab das ganze damals testweise Mal mit nem UI gemacht das Blitz Kollision nutzt anstatt rumgemathehampel.
Das Resultat war sauberer und sehr schneller Code.
Sauber weil du zb viel weniger Probleme hast mit onEnter, onLeave und welches zb das oberste Gadget ist, denn das ist alles trivialerweise durch den Array des Kollisionslesen schon gelöst!

Derzeit versuche ich das ganze soweit zu abstrahieren und designen, dass ich ein simples Kollisionssystem habe das nur noch send collision und receive collision besitzt, sowie onCollision Callbacks die man setzen kann. (bin nicht fan von Event gehacke. Warum einen Hook wenn ich direkt einen EventHandler aufrufen kann??)
Der Rest soll bei Veränderung automatisch im Hintergrund gemacht werden.

Läuft bis anhin garnicht schlecht muss ich sagen, muss nur noch einige der Hintergrund Algorithmen redesignen oder komplett ersetzen, damit sie sich ein wenig intelligenter verhalten Wink
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

LordArtus

 BeitragDo, Sep 06, 2007 20:19
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi,

danke nochmal für die Tipps , ich melde mich wieder , wenn ich etwas "gutes" zu zeigen habe.

MfG

LordArtus

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group