Algorithm for falling grid items

Question

I do not know how to describe the goal succinctly, which may be why I haven't been able to find an applicable algorithm despite ample searching, but a picture shows it clearly:

Given the state of items in the grid at the left, does anyone know of an algorithm for efficiently finding the ending positions shown in the grid at right? In this case all the items have "fallen" "down", but the direction of course is arbitrary. The point is just that:

• There are a collection of items of arbitrary shapes, but all composed of contiguous squares
• Items cannot overlap
• All items should move the maximum distance in a given direction until they are touching a wall, or they are touching another item which [...is touching another item ad infinitum...] is touching a wall.

This is not homework, I'm not a student. This is for my own interest in geometry and programming. I haven't mentioned the language because it doesn't matter. I can implement whatever algorithm in the language I'm using for the specific project I'm working on. A useful answer could be described in words or code; it's the ideas that matter.

This problem could probably be abstracted into some kind of graph (in the mathematical sense) of dependencies and slack space, so perhaps an algorithm aimed at minimizing lag time could be adapted.

If you don't know the answer but are about to try to make up an algorithm on the spot, just remember that there can be circular dependencies, such as with the interlocking pink (backwards) "C" and blue "T" shapes. Parts of T are below C, and parts of C are below T. This would be even more tricky if interlocking items were locked through a "loop" of several pieces.

Some notes for an applicable algorithm: All the following are very easy and fast to do because of the way I've built the grid object management framework:

• Enumerate the individual squares within a piece
• Enumerate all pieces
• Find the piece, if any, occupying a specific square in the overall grid

A note on the answer: maniek hinted it first, but bloops has provided a brilliant explanation. I think the absolute key is the insight that all pieces moving the same amount maintain their relationship to each other, and therefore those relationships don't have to be considered.

An additional speed-up for a sparsely populated board would be to shift all pieces to eliminate rows that are completely empty. It is very easy to count empty rows and to identify pieces on one side ("above") an empty row.

Last note: I did in fact implement the algorithm described by bloops, with a few implementation-specific modifications. It works beautifully.

Answer 1

The Idea

Define the set of frozen objects inductively as follows:

• An object touching the bottom is frozen.

• An object lying on a frozen object is frozen.

Intuitively, exactly the frozen objects have reached their final place. Call the non-frozen objects active.

Claim: All active objects can fall one unit downwards simultaneously.

Proof: Of course, an active object will not hit another active object, since their relative position with respect to each other does not change. An active object will also not hit a frozen object. If that was so, then the active object was, in fact, frozen, because it was lying on a a frozen object. This contradicts our assumption.

Our algorithm's very high-level pseudo-code would be as follows:

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

Notice that at least one object becomes frozen in each iteration of the while loop. Also, every object becomes frozen exactly once. These observations would be used while analyzing the run-time complexity of the actual algorithm.

The Algorithm

We use the concept of time to improve the efficiency of most operations. The time is measured starting from 0, and every unit movement of the active objects take 1 unit time. Observe that, when we are at time t, the displacement of all the objects currently active at time t, is exactly t units downward.

Note that in each column, the relative ordering of each cell is fixed. One of the implications of this is that each cell can directly stop at most one other cell from falling. This observation could be used to efficiently predict the time of the next collision. We can also get away with 'processing' every cell at most once.

We index the columns starting from 1 and increasing from left to right; and the rows with height starting from 1. For ease of implementation, introduce a new object called bottom - which is the only object which is initially frozen and consists of all the cells at height 0.

Data Structures For an efficient implementation, we maintain the following data structures:

• An associative array A containing the final displacement of each cell. If a cell is active, its entry should be, say, -1.

• For each column k, we maintain the set S_k of the initial row numbers of active cells in column k. We need to be able to support successor queries and deletions on this set. We could use a Van Emde Boas tree, and answer every query in O(log log H); where H is the height of the grid. Or, we could use a balanced binary search tree which can perform these operations in O(log N); where N is the number of cells in column k.

• A priority queue Q which will store the the active cells with its key as the expected time of its future collision. Again, we could go for either a vEB tree for a query time of O(log log H) or a priority queue with O(log N) time per operation.

Implementation

The detailed pseudo-code of the algorithm follows:

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

The final position of any object can be obtained by querying A for the displacement of any cell belonging to that object.

Running Time

We process and freeze every cell exactly once. We perform a constant number of lookups while freezing every cell. We assume parent_object lookup can be done in constant time. The complexity of the whole algorithm is O(N log N) or O(N log log H) depending on the data structures we use. Here, N is the total number of cells across all objects.

Answer 2

And now something completely different :)

Each piece that rests on the ground is fixed. Each piece that rests on a fixed piece is fixed. The rest can move. Move the unfixed pieces 1 square down, repeat until nothing can move.

Answer 3

Okay so this appears to be as follows -

• we proceed in step
• in each step we build a directed graph whose vertices are the object set and whose edges are as follows =>

1) if x and y are two objects then add an edge x->y if x cannot move until y moves. Note that we can have both x->y and y->x edges.

2) further there are objects which can no longer move since they are at the bottom so we colour their vertices as blue. The remaining vertices are red.

2) in the directed graph we find all the strongly connected components using Kosaraju's algorithm/Tarjan's algorithm etc. (In case you are not familiar with SCC then they are extremely powerful technique and you can refer to Kosaraju's algorithm.) Once we get the SCCs we shrink them to a small vertex i.e. we replace the SCC by a single vertex while preserving all external(to SCC) edges. Now if any of the vertex in SCC is blue then we color the new vertex as blue else it is red. This implies that if one object cannot move in SCC then none can.

3) the graph you get will be a directed acyclic graph and you can do a topological sort. Traverse the vertex in increasing order of top numbering and as long as you see a red colour vertex and move the objects represented by the vertex.

continue this step until you can no longer move any vertex in step 3.

If two objects A and B overlap then we say that they are inconsistent relative to each other. For proof of correctness argue the following lemmas 1) "if I move an SCC then none of the object in it cause inconsistency among themselves." 2) "when I move an object in step 3 then I do not cause inconsistencies"

The challenge for you now will be to formally prove the correctness and find suitable data structures to solve it in efficient. Let me know if you need any help.