Frage Pixelmovement Kollisionsabfrage

[Cornix]

Ich habe es nicht getestet, ich bin einfach davon ausgegangen, dass der Zugriff auf eine Zelle einer Tabelle nicht so viel arbeit kosten sollte wie all die Rechenoperationen und der Vergleich der Farbe eines Pixels.


Nun, 30 Megabyte sind immernoch eine gehörige Menge, auch wenn sie sich dadurch schon beachtlich verringert hat.
Den Beigefügten Script allerdings verstehe ich nichteinmal ansatzweise.

Ich versuche hierbei möglichst viel zu verstehen und zu lernen, einen Script einfach nur zu kopieren ist nach meiner Ansicht ein Schritt in die falsche Richtung.
Ich kann den Script leider im Moment nicht testen, daher kann ich nicht sagen ob er mir hilft mein kleines Problem zu lösen.

Könntest du mir vielleicht genauere Informationen zu dem Script und dessen Funktionen geben; oder vielleicht einen Hinweis wo ich mehr über das Zlib Module erfahren kann, ich habe derartiges noch nicht in der Hilfe-Datei des Makers gefunden.

Vielen Dank soweit für die Hilfe.

[-KD-]

Zur BitTable2D Klasse: Grundidee ist es ein Array aus Bits zu erstellen, so dass man einzelne Bits ansehen und ändern kann. Die kleinste Einheit für ein Objekt in Ruby ist aber 4 Byte (bzw. 8 Byte bei 64 Bit Systemen). D.h. jedes Element eines Rubyarrays kostet dich immer mindestens 4 Byte Speicher. Darum bietet die RGSS die Table-Klasse, bei der die Elemente nur 2 Byte groß sind und dadurch speichereffizienter sind. Aber um 1 Bit große Elemente zu bekommen musst du auf Strings zurückgreifen. Ein String ist ein Array aus Characters, wobei jeder Character ein Byte groß ist. Das ist schon ziemlich speichereffizient. Darum ist deine Idee, einen String aus "0" für "nicht passierbar" und "1" für passierbar schon sehr effizient. Eine 500x500 Map bräuchte aber bei dem Verfahren immer noch 244 Megabyte. Noch effizienter geht es, wenn du die einzelnen Characters nochmal in 8 Bits unterteilst die du individuell belegen und abfragen kannst. Das wird bei der BitTable2D Klasse gemacht.

Bsp: Die Tabelle für eine 20x15 Map ist ja 640x480 Felder groß. Demnach gibt es 640*480 = 307200 viele Einträge. Da jedes Byte 8 Einträge speichern kann, brauchst du demnach 38400 viele Byte-Einträge, also ein String mit 38400 Elementen.
Wenn du nun auf den Pixel 322x225 zugreifen willst, musst du erstmal ausrechnen was für ein Eintrag das ist. Das hast du aber ja bei deiner Tilesetlösung auch schon machen müssen, wo du von der Position eines Tiles auf dessen ID oder andersrum von der ID eines Tiles auf dessen Position zugreifen wolltest. Hier ist das nichts anderes. 225*640 + 322 = 144322 ist die Nummer des Bits auf das du zugreifen willst. Das durch 8 geteilt ist die Nummer des Bytes, also 18040, und damit auch die Position im String in der du suchen musst. 18040 MODULO 8 = 2, also musst du auf das dritte Bit (man fängt bei 0 an zu zählen) im 18040ten Byte zugreifen.
Mit string[18040] bekommst du das Byte (als Zahl) zurück. Du kannst ja mal spaßeshalber string[18040].to_s(2) eingeben und bekommst die Zahl in Binärdarstellung. Die könnte z.B. so aussehen
01010011
Von rechts nach links hieße das dann: die ersten beiden Bits sind passierbar, dann folgen zwei Pixel die nicht passierbar sind, dann wieder ein passierbares usw.
Willst du wissen ob das dritte Pixel passierbar ist, so erzeugst du dir erstmal ein Byte in dem nur das dritte Bit gesetzt ist. Also so eines:
00000100
Das erhälst du in dem du 1 << 3 schreibst. Denn 1 = 00000001 und das << 3 bewirkt das alle Ziffern um 3 Stellen nach links verschoben werden.
Wenn du nun das Byte im String mit deinem neu erzeugten Byte mit UND (in Ruby &) vergleichst, passiert folgendes:
01010011 UND
00000100 IST
00000000

