Welche Methode zum prüfen einer Kollision von Objekten?

Guten Tag, etwas her seitdem ich zuletzt eine Frage hatte, diesmal kommt wieder eine bezüglich der Performance verschiedener Methoden um die Kollision von zwei Objekten zu prüfen.

Zugrundelegend ein einfaches Movement-System aufbauend auf einem 4x4 Tile Raster.

Es bewegen sich nun verschiedene Figuren auf der Karte, die Anzahl ist unbegrenzt. Jede Figur wird durch Position und Kollisionsgröße definiert. Es soll einer Figur nicht möglich sein innerhalb einer anderen zu stehen oder sich durch eine andere hindurch zu bewegen.

Mir sind nach ein wenig Überlegung drei Wege eingefallen:

1). Die simpelste Methode mit einem Array von Objekten und einer Iteration.
Alle Figuren werden in einem Array gespeichert, bei der Bewegung wird durch jedes Objekt im Array iteriert und die Entfernung zwischen dem sich bewegenden Objekt und dem Iterierten geprüft. Ist die Entfernung kleiner oder gleich der Summe ihrer Kollisionsgrößen sind sie kollidiert, die Bewegung ist verhindert.
Nachteil: Bei jeder Bewegung müsste durch alle Objekte iteriert werden, gerade bei den Bewegungen bei welchen keine Kollision stattfindet (und diese werden doch wohl den Hauptteil ausmachen) ist dies ein linear mit der Objektzahl wachsender Aufwand.

2). Über eine Tabelle.
Bei jeder Bewegung eines Objektes wird in einer Tabelle welche die Karte repräsentiert abhängig von der Kollisionsgröße des Objektes entsprechende Punkte als "Besetzt = 1" verzeichnet. Will sich ein Objekt auf ein neues Tile bewegen wird einfach in dieser Tabelle an der entsprechenden Position nachgeprüft ob der Wert "Besetzt = 1" oder "Unbesetzt = 0" ist.
Nachteil: Die Tabelle wird eine Menge RAM verbrauchen und unabhängig davon wie viele Objekte existieren wird die gleiche Menge an Speicherplatz verwendet. Der Speicherverbrauch steigt quadratisch mit der Kartengröße.

3). Über einen Hash.
Ähnlich wie die Tabelle, doch wird nun ein Hash verwendet, die Keys wären Arrays mit Koordinaten "[x,y]", diese würden die ID des besetztenden Objektes speichern falls der Punkt besetzt ist.
Ist ein Punkt nach der Bewegung eines Objektes nichtmehr besetzt wird der Eintrag gelöscht.
Ist also kein Eintrag für die Position [x,y] vorhanden so ist dieser Punkt frei, sollte ein Eintrag vorhanden sein so kann diese Position nicht betreten werden.
Nachteil: Kann ich schwer beurteilen, da ich mich mit Hashs noch nicht sonderlich gut auskenne.

Hier also meine drei Einfälle der letzten Tage. Im Moment genügt die erste Methode, allerdings würde ich mich liebend gern auf die effektivste Umsetzung verlassen.
Kann mir hierbei jemand helfen? Besonders was den Hash angeht welcher für mich als eine sehr gute Wahl erscheint bin ich etwas stutzig, wie gut ist die Speicher- und Rechenauslastung mit dieser Variante?

Vielen Dank für alle Antworten,
Cornix.

