verkettete Listen für GLBasic

[Quentin]

Ich wünsche mir zu Weihnachten verkettete Listen in GLBasic.

Klar sind Arrays in GL einfach zu handhaben und mit REDIM/DIMPUSH auch sehr schön dynamisch zu verwalten. Auch die Performance ist in Ordnung, solange man nur einige hundert Elemente darin verwaltet. Werden es jedoch einige Tausend, geht der Rechner schnell in die Knie, vor allem wenn man während der Hauptschleife mit REDIM & Co arbeitet.

Wenn ich das richtig verstanden habe, wird bei jedem REDIM/DIMPUHS das komplette Array umgeschaufelt, also Speicher für die neue Größe allokieren, Daten umschaufeln, Speicher für das alte Array freigeben. Je größer das Array umso mehr Zeit wird dafür benötigt.

[Kitty Hello]

Falsch.
Intern alloziiert GLBaic "intelligent" etwas mehr, damit nicht jedesmal neu alloziiert werden muss. Darum sind die Arrays auch viel viel schneller als Verkettete Listen.
Bei mehr als 1000 Elementen, die man an willkürlichen Positionen löschen will ist eine Verkettete Liste evtl. schneller. Aber: Das durchlaufen der Kette ist dann wieder langsamer.
Was für ein Problem hast Du denn konkret?

[Quentin]

Aktuell:
Exzessive Partikel-Spielereien. Da kommt halt eben ganz schön was zusammen, wobei ich schnell bei mehreren tausend Partikeln bin. Ok, zugegeben, ich habe das etwas übertrieben, auch um mal zu testen, was machbar ist und was nicht.
Dann wäre es dann wohl sinnvoller, die Anzahl der Partikel zu begrenzen und mit einem Array fester Größe zu arbeiten.

Dann noch eine Frage zu Type-Arrays: Wird auch hier prinzipiell mit 4 Dimensionen gearbeitet?

[trucidare]

Ähm.... Bahnhof?

[Kitty Hello]

OK. Ist einfach ein Designfehler für GLBasic.
Mach's so:
Jeder Partikel hat eine Zeit, zu der er "Zerfällt".
Zeichne nur Partikel, die noch nicht zerfallen sind (die Abfrage ist schnell, wenn Du mit FOREACH arbeitest)
Wenn Du neue Partikel hinzufügt, dann such immer nach zerfallenen, und überschreib die. Gibt es nicht genug davon, mach hinten neue dran mit REDIM -> hier evtl. selbst großzügig in 100er Schritten erweitern.
So mach ich's auch immer und das fetzt.

Edit:
Type arrays sind arrays. Ja, immer 4 Dimensionen.
Ich wollte mal was einbauen, dass GLBasic erkennt, wieviele Dimensionen man maximal verwendet hat und evtl. den kompletten Kern dahingehend reduziert. Könnte was bringen.

[Quentin]

Ja genauso hatte ich mir das jetzt gedacht. Array fester Größe und die "freiwerdenden" Stellen neu besetzen. Danke.

//EDIT

hier mal als Vergleich ein Beispiel. Ok, über Sinn und Unsinn mag man sich streiten, aber wie gesagt ging es mir hier eher darum, das Machbare auszureizen.

eine kleine Beispielgrafik kann mit der Maus über den Bildschirm bewegt werden und zieht dabei eine Partikelspur hinter sich hier. Die Partikel sind einfach nur Punkte, die langsam verblassen.

1. Beispiel
Jedes Partikel wird mit DIMPUSH hinzugefügt. Je nachdem, wie schnell man die Maus über den Bildschirm jagt, kamem bei Tests hier locker mal über 15.000 Partikel zusammen. Das brachte den Rechner doch arg ins Ruckeln

Code (glbasic) Select Expand

TYPE t_smoke
  x
  y
  color
ENDTYPE
LOCAL smoke[] AS t_smoke


SETTRANSPARENCY RGB(0, 0, 0)
DRAWRECT 0, 0, 40, 40, RGB(0, 0, 0)
STARTPOLY -1
  POLYVECTOR 20, 0, 0, 20, RGB(80, 80, 80)
  POLYVECTOR 0, 20, 20, 40, RGB(120, 120, 120)
  POLYVECTOR 20, 40, 40, 20, RGB(200, 200, 200)
  POLYVECTOR 40, 20, 20, 0, RGB(80, 80, 80)
ENDPOLY
GRABSPRITE 0, 0, 0, 40, 40


LOCAL mx, my, b1, b2, oldx, oldy

GETSCREENSIZE scx, scy
mx = oldx = scx / 2
my = oldy = scy / 2
SETMOUSE mx, my

WHILE TRUE
  MOUSESTATE mx, my, b1, b2
  IF mx <> oldx OR my <> oldy
    create_smoke(mx, my, oldx, oldy, 20, smoke[])
  ENDIF
  oldx = mx
  oldy = my
  draw_smoke(smoke[])
  DRAWSPRITE 0, mx, my
  SHOWSCREEN
WEND



// ------------------------------------------------------------- //
// -=#  RAND  #=-
// (C) by Big Daddy Schranzor the double-post-killer
// ------------------------------------------------------------- //
FUNCTION RAND: minimum, maximum
  RETURN minimum + RND(-minimum + maximum)
ENDFUNCTION // RAND


