How can I efficiently shift everything in a 2d array down by a given amount?

Question

I have a 2d char array that represents a game board similar to tetris. I remove blocks from the board when there are three or more in a row. Now, I want to basically remove the spaces in between the blocks. So I want to start at the bottom right and go up each column, and them move to the next column. When I reach a blank '.' piece, I need to shift everything down.

Here are the methods I'm trying to use

public void boardGravity() {

        for (int j = c - 1; j > 0; j--) {
            for (int i = r - 1; i > 0; i--) {
                if (board[i][j] != '.') {
                    int count = 0;
                    while(isEmpty(i + count + 1, j)) {
                        count++;
                    }
                    board[i + count][c] = board[r][c];
                    board[r][c] = '.';
                }
            }
        }
    }

    public boolean isEmpty(int row, int col) {
        if (row >= 0 && col >= 0 && board[row][col] == '.') {
            return true;
        }
        return false;
    }

I'm having a hard time wrapping my head around the logic of this! I can't find anything similar enough to this either.

Edit: Here is an example output:

New Board Created!
.....
.....
.....
.....
.....
.....

.....
.....
.....
a....
a....
a....

a....
c....
b....
a....
a....
a....

a....
c....
b....
.....
.....
.....

a....
c....
b....
.....
.....
.....

In the last board print, I need the characters in the top left to be shifted to the bottom.

Can you give an example of a board, what you expected to happen, and what actually happens when you run your code? — tucuxi, Apr 26 '17 at 16:05
[What does your step debugger tell you?](http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — , Apr 26 '17 at 16:09
Sure! Okay, I added an example output of the manager. I need to shift the game pieces down like tetris. — presence, Apr 26 '17 at 16:10
Is 2d arrays even the best data (most intuitive) structure? A `deque` where you delete the bottom row at the same time as you add the top one should be simple enough? — Viktor Mellgren, Apr 26 '17 at 16:19
I may have pieces in the bottom row that don't have to be removed. I'm a beginner programmer so I don't know if a char array was the best approach but it's what everything uses at the moment and it is what my TA recommended. — presence, Apr 26 '17 at 16:23

score 0 · Answer 1 · answered Apr 26 '17 at 16:06

0

actually you don't need to detect empty line, its much easier to do:

public void boardGravity() {
    for (int i = r - 1; i > 0; i--)
        System.arraycopy(board[i - 1], 0, board[i], 0, c);
    Arrays.fill(board[0], '.');
}

answered Apr 26 '17 at 16:06

Iłya Bursov

23,342
4
33
57

score 0 · Answer 2 · answered Apr 26 '17 at 16:12

You haven't shown enough code to give a specific answer (and we're not here to write your code for you anyway!) but I can give you the general solution.

You need two pointers, one is a "write" pointer, one is a "read" pointer. The pointer is most likely just an integer value saying what to index the array with.

Start with both at 0. 

Loop until read pointer reaches top of column
   Increment the read pointer 
   If you find a match 
      Copy the value to the write pointer
      Increment the write pointer.

Loop until write pointer reaches top of column
   Increment the write pointer
   Write a blank space

You need to work out your own code for what counts as a match - an empty space. You also need to work out if you want to limit the difference between read and write pointers (so everything shuffles down a maximum of X spaces) or just want to move everything right to the bottom.

score 0 · Answer 3 · answered Apr 26 '17 at 16:12

You can make your task easier by breaking it into methods with clear names.

 void boardGravity(int[][] board) {
      for(int column = 0; column < board.length; column++) {
          columnGravity(board[column]);
      }
 }

 void columnGravity(int[] column) {
      for(int row = 0; row < column.length; column ++) {
          if(isEmpty(column[row]) {
              dropCells(column, row + 1);
          }
      }
 }

... and so on.

This assumes that your "board" is an array of columns, and your columns are arrays of cells with 0 at the bottom. However it could be adapted.

Your code would become even easier to understand if you hid your arrays in a Board class and interacted with it using method names that fit the abstraction.

How can I efficiently shift everything in a 2d array down by a given amount?

3 Answers3