最近,我在一家优秀的公司接受了面试,并被要求用高效的数据结构设计俄罗斯方块游戏。我回答了每个形状的二维数组,但面试官正在寻找更好的答案。然后,他让我也来设计Ludo。
对这两个问题有什么看法吗?
发布于 2012-11-22 03:09:16
我不知道怎么做Ludo,但是对于俄罗斯方块来说,首先想到的是使用位掩码。
你可以制作一个足够大的“超级形状”,包括俄罗斯方块中的所有形状,然后打开蒙版中的比特来生成“形状”。
这样,每个图形都可以具有相同的对象类型。当它们“着陆”时,你可以打开一个更大的比特掩码中的比特来表示电路板。当正确的位集都在“生成一行”上时,您可以处理事件。
发布于 2012-11-22 03:14:45
一个不错的选择是列出每一块相对于原点的三对偏移量(第四个偏移量是{0.0}
)。这将允许您按如下方式对shapes进行编码:
I {0,1} {0,2} {0,3}
J {0,1} {1,1} {2,1}
L {0,1} {-1,1} {-2,1}
O {0,1} {1,1} {1,0}
S {-1,0} {-1,1} {-2,1}
T {-1,1} {0,1} {1,1}
Z {1,0} {1,1} {2,1}
有了这些列表,你就能够绘制形状,检查“玻璃”中相应形状的空间可用性,应用旋转,并将其放置在玻璃内部的最终休息位置。与大多数操作需要两个嵌套循环的2D结构不同,这种结构可以让您使用单个循环进行测试,如果您unroll其简单的四个步骤,甚至可以不使用循环。
https://stackoverflow.com/questions/13500257
复制相似问题