编程之美1.17——俄罗斯方块游戏
问题：
让电脑自动下俄罗斯方块游戏。
解法：
对当前的积木块，枚举它旋转后的每一个形状从每一列落下的棋盘，将该棋盘和前一个棋盘进行对比，并打分，最后取得分最高的那个形状和那一列作为电脑的当前操作。（鉴于有读者不会用这个程序，在此说明下，运行这个程序需要加上文件重定向<1_17.txt，或者把程序中的控制台输入scanf改成文件输入FILE* fin=fopen("1_17.txt"); fscanf(fin,"%d",...);）
[cpp]
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
// 积木块的信息
#define BLOCK_SIZE 7
#define ROTATE_SIZE 4
#define SIDE_LEN 4
const int BLOCK_AREA = SIDE_LEN*SIDE_LEN;
// 棋盘的信息
#define HORIZ_LEN 12
#define VERT_LEN 15
const int CHESS_AREA = HORIZ_LEN*VERT_LEN;
// 其它信息
#define TOP_STEP 25
#define inf 10000
// 计分信息
const int clearLineScore[] = {0, 1, 3, 7, 13};
struct Block // 积木块
{
void init(unsigned char *l)
{
memcpy(layout, l, BLOCK_AREA);
int i, j;
for (i=0; i<SIDE_LEN; i++)
{
for (j=SIDE_LEN-1; j>=0 && layout[j*SIDE_LEN+i]==0; j--);
maxRow[i] = j+1;
}
for(i=0; i<SIDE_LEN && maxRow[i]==0; i++);
minCol = i;
for (i=SIDE_LEN-1; i>=0 && maxRow[i]==0; i--);
maxCol = i;
}
unsigned char layout[BLOCK_AREA]; // 积木块的布局
unsigned char maxRow[SIDE_LEN]; // 积木块每一列所占区域的最大行，取值从1开始
unsigned char minCol; // 积木块所占区域的最小值列和最大列，取值从0开始
unsigned char maxCol;
};
Block blockSet[BLOCK_SIZE][ROTATE_SIZE]; // 7种积木块，每种积木块有4种旋转方向
unsigned char chess[CHESS_AREA]; // 棋盘的布局
unsigned char nextChess[CHESS_AREA]; // 下一步棋盘的布局
int height[HORIZ_LEN]; // 棋盘每一列所占区域的最小行，即高度
void calcHeight(unsigned char *curchess) // 计算当前棋盘的高度信息
{
int i, j;
for (i=0; i<HORIZ_LEN; i++)
{
for (j=0; j<VERT_LEN && curchess[j*HORIZ_LEN+i]==0; j++);
height[i] = j;
}
}
// 计算若积木块从offsetX列落下，会落在第几行，即offsetY
int calcBottomOffsetY(const Block& b, int offsetX)
{
int offsetY = VERT_LEN;
for (int i=0; i<SIDE_LEN; i++)
{
if (b.maxRow[i]==0) continue;
offsetY = min(offsetY, height[offsetX+i]-b.maxRow[i]);
}
return offsetY;
}
// 将积木块贴到棋盘上
void pasteTo(unsigned char *curchess, const Block& b,
int offsetX, int offsetY)
{
for (int i=b.minCol; i<=b.maxCol; i++)
for (int j=0; j<SIDE_LEN; j++)
{
unsigned char bij = b.layout[j*SIDE_LEN + i];
unsigned char& cij = curchess[(j+offsetY)*HORIZ_LEN + i+offsetX];
if (bij && cij==0)
cij = bij;
else if (bij && cij)
cout << "ERROR" << endl;
}
}
// 消去[offsetY,offsetY+SIDE_LEN)中remline为1的行
void clearLines(unsigned char *curchess, int offsetY, unsigned char *remline)
{
int i, j, gap=0;
for (j=offsetY+SIDE_LEN-1; j>=0; j--)
{
if (j-offsetY>=0 && remline[j-offsetY])
gap++;
else if (gap)
{
memcpy(curchess+(j+gap)*HORIZ_LEN, curchess+j*HORIZ_LEN, HORIZ_LEN);
}
}
}
// 计算[offsetX,offsetX+SIDE_LEN)列的洞的个数
int calcHoles(unsigned char *curchess, int offsetX, int offsetY)
{
int i, j;
int holeCount = 0;
for (i=offsetX; i<offsetX+SIDE_LEN; i++)
{
if (i<0 || i>=HORIZ_LEN) continue;
for (j=offsetY; j<VERT_LEN && curchess[j*HORIZ_LEN+i]==0; j++);
for (; j<VERT_LEN; j++)
if (curchess[j*HORIZ_LEN+i]==0)
holeCount++;
}
return holeCount;
}
// 计算当前棋盘的得分
int calcScore(unsigned char *curchess, int offsetX, int offsetY)
{
int i, j, score = 0;
int remlineCount = 0;
unsigned char remline[SIDE_LEN] = {0};
// 统计消行数
for (j=offsetY; j<offsetY+SIDE_LEN; j++)
{
for (i=0; i<HORIZ_LEN && curchess[j*HORIZ_LEN+i]; i++);
if (i==HORIZ_LEN)
{
remlineCount++;
remline[j-offsetY] = 1;
}
}
score += clearLineScore[remlineCount];
// 统计洞的个数
if (remlineCount)
clearLines(curchess, offsetY, remline);
int holeCount = calcHoles(curchess, offsetX, offsetY) -
calcHoles(chess, offsetX, offsetY);
score -= holeCount*4;
// 位置过高则扣分
if (holeCount > 5) score -= 15;
if (offsetY-remlineCount < VERT_LEN*3/5)
score -= VERT_LEN*3/5-(offsetY-remlineCount);
return score;
}
void output(unsigned char *curchess)
{
for (int j=0; j<VERT_LEN; j++)
{
for (int i=0; i<HORIZ_LEN; i++)
cout << curchess[j*HORIZ_LEN+i] << " ";
cout << endl;
}
}
int main()
{
srand(time(0));
int i, j, k, n, m;
// 初始化积木块
for (i=0; i<BLOCK_SIZE; i++)
for (j=0; j<ROTATE_SIZE; j++)
{
unsigned char l[BLOCK_AREA];
for (k=0; k<BLOCK_AREA; k++)
scanf("%d",&l[k]);
blockSet[i][j].init(l);
}
// 初始化棋盘
for (i=0; i<CHESS_AREA; i++)
scanf("%d",&chess[i]);
// 显示前TOP_STEP步
int offsetX, offsetY;
unsigned char tmpchess[CHESS_AREA];
for (n=TOP_STEP; n>=0; n--)
{
output(chess);
calcHeight(chess); // 为每一步计算一次height数组，避免计算offsetY时过多的重复计算
int bind = rand()%BLOCK_SIZE; // 积木块的序号
int maxScore = -inf;
for (j=0; j<ROTATE_SIZE; j++) // 要考虑积木块的各种旋转情况
{
const Block& b = blockSet[bind][j]; // 得到当前的积木块
for (offsetX=-b.minCol; offsetX<HORIZ_LEN-b.maxCol; offsetX++)
{
// 计算从offsetX列落下，所落在棋盘的位置offsetY
offsetY = calcBottomOffsetY(b, offsetX);
if (offsetY<0) continue;
memcpy(tmpchess, chess, CHESS_AREA);
pasteTo(tmpchess, b, offsetX, offsetY); // 在棋盘中添加积木块
int curScore = calcScore(tmpchess, offsetX, offsetY); // 计算当前情况下的得分
if (curScore > maxScore)
{
maxScore = curScore; www.2cto.com
memcpy(nextChess, tmpchess, CHESS_AREA);
}
}
}
memcpy(chess, nextChess, CHESS_AREA);
}
}
