Hard-dropping pieces in tetris-like game

Question

I'm building a tetris-like game, where in stead of removing just one line when you've got a full line I remove all the connected pieces. This has got me stumped on the hard-drop after clearing the pieces.

See this example for a quick and dirty version of what I'm trying to do.

function Board (width, height) {
    this.width = width;
    this.height = height;
    this.board = [];
    this.pieces = [];
    for (var y = 0; y < this.height; y++) {
        for (var x = 0; x < this.width; x++) {
            if (!this.board[y]) {
                this.board[y] = [];
            }
            this.board[y][x] = null;
        }
    }

    this.canPlace = function(piece, at) {
        for (var y = 0; y < piece.getHeight(); y++) {
            for (var x = 0; x < piece.getWidth(); x++) {
                if ((y+at.y >= this.height) || this.board[y+at.y][x+at.x]) {
                    return false;
                }
            }
        }
        return true;
    }

    this.hasFullLine = function(line) {
        for (var x = 0; x < this.width; x++) {
            if (!this.board[line][x]) {
                return false;
            }
        }
        return true;
    }

    this.place = function(piece) {
        var position = piece.getPosition();
        var shape = piece.getShape();
        for (var y = 0; y < piece.getHeight(); y++) {
            for (var x = 0; x < piece.getWidth(); x++) {
                if (shape[y][x]) {
                    this.board[y+position.y][x+position.x] = piece;
                }
            }
        }
        if (this.pieces.indexOf(piece) === -1) {
            this.pieces.push(piece);
        }
        piece.render();
    }

    this.hardDropPieces = function() {
        var pieces = this.pieces.slice();
        pieces = pieces.sort(function(a,b) {
            var aBottom = a.getPosition().y+a.getHeight();
            var bBottom = b.getPosition().y+b.getHeight();
            return bBottom-aBottom;
        });
        for (var i = 0; i < pieces.length; i++) {
            this.hardDrop(pieces[i]);
        }
    }

    this.hardDrop = function(piece) {
        var position = piece.getPosition();
        this.clearArea(piece);
        while(this.canPlace(piece, {x: piece.getPosition().x, y: piece.getPosition().y+1})) {
            piece.setPosition(piece.getPosition().x, piece.getPosition().y+1);
        }
        this.place(piece);
    }

    this.clearArea = function(piece) {
        var position = piece.getPosition();
        var shape = piece.getShape();
        for (var y = 0; y < piece.getHeight(); y++) {
            for (var x = 0; x < piece.getWidth(); x++) {
                if (shape[y][x]) {
                    this.board[y+position.y][x+position.x] = null;
                }
            }
        }
    }

    this.remove = function(piece) {
        this.clearArea(piece);
        this.pieces.splice(this.pieces.indexOf(piece),1);
    }

    this.clearPiecesOnLine = function(line) {
        var piecesToClear = [];
        for (var x = 0; x < this.width; x++) {
            var piece = this.board[line][x];
            if (piecesToClear.indexOf(piece) === -1) {
                piecesToClear.push(piece);
            }
        }
        for (var i = 0; i < piecesToClear.length; i++) {
            this.remove(piecesToClear[i]);
        }
        return piecesToClear;
    }

    this.toString = function() {
        var str = "";
        for (var y = 0; y < this.height; y++) {
            for (var x = 0; x < this.width; x++) {
                str += this.board[y][x] ? "1" : "0";
            }
            str += "\n";
        }
        return str;
    }
}

function Piece (shape, fill, stroke, paper, cellWidth) {
    this.shape = shape;
    this.fill = fill;
    this.stroke = stroke;
    this.cellWidth = cellWidth;
    this.svgGroup = paper.g().append();
    this.position = {x:0, y:0};
    this.width = this.shape[0].length;
    this.height = this.shape.length;
    this.removed = false;
    for (var y = 0; y < this.height; y++) {
        for (var x = 0; x < this.width; x++) {
            if (this.shape[y][x]) {
                var rect = paper.rect(x*cellWidth, y*cellWidth, cellWidth, cellWidth);
                rect.attr({
                    fill: this.fill,
                    stroke: this.stroke
                });
                rect.appendTo(this.svgGroup);
            }
        }
    }
    this.setPosition = function(x, y) {
        this.position.x = x;
        this.position.y = y;
    }
    this.getPosition = function() {
        return this.position;
    }
    this.render = function() {
        var matrix = new Snap.Matrix();
        matrix.translate(this.position.x*cellWidth, this.position.y*cellWidth);
        this.svgGroup.attr({
            transform: matrix
        });
    }
    this.getWidth = function() {
        return this.width;
    }
    this.getHeight = function() {
        return this.height;
    }
    this.getShape = function() {
        return this.shape;
    }
    this.delete = function() {
        this.svgGroup.remove();
    }
    this.isRemoved = function() {
        return this.removed;
    }
}

var shapes = [
    [
        [0,1,0],
        [1,1,1]
    ],
    [
        [1,1,1,1]
    ],
    [
        [1,1,1],
        [0,1,0],
        [1,1,1]
    ],
    [
        [1,1],
        [1,1]
    ],
    [
        [1,1,1],
        [0,1,1],
        [0,1,1],
        [1,1,1]
    ],
    [
        [1,1,1,1],
        [1,1,1,1],
        [1,1,1,1],
        [1,1,1,1]
    ],
    [
        [1,0,1],
        [1,1,1]
    ]
];

var width = 10;
var height = 20;
var cellWidth = 20;
var paper = Snap("#svg");
var board = new Board(width, height);
var tick = 500;

paper.attr({
    width: cellWidth*width,
    height: cellWidth*height
});

