Frage Pixelmovement Kollisionsabfrage

Guten Abend.

Ich habe einmal mehr eine Frage bezüglich der Kollisionsabfrage eines Pixelmovement Scriptes welches ich selbst geschrieben habe.

Bisher habe ich für jedes Tileset (Bilddatei) eine weitere Bilddatei erstellt welche lediglich zwei Farben aufwies: Schwarz und Weiß.
Schwarz stellt nicht passierbare Stellen des Tilesets dar und Weiß passierbare.
(Vergleich)

Im Spiel habe ich nun einfach bei der Bewegung den entsprechenden Abschnitt der Map auf welchen sich mein Objekt bewegen wollte mit der Schwarz/Weißen "Pathing Map" nachgebildet und darüber verglichen ob der zu betretende Pixel begehbar ist oder nicht.

Ich kam auf den Gedanken ob dies nicht eine recht ineffiziente Methode sei, es boten sich mir folgende Argumente:
1). Es verbraucht mehr Speicherplatz für jedes Tileset eine Pathing Map ab zu speichern.
2). Es muss für jede kleine Bewegung eigens eine Bitmap Datei angelegt werden auf welcher der Ausschnitt (32x32 Pixel) auf welchem sich das Objekt bewegt in der Pathing Map nach modeliert wird.
Dies braucht nicht nur ein Sprite sondern auch 3 block transfers für alle 3 Layer des Bitmaps. (Falls sich natürlich bereits im ersten Layer entpupt, dass besagte Stelle unpassierbar ist werden die folgenden beiden Layer nicht mehr geprüft)

Ich habe daher eine neue Idee gehabt wie ich die Abfrage vielleicht effektiver machen könnte. Statt einer Pathing Map benutze ich eine Tabelle welche die Werte 1 = Passierbar und 2 = Unpassierbar für jede mögliche X/Y Koordinate speichert.
Ich habe mich direkt darangesetzt und es getestet, allerdings bin ich mir nicht ganz sicher ob die Ergebnisse das hervorbrachten was ich gehofft habe.
bereits für eine kleine 20x15 große Map ist die gespeicherte Tabelle 600kb groß (ich habe sie direkt in die Map Datei speichern lassen).

Ist diese Methode eine Tabelle statt der Bilddatei zu verwenden effektiver? 600kb sind im vergleich zu meinem 512kb großem Projekt ziemlich gigantisch. Wenn ich für jede weitere Map jeweils nocheinmal 600+ kb benötige expandiert die Größe enorm.

Danke.
Cornix.

Zitat:

---

Es muss für jede kleine Bewegung eigens eine Bitmap Datei angelegt werden auf welcher der Ausschnitt (32x32 Pixel) auf welchem sich das Objekt bewegt in der Pathing Map nach modeliert wird.

---

Häh? Warum. Du suchst dir über das Tileset die Tiles raus, die der Held betritt und prüfst in diesen die jeweiligen Pixel. Warum musst du da temporäre Bitmaps anlegen?

Zitat:

---

Statt einer Pathing Map benutze ich eine Tabelle welche die Werte 1 = Passierbar und 2 = Unpassierbar für jede mögliche X/Y Koordinate speichert.
Ich habe mich direkt darangesetzt und es getestet, allerdings bin ich mir nicht ganz sicher ob die Ergebnisse das hervorbrachten was ich gehofft habe.
bereits für eine kleine 20x15 große Map ist die gespeicherte Tabelle 600kb groß (ich habe sie direkt in die Map Datei speichern lassen).

---

Wieder die Frage: Warum mapspezifisch? Die Begehbarkeit ist doch Tile-spezifisch. Demnach müsstest du die Tabelle pro Tileset und nicht pro Map anlegen.

Ansonsten ist eine Tabelle mitunter noch der speicherschonenste Weg. Speichereffizienter geht nur eine BitTable, die du über die String-Klasse implementieren kannst. BitTabellen sind aber geringfügig langsamer als Arrays und Tables.
Implementierung könnte folgendermaßen aussehen:

Code:

---

class BitTable2D
 
  def initialize width, height, initial=false
    @width = width
    @height = height
    cells = ((@width * @height) / 8.0).ceil
    @data = (initial ? 0xff.chr : 0x00.chr) * cells
  end
 
  def [](x, y)
    bit = y * @width + x
    byte_offset = bit / 8
    byte_value = 1 << (bit % 8)
    @data[byte_offset] & byte_value == byte_value
  end
 
  def []=(x, y, value)
    bit = y * @width + x
    byte_offset = bit / 8
    byte_value = 1 << (bit % 8)
    if value then
      @data[byte_offset] = (@data[byte_offset] | byte_value).chr
    else
      @data[byte_offset] = (@data[byte_offset] & ~byte_value).chr
    end
  end
 
end

---

Die Kollisionsabfrage läuft derzeit auf Basis dieses Scriptes:

Code:

---

def pathing_test(real_x, real_y)
    block = Color.new(0,0,0,255) #Farbe die Blockt = Schwarz
    tile = RPG::Cache.tileset("PathingMap-"+@tileset_name) #Bilddatei der Pathing Map
    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]
      #Durchlauf pro Layer
      tile_id = data[int_x, int_y, i] - 384
      next if tile_id < 0
      ry = tile_id / 8
      rx = tile_id % 8
      #Passierbarkeits Check
      return false if tile.get_pixel(rx*32+add_x, ry*32+add_y) == block
    end
    return true
  end

