Falling Blocks and complex shapes

Question

I currently have a simple Tetris-like game and have come across a problem I cannot solve.

Unlike Tetris where there is a single falling shape, I have multiple, potentially interlocking shapes that need to fall; I need to calculate their final positions. Consider the following:

1. To calculate the final position of the green shape, I simply scan down for every square until I hit another square or the edge of the board. Done

2. For multiple, simple shapes I work my way UP the board. Thus the red is found to not need moving, the orange goes down by one, the green down by three. Done

3. I don't know how to treat the interlocked green and red shapes. Using the logic of #2 we would end up "stuck" floating mid-air. If I scan down for the green shape, I encounter the red and thus do not move, and vice-versa for the red. The solution might be to treat the two shapes as one.

4. Similar to #3, in this scenario I could also succeed by treating the objects as one.

5. Unlike #3 and #4 I could not treat the shape as one as the orange shape would end up floating one-square too high...

6. Another variation of problem #6.

There could be other scenarios whereby I have many many shapes that interweave in more and more complex scenarios, but I think the above covers the most fundamental parts of the problem.

I feel like there's an elegant solution that I've yet to encounter / think up and would be very grateful at any insight, ideas or resources.

SOLUTION

The solution I've come up with is indeed elegant, based on @user35958's answer below, I have created the following recursive function (pseudo code)

function stop(square1, square2){
    // Skip if we're already stopped
    if(square1.stopped){
        return;
    }
    // Are we comparing squares?
    if(!square2){
        // We are NOT comparing squares, simply stop.
        square1.stopped = true;
    } else {
        // Stop IF
        // square1 is directly above square2
        // square1 is connected to square2 (part of the same complex shape)
        if(square1.x == square2.x && square1.y == (square2.y+1) || isConnected(square1, square2)){
            square1.stopped = true;
        }
    }
    // If we're now stopped, we must recurse to our neighbours
    stop(square1, squareAbove);
    stop(square1, squareBelow);
    stop(square1, squareRight);
    stop(square1, squareDown);
}

Animated GIF showing each pass of the solution

To summarise:

• When "stopping" a square, we also stop:
  • ANY square above it. ALWAYS.
  • Neighbouring square that we are connected to (ie the same shape).
• We stop the entire bottom row, and the function recurs up through the squares.
• We repeat until all squares are stopped.
• Then we animate.

Answer 1

Well, you don't exactly need to treat to shapes as one if there's a distinction between shapes that are moving and shapes that are at rest. A shape (A) could detect a shape (B) directly below it and if it's moving, then the B shape could then see if there's anything directly below it, and if there's an resting shape, then A and B are now resting, and if there's nothing, they both move down, but if there is a moving shape, then this new shape will be treated by A and B as A treated B, so it's sort of recursive. Keep in mind that for each step, the lowest shapes need to check for shapes below them first.

So, for problem #6, the green shape is the lowest moving shape, and it would see that the only shape that's directly below it is the red shape, so then the red shape would detect nothing directly below it, and they would move down. Once the green shape is adjacent to the orange shape, it would rest, and the red shape would move down and then detect the resting green shape, and it would rest too.

Answer 2

It seems like the problem with cases #5 and #6 stem from a single root: you're only performing one pass of movement checks. You should keep moving things down (lets call it a "gravity pass") until you know nothing moved.

For example, in case 6, this is what would happen if you used multiple passes:

• Orange moves down
• Green moves down
• Orange moves down
• Green moves down
• Orange moves down
• Nothing moves down (done!)

This strategy of multiple gravity passes could solve #5 as well, although it won't help with cases #3 and #4 where it seems you need to treat them like one piece.

To distinguish when two or more pieces should be treated as a single piece, I think the easiest algorithm is to check if there are any "holes" in the combined space of all the pieces. If there are, it can be treated as multiple pieces.