Überall wo zwei 1en untereinander liegen wird wieder eine 1 gesetzt, sonst eine 0. Das passiert nur, wenn genau an der Stelle die du abfragen willst (also dem dritten Bit) eine 1 ist. Und dann kommt genau wieder ein Byte ungleich 0 heraus. Auf diese Weise kannst du also abfragen ob an einer bestimmten Stelle ein Bit gesetzt ist.

Bsp: Ist in 01010011 das Bit Nummer 4 gesetzt?
01010011 UND
00010000 IST
00010000 -> JA

Willst du ein bestimmtes Bit auf 1 setzen, erzeugst du wieder ein Byte was alles 0en hat und nur an der gewünschten Stelle eine 1 und wendest dann mit dem Byte im String eine ODER (in Ruby | ) Operation an.

Bsp: Setze in 01010011 das Bit Nummer 2 auf 1.
01010011 ODER
00000100 IST
01010111

Willst du ein Bit auf 0 setzen, so erzeugst du ein Byte aus 1en, welches nur an der gewünschten Position eine 0 hat und verknüpfst es mit UND.

Bsp: Setze in 01010011 das Bit Nummer 1 auf 0.
01010011 UND
11111101 IST
01010001

Das Bit aus 1en mit nur einer 0 erhälst du, in dem du das 0er Byte mit nur einer 1 invertierst (in Ruby der ~ Operator).

So, wenn du dir den Quellcode der BitTable2D anguckst wird dort auch nichts anderes gemacht.

Zum Komprimieren: Da ist nicht groß was dran. Die Klasse Zlib:eflate hat eine Methode deflate die den als Parameter übergebenen String komprimiert. Als zweiten Parameter darfst du noch eine Zahl von 0 bis 9 angeben, die den Komprimierungsgrad festlegt (kleinere Zahlen = schnell aber wenig komprimiert, höhere Zahlen eben langsam aber stark komprimiert).
Zum Dekomprimieren verwendest du Zlib::Inflate.inflate(komprimierter_string) was dir wieder den Originalstring zurückgibt.
Die Methode _dump ist eine vorgegebene Methode, die automatisch verwendet wird wenn du ein Objekt mit Marshal.dump oder save_data abspeicherst. Sie muss einen String zurückgeben. Die Methode _load wird bei Marshal.load bzw. load_data aufgerufen und bekommt genau diesen String und muss daraus wieder das ursprüngliche Objekt basteln. In dem Fall passiert das, in dem der komprimierte Datenarray (mit den Tabelleneinträgen) und die Breite und Höhe der Tabelle als String abgespeichert werden. [@width, @height].pack("NN") heißt: Gib einen String zurück der die Zahlen @width und @height in je 4 Byte im Big Endian Format (höchstwertiges Byte kommt nach links) enthält. Du kannst die beiden Zahlen natürlich auch anders abspeichern (im unschönsten Fall sogar direkt als Ziffern im String). In der _load Methode werden dann die letzten 8 Byte aus dem String gelöscht und daraus wieder die @width und @height Werte gelesen. Der Rest des Strings wird dekomprimiert und bildet wieder den String mit Tabelleneinträgen.

[Cornix]

Vielen Dank für die detailreiche Erklärung. Ich habe leider im Moment noch nicht die Gelegenheit alles zu testen und mich genauer damit zu befassen, das werde ich aber sobald es sich mir ermöglicht nachholen.

Könntest du mir vielleicht auch noch ein wenig bei meiner Entscheidung helfen. Soweit ich das nun beurteilen kann bietet die Tabelle eine bessere Performance (obwohl genaue Angaben wohl nur schwer zu bestimmen sind im Moment) dafür aber einen höheren Speicherbedarf.
Die Benutzung der Pathing Map als Bilddatei verbraucht zwar weniger Speicherplatz dafür muss der Computer bei jeder bewegung selbst berechnen ob der angegebene Punkt begehbar ist oder nicht.

Demnach ergibt sich ein Scheideweg:
Geringe Performanceverbesserung gegen Speicherplatzeinsparung

Welche Methode soll ich wählen?

[-KD-]

Die Frage ist doch, ob die Performance darunter leidet oder nicht. So wie ich das sehe musst du nur wenige Abfragen machen (Koordinaten des Tiles im Tileset berechnen, dort dann den Pixel abfragen, das drei Mal für jeden Layer). Das sollte eigentlich in wenigen Microsekunden gehen. Bevor du also krampfhaft nach anderen Lösungen suchst, würde ich erstmal testen ob das Spiel durch diese Entscheidung zu ruckeln anfängt.
Zudem ist die erste Lösung ja auch erstmal leichter umzusetzen bzw. hast du sie ja schon so ziemlich fertig.