---

"tile" und "block" können auch als private Variablen bei der initialisierung der Map gespeichert werden, ich habe sie nur hier eingefügt um den Code leichter verständlich zu machen.

Was die Tabellen angeht so wollte ich für jede Map die genauen Passierbarkeiten jedes Pixels speichern.
Eine 20x15 Tiles große Karte ist 640x480 Pixel groß (32 Pixel pro Tile) und damit wäre auch die Tabelle 640 x 480 Einheiten groß und würde jedes Pixel mit einem Wert zwischen 1 und 2 versehen.
Dadurch müsste der Computer weder die Bilddatei "Tile" laden noch irgendwelche Rechenoperationen ausführen. Ich könnte direkt über die zu prüfenden Koordinaten in der Tabelle nachschlagen ob der betreffende Punkt begehbar ist oder nicht.

Ja, aber wo musst du da ein neues Bitmap erzeugen? Das Tileset bzw. deine Begehbarkeitsmap ist im RPG::Cache gecacht. Du musst lediglich von der Tile-ID auf die Koordinaten im Tileset schließen und dort deine Abfrage machen.

Zitat:

---

Was die Tabellen angeht so wollte ich für jede Map die genauen Passierbarkeiten jedes Pixels speichern.
Eine 20x15 Tiles große Karte ist 640x480 Pixel groß (32 Pixel pro Tile) und damit wäre auch die Tabelle 640 x 480 Einheiten groß und würde jedes Pixel mit einem Wert zwischen 1 und 2 versehen.

---

Selbst mit einer BitTable bräuchtest du noch 30 Megabyte um eine 500*500 Map abzuspeichern. Wobei du natürlich die Tabelle leicht komprimieren kannst. In der Datei ist sie vermutlich nur wenige Kilobyte groß.

Das ist nun das Dilemma in welchem ich stecke, auf der einen Seite habe ich nunmal dieses Argument:

Code:

---

def pathing_table_test(real_x, real_y)
    return @pathing_table[real_x, real_y] == 1
    #returns true if the position is pathable and false if its not
end

def pathing_map_test(real_x, real_y)
    block = Color.new(0,0,0,255) #Farbe die Blockt = Schwarz
    tile = RPG::Cache.tileset("PathingMap-"+@tileset_name) #Bilddatei der Pathing Map
    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]
      #Durchlauf pro Layer
      tile_id = data[int_x, int_y, i] - 384
      next if tile_id < 0
      ry = tile_id / 8
      rx = tile_id % 8
      #Passierbarkeits Check
      return false if tile.get_pixel(rx*32+add_x, ry*32+add_y) == block
    end
    return true
  end

---

Ich denke die erste Funktion ist definitiv mit weniger Arbeit verbunden.

Allerdings verbraucht diese Tabelle, wie gesagt, unmengen an Speicherplatz.
Gibt es nicht eine Möglichkeit die Tabelle zu komprimieren und nur jeweils diejenige Tabelle zu dekomprimieren welche gerade benötigt wird?
Zum Beispiel wird die Tabelle als String oder Zahl mit WIDTH*HEIGHT Ziffern gespeichert und durch besondere Verfahren komprimiert und beim Betreten der jeweiligen Karte dann einmalig geladen und dekomprimiert.

Ich bitte um eure Hilfe hierbei, ich bin leider ein Anfänger in derlei Angelegenheit aber ich würde sehr gerne mehr darüber lernen.

Danke bereits für die Aufmerksamkeit.
Cornix.

Zitat:

---

Ich denke die erste Funktion ist definitiv mit weniger Arbeit verbunden.

---

Überzeugt mich nicht so recht. Hast du denn mal getestet ob das wirklich die Performance runterreißt?

Zitat:

---

Gibt es nicht eine Möglichkeit die Tabelle zu komprimieren und nur jeweils diejenige Tabelle zu dekomprimieren welche gerade benötigt wird?
Zum Beispiel wird die Tabelle als String oder Zahl mit WIDTH*HEIGHT Ziffern gespeichert und durch besondere Verfahren komprimiert und beim Betreten der jeweiligen Karte dann einmalig geladen und dekomprimiert.

---

Ich habe doch schon Code für eine BitTable-Klasse geschrieben. Die speichert jeden Tabelleneintrag in ein Bit ab. Für eine 500x500 Map bräuchtest du also nur noch 30 Megabyte, statt 488, wie bei einer Table, oder gar 976 Megabyte, wie bei einem Bitmap.

Zum Komprimieren in eine Datei verwendest du einfach die Zlib Library.
Hier mal als Beispiel für meine BitTable2D Klasse

Code:

---

class BitTable2D
  def _dump depth
    compress << [@width, @height].pack("NN")
  end
  def self._load str
    object = allocate
    object.instance_eval do
      @width, @height = str.slice!(-8, 8).unpack("NN")
      @data = decompress(str)
    end
    object
  end
  private
  def compress
    Zlib::Deflate.deflate(@data)
  end
  def decompress(data)
    Zlib::Inflate.inflate(data)
  end
end

---

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.

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::Deflate 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.

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?

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.

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?

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.

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.

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.