Tetris timer - the first part

Marek Piechula — Mon, 20 Mar 2023 22:07:51 +0000

Introduction

In my first post, I introduce an eye-candy timer with tetris animation in javascript and d3.js.

Motivation

Several years ago (before the pandemic time) I was a co-organizer of Coding Dojo Silesia. The formula of coding dojo was gathering people into pairs, coding a solution to the task in 1 hour in pairs (with mentors which try to help to understand a topic) and for the next hour, we were talking about solutions together. It was a great time - some attendees learned better skills, and someone found a better or first CS job.

In the coding phase, attendees needed to show a link to the repository with the task and the time left at the end of the coding phase. But the link and timer on the projector were a little boring, so I decided to make a landing page with simple animation. I decided to make a tetris game that was played by a bot instead of a player. Like an hourglass; a percent of the filled game’s area means time left to the end of coding. If the area was filled to half, then only 30 minutes left. If the area was complete then time was over.

Unfortunately, the event is closed because of the pandemic and lack of attendees and the tetris timer has forgotten in alone github’s repository. So I decided to restore this and write this article.

This article is the first part - I've tried to write the whole article, but it would be too big. In this part, I show the core of tetris time by inserting puzzles into the board.

Solution

Techstack

Because I wanted to make an animation that can run on each computer with a projector, I decided to make a standalone website hosted on github pages. Because I wanted a website, so I needed to choose a javascript language. The core of tetris has been written in pure ecmascript6, and animation has been rendered by SVG and d3.js.

The code is not perfect - it was a project after hours and the aim was the joy of writing the code in KISS principle. Some lines of code could be hard to understand like string operating, 2d array indexing, or filter/map methods but I've tried to write "clean" with comments.

I haven't written tests (what a shame!) because several years ago I have treated this as an experiment, not a “production” code.

Core

Board

First, we need a board for the game. Because on first, I wanted to print to terminal simple results, then I decided to make an array of strings, in which the element of the array is a row, and the element of the row is a cell. An empty cell is a dot ., and a non-empty cell is everything else. Let’s try:

class Board {
    constructor(width, height) {
        this.width = width || 10;
        this.height = height || 10;
        this.board = Array(this.height)  // Create the array of rows
            .fill('.') // Fill anything to avoid an undefined value
            .map(row => Array(this.width).fill('.')); // Each row is an array of characters.
    }

    toConsole() {
        console.log( // Convert the array to string
            this.board.map(row => row.join('')).join('\n')
        );
    }
}

const b = new Board(10, 10);
b.toConsole();

We can run this code, and result should be:

$ node new_board.js
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........

That is, an empty board! Now, we can put a puzzle.

Puzzle

The next step is to define the structure of the puzzle. I considered two ways:

Each puzzle is an array of four 2d points.
Each puzzle is a 4×4 array of cells.

The first way is more compact because I need only 4 points to define each puzzle, but I decided to use a 4×4 array because is easier to implement and I can make puzzles using characters like ASCII art in my code.

During the writing of the article I've been thinking about the first way would be better (complexity reduces from O(4²) to O(4) and one for loop on points instead of two for loops on 2 dimensions), but 4×4 has been easier for me to imagine and implement the algorithm. Because of KISS principle and because I would have to rewrite the finished code, I've chosen to stay with the “worse” way.

The 4×4 array has three rules:

Array should be aligned to the bottom left. I’ll explain it later.
Array has two kinds of cells: # and ..
Cells # must be connected with another # (not floating cells).

class Puzzle {
    constructor(array) {
        this.array = array;
    }
}

const PUZZLES = [
    [
        '....',
        '....',
        '##..',
        '##..',
    ],
    [
        '....',
        '....',
        '##..',
        '.##.', // The little caveat, I'll explain this later.
    ],
    [
        '#...',
        '#...',
        '#...',
        '#...',
    ],
    // Another puzzles
].map(a => new Puzzle(a));

Filling last (bottom) row

According to the real game, the first filled row is the last. The filling last row is pretty simple:

while is empty place in the row:
    pick random puzzle
    put puzzle somewhere in the row.