// ------------------------------------------------------------- //
// -=#  CREATE_SMOKE  #=-
// ------------------------------------------------------------- //
FUNCTION create_smoke: x1, y1, x2, y2, radius, smoke[] AS t_smoke

  LOCAL tx, ty, count, col, i, k
  LOCAL ls AS t_smoke

  IF x1 > x2
    tx = x1
    x1 = x2
    x2 = tx
  ENDIF

  IF y1 > y2
    ty = y1
    y1 = y2
    y2 = ty
  ENDIF

  count = SQR(POW(x2 - x1, 2)  + POW(y2 - y1, 2))
  IF count < 1 THEN RETURN

  facx = (x2 - x1) / count
  facy = (y2 - y1) / count

  FOR i = 0 TO count
    //FOR k = 0 TO radius
      ls.x = x1 + SIN(i*facx) + RAND(-radius, radius) + radius
      ls.y = y1 + COS(i*facy) + RAND(-radius, radius) + radius
      ls.color = RGB(128, 128, 128)
      DIMPUSH smoke[], ls
    //NEXT
  NEXT

ENDFUNCTION // CREATE_SMOKE


// ------------------------------------------------------------- //
// -=#  DRAW_SMOKE  #=-
// ------------------------------------------------------------- //
FUNCTION draw_smoke: smoke[] AS t_smoke

  LOCAL ls AS t_smoke

  FOREACH ls IN smoke[]
    SETPIXEL ls.x, ls.y, ls.color
    DEC ls.color, RGB(1, 1, 1)
    IF ls.color <= RGB(10, 10, 10) THEN DELETE ls
  NEXT

ENDFUNCTION // DRAW_SMOKE2. Beispiel

Im Prinzip das gleiche Coding, aber die Partikel werden wie von Gernot vorgeschlagen in einem Array fester Größe (hier 5.000) gespeichert. Die Lebensdauer der Partikel ist der Farbwert (COLOR). Ist dieser 0, kann die Stelle im Array neu besetzt werden (siehe create_smoke).
Bei sehr schneller Bewegung der Maus über den Bildschirm kann es passieren, daß keine neuen Partikel erstellt werden können, weil das Array "voll" ist. Aber immerhin gibt es so keine Ruckler mehr

Code (glbasic) Select Expand

TYPE t_smoke
  x
  y
  color
ENDTYPE
LOCAL smoke[] AS t_smoke
LOCAL MAX_SMOKE = 5000
DIM smoke[MAX_SMOKE]


// Beispielgrafik
SETTRANSPARENCY RGB(0, 0, 0)
DRAWRECT 0, 0, 40, 40, RGB(0, 0, 0)
STARTPOLY -1
  POLYVECTOR 20, 0, 0, 20, RGB(80, 80, 80)
  POLYVECTOR 0, 20, 20, 40, RGB(120, 120, 120)
  POLYVECTOR 20, 40, 40, 20, RGB(200, 200, 200)
  POLYVECTOR 40, 20, 20, 0, RGB(80, 80, 80)
ENDPOLY
GRABSPRITE 0, 0, 0, 40, 40


LOCAL mx, my, b1, b2, oldx, oldy

GETSCREENSIZE scx, scy
mx = oldx = scx / 2
my = oldy = scy / 2
SETMOUSE mx, my

WHILE TRUE
  MOUSESTATE mx, my, b1, b2
  IF mx <> oldx OR my <> oldy
    create_smoke(mx, my, oldx, oldy, 20, smoke[])
  ENDIF
  oldx = mx
  oldy = my
  draw_smoke(smoke[])
  DRAWSPRITE 0, mx, my
  SHOWSCREEN
WEND



// ------------------------------------------------------------- //
// -=#  RAND  #=-
// (C) by Big Daddy Schranzor the double-post-killer
// ------------------------------------------------------------- //
FUNCTION RAND: minimum, maximum
  RETURN minimum + RND(-minimum + maximum)
ENDFUNCTION // RAND


// ------------------------------------------------------------- //
// -=#  CREATE_SMOKE  #=-
// ------------------------------------------------------------- //
FUNCTION create_smoke: x1, y1, x2, y2, radius, smoke[] AS t_smoke

  LOCAL tx, ty, count, col, i, k
  LOCAL ls AS t_smoke

  IF x1 > x2
    tx = x1
    x1 = x2
    x2 = tx
  ENDIF

  IF y1 > y2
    ty = y1
    y1 = y2
    y2 = ty
  ENDIF

  count = SQR(POW(x2 - x1, 2)  + POW(y2 - y1, 2))
  IF count < 1 THEN RETURN

  facx = (x2 - x1) / count
  facy = (y2 - y1) / count

  FOR i = 0 TO count
    FOREACH ls IN smoke[]    // freie Stelle suchen
      IF ls.color = 0
        ls.x = x1 + SIN(i*facx) + RAND(-radius, radius) + radius
        ls.y = y1 + COS(i*facy) + RAND(-radius, radius) + radius
        ls.color = RGB(128, 128, 128)
        BREAK                // wenn gefunden, dann FOR-Schleife verlassen
      ENDIF
    NEXT
  NEXT

ENDFUNCTION // CREATE_SMOKE


// ------------------------------------------------------------- //
// -=#  DRAW_SMOKE  #=-
// ------------------------------------------------------------- //
FUNCTION draw_smoke: smoke[] AS t_smoke

  LOCAL ls AS t_smoke

  FOREACH ls IN smoke[]
    SETPIXEL ls.x, ls.y, ls.color
    DEC ls.color, RGB(1, 1, 1)
    IF ls.color <= RGB(10, 10, 10) THEN ls.color = 0
  NEXT

ENDFUNCTION // DRAW_SMOKE