Hashs sind schon die richtige Idee, aber ich würde keine Hashs mit einem [x,y] Key verwenden. Besser wäre ein Hash in der Form eines Gitternetzes. Du hast ja vorher die Idee einer Tabelle geäußert, bei der jedes 4x4 Tile einen Tabelleneintrag hat. Du musst aber nicht jedem Tile einen Tabelleneintrag geben. Du kannst die Tabelle auch gröber machen. Stell sie dir wie ein grobmaschiges Netz vor, dass du über die Karte spannst. Es könnte z.B. 64x64 große Gitterfelder haben, oder noch größer, je nachdem wie du zwischen Speicher und Performance ausbalancieren willst. Solch ein Gitternetz hat noch einen weiteren Vorteil: Du kannst nicht nur effizient Kollisionen überprüfen, sondern auch effizient ob ein Event in der Nähe eines anderen ist (goldwert, wenn du sowas wie "Sichtweite, oder Reichweite von Waffen o.ä. einführen willst). Denn dann musst du nicht jedes Nachbarfeld absuchen, sondern nur noch Events die sich innerhalb der benachbarten großen Gitterfelder aufhalten (was bei dünnbesiedelten Maps WESENTLICH weniger Aufwand ist).

Wie könnte so eine Tabelle aussehen?
Hier mal der Rohbau für einen 2D-Array:

Code:

---

class Array2D
  include Enumerable
  def initialize rows, cols, content=nil &content_block
    @rows = rows
    @cols = cols
    if content_block then
      @data = Array.new(@rows * @cols, &content_block)
    else
      @data = Array.new(@rows * @cols, content)
    end
  end

  def [](row, col)
    @data[row * @cols + col]
  end

  def []=(row, col, value)
    @data[row * @cols + col] = value
  end

  def each &block
    @data.each &block
  end
end

---

Damit hast du schon mal eine einfache 2D-Array Konstruktion.

Code:

---

tabelle = Array2D.new(10, 10, 0)
print tabelle[5, 5] #=> 0

---

Jetzt kannst du davon eine Subklasse für eine GridMapHash Klasse machen:

Code:

---

class GridMapHash < Array2D
  def initialize mapwidth, mapheight, resolution=64
    super((mapwidth/resolution.to_f).ceil, (mapheight/resolution.to_f).ceil) {Array.new}
    @resolution = resolution
  end

  def characters_at x, y
    self[x%@resolution, y % @resolution]
  end

  def field_blocked? x, y, char
    characters_at(x, y).any? {|event| event != char && !event.through && event.is_blocking(char, x, y) }
  end

  def character_moves(char, fromx, fromy, tox, toy)
    unless (fromx%@resolution) == (tox%@resolution) && (fromy%@resolution)==(toy%@resolution)
      characters_at(fromx, fromy).delete(char)
      characters_at(tox, toy) << char
    end
  end
end

---

Jetzt überschreibst du noch die movement-Methoden der Game_Character Klasse und sagst den Events, dass sie alle Positionsänderungen an diese GridMapHash Instanz melden sollen. DIe Methode is_blocking? musst du noch selbst schreiben. Die sollte prüfen ob das Event dem Char wirklich im Weg steht.

Edit: Ich hab noch was übersehen. Du verwendest Kollisionsbereiche für deine Events. Das hat natürlich den Nachteil, dass ein Event zwar im Gitterfeld x/y stehen kann, sein Kollisionsbereich aber ins Feld x+1/y hineinragt. Entsprechend musst du die field_blocked? Methode umschreiben, so dass sie auch die umliegenden Felder überprüft, die im Kollisionsradius liegen. Wenn du die Auflösung größer als den größtmöglichen Kollisionsradius wählst, werden immer maximal 3 Gridfelder überprüft werden müssen. Der Aufwand hält sich dann also trotzdem in Grenzen. Es ist nur eben etwas mehr Programmieraufwand das hinzuschreiben.

Vielen vielen Dank, ein ziemlich ausführlicher Beitrag.

Ich versuche einmal zu rekapitulieren da ich mir selbst noch nicht vollkommen sicher bin alles richtig verstanden zu haben.

Deine Idee ist es also ein grobes Gitternetz zu spannen mit größeren Einheiten welche jeweils eine gewisse Menge von Tiles umspannt. Und in diesen Gitternetzknoten werden alle Objekte gelistet welche für Kollisionen in Frage kommen.

Das würde bedeuten falls ich die Kollision eines Objektes mit einem anderen überprüfen möchte müsste ich nichtmehr durch alle Objekte auf der ganzen Karte iterieren sondern lediglich durch jedes Objekt innerhalb des selben und der benachbarten Gitternetzknoten, sprich 9 insgesamt gegeben dem Fall die Kollisionsgröße könnte die Größe eines Gitternetzknotens nicht übersteigen.

Würde diese Methode auch Sinn ergeben bei relativ kleinen Zahlen von Objekten, sagen wir nicht mehr als 20 meistens eher weniger als 10?

Bei 20 Objekten kannst du auch einfach iterieren (wie es der Maker normalerweise macht). Selbst wenn jedes der 20 Objekte jeden Frame alle anderen 20 Objekte überprüft, hättest du nur 400 Iterationsschritte. Das geht binnen von Mikrosekunden und sollte die FPS nicht beeinflussen.
Solche komplexeren Methoden lohnen sich, denke ich, nur wenn du auf der Map mehrere dutzend, sagen wir mal >=40 Events hast.

Das heist bei weniger Objekten wäre solch eine Methode eher ein Verlust denn ein Gewinn deiner Meinung nach?

Kommt darauf an was du als Verlust und Gewinn bezeichnest.
Wenn es dir rein um Performance geht, so hilft nichts anderes als ein Performance test.
Was KD mit "lohnen" meint ist, so denke ich mal, dass sich bei geringen Objektmengen der Programmieraufwand nicht lohnt, weil es eine einfach Iteration auch tut.

Der Aufwand ist für mich kein Nachteil, eher im Gegenteil, ich schätze jede Gelegenheit etwas auszuprobieren und zu lernen. Es geht nur darum ob es auch tatsächlich etwas bringen wird.

Bei kleinen Objektmengen wirst du sicherlich keinen spürbaren Performancegewinn haben. Daher lohnt sich auch der erhöhte Programmieraufwand nicht. Wenn du wissen willst ob du bei kleinen Objektmengen sogar einen Performanceverlust hast, dann wirst du wohl oder übel einen Test durchführen müssen.