Algorithm that searches a 2D array

Question

I'm trying to recreate a tetris-like game. I have a 2D array, "_tiles" that stores objects called "ColorShape" .

private ColorShape[][] _tiles = new ColorShape[8][17];;

im trying to make a quickDrop() method for when I hit the down arrow key to find the next available slot in the array to quickly place the shapes. I am having a hard time figuring out the algorithm that will search the rows below the current piece in the column that the piece is in.

This is what I tried to do so far but I think that I am going about this all wrong: (the Pieces are 30x30 pixels thats why they are being divided by 30, so that the array location corresponds to the x and y locations of the shape)

public void quickDrop(){

   // j is the column that the piece is currently in
   int j = _proxyPiece.getXLocation()/30;

    for (int i=0; i<17;i++){

        if(_tiles[j][i] == null)
          continue;



       else if (_tiles[j][i] != null){
         _tiles[j][i-2] =  _proxyPiece.getFirstPiece();  
         _tiles[j][i-1] =  _proxyPiece.getSecondPiece();
         repaint();

         _proxyPiece.setPiece(this.newPiece());
         repaint();
         break;
       }    


  }
}

public void paintComponent(Graphics g) {
    if (_pauseState == false){
    _pauseText.setVisible(false);
    super.paintComponent(g);
    // simplify the positioning of things.
    g.translate(0, 0);

    //Draws the board outline and fills it white
    g.setColor(Color.WHITE);
    g.drawRect(0, 0, 240, 480);
    g.fillRect(0, 0, 240, 480);

    //Draws a dark gray grid 
    g.setColor(Color.DARK_GRAY);

        for(int x = 0; x < COL_COUNT + 1; x++) {
            for(int y = 0; y < VISIBLE_ROW_COUNT+1; y++) {
                g.drawLine(0, y * TILE_SIZE, COL_COUNT * TILE_SIZE, y * TILE_SIZE);
                g.drawLine(x * TILE_SIZE, 0, x * TILE_SIZE, VISIBLE_ROW_COUNT *    TILE_SIZE);
            }
        }

    Graphics2D aBetterPen = (Graphics2D)g;    
    _proxyPiece.fill(aBetterPen);

    for (int i = 0; i<16; i++){
        for(int j=0; j<8;j++){
            if(_tiles[j][i] != null)
             _tiles[j][i].fill(aBetterPen);
        }
    }
}
   else if (_pauseState == true){
       _pauseText.setVisible(true);
       super.paintComponent(g);
       // simplify the positioning of things.
       g.translate(0, 0);
       g.setColor(Color.WHITE);
       g.drawRect(0, 0, 240, 480);
       g.fillRect(0, 0, 240, 480);

    }

}

What does getXLocation() return? Simply dividing it be 30 could produce unexpected results if it doesn't result in a whole number. — Jesse Jashinsky
– Jesse Jashinsky, Commented Jul 5, 2013 at 20:12
Nice to see you again, and interesting to see you're working on a tetris-like game. It will teach you much, good choice. I've given a possible solution to your question, please let me know if I can be of further assistance. — William Morrison
– William Morrison, Commented Jul 5, 2013 at 20:37

William Morrison · Accepted Answer · 2013-07-05 20:38:23Z

1

One algorithm to solve this:

Take the current dropping piece and move it over every Y value from its current position downwards.
If it collides with a previously placed piece, or exceeds the bottom of your grid, the last Y position you checked is a valid solution.

If you want all valid solutions instead of just one, repeat this algorithm for all possible rotations of the currently selected piece.

Here's an example of the algorithm. It won't work with your code as is, but it will get you off to a quick start.

ColorShape[][] grid = new ColorShape[width][height];
TetrisShape shape = new TetrisShape(Shape.L_SHAPE);

//position will be bottom left coordinate of bounding rectangle of dropping shape.
Point position = new Point(shape.getPosition());
int resultY = -1;
for(int dy=0;dy<height;dy++){
    for(int y=0;y<height;y++){
        int shapeY = position.y+y;
        if(shapeY>=height || shape.intersectsGrid(grid)){
            resultY = shapeY -1;
            break;
        }        
    }
}

edited Jul 5, 2013 at 20:38

answered Jul 5, 2013 at 20:14

William Morrison

11.1k2 gold badges36 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

ajp15243 Over a year ago

Given the relatively small grid of a typical Tetris game (and what I assume are the dimensions of 8x17 for OP), the typical inefficiencies of brute forcing it will probably not be noticeable.

William Morrison Over a year ago

I completely agree. I've edited my post to not include this.

William Morrison Over a year ago

I think you've unaccepted my answer. If so, please explain why. I am happy to help you further.

steven Over a year ago

@WilliamMorrison thank for your help, but I have tried to use your advice and couldn't get it to work. I updated my post with a method I am currently testing. it seems to work but there is some problem with painting the pieces

William Morrison Over a year ago

You are calling getXLocation, assiging it to J, then using J as a y coordinate...

Collectives™ on Stack Overflow

Algorithm that searches a 2D array

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related