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.

Dorcus

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.

Braunstein

and if you dont want to use closure, few days ago a new implementation appeared: mikechambers.com/blog/2011/03/21/… – Annabell

I had a feeling I was just scratching the surface of a problem many people have solved well. I'm reading through the sources now, I'll update when I've got one that works. Thanks for the excellent response. – Dorcus

epitaph, forgive my naivete here, I'm a front end guy unaccustomed to so much math in my work day. Spatial indexing seems like the most efficient way to store the shapes, but I'm struggling with how you search for available space within the curve structure. The logic to 'check one space to the right' is not clear and most of the results I'm finding are abstracts to papers. Thoughts? – Dorcus

I'm not sure I understand you though your idea is interesting but your problem is most likely is not a search and query or index problem. A quadtree or a spatial index isn't solve your problem of space optimization. It's most likley you have a bin-packing or 2D-cutting-stock problem. Like wildcard shows us a quadtree is to speed-up soley collision detection. A spatial index is for storing geo coordinates or spatial indexed problem (augmented reality). But I think you want to look for a depth-first search? – Braunstein

And also if you use a spatial index your canvas has to fit into a power of 2. – Braunstein

Here is a similar problem: #5222056 – Braunstein