Structure de données optimisée pour la recherche spatiale 2D et l'implémentation JavaScript?

Question

Je travaille sur un jeu HTML5 de type Tetris et j'ai besoin de renforcer un algorithme d'optimisation de l'espace. Des blocs rectangulaires de taille variable doivent être ajoutés à la toile de la manière la plus efficace de l'espace. Je sais combien d'espace le bloc prend, j'ai besoin de trouver le point le plus proche que le bloc peut être ajouté avec une coordonnée X fixe - le point le plus proche absolu est une belle à avoir.

J'ai implémenté une version qui recherche à l'aide de pixels par la vérification de la valeur de pixel sur la toile qui pousse vers le bas jusqu'à ce qu'elle trouve suffisamment d'espace libre pour la forme, puis l'ajoute. Cela ne fonctionne (lentement) que si l'espace se remplit de gauche à droite - l'algorithme peut supposer en toute sécurité si la première colonne de pixels est sûre, tout le bloc entier peut être ajouté.

J'ai besoin de rendre cela plus robuste, c'est là que je pense que cela devrait aller.

Le stockage d'un quad pour représenter l'état du conseil d'administration me donne un moyen plus rapide d'identifier où il y a de l'espace.

4 nœuds sont stockés pour chaque niveau de profondeur - chaque nœud est soit 0 pour complètement vide, soit 1 pour «a des trucs quelque part». Chaque niveau progressif de profondeur donne de plus en plus d'informations sur le conseil d'administration.

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'

Quelle est la meilleure structure de données JavaScript pour représenter la grille?

Des choses que j'ai considérées jusqu'à présent:

A. Construisez un plein tree Objet avec des pointeurs sur les enfants et les valeurs et un ensemble de méthodes pour y parcourir. Ce serait intuitif et probablement économe en espace, mais je soupçonne que c'est horriblement lent.

B. Regardez chaque grille comme 4 bits et stockez les profondeurs sous forme de réseaux ou d'objets hexadécimaux. S'il est fait par une personne plus intelligente que moi-même, cela optimise probablement non seulement le stockage, mais rend les opérations de bit intelligentes disponibles pour comparer les cellules adjacentes, activer et désactiver les blocs, etc. J'imagine que ce serait incroyablement rapide, incroyablement efficace, mais c'est au-delà mes compétences à développer.

C. Stockez chaque profondeur dans un tableau. 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. C'est là que je me dirige en ce moment. Ce n'est pas très efficace dans l'espace et ce ne sera probablement pas incroyablement rapide, mais je pense que je peux y arriver.

Il y a une limite pratique à toute structure au nombre de profondeurs (le tableau pour stocker la disponibilité des espaces 4x4 dans ma dernière approche est supérieur à 65 mille) après avoir fait l'appel coûteux pour vérifier les derniers pixels de données d'image de la toile avec Un itérateur régulier est inévitable.

Alors, a, b, c, autre?

Comme d'habitude, toutes les idées ont apprécié.