10
\$\begingroup\$

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:

examples of the falling blocks problem

  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.

Animated GIF showing each pass of the logical sequence

\$\endgroup\$
  • \$\begingroup\$ I imagine if you solved 5 that 6 would be solved as well. In fact, I believe solving 5 would probably solve all these situations. \$\endgroup\$ – UnderscoreZero Oct 10 '13 at 15:51
  • \$\begingroup\$ +1 thanks for sharing. Amazing solution. Love the animation :) \$\endgroup\$ – ashes999 Oct 14 '13 at 19:50
  • \$\begingroup\$ Cheers ashes999, I think I need a new animation with arrows that show the how the stop logic "flows" up from the bottom row and proliferates through the entire stage... \$\endgroup\$ – oodavid Oct 15 '13 at 10:25
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Am I right in thinking that we'd have to assume all shapes aren't at rest until we prove otherwise? \$\endgroup\$ – oodavid Oct 10 '13 at 16:38
  • \$\begingroup\$ I've just spent some time pondering this and I must say it sounds like a very good technique. I'll give it a try tomorrow / the weekend and see how it pans out. \$\endgroup\$ – oodavid Oct 10 '13 at 20:20
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ With #3 and #4 there could also be variations where say 2 or 3 shapes are fully enclosed by a larger "C" shape, figuring out if pieces are coagulated could throw up further problems. I'll give that a go and see what comes of it! Cheers @ashes999 \$\endgroup\$ – oodavid Oct 10 '13 at 16:38
  • \$\begingroup\$ @oodavid your requirements/design seems unnecessarily complicated to me. Start with something simpler and work your way up as you solve these problems. \$\endgroup\$ – ashes999 Oct 10 '13 at 19:53
  • \$\begingroup\$ Nahhhh, the problem above is a thoroughly simplified / abstracted way to describe a much more complex problem. I'm doing this for the thrill of the chase! \$\endgroup\$ – oodavid Oct 10 '13 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.