Optimized data structure for 2d spatial search and Javascript implementation?

Question

I'm working on a Tetris-type HTML5 game and need to beef up a space optimization algorithm. Rectangular blocks of varying size need to be added to the canvas in the most space efficient way. I know how much space the block takes, I need to find the closest spot the block can be added with a fixed x coordinate- the absolute closest spot is a nice to have.

I've implemented a version that searches using pixel by pixel value checking on the canvas that pushes down until it finds enough free space for the shape and then adds it. This works (slowly) only if the space fills left to right- the algorithm can safely assume if the first pixel column is safe then the entire block can be added.

I need to make this more robust, here's where I think this should go.

Storing a quad tree to represent the board state gives me a quicker way to identify where there's space.

4 nodes are stored for each level of depth- each node is either 0 for completely empty, or 1 for 'has some stuff somewhere'. Each progressive level of depth gives more and more information about the board.

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'

What is the best javascript data structure to represent the grid?

Things I've considered so far:

A. Build a full tree object with pointers to children and values and a set of methods to navigate it. This would be intuitive and probably space-efficient, but I suspect horribly slow.

B. Look at each grid as 4 bits and store the depths as hex arrays or objects. If done by a person more clever than myself, this probably optimizes not just the storage but makes clever bit operations available to compare adjacent cells, turn blocks on and off, etc. I imagine it would be incredibly fast, incredibly efficient, but it's beyond my skills to build.

C. Store each depth in an 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] etc. This is where I'm headed at the moment. It's not very space efficient and it probably won't be incredibly fast, but I think I can get my head around it.

There's a practical limit to any structure to the number of depths (the array to store availability of 4x4 spaces in my last approach is more than 65 thousand) after which making the expensive call to check the last few pixels of image data from the canvas with a regular iterator is unavoidable.

So, A,B,C, other?

As usual, all insights appreciated.

Answer 1

You want answer b) and you want to implement a space-filling-curve or a spatial index. You don't want to store the bits in an array or object or an index but in a string-key. You want to read this string-key from the left to the right and thus you can easy query each depth with any string matching algorithm. You want to google for Nick's spatial index hilbert curve quadtree blog. But you are right with your assumption that answer b) is very expensive so I suggest you answer a) because it's not that slow and also there is already a free implementation of a javascript quadtree available from the closure library: closure-library.googlecode.com/svn/docs/class_goog_structs_QuadTree.html.