Оптимизированная структура данных для двумерного пространственного поиска и реализация Javascript?

Я работаю над HTML5-игрой в стиле Тетрис, и мне нужно улучшить алгоритм оптимизации пространства. Прямоугольные блоки разного размера нужно добавлять на холст с максимальной экономией места. Я знаю, сколько места занимает блок, мне нужно найти ближайшее место, в которое блок может быть добавлен с фиксированной координатой x. Было бы неплохо иметь абсолютное ближайшее место.

Я реализовал версию, которая выполняет поиск с использованием пикселей путем проверки значения пикселя на холсте, который сдвигается вниз, пока не найдет достаточно свободного места для фигуры, а затем добавляет ее. Это работает (медленно), только если пространство заполняется слева направо - алгоритм может с уверенностью предположить, что если первый столбец пикселей безопасен, тогда можно добавить весь блок.

Мне нужно сделать это более надежным, вот где я думаю, что это должен уйти.

Сохранение дерева квадратов для представления состояния доски дает мне более быстрый способ определить, где есть место.

4 узла хранятся для каждого уровня глубины - каждый узел либо равен 0, если он полностью пуст, либо 1, если «где-то есть что-то». Каждый прогрессивный уровень глубины дает все больше и больше информации о доске.

given(boardstate, block width, block height)
-calculate the largest grid space the block must span
  // a block which is 242x38 MUST span a 16x16 free space 
  // (based on 1/2 of smallest dimension)
-the block width requires n consecutive free spaces
  // (242/16) = 15
-find the first available 15x1 spaces in the board
-check the surrounding tiles at the next level of depth for collisions
  -check the surrounding tiles at the next level of depth for collisions... etc
-if there's a fit 
  draw the block 
  mark all affected nodes at all depths as 'filled'

Какая структура данных javascript лучше всего представляет сетку?

Что я рассмотрел до сих пор:

A. Создайте полное древовидное объект с указателями на дочерние элементы и значения и набор методов для навигации по нему. Это было бы интуитивно понятно и, вероятно, экономно, но я подозреваю, что это ужасно медленно.

В. Посмотрите на каждую сетку как на 4 бита и сохраните глубины как шестнадцатеричные массивы или объекты. Если бы это сделал человек более умный, чем я, это, вероятно, оптимизирует не только хранилище, но и сделает доступными умные битовые операции для сравнения соседних ячеек, включения и выключения блоков и т. Д. Я полагаю, это было бы невероятно быстро, невероятно эффективен, но построить это вне моих возможностей.

C. Сохраните каждую глубину в массиве. Глубина [0] = [1,0,0,0]; Глубина [1] [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0] и т. Д. Вот куда я направляюсь момент. Это не очень эффективно с точки зрения использования пространства и, вероятно, не будет невероятно быстрым, но я думаю, что смогу обойти это.

Существует практическое ограничение для любой структуры на количество глубин (массив для хранения наличия мест 4x4 в моем последнем подходе - более 65 тысяч), после чего неизбежен дорогостоящий вызов для проверки последних нескольких пикселей данных изображения с холста с помощью обычного итератора.

Итак, A, B, C, другие?

Как обычно, все идеи оценены.