1. Pick a tetromino randomly.
2. Consider the patterns that handle this tetromino. Each pattern in the game can handle only one tetromino (*1). I use the word "column" to denote the set of patterns that handle the same tetromino (*2).
3. Patterns in any column are ordered. Take the first pattern.
4. Run the matching algorithm.
5. If the pattern matches a region of the playing field, put the tetromino into the place specified by this pattern and let it fall according to the rules of the Game of Falling Tetrominoes.
6. If the pattern doesn't match any region, take the next pattern and go to step 4.
The matching algorithm consists of four steps.
1. Find all regions that match the pattern (*3).
2. Remove all regions that are obscured by tiles above them.
3. If there are more than one region left, pick the lowest regions.
4. If there are more than one of them, pick one randomly.
It is important which region you pick, because the desired position of a tetromino is specified in the local coordinate system of the pattern, so where the tetromino ends up being placed depends on where on the field the region is.
To assess the quality of a player's program I use the average game length. The length of an individual game is the number of lines completed (and thus removed) during that game. Any game starts with an empty playing field and ends when there is no place for new tetrominoes. I run the game many times and average lengths of all games in that run. The quality of the program is the limit of that average when the number of games goes to infinity (*4). We can't calculate the limit precisely, but we can approximate it by running the game many times. The more games are run, the more precise the estimate is. Usually I drop 50 000 tetrominoes, however many games this constitutes. On my desktop this takes a couple of seconds.
The problem is, when the average game length is 150, this is already not enough, because, empirically, the result can differ between runs by 10, which makes the measurements useless. Therefore, I need to either invent different ways to test the program (which I will definitely do later just because it is an interesting direction to explore), or to increase the number of tetrominoes in one run. For now, I will go with the latter. And since nobody wants to wait for half a minute to get the stats, the game needs to run faster.
Generally, this month hasn't been particularly productive, I got swamped at school, and the next month is likely to be unproductive as well, because the semester is not over. However, I did a simple profiling of the prototype.
I drop 10 000 tetrominoes and measure how long it takes to process them. Looking for a match currently takes 115 ms, and removing matches takes 86 ms. Dropping the tetromino takes the currently negligible 10 ms.
The most interesting part is that a trivial change from
1 2 | for (var i = command.walls?0:1; i < fieldWid - command.patternWid + command.walls?1:0; i++) { for (var j = 0; j < fieldHeit + 1 -command.patternHeit + 1; j++) { |
to
1 2 3 4 | var upperLimitI = fieldWid - command.patternWid + command.walls?1:0; var upperLimitJ = fieldHeit + 1 -command.patternHeit + 1; for (var i = command.walls?0:1; i < upperLimitI; i++) { for (var j = 0; j < upperLimitJ; j++) { |
made a huge difference. It reduced the total matching time from 380 ms to 246 ms. Apparently, a lot of time was spent just calculating these upper limits multiple times. This made me think that I could actually optimize the prototype before rewriting it in C to be able to distinguish between improving efficiency, which, I think, can be done in javascript, and improving performance.
There are two more things that I plan to do. I recently realized that I shouldn't make people download my prototype that runs in a browser from github, when I can just put it online. Also, I'm trying to figure out a way to explain how to play the game without making people read the tutorial.
*1 This is the decision I made at the very beginning after mistakenly trying to make each pattern specify the desired position for every tetromino.
*2 This is not necessarily the word that I want to use in the future, but for now I don't have a better alternative.
*3 This is currently done by trying to match the pattern to every possible region of the same size. I will optimize it later.
*4 This limit, according to my intuition, always exists, although I didn't try to prove its existence.