网格项下落算法

Question

我不知道如何简洁地描述这个目标，这可能是为什么尽管进行了大量的搜索，但我仍然无法找到适用的算法，但一张图片可以清晰地展示它：

给定左侧网格中的项目状态，有人知道一种有效的算法来查找右侧网格中显示的结束位置吗？在这种情况下，所有项目都已“下降”，但是方向当然是任意的。重点是：

- 有一组由相邻正方形组成的任意形状的项目 - 项目不能重叠 - 所有项目应该沿着给定方向移动最大距离，直到它们接触墙壁，或者它们接触另一个项目，该项目[...无限制地接触另一个项目...]接触墙壁。

这不是作业，我不是学生。这是我对几何和编程的兴趣。我没有提及语言，因为它并不重要。我可以在我正在工作的特定项目所使用的语言中实现任何算法。有用的答案可以用文字或代码描述；思想很重要。

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

如果您不知道答案，但即将试图即兴制定算法，请记住可能存在循环依赖关系，例如交错的粉色（向后）“C”和蓝色“T”形状。 T的一部分在C下方，C的一部分在T下方。如果交错的物品通过几个零件的“循环”锁定，这将更加棘手。

适用算法的一些说明：由于我构建了网格对象管理框架，以下所有内容都非常容易快速完成：

- 枚举每个零件内的单个正方形 - 枚举所有零件 - 查找在整个网格中占据特定正方形的零件（如果有）

答案的一个提示是：maniek首先提到了它，但bloops提供了一个绝妙的解释。我认为绝对关键是洞察到所有移动相同量的零件保持彼此的关系，因此那些关系不必考虑。

对于稀疏填充的板的另一个加速方法是移动所有零件以消除完全为空的行。很容易计算空行并识别位于空行上方的一侧（“以上”）的零件。

最后说明：我确实实现了bloops所描述的算法，并进行了一些特定于实现的修改。它的工作效果非常好。

- Joshua Honig

---

好问题。一开始我还以为你在看俄罗斯方块，但原来不是。 - James

@James 是的。看起来很相似，但更加通用化。 - Joshua Honig

Answer 1

思路

将一组冻结对象归纳定义如下：

• 接触底部的物体为冻结。

• 位于冻结物体上方的物体为冻结。

直观地说，仅有冻结的物体已经到达了它们的最终位置。未冻结的物体称为活动物体。

声明：所有活动物体可以同时向下移动一个单位。

证明：显然，一个活动物体不会撞到另一个活动物体，因为它们相对于彼此的位置不会改变。活动物体也不会撞到冻结物体。如果是这样的话，那么活动物体实际上就是冻结的，因为它位于一个冻结物体上面。这与我们的假设矛盾。

我们算法的高层次伪代码如下：

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个单位向下。

请注意，在每列中，每个单元格的相对顺序是固定的。其中一个影响是每个单元格最多只能直接阻止一个其他单元格下落。这个观察结果可用于有效地预测下一个碰撞的时间。我们也可以最多处理每个单元格一次。

我们从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 是所有对象中单元格的总数。

- bloops

---

他确实提到了，但你对这个想法进行了很好的扩展。作为第一个回答，做得很好！在我测试一些东西之前，我不会标记答案。但是你的口头阐述是有说服力的。 - Joshua Honig

非常优雅，解释得非常清晰，分析得也很好。点个赞！ - Li-aung Yip

@Li-aungYip 谢谢你的赞美。 :) - bloops

Answer 2

现在换个完全不同的话题 :)

每个放在地面上的部分都是固定的。每个放在固定部分上的部分也是固定的。其他部分可以移动。将非固定部分向下移动1个方块，重复此过程直到没有任何部件可以移动。

- maniek

---

我认为这是正确的方法。它也可以高效地实现。唯一的注意事项是，对于一个稀疏的高棋盘（例如100000高度和5个棋子），它会很慢，因为它只能每次移动1个方块。在这种情况下，似乎不容易将其扩展为快速操作，因为您必须对强连接的棋子进行处理。 - Claudiu

@Claudiu 很好的观点，但很容易解决：对于稀疏的棋盘，可以轻松地批量移动棋子，以消除完全为空的行。很容易计算空行并识别在空行上方的棋子。 - Joshua Honig