We can make it easier if we assume filling from left (index zero) to right (last index), so what only we need is where we should put a puzzle and move this “pointer” by the width of the puzzle. The animation below should explain the idea:

But before we need to set two values per puzzle:

Start the last row from the left side. (Most puzzles start on the 0 index, but “z” puzzle starts on 1 index)
Stop the last row.

The width of the last row is the difference between the stop and start index.

So we need to add three attributes to the puzzle class:

class Puzzle {
    constructor(array) {
        this.array = array;
        const lastRow = array[3];
        this.lastRowStart = lastRow.indexOf("#");
        this.lastRowStop = lastRow.lastIndexOf("#");
        this.lastRowWidth = this.lastRowStop - this.lastRowStart + 1;
    }
}

Let’s try with main logic of filling the last row:

class Board {
    constructor(width, height) {
        // previous code
        this.rowIndex = this.height - 1;
    }

    fillLastRow() {
        let pointer = 0;
        while(pointer < this.width) {
            const coords = [pointer, this.rowIndex];
            const puzzle = this.pickRandomPuzzle(coords);
            if (puzzle === null) {
                // Let's try with another place.
                pointer += 1;
                continue;
            }
            this.putPuzzle(puzzle, coords);
            pointer += puzzle.lastRowWidth;
        }
        this.rowIndex -= 1;
    }

As you see, we need to add two methods: pickRandomPuzzle and putPuzzle. Let’s start with the first method:

    pickRandomPuzzle(coords) {
        const validPuzzles = PUZZLES
            .filter(puzzle => this.isPuzzleMatching(puzzle, coords));

        if (validPuzzles.length == 0) {
            // Any puzzle is not valid.
            return null;
        }

        const index = Math.floor(Math.random() * validPuzzles.length);
        return validPuzzles[index];
    }

The next method is isPuzzleMatching which checks if is possible to put a puzzle into the board. The main goal of matching is checking a collision between a 4×4 array from a puzzle with part of the board. The animation should help:

    isPuzzleMatching(puzzle, [startX, startY]) {
        // The main idea is to check the board cell with a puzzle cell.
        // So we have to check 4x4 area.
        for(let y = 0; y < 4; y++) {
            for(let x = 0; x < 4; x++) {
                const puzzleCell = puzzle.array[y][x];
                // Assume start of the puzzle coordination
                // is the first left bottom non-empty cell.
                const boardX = startX + x - puzzle.lastRowStart;
                const boardY = startY + y - 3;
                // boardX/Y could be a negative / above size of board.
                // so we need to check if a row and a cell exists.
                // If coords are above size of board then
                // we can treat cell as "solid".
                const boardRow = this.board[boardY] || [];
                const boardCell = boardRow[boardX] || "#";
                if (boardCell != "." && puzzleCell != ".") {
                    // Collision between the board and the puzzle,
                    // so the puzzle can't fit in the board.
                    return false;
                }
            }
        }
        // All cells are matching with board.
        return true;
    }

Ok, now let’s try with putPuzzle method:

    putPuzzle(puzzle, [startX, startY]) {
        // Assume a puzzle can be added to the board.
        // Otherwise it could "damage" the board.
        for(let y = 0; y < 4; y++) {
            for(let x = 0; x < 4; x++) {
                const puzzleCell = puzzle.array[y][x];
                // Assume start of the puzzle coordination
                // is the first left bottom non-empty cell.
                const boardX = startX + x - puzzle.lastRowStart;
                const boardY = startY + y - 3;
                if ( // check if the cell on the board exists.
                    boardX >= 0
                    && boardX < this.width
                    && boardY >= 0
                    && boardY < this.height) {
                    this.board[boardY][boardX] = puzzleCell;
                }
            }
        }
    }

And finally:

const b = new Board(10, 10);
b.fillLastRow();
b.toConsole();

$ node new_board.js 
..........
..........
..........
..........
..........
..........
..........
...#.....#
##.#.#.#.#
##########

It’s a first try but doesn’t look well. Let’s try with indexing:

class Board {
    constructor(width, height) {
        // The previous code.
        this.puzzleIndex = 0;
    }

    // previous code

