優化的二維空間搜索和Javascript實現的數據結構？

Question

我正在研究一個Tetris類型的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.建立並指出了兒童和值和一套方法來瀏覽其全tree對象。這將是直觀的，可能節省空間，但我懷疑是非常緩慢。

B.將每個網格看作4位，並將深度存儲爲十六進制數組或對象。如果一個比我更聰明的人完成，這可能不僅優化了存儲空間，而且使得巧妙的位操作可用於比較相鄰單元格，打開和關閉塊等等。我想它會非常快速，非常高效，但它超越了我的技能打造。 C.將每個深度存儲在數組中。 Depth[0]=[1,0,0,0]; Depth[1][1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0]等。這是我目前所處的位置。這不是非常節省空間，它可能不會非常快，但我想我可以讓我的頭。

任何結構的深度數（在我的最後一種方法中存儲4x4空間的可用性的數組超過65,000）都有實際的限制，之後會花費昂貴的時間檢查圖像數據的最後幾個像素從具有常規迭代器的畫布是不可避免的。

那麼，A，B，C，其他？

像往常一樣，所有的見解都被讚賞。

Answer 1

你想要回答b）並且你想要實現一個空間填充曲線或空間索引。您不希望將這些位存儲在數組或對象或索引中，而是存儲在一個字符串鍵中。你想從左到右閱讀這個字符串鍵，因此你可以用任何字符串匹配算法輕鬆查詢每個深度。你想爲Nick的空間索引希爾伯特曲線四叉樹博客谷歌。但是你認爲答案b）非常昂貴，所以我建議你回答a），因爲它的速度並不慢，並且已經有一個可從閉包庫中獲得的javascript quadtree的免費實現：closure-library.googlecode。 COM/SVN /文檔/ class_goog_structs_QuadTree.html。