Naive Gravity for Tetris game using 2D Array for the playfield

Question

I'm writing a Tetris-clone and I'm prototyping in C#. The final code is supposed to run on an embedded system (using an 8-Bit CPU and very little RAM), so I'm trying to use a naïve algorithm to do line clear.

Right now, my playfield is a 2D Array:

private readonly TetrominoType[][] _playfield;

(where TetrominoType is an enum to indicate either None or one of the 7 types, used for coloring blocks)

When a line is cleared, I want to modify this array in-place, which is where my problem is. Take this example:

   Before       After
0 #      #     #      #
1 #      #     #      #
2 #      #     #      #
3 #      #     #      #
4 #      #     #      #
5 #xxxxxx#     #      #
6 #x   xx#     #      #
7 #xxxxxx#     #      #
8 #xxxxxx#     #x   xx#
9 #x xxxx#     #x xxxx#
  ########     ########

I have already determined that lines 5, 7 and 8 need to be removed and thus other lines should fall down, leaving me with the state on the right.

My naïve way is to iterate backwards and copy the line above a cleared one, basically:

for(int iy = 9; iy >= 0; iy--) {
    if(_linesToClear.Contains(iy)) {
        for(int ix = 0; ix < 6; ix++) {
            _playfield[iy][ix] = _playfield[iy-1][ix];
        }
    }
 }

The problem here is that the line above might also be cleared (e.g, if iy == 8 then I don't want to copy line 7 but line 6) and also that I need to clear the copied line (iy-1) - or copy the line above that one which in turn need to trickle upward.

I tried counting how many lines I already skipped, but that works only if I create a new array and then swap them out, but I can't get the math work for in-place modification of the playfield array.

It's possibly really simple, but I'm just not seeing the algorithm. Does anyone have some insight how I can do this?

It wouldn't perform as well, but have you considered scanning your playing field for a *single* removed line, removing that, and adjusting the rest accordingly, and repeating this algorithm until there are no removed lines? This sort of "sweep" algorithm is often used to deconstruct dependency graphs -- while inefficient, they're really easy to reason about and might fit the bill here. On the other hand, they're probably not as efficient as possible. — Kirk Woll, Feb 04 '14 at 03:06
@KirkWoll I thought about that, it seemed to inefficient without even testing it though, so I might give it another shot. Even on a 1 MHz 6502 Processor (the target), that should be fairly quick. Feels a bit too brute force though, but then again, sometimes brute force is exactly what's needed. — Michael Stum, Feb 04 '14 at 03:08
I think usual code for that is "from bottom to top, copy all lines that should stay, fill the rest with empty lines" - just 2 indexes to remember - current line to write to and current line to read from ( read >= write)... Also you may want to remove one line/redraw depending on what you want to show. — Alexei Levenkov, Feb 04 '14 at 03:11
@MichaelStum I would suggest using a `List`, that way when you remove a row you simply do `List.Remove()`; — Matthew Pigram, Feb 04 '14 at 05:50
@MatthewPigram Indeed, I would use that if C# was the final language. I'm using it as a prototype/proof of concept to understand the algorithms, the final program will be written in 6502 Assembly on a 4k RAM system, hence I'm keeping stuff as simple as possible :) — Michael Stum, Feb 04 '14 at 05:54

score 2 · Answer 1 · answered Feb 04 '14 at 03:10

The main problem is multiple cleared lines, so we need to make sure that when you have multiple cleared lines in a row to move everything down through all of them. Since you have a list of which lines need to be cleared, instead of just copying the line above it, you can find how far up the next non-cleared line is, and move everything above it down that many lines. For example, you could do this:

for(int iy = 9; iy >= 0; iy--)
{
    if(_linesToClear.Contains(iy))
    {
        int nextLineIndex = iy-1;
        while( _linesToClear.contains(nextLineIndex) && nextLineIndex >= 0 )
        {
            nextLineIndex--;
        }
        if ( nextLineIndex >= 0 )
        {
            int amountToDrop = iy - nextLineIndex
            for(int ix = 0; ix < 6; ix++)
            {
                _playfield[iy][ix] = _playfield[iy-amountToDrop][ix];
            }
        }
    }
 }

This would figure out how many cleared lines there are in a row, then drop everything down that many lines. I hope this helps!

AlexD · Accepted Answer · 2014-02-04T03:40:16.067

1

Would it work?

int k = 0;
for(int iy = 9; iy >= 0; iy--) {
    if(!_linesToClear.Contains(iy)) {
        for(int ix = 0; ix < 6; ix++) {
            _playfield[iy + k][ix] = _playfield[iy][ix];
        }
    }
    else
        k++;
}

edited Feb 04 '14 at 03:40

answered Feb 04 '14 at 03:34

AlexD

32,156
3
71
65

The problem with that is that it doesn't take care of multiple lines and might duplicate the rows above cleared lines. That is the thing that gives me trouble. – Michael Stum Feb 04 '14 at 03:43
@MichaelStum The loop creates the "bottom part". After that, cannot you just clean up the "top part", 9 - k lines? – AlexD Feb 04 '14 at 03:48
Bingo! Didn't even need to clean it up, the way `k` is used to keep a running count of skipped lines is perfect. Thanks so much! – Michael Stum Feb 04 '14 at 03:54

Naive Gravity for Tetris game using 2D Array for the playfield

2 Answers2