    putPuzzle(puzzle, [startX, startY]) {
        // Assume a puzzle can be added to the board.
        // Otherwise it could "damage" the board.
        for(let y = 0; y < 4; y++) {
            for(let x = 0; x < 4; x++) {
                const puzzleCell = puzzle.array[y][x];
                if (puzzleCell == ".") {
                    continue;
                }
                // Assume start of the puzzle coordination
                // is the first left bottom non-empty cell.
                const boardX = startX + x - puzzle.lastRowStart;
                const boardY = startY + y - 3;
                if ( // check if the cell on the board exists.
                    boardX >= 0
                    && boardX < this.width
                    && boardY >= 0
                    && boardY < this.height) {
                    const ascii = 48 + this.puzzleIndex % 10;
                    const char = String.fromCharCode(ascii);
                    this.board[boardY][boardX] = char;
                }
            }
        }
        this.puzzleIndex += 1;
    }

$ node new_board.js
..........
..........
..........
..........
..........
..........
0.........
0...2.....
0.112.3344
011223344.

Much better - we can see now single puzzles! We can try with colors, but we have a more necessary job. As you see we have a problem with the last row - is not filled. Because the “reverse Z” puzzle is matching on the board, but lefts one cell. Let’s skip this and try to fix in another way.

Filling next rows

Let’s return to idea with filling rows:

while is empty place in the row:
    pick random puzzle
    put puzzle somewhere in the row.

For the last row, we insert puzzles from the left to the right because the row was empty. But now, the next row is not fully empty. We need to find “gaps” to fill. Maybe animation should help:

    fillLastRow() {
        const gaps = this.findGaps();
        gaps.forEach(gap => this.fillGap(gap));
        this.rowIndex -= 1;
        // Return if is possible to fill another rows.
        return this.rowIndex > 0;
    }

Let’s go with findGaps and fillGap

    findGaps() {
        const row = this.board[this.rowIndex];
        const gaps = [];
        let pointer = 0;
        while(pointer < this.width) {
            // Find the next empty cell
            const start = row.findIndex((c, i) => i >= pointer && c == ".");
            if (start == -1) { // not found
                break;
            }
            // Find the next non-empty cell
            const end = row.findIndex((c, i) => i >= start && c != ".");
            if (end == -1) { // not found
                gaps.push([start, this.width - 1]);
                break;
            }
            gaps.push([start, end - 1]);
            pointer = end;
        }
        return gaps;
    }

    fillGap([start, end]) {
        // Basically it's the old fillLastRow method.
        let pointer = start;
        while(pointer <= end) {
            const coords = [pointer, this.rowIndex];
            const puzzle = this.pickRandomPuzzle(coords);
            if (puzzle === null) {
                // Let's try with another place.
                pointer += 1;
                continue;
            }
            this.putPuzzle(puzzle, coords);
            pointer += puzzle.lastRowWidth;
        }
    }

And run:

const b = new Board(10, 10);
while(b.fillLastRow());
b.toConsole();

$ node new_board.js
..........
..........
3.....4..5
3...1.4..5
3.9.1042.5
3596104285
0596102284
0596207784
0516277384
0111223334

Looks very nice! Let’s try with UNIX colors (very hacky code, don’t worry; is not necessary for the core of the algorithm):