for (var x = 0; x < width; x++) {
    for (var y = 0; y < height; y++) {
        var rect = paper.rect(x*cellWidth, y*cellWidth, cellWidth, cellWidth);
        rect.attr({
            fill: "#ccc",
            stroke: "#ddd"
        });
    }
}

var piece = new Piece(shapes[0], "red", "white", paper, cellWidth);
piece.setPosition(0, 18);
board.place(piece);

piece = new Piece(shapes[1], "orange", "white", paper, cellWidth);
piece.setPosition(3, 19);
board.place(piece);

piece = new Piece(shapes[2], "yellow", "white", paper, cellWidth);
piece.setPosition(2, 8);
board.place(piece);

piece = new Piece(shapes[3], "green", "white", paper, cellWidth);
piece.setPosition(0, 17);
board.place(piece);

piece = new Piece(shapes[4], "blue", "white", paper, cellWidth);
piece.setPosition(2, 15);
board.place(piece);


piece = new Piece(shapes[5], "indigo", "white", paper, cellWidth);
piece.setPosition(1, 11);
board.place(piece);

piece = new Piece(shapes[6], "violet", "white", paper, cellWidth);
piece.setPosition(7, 17);
piece.render();

function update() {
    if (piece.isRemoved()) {
        return;
    }
    var position = piece.getPosition();
    if (board.canPlace(piece, {x:position.x,y:position.y+1})) {
        piece.setPosition(position.x,position.y+1);
        board.place(piece);
        for (var y = 0; y < piece.getHeight(); y++) {
            if (board.hasFullLine(piece.getPosition().y+y)) {
                var removed = board.clearPiecesOnLine(piece.getPosition().y+y);
                setTimeout(function() {
                    for (var i = 0; i < removed.length; i++) {
                        removed[i].delete();
                    }
                    board.hardDropPieces();
                },tick);
            }
        }
    }
}
setTimeout(update, tick);

That's pretty much the gist of the Board-logic. Placed pieces kept by reference in an array, after clearing I sort the pieces that are not removed by their lowest point and then drop each one of them as far as they can go.

This works when no pieces are interconnected, but I just can't figure out how to do it when they are, as in this example.

Obviously, the blue piece is the lowest point, but it cannot move downards since the green piece is inside of it. I thought about merging them and dropping them, but that leads to other problems. Like what would happen in this case?

I'm pretty sure I'm just being thick, and there's a relatively easy way of fixing this...? Any help would be much appreciated!

All the pieces are automatically generated, and there's way too many, and more could be added any time, to not make a general solution.

Answer 1

I found two parts that had some missing logic. The first part was where you were performing the drops. You'll need to do it one step at a time for each block, and then keep doing it until you can drop no more. Like this

this.hardDropPieces = function() {
    var pieces = this.pieces.slice();
    pieces = pieces.sort(function(a,b) {
        var aBottom = a.getPosition().y+a.getHeight();
        var bBottom = b.getPosition().y+b.getHeight();
        return bBottom-aBottom;
    });
    var canStillDrop = true;
    while (canStillDrop) { // Keep going until we can't drop no more
        canStillDrop = false;
        for (var i = 0; i < pieces.length; i++) {
            canStillDrop = this.hardDrop(pieces[i]) ? true : canStillDrop;
        }
    }
}

this.hardDrop = function(piece) {
    var didDrop = false;
    var position = piece.getPosition();
    this.clearArea(piece);
    if(this.canPlace(piece, {x: position.x, y: position.y+1})) {
        piece.setPosition(position.x, position.y+1);
        didDrop = true; // Oh, I see we have dropped
    }
    this.place(piece);
    return didDrop; // Did we drop a spot? Then we should keep going
}

The second part is that you could use a little recursiveness to check if any of the tiles keeping you from dropping is actually connected to the floor. This one you already recognize:

this.canPlace = function(piece, at) {
    // Will it fall below the floor? Then it's a no-go
    if (piece.getHeight()+at.y > this.height) {
        return false;
    }
    // Loop through shape
    for (var y = 0; y < piece.getHeight(); y++) {
        for (var x = 0; x < piece.getWidth(); x++) {
            // Ignore non-shape positions
            if (!piece.shape[y][x]) continue;
            // Get piece at current shape position
            var pieceAtPos = this.board[y+at.y][x+at.x];
            // Is the piece (or any that it's resting on) connected to the floor?
            if (pieceAtPos && pieceAtPos!==piece && this.isPieceGrounded(pieceAtPos, [piece]) ){
                return false;
            }
        }
    }
    return true;
}

But say hello also to isPieceGrounded.

this.isPieceGrounded = function(piece, testedPieces) {
    // Check all positions BELOW the piece
    var at = { x: piece.getPosition().x, y: piece.getPosition().y+1 };
    // Is it connected to the floor? 
    if (piece.getHeight()+at.y+1 >= this.height) {
        return true;
    }
    // *Sigh* Loop through THIS whole piece
    for (var y = 0; y < piece.getHeight(); y++) {
        for (var x = 0; x < piece.getWidth(); x++) {
            if (!piece.shape[y][x]) continue;
            var pieceAtPos = this.board[y+at.y][x+at.x];
            if (pieceAtPos && pieceAtPos!==piece && testedPieces.indexOf(pieceAtPos) < 0) {
                // Keep a list of all tested pieces so we don't end up in an infinite loop by testing them back and forth
                testedPieces.push(pieceAtPos);
                // Let's test that one and all its connected ones as well
                if (this.isPieceGrounded(pieceAtPos, testedPieces)) {
                    return true;
                };
            }
        }
    }
    return false;
}

http://jsfiddle.net/971yvc8r/2/

I'm sure there are lots of different solutions, but I think something like this might be the most efficient.