下降网格项的算法
我不知道如何简洁地描述目标,这可能是为什么我无法找到适用的算法,尽管搜索量充足,但图片清楚地显示:
鉴于左侧网格中的项目状态,是否有人知道有效查找右侧网格中显示的结束位置的算法？在这种情况下,所有项目都"下降""向下",但当然方向是任意的.关键在于:
- 有一组任意形状的项目,但都由连续的正方形组成
- 物品不能重叠
- 所有物品都应该沿给定方向移动最大距离,直到它们碰到墙壁,或者他们正在触摸另一个项目[...正在触摸另一个项目无限...]正在触摸墙壁.
这不是家庭作业,我不是学生.这是出于我对几何和编程的兴趣.我没有提到这种语言因为没关系.我可以使用我正在使用的语言中的任何算法来处理我正在处理的特定项目.一个有用的答案可以用文字或代码来描述; 这是重要的想法.
这个问题可能被抽象成依赖性和松弛空间的某种图形(在数学意义上),因此可能会采用旨在最小化滞后时间的算法.
如果您不知道答案但是即将尝试在现场编写算法,请记住可能存在循环依赖关系,例如互锁粉红色(向后)"C"和蓝色"T"形状.T的部分低于C,C的部分低于T.如果通过几个部件的"环"锁定互锁物品,这将更加棘手.
适用算法的一些注意事项:由于我构建网格对象管理框架的方式,以下所有内容都非常简单快捷:
- 枚举一块中的各个正方形
- 列举所有部分
- 找到占据整个网格中特定方块的块(如果有)
关于答案的说明: maniek首先暗示了它,但是bloops提供了一个精彩的解释.我认为绝对关键是所有移动相同数量的作品保持彼此之间的关系的洞察力,因此不必考虑这些关系.
对于人口稀少的板,额外的加速是将所有部件移位以消除完全空的行.计算空行并在一侧("上方")标识空行非常容易.
最后一点:我确实实现了bloops描述的算法,并进行了一些特定于实现的修改.它工作得很漂亮.
想法
归纳定义冻结对象集如下:
触摸底部的物体被冻结.
躺在冻结物体上的物体被冻结.
直觉上,确切地说,冷冻物体已经到达最终位置.将非冻结对象调用为活动状态.
声明:所有活动对象可以同时向下落入一个单元.
证明:当然,活动对象不会碰到另一个活动对象,因为它们相对于彼此的相对位置不会改变.活动对象也不会命中冻结对象.如果是这样,那么活动对象实际上是冻结的,因为它躺在一个冻结的物体上.这与我们的假设相矛盾.
我们算法的非常高级的伪代码如下:
while (there are active objects):
move active objects downwards simultaneously until one of them hits a frozen object
update the status (active/frozen) of each object
请注意,在while循环的每次迭代中,至少有一个对象被冻结.此外,每个对象都会被冻结一次.在分析实际算法的运行时复杂度时将使用这些观察结果.
算法
我们使用时间概念来提高大多数操作的效率.从0开始测量时间,活动对象的每个单位移动需要1个单位时间.观察到,当我们及时时t,当前活动的所有物体的位移t正好是t向下的单位.
请注意,在每列中,每个单元格的相对顺序是固定的.其中一个含义是每个细胞可以直接阻止其他一个细胞落下.该观察结果可用于有效地预测下一次碰撞的时间.我们也可以最多一次"处理"每个单元格.
我们将列从1开始索引并从左向右递增; 高度为1的行.为了便于实现,引入一个名为bottom- 的新对象,它是最初被冻结的唯一对象,由高度为0的所有单元组成.
数据结构 为了实现高效,我们维护以下数据结构:
A包含每个单元格的最终位移的关联数组.如果一个单元是活动的,那么它的入口应该是-1.对于每列
k,我们维护S_k列中活动单元格的初始行数集合k.我们需要能够支持此集合上的后续查询和删除.我们可以使用Van Emde Boas树,并回答每个查询O(log log H);H网格的高度在哪里.或者,我们可以使用可以执行这些操作的平衡二叉搜索树O(log N); 其中N是在列的单元的数目k.一个优先级队列
Q,它将使用其密钥存储活动单元作为其未来冲突的预期时间.同样,我们可以选择查询时间的vEB树O(log log H)或O(log N)每个操作的时间优先级队列.
履行
该算法的详细伪代码如下:
Populate the S_k's with active cells
Initialize Q to be an empty priority queue
For every cell b in bottom:
Push Q[b] = 0
while (Q is not empty):
(x,t) = Q.extract_min() // the active cell x collides at time t
Object O = parent_object(x)
For every cell y in O:
A[y] = t // freeze cell y at displacement t
k = column(y)
S_k.delete(y)
a = S_k.successor(y) // find the only active cell that can collide with y
if(a != nil):
// find the expected time of the collision between a and y
// note that both their positions are currently t + (their original height)
coll_t = t + height(a) - height(y) - 1
Push/update Q[a] = coll_t
可以通过查询A属于该对象的任何单元的位移来获得任何对象的最终位置.
运行时间
我们处理并冻结每个单元格一次.我们执行恒定数量的查找,同时冻结每个单元格.我们假设parent_object查找可以在恒定时间内完成.在整个算法的复杂度O(N log N)还是O(N log log H)取决于我们使用的数据结构.这N是所有对象的单元格总数.