优化的数据结构,用于2d空间搜索和Javascript实现？

Question

我正在研究俄罗斯方块式的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空间的可用性的数组超过65000)之后进行昂贵的调用以检查来自画布的最后几个像素的图像数据常规迭代器是不可避免的.

那么,A,B,C,其他？

像往常一样,所有见解都表示赞赏.

Answer 1

您想要答案 b) 并且想要实现空间填充曲线或空间索引。您不想将这些位存储在数组、对象或索引中，而是存储在字符串键中。您希望从左到右读取此字符串键，因此您可以使用任何字符串匹配算法轻松查询每个深度。您想在 google 上搜索 Nick 的空间索引希尔伯特曲线四叉树博客。但你的假设是正确的，答案 b) 非常昂贵，所以我建议你回答 a)，因为它并没有那么慢，而且闭包库中已经有一个 javascript 四叉树的免费实现：closure-library.googlecode。 com/svn/docs/class_goog_structs_QuadTree.html。