Answer 3

我还没有清楚地了解所有细节，但我认为以下方法似乎是一个比较系统的做法：

1. 把整个图像看作一个图，你需要的是所有顶点（即项目）的拓扑排序。如果A的任何部分在B的下方，则A应该在B之前进行排序。然后，当你按照这个顺序对它们进行排序时，你可以直接迭代它们，并确定它们的位置，因为所有在当前项目下面的项目已经有了固定的位置。
2. 为了能够进行拓扑排序，你需要一个无环图。然后，你可以使用一些算法去查找所有的循环和压缩成单个顶点，例如强连通分量。然后你就可以对结果图进行拓扑排序。
3. 要找出SCC中各个元素的位置：首先把它看作一个大块，并确定它的最终位置。这将确定一些不能再移动的固定块。然后删除它们并针对SCC中其余部分（如果有的话）重复相同的过程，以找出它们的最终位置。

第三部分似乎是唯一需要计算密集型的部分 - 如果你的碎片结构非常复杂，但仍然比试图将碎片一格一格地移动更优化。

- Ivan Vergiliev

Answer 4

好的，看起来这是以下情况 -

- 我们按步骤进行 - 在每一步中，我们构建一个有向图，其顶点是对象集合，其边如下 => 1. 如果x和y是两个对象，则添加一个边x->y，如果x在y移动之前不能移动。请注意，我们可以同时拥有x->y和y->x边。 2. 此外，有些对象由于处于底部而无法再移动，因此我们将它们的顶点染成蓝色。剩余的顶点为红色。

- 在有向图中，我们使用Kosaraju算法/Tarjan算法等找到所有强连接组件。 （如果您不熟悉SCC，则它们是非常强大的技术，您可以参考Kosaraju算法。）一旦我们获得了SCC，我们将它们缩小到一个小顶点，也就是用单个顶点替换SCC，同时保留所有外部（对于SCC）边缘。现在，如果SCC中任何顶点都是蓝色的，则我们将新顶点着色为蓝色，否则它是红色的。这意味着如果SCC中的一个对象不能移动，则没有一个对象能够移动。 - 您得到的图将是有向无环图，并且您可以进行拓扑排序。按照顶部编号递增的顺序遍历顶点，并在看到红色顶点时移动表示该顶点的对象。 - 在步骤3中，只要您无法再移动任何顶点，就继续执行此步骤。

如果两个对象A和B重叠，则我们称它们相对于彼此不一致。为证明正确性，请考虑以下引理 1）“如果我移动一个SCC，则其中任何一个对象都不会导致它们自己之间的不一致性。” 2）“当我在第三步中移动一个对象时，我不会造成不一致性。”

现在对于您的挑战是正式证明正确性并找到适合的数据结构以高效地解决它。如果需要帮助，请告诉我。

- Dipendra Kumar Mishra

Answer 5

已经进行了多次编辑。我认为您只需要执行以下操作：

1. 查找所有仅能相互依赖的碎片，并将它们组合成一个等效的更大碎片（例如，您图片中的T和反向的C）。

2. 迭代所有碎片，将它们沿最大方向向下移动，直到撞到物体。重复此过程，直到没有东西可以移动。

- Claudiu

---

@James：实际上，你只需要其中一个方向为真就可以组合这些部件。这意味着它们必须一起掉落。 - Claudiu

我在考虑如果一个方块被另一个方块阻止下落到最大高度，那么它们之间的 dependsOn 属性应该设置为 true。例如，蓝色 T 方块会依赖于浮动的紫色 _ 方块。在这种情况下，你不会进行任何组合，直到它们真正接触。 - James

我非常确定这不起作用，比如我们从正确的图片开始但没有两个粉色块的情况。 - Nabb

@Nabb：在那种情况下为什么不起作用呢？T，C，L组合将全部向下移动1个方块，然后就完成了。 - Claudiu

如果存在间接连接，第一步可能会有些棘手http://i.stack.imgur.com/JSQzL.png，因此我会扩展答案以更详细地涵盖这一点。 - unkulunkulu