[Cornix]

Ich habe gerade eben einen Test durchgeführt und die erste und zweite Möglichkeit verglichen.

Ich habe folgende Scripte Verwendet um die Performance zu vergleichen:
Das Update läuft jedes Frame, je nach Wert von @check wird die Passierbarkeit an der Position (1,1) beliebig oft getestet.

Code:

  def update
    if Input.press?(Input::UP)
      @check += 1
      @sprite.bitmap.clear
      @sprite.bitmap.draw_text(0,0,640,20,@check.to_s)
    end
    if Input.press?(Input::DOWN)
      @check -= 1 if @check > 0
      @sprite.bitmap.clear
      @sprite.bitmap.draw_text(0,0,640,20,@check.to_s)
    end
    for i in 1..@check
      self.pathing_test(1,1)
    end
  end
  
  def pathing_test(real_x, real_y)
    int_x = real_x / 32
    int_x -= 1 if real_x % 32 == 0
    int_y = real_y / 32
    int_y -= 1 if real_y % 32 == 0
    add_x = real_x % 32
    add_y = real_y % 32
    for i in [2, 1, 0]
      tile_id = @map.data[int_x, int_y, i] - 384
      next if tile_id < 0
      ry = tile_id / 8
      rx = tile_id % 8
      return false if @tile.get_pixel(rx*32+add_x, ry*32+add_y) == @block
    end
    return true
  end

Das Ergebniss:
Die Framerate betrug am Anfang des Testes konstante 40.
Ich habe die Variable @check kontinuirlich pro Frame um 1 erhöht.
Als @check ungefähr den Wert 350 angenommen hatte sank die Framerate auf 37 - 39.
Von da an aufwärts sank sie stetig weiter bis ich um den Wert 1000 für @check bereits 10 Frames pro Sekunde verloren habe.

Den gleichen Test mit einer Tabelle:
Ich habe eine normale Table benutzt mit den Maßen 640 x 480.

Code:

def update
    if Input.press?(Input::UP)
      @check += 1
      @sprite.bitmap.clear
      @sprite.bitmap.draw_text(0,0,640,20,@check.to_s)
    end
    if Input.press?(Input::DOWN)
      @check -= 1 if @check > 0
      @sprite.bitmap.clear
      @sprite.bitmap.draw_text(0,0,640,20,@check.to_s)
    end
    for i in 1..@check
      self.pathing_test(1,1)
    end
  end
  
  def pathing_test(real_x, real_y)
    return @table[real_x,real_y] == 1
  end

Das Ergeniss:
Zu beginn brauchte der Computer eine kurze Zeitspanne (nicht mehr denn eine Sekunde) um die Tabelle zu erstellen.
Die Performance begann bei 39 und blieb konstant bis die Variable @check ungefähr bei 5000 angekommen ist. Von da an lag die Framerate bei 38 für die nächsten Tausend Werte von @check.
Ich habe den Test an dieser Stelle abgebrochen, ich denke es wurde genug bewiesen, dass die Tabelle die Effizienz enorm verbessern würde.

Mit der BitTable2D welche du geschrieben hast war die Performance zwar besser als mit der Berechnung durch die Pathing Map allerdings weitaus schlechter als mit der normalen Tabelle.
Die Framerate sank hier bereits bei einem Wert von ungefähr 850 auf 36 - 38.


Würde eine Art hybrid-Lösung funktionieren?
Zum Speichern der Werte einen String welcher beim betreten der Karte in eine Table umgewandelt werden würde?

[-KD-]

350 Abfragen pro Frame sind doch ganz gut. Angenommen jedes Event bewegt sich jeden Frame, so könntest du 350 Events bewegen lassen mit minimalem Framerateverlust.

[Cornix]

Angenommen ich würde nichts anderes machen als diese 350 Objekte bewegen zu lassen.

Was würdest du mir empfehlen? Sollte ich die Tabellen nutzen?
Der Code dürfte nicht schwerer zu schreiben sein, die Performance verbessert sich bewiesenermaßen und dank der von dir geschriebenen Tabellen Klasse sollte auch der Speicherplatzbedarf geringer ausfallen.

[Cornix]

Ich habe die BitTabelle getestet und ich muss gestehen, ich bin begeistert.

Die Resultate sind bei weitem über allen meinen Erwartungen, die Größe der Tabelle hat sich von 600kb auf 1kb verringert.
Ganz recht, ohne Tabelle ist meine Map 4kb groß, mit der BitTabelle 5kb.

Den allergrößten Dank für deine Zeit, es ist eine gigantische Hilfe gewesen.