Tetris 俄罗斯方块 - 编程之美

第一章 游戏之乐 Edit 2 96…

1.17 俄罗斯方块游戏 ★★★

俄罗斯方块（英文：Tetris）是从20世纪80年代开始风靡全世界的电脑游戏。俄罗斯方块是由下面这几种形状的积木块构成，如图1-10所示。

图1-10

如果你说你没玩过Tetris游戏，面试者一定会比较惊讶，不过面试者还是会耐心地跟你解释它的游戏规则：
n 积木块会从游戏区域上方开始缓慢落下。
n 玩家可以做的操作有：90度旋转积木块，左右移动积木块，或者让积木块加速落下。
n 积木块移到游戏区域最下方或是落到其他积木块上无法移动时，就会固定在该处，而之后新的积木块就会出现在区域上方开始落下。
n 当游戏区域中某一行格子全部由积木块填满，则该行会消失并成为玩家的得分。一次删除的行数越多，得分越多。
n 当积木块堆到区域最上方，则游戏结束。
好，现在的问题是：
1. 如果你是设计者，如何设计各种数据结构来表示这个游戏的各种元素，如每一个可活动的积木块、在底层堆积的积木等。
2. 现在已经知道底层积木的状态，然后在游戏区域上方出现了一个新的积木块，你如何运用刚才设计的数据结构来判断新的积木块要如何移位或旋转，才能最有效率地消除底部累积的积木？
3. 有些版本的Tetris游戏有一个预览窗口，从预览窗口可以看到下一个积木块是什么形状。玩家这时候就可以提前计划，比如，如果下一个积木块是一根长条，我们就不要把最深的“峡谷”堵住。那么我们有了这个新的参数，如何改写上一个程序，才能最有效率地消除底部累积的积木？

http://cslibrary.stanford.edu/112/Tetris-Architecture.html
http://meatfighter.com/tetrisprinteralgorithm/
LameBrain includes heuristic logic that knows how to play the game of tetris. The LameBrain algorithm is very simple -- it knows that height is bad and creating holes is bad. Students can write their own brains. 
public double rateBoard(Board board) {
 final int width = board.getWidth();
 final int maxHeight = board.getMaxHeight();
 int sumHeight = 0;
 int holes = 0;
 // Count the holes, and sum up the heights
 for (int x=0; x<width; x++) {
  final int colHeight = board.getColumnHeight(x);
  sumHeight += colHeight;
  int y = colHeight - 2; // addr of first possible hole
  while (y>=0) {
   if  (!board.getGrid(x,y)) {
    holes++;
   }
   y--;
  }
 }
 double avgHeight = ((double)sumHeight)/width;
 // Add up the counts to make an overall score
 // The weights, 8, 40, etc., are just made up numbers that appear to work
 return (8*maxHeight + 40*avgHeight + 1.25*holes);
}
http://totologic.blogspot.com/2013/03/tetris-ai-explained.html
Related:
http://www.iteye.com/topic/595321
http://outofmemory.cn/code-snippet/6581/java-release-e-luosi-fangkuai-source-code
http://www.jianshu.com/p/dc80709e37c3
http://www.blogjava.net/evapocket/archive/2009/08/12/290897.html