Welche Methode zum prüfen einer Kollision von Objekten?

[Cornix]

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.