下降网格项目的算法

Question

我不知道如何简洁地描述目标，这可能是为什么我尽管搜索了很多也找不到适用的算法，但一张图清楚地说明了这一点:

给定左侧网格中项目的状态，有谁知道一种算法可以有效地找到右侧网格中显示的结束位置？在这种情况下，所有项目都“掉落了” ” “向下”，但方向当然是任意的。重点是:

• 有一组任意形状的元素，但都是由连续的正方形组成
• 项目不能重叠
• 所有项目都应在给定方向上移动最大距离，直到它们接触到墙壁，或者它们正在接触另一个项目，而另一个项目[...正在无限地接触另一个项目...]正在接触墙壁。

这不是作业，我不是学生。这是出于我自己对几何和编程的兴趣。我没有提到语言，因为它无关紧要。我可以用我正在从事的特定项目使用的语言实现任何算法。有用的答案可以用文字或代码来描述；重要的是想法。

这个问题可能会被抽象成某种依赖关系和松弛空间的图(在数学意义上)，因此也许可以采用旨在最小化滞后时间的算法。

如果您不知道答案但准备当场尝试编写算法，请记住可能存在循环依赖关系，例如互锁的粉色(向后)“C”和蓝色“T” “形状。 T 的部分在 C 下方，C 的部分在 T 下方。如果互锁项目通过几个部分的“循环”锁定，这将更加棘手。

适用算法的一些注意事项:由于我构建网格对象管理框架的方式，以下所有操作都非常容易和快速:

• 枚举一 block 中的各个方 block
• 枚举所有片段
• 找到占据整个网格中特定方格的棋子(如果有的话)

关于答案的注释:maniek 首先暗示了这一点，但 bloops 提供了一个绝妙的解释。我认为绝对关键是所有移动相同量的部分都保持彼此之间的关系，因此不必考虑这些关系。

对于人口稀少的棋盘，另一个加速方法是移动所有棋子以消除完全空的行。计算空行数和识别空行一侧(“上方”)的棋子非常容易。

最后一点:我确实实现了 bloops 描述的算法，并进行了一些特定于实现的修改。效果很好。

Answer 1

理念

如下归纳定义卡住对象集:

• 接触底部的物体被卡住。

• 躺在卡住物体上的物体被卡住。

直觉上，卡住的物体正好到达了它们的最终位置。调用非卡住对象active。

声明:所有事件物体可以同时向下掉落一个单位。

证明:当然，一个事件物体不会撞击另一个事件物体，因为它们相对于彼此的相对位置不会改变。事件对象也不会撞到卡住的对象。如果是这样，那么事件对象实际上是卡住的，因为它躺在一个卡住的对象上。这与我们的假设相矛盾。

我们算法的高级伪代码如下:

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，我们维护 k 列中事件单元格的初始行号的集合 S_k。我们需要能够支持对该集合的后续查询和删除。我们可以使用 Van Emde Boas 树，并在 O(log log H) 中回答每个查询；其中 H 是网格的高度。或者，我们可以使用平衡二叉搜索树，它可以在 O(log N) 中执行这些操作；其中 N 是 k 列中的单元格数。

• 一个优先级队列Q，它将存储事件单元及其键作为其 future 碰撞的预期时间。同样，我们可以选择查询时间为 O(log log H) 的 vEB 树或每个操作时间为 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 是所有对象的单元格总数。