9

我正在开发一款俄罗斯方块类型的 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. 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.

4

1 回答 1

3

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

于 2011-03-26T00:11:41.463 回答