    toColorConsole() {
        console.log(
            this.board.map(
                row => row
                    .join('')
                    .replace(/\d/g, w => {
                        const d = w.charCodeAt() - 48;
                        const fg = parseInt(d) + (d < 7 ? 31 : 91 - 7);
                        const bg = parseInt(d) + (d < 7 ? 41 : 101 - 7);
                        return `\x1b[${fg}m\x1b[${bg}m${w + w}\x1b[0m`;
                    })
                    .replace(/\./g, '..')
            ).join('\n')
        );
    }

It looks brilliant!

Rotating

Because we have a list of puzzles without rotation, we should write code that rotates each puzzle for us. Each rotation of the puzzle we can use as another puzzle and the previous code is not necessary to modify.

Because our structure is a 4×4 array so is not a problem to rotate because we have an algorithm:

function rotate90(array) {
    // Let's create an array of arrays
    const newArray = Array(4).fill('.').map(() => ['.', '.', '.', '.']);
    for(let y=0; y < 4; y++) {
        for(let x=0; x < 4; x++) {
            const cell = array[y][x];
            const row = newArray[4 - x - 1];
            row[y] = cell;
        }
    }
    // Return to array of strings.
    return newArray.map(c => c.join(''));
}

And write an example:

const p0 = [
    '....',
    '....',
    '##..',
    '##..',
];
const p1 = rotate90(p0);
const p2 = rotate90(p1);
const p3 = rotate90(p2);
console.log(p0.join('\n'), '\n');
console.log(p1.join('\n'), '\n');
console.log(p2.join('\n'), '\n');
console.log(p3.join('\n'), '\n');

This should produce:

....
....
##..
##.. 

....
....
..##
..## 

..##
..##
....
.... 

##..
##..
....
....

As you see - rotation works, but not meets the first condition:

The array should be aligned to the bottom left

And sadly, any rotation doesn't meet this condition (what lazy rotations!) so we need to move cells to the bottom left:

function shiftToBottomLeft(array) {
    array = shiftToBottom(array);
    array = shiftToLeft(array);
    return array;
}

function shiftToBottom(array) {
    const newArray = [...array];
    // If the last row is empty
    // then pop the row
    // and put on the top.
    while(newArray[3] == '....') {
        const row = newArray.pop();
        newArray.unshift(row);
    }
    return newArray;
}

function shiftToLeft(array) {
    let newArray = [...array];
    // If the first column is empty
    // then for each row drop the first cell
    // and put an empty cell on the end of row.
    while(newArray.every(col => col[0] == '.')) {
        newArray = newArray.map(col => col.substr(1) + '.');
    }
    return newArray;
}

const p0 = [
    '....',
    '....',
    '##..',
    '##..',
];
const p1 = rotate90(p0);
const p2 = rotate90(p1);
const p3 = rotate90(p2);
console.log(shiftToBottomLeft(p0).join('\n'), '\n');
console.log(shiftToBottomLeft(p1).join('\n'), '\n');
console.log(shiftToBottomLeft(p2).join('\n'), '\n');
console.log(shiftToBottomLeft(p3).join('\n'), '\n');

And the result is:

....
....
##..
##.. 

....
....
##..
##.. 

....
....
##..
##.. 

....
....
##..
##..

As you noticed - we have four rotations and the result is this same puzzle. So we should if the rotated puzzle is still the same puzzle:

function isArrayEquals(a, b) {
    // Checks each cell.
    for(let y=0; y < 4; y++) {
        for(let x=0; x < 4; x++) {
            if (a[y][x] != b[y][x]) {
                return false;
            }
        }
    }
    return true;
}

And finally, we can write code to rotate each puzzle:

function makePuzzleWithRotating(puzzle) {
    const rotations = [puzzle];
    let rot = puzzle;
    for(let i=0; i < 4; i++) {
        const newRot = shiftToBottomLeft(rotate90(rot));
        const isAnyEqual = rotations.some(r => isArrayEquals(r, newRot));
        if (!isAnyEqual) {
            rotations.push(newRot);
        }
        rot = newRot;
    }
    return rotations.map(p => new Puzzle(p));
}

const PUZZLES = [
    // some puzzles
].map(makePuzzleWithRotating).flat();

We can run the code:

PUZZLES.forEach(p => console.log(p.array.join('\n'), '\n'));

And we've got puzzles with each variant of rotation. And we can show the result:

As you noticed, the image below shows the board with some puzzles with other rotations.

Result and Conclusion

Today we've written a nice piece of code that fills the board of the game with tetris puzzles for us. Is not perfect and not finished - in the article's implementation we still have a problem with non-filling cells and a lack of a webpage with animation.

The code from the article is on github repository and the finished code is here but I think is a little difficult to understand but if you want… :-)

In the next part, I will write about how to change a 4×4 array to SVG polygon and how to use d3.js framework and vanilla js to make a timer with animation.

Thanks for reading my first article!

DEV Community: Marek Piechula