Estructura de datos optimizada para la búsqueda espacial 2d y la implementación de Javascript?

Question

Estoy trabajando en un juego HTML5 de tipo Tetris y necesito reforzar un algoritmo de optimización de espacio. Los bloques rectangulares de diferentes tamaños deben agregarse al lienzo de la manera más eficiente en cuanto a espacio. Sé cuánto espacio ocupa el bloque, necesito encontrar el lugar más cercano al que se puede agregar el bloque con una coordenada x fija: el lugar más cercano es un lugar agradable.

Implementé una versión que busca utilizando la comprobación del valor de píxel por píxel en el lienzo que empuja hacia abajo hasta que encuentra suficiente espacio libre para la forma y luego lo agrega. Esto funciona (lentamente) solo si el espacio se llena de izquierda a derecha: el algoritmo puede asumir con seguridad que si la primera columna de píxeles es segura, entonces se puede agregar todo el bloque.

Necesito hacer esto más robusto, aquí es donde creo que debería ir esto.

El almacenamiento de un árbol cuádruple para representar el estado de la placa me proporciona una forma más rápida de identificar dónde hay espacio.

4 nodos se almacenan para cada nivel de profundidad- cada nodo es o bien 0 para completamente vacío, o 1 de 'tiene un poco de materia en algún lugar'. Cada nivel progresivo de profundidad brinda más y más información sobre el tablero.

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' 

¿Cuál es la mejor estructura de datos Javascript para representar la red?

cosas que he considerado hasta ahora:

A. Construir un objeto tree completa con punteros a los niños y los valores y un conjunto de métodos para navegar por ella. Esto sería intuitivo y probablemente eficiente en el uso del espacio, pero sospecho que es terriblemente lento.

B. Mire cada cuadrícula como 4 bits y almacene las profundidades como matrices hexagonales u objetos. Si lo hace una persona más inteligente que yo, probablemente optimice no solo el almacenamiento, sino que haga que las operaciones de bits inteligentes estén disponibles para comparar celdas adyacentes, activar y desactivar bloques, etc. Me imagino que sería increíblemente rápido, increíblemente eficiente, pero está más allá mis habilidades para construir

C. Almacene cada profundidad en una matriz. 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. Aquí es hacia donde me dirijo. No es muy eficiente en el uso del espacio y probablemente no sea increíblemente rápido, pero creo que puedo entenderlo.

Hay un límite práctico para cualquier estructura en el número de profundidades (la matriz para almacenar la disponibilidad de espacios 4x4 en mi última aproximación es más de 65 mil) luego de realizar la llamada costosa para verificar los últimos píxeles de datos de imagen desde el lienzo con un iterador regular es inevitable.

Entonces, A, B, C, otro?

Como de costumbre, todos los comentarios fueron apreciados.

Answer 1

Desea la respuesta b) y desea implementar una curva de relleno de espacio o un índice espacial. No desea almacenar los bits en una matriz, un objeto o un índice, sino en una clave de cadena. Desea leer esta clave de cadena de izquierda a derecha y así puede consultar cada profundidad con cualquier algoritmo de coincidencia de cadenas. Desea buscar en google el índice espacial hilbert curve quadtree blog de Nick.Pero tiene razón al suponer que la respuesta b) es muy cara, así que le sugiero que responda a) porque no es tan lenta y también existe una implementación gratuita de un quadtree javascript disponible en la biblioteca de cierre: closure-library.googlecode. com/svn/docs/class_goog_structs_QuadTree.html.