Optimierte Datenstruktur für 2d räumliche Suche und Javascript-Implementierung?

Ich arbeite an einem HTML5-Spiel vom Tetris-Typ und muss einen Raumoptimierungsalgorithmus verbessern. Rechteckige Blöcke unterschiedlicher Größe müssen der Leinwand auf möglichst platzsparende Weise hinzugefügt werden. Ich weiß, wie viel Platz der Block braucht, ich muss den nächstgelegenen Punkt finden, an dem der Block mit einer festen x-Koordinate hinzugefügt werden kann - der absolut nächste Punkt ist ein schöner Platz.

Ich habe eine Version implementiert, die Pixel-für-Pixel-Wertprüfung auf der Leinwand durchsucht, die nach unten gedrückt wird, bis sie genug freien Platz für die Form findet und sie dann hinzufügt. Dies funktioniert (langsam) nur, wenn der Raum von links nach rechts gefüllt ist - der Algorithmus kann sicher annehmen, dass, wenn die erste Pixelspalte sicher ist, der gesamte Block hinzugefügt werden kann.

Ich muss es robuster machen, hier ist, wo ich denke, das sollte gehen.

Wenn Sie einen Quad-Tree speichern, um den Board-Status darzustellen, kann ich schneller erkennen, wo sich Platz befindet.

4 Knoten werden für jede Ebene der Tiefe gespeichert - jeder Knoten ist entweder 0 für vollständig leer, oder 1 für "hat etwas Zeug irgendwo". Jedes progressive Niveau der Tiefe gibt mehr und mehr Informationen über das Brett.

Was ist die beste JavaScript-Datenstruktur, um das Gitter darzustellen?

Dinge, die ich bisher betrachtet habe:

A. Erstellen Sie ein vollständiges tree -Objekt mit Zeigern auf Kinder und Werte und eine Reihe von Methoden, um es zu navigieren. Dies wäre intuitiv und wahrscheinlich platzsparend, aber ich vermute schrecklich langsam.

B. Betrachten Sie jedes Gitter als 4 Bits und speichern Sie die Tiefen als Hex-Arrays oder Objekte. Wenn es von einer clevereren Person als mir gemacht wird, optimiert das wahrscheinlich nicht nur den Speicher, sondern macht clevere Bit-Operationen verfügbar, um benachbarte Zellen zu vergleichen, Blöcke ein- und auszuschalten usw. Ich kann mir vorstellen, dass es unglaublich schnell und unglaublich effizient wäre meine Fähigkeiten zu bauen.

C. Speichern Sie jede Tiefe in einem Array. Depth[0]=[1,0,0,0]; Depth[1][1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0] usw. Hier gehe ich gerade hin. Es ist nicht sehr platzsparend und es wird wahrscheinlich nicht unglaublich schnell sein, aber ich denke, ich kann mich darum kümmern.

Es gibt ein praktisches Limit für jede Struktur auf die Anzahl der Tiefen (das Array zu speichern Verfügbarkeit von 4x4 Leerzeichen in meinem letzten Ansatz ist mehr als 65 Tausend), nach denen die teure Aufforderung, die letzten paar Pixel von Bilddaten aus zu überprüfen Der Canvas mit einem regulären Iterator ist unvermeidlich.

Also, A, B, C, andere?

Wie immer, alle Einsichten geschätzt.