TC2.0版“连连看”游戏
昨天想起这个问题。两个晚上进行编码，基本测试完成。核心算法的编码难度感觉还是比俄罗斯方块略大一些，但代码量并不很大。算法：
在纸上设计完成后，又简单baidu了下参考了网上某个blog提出的算法，和我设计相同。在两个方块之间寻找路径，主要是基于一种类似贪心策略（最快的找到一条路径，不求最优），又类似穷举法（枚举所有公垂线直到找到通路）。具体实现可见如下代码中的FindPath函数，这是这个小game中的核心算法。看了后面网友的一个回复，算法应该本质相同。因此形式上有很多类似。
重要函数：
FindPath：核心算法。用于查找两个方块之间是否可以消除。
DrawPath：函数接收4个点坐标，用于绘制程序搜索到的一条路径呈现给用户。
InitGame：初始化游戏。为了简单起见，只是采用了几种填充样式来绘制方块，界面美化上还可以更加提升。
DrawBorderRect：由于没有鼠标操作，因此这个函数用于绘制焦点框以提供用户反馈，按方向键可以移动该焦点框。
玩法：
主要功能按键：方向键 - 移动焦点框进行方块选中。被选中的方块用蓝色框框住。红色方框表示当前位置。
回车键 - 确认选中当前位置的方块，或者尝试消去方块。
ESC 键 - 结束游戏。
由于经历有限，这里只完成了最关键的部分，因此需要改进和提升的空间也有很多：例如方块采用图像资源，操作支持鼠标操作，提供难度等级选择等。
代码如下：
程序代码：/*
* 连连看游戏（棋盘法）
* Author: hoodlum1980
* Date: 2008.04.23
* Email: jinfd@*/
#include <stdio.h>
#include <graphics.h>
#include <stdlib.h>
#include <math.h>
#include <dos.h>
#define true 1
#define false 0
/* ---------------------全局变量------------------------------------ */
int BkGndColor=BLACK;
int BorderColor=LIGHTGRAY;
int LineColor=LIGHTBLUE;/* 消除一对方块时时候的连线颜色 */
/* Pb - ProgressBar */
int PbColor=LIGHTGREEN;
int PbY=4;
int PbHeight=4;
int PbValue; /* 进度条百分比，初始值为100.*/
long StartTime; /* 开始时间的秒数，只统计分钟，秒 */
long TotalTime; /* 游戏总共的最大秒数！，*/
/* BoardDatas: a small-size board */
/* Board[x][y][0] - 0:empty, 1:filled */
/* Board[x][y][1] - cell's key; */
unsigned char Board[10][10][2];
int CellSize=30;
int BoardX=20;
int BoardY=60;
int BoardWidth=10;
int BoardHeight=10;
int CellColor=WHITE;
int SelColor=BLUE; /* selCell's border rect color */
int CurColor=RED; /* curCell's border rect color */
int EraColor=CYAN; /* 用于擦除cell的颜色！*/
int PairsCount; /* how much pairs we have put on board */
/* 用于存储逻辑坐标（索引） */
typedef struct _tagCELL
{
char x;
char y;
} CELL;
CELL selCell,curCell;/*缓存前一个被选中的位置以及当前所处位置！*/
/*Scan Codes Define*/
enum KEYCODES
{
K_ESC =0x011b,
K_UP =0x4800, /* upward arrow */
K_LEFT =0x4b00,
K_DOWN =0x5000,
K_RIGHT =0x4d00,
K_SPACE =0x3920,
K_P =0x1970,
K_RETURN =0x1c0d, /* Enter */
};
/* ---------------------函数列表------------------------------------ */
void InitGame(char *bgiPath);
void PlayGame();
void QuitGame();
void InitProgressBar();
void UpdateProgressBar(int percent);
void DrawCell(int key,int x,int y,int color);
void EraseCell(int x,int y);
void DrawBorderRect(CELL *c,int color);
void DrawGameOver(char* info);
int GetKeyCode();
int FindPath(CELL *c1,CELL *c2);
/*绘制消除方块时候的连接路径！，用指定颜色！*/
void DrawPath(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4,int color);
/* ----------------------函数实现----------------------------------- */
/* ----------------------[ 核心算法 ]---------------------------------
* 先进行水平方向判断，找出两点所在的水平直线活动范围，
* 算出这两条线段在垂直方向的共同区域!!!，
* 遍历该区域判断能否在两线段间架起公垂线，能则两点连接上；
* 接着进行垂直方向判断，类同。无论两点在不在一条直线上，
* 都能使用该算法，因为两点同线只是两点作为矩形对角点的特例而已。
*/
/* 找到两个CELL之间的路径，成功返回true */
int FindPath(CELL *c1,CELL *c2)
{
int i,j,path,min1,max1,min2,max2,left,right,top,bottom;
/*---------------（0）判断是否点中相同块！ ------------*/
if(Board[c1->x][c1->y][1] != Board[c2->x][c2->y][1])
return false;
/*---------------（1）查找水平方向公共区域！-----------*/
min1=max1=c1->x;
min2=max2=c2->x;
while(min1-1>=0 && Board[min1-1][c1->y][0]==0) min1--;
while(min2-1>=0 && Board[min2-1][c2->y][0]==0) min2--;
left=max(min1,min2); /* 左边界 */
while(max1+1<BoardWidth && Board[max1+1][c1->y][0]==0) max1++;
while(max2+1<BoardWidth && Board[max2+1][c2->y][0]==0) max2++;
right=min(max1,max2); /* 右边界 */
/* 检查两条水平线之间是否有公垂线连通！*/
/* 可以在边缘连通 */
if(left==0)
{
/* 左边缘连通 */
DrawPath(c1->x,c1->y, -1,c1->y, -1,c2->y, c2->x,c2->y, LineColor);
delay(6000);
DrawPath(c1->x,c1->y, -1,c1->y, -1,c2->y, c2->x,c2->y, BkGndColor);/*插除线条！*/
return true;
}
if(right==(BoardWidth-1))
{
DrawPath(c1->x,c1->y, BoardWidth,c1->y, BoardWidth,c2->y, c2->x,c2->y, LineColor);
delay(6000);
DrawPath(c1->x,c1->y, BoardWidth,c1->y, BoardWidth,c2->y, c2->x,c2->y, BkGndColor);/*插除线条！*/
return true;
}
for(i=left;i<=right;i++)
{
path=0;/*统计垂直的公垂线长度！*/
for(j=min(c1->y,c2->y)+1;j<max(c1->y,c2->y);j++)
{
path+=Board[i][j][0];
if(path>0) break;
}
if(path==0)
{
DrawPath(c1->x,c1->y, i,c1->y, i,c2->y, c2->x,c2->y, LineColor);
delay(6000);
DrawPath(c1->x,c1->y, i,c1->y, i,c2->y, c2->x,c2->y, BkGndColor);/*插除线条！*/
return true;
}
}
/*---------------（2）查找垂直方向公共区域！-----------*/
min1=max1=c1->y;
min2=max2=c2->y;
while(min1-1>=0 && Board[c1->x][min1-1][0]==0) min1--;
while(min2-1>=0 && Board[c2->x][min2-1][0]==0) min2--;
top=max(min1,min2);
while(max1+1<BoardHeight && Board[c1->x][max1+1][0]==0) max1++;
while(max2+1<BoardHeight && Board[c2->x][max2+1][0]==0) max2++;
bottom=min(max1,max2);
/* 检查两条垂直线之间是否有公垂线连通！*/
/* 可以在边缘连通 */
if(top==0)
{
/* 同在顶端消除 */
DrawPath(c1->x,c1->y, c1->x,-1, c2->x,-1, c2->x,c2->y, LineColor);
delay(6000);
DrawPath(c1->x,c1->y, c1->x,-1, c2->x,-1, c2->x,c2->y, BkGndColor);/*插除线条！*/
return true;
}
if(bottom==(BoardHeight-1))
{
DrawPath(c1->x,c1->y, c1->x,BoardHeight, c2->x,BoardHeight, c2->x,c2->y, LineColor);
delay(6000);
DrawPath(c1->x,c1->y, c1->x,BoardHeight, c2->x,BoardHeight, c2->x,c2->y, BkGndColor);/*插除线条！*/
return true;
}
for(j=top;j<=bottom;j++)
{
path=0;/*统计水平的公垂线长度！*/
for(i=min(c1->x,c2->x)+1; i<max(c1->x,c2->x); i++)
{
path+=Board[i][j][0];
if(path>0) break;
}
if(path==0)
{
/* 水平公垂线 */
DrawPath(c1->x,c1->y, c1->x,j, c2->x,j, c2->x,c2->y, LineColor);
delay(6000);
DrawPath(c1->x,c1->y, c1->x,j, c2->x,j, c2->x,c2->y, BkGndColor);/*插除线条！*/
return true;
}
}
/* 到达这里说明没有任何通路 */
return false;
}
/*Get Key Code */
int GetKeyCode()
{
int key=0;
if(bioskey(1))
{
key=bioskey(0);
}
return key;
}
/*绘制消除方块时候的连接路径！，用指定颜色！，坐标是CELL逻辑坐标！*/
void DrawPath(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4,int color)
{
setcolor(color);
moveto(BoardX+CellSize/2+CellSize*x1,BoardY+CellSize/2+CellSize*y1);
lineto(BoardX+CellSize/2+CellSize*x2,BoardY+CellSize/2+CellSize*y2);
lineto(BoardX+CellSize/2+CellSize*x3,BoardY+CellSize/2+CellSize*y3);
lineto(BoardX+CellSize/2+CellSize*x4,BoardY+CellSize/2+CellSize*y4);
}
/* congratulations info,the user has success finish the game ! */
void DrawGameOver(char* info)
{
/*计算棋盘的中心点*/
int cx=BoardX+CellSize*BoardWidth/2;
int cy=BoardY+CellSize*BoardHeight/2;
struct textsettingstype textInfos;
/*获取此前的文字信息*/
gettextsettings(&textInfos);
setcolor(DARKGRAY);
setfillstyle(SOLID_FILL,BLUE);
/* 文字居中 */
rectangle(cx-102,cy-22,cx+102,cy+22);
floodfill(cx,cy,DARKGRAY);
rectangle(cx-100,cy-20,cx+100,cy+20);
settextjustify(CENTER_TEXT,CENTER_TEXT);
setcolor(LIGHTBLUE);
outtextxy(cx,cy,info);
/*restore orignal text settings */
settextjustify(textInfos.horiz, textInfos.vert);
}
/* draw a focus rect on the cell with the color */
/* 用制定颜色绘制一个选中的外边框 */
void DrawBorderRect(CELL *c,int color)
{
setcolor(color);
rectangle(BoardX+(c->x)*CellSize+1, BoardY+(c->y)*CellSize+1, BoardX+(c->x+1)*CellSize-2, BoardY+(c->y+1)*CellSize-2);
rectangle(BoardX+(c->x)*CellSize, BoardY+(c->y)*CellSize, BoardX+(c->x+1)*CellSize-1, BoardY+(c->y+1)*CellSize-1);
}
/* 在x，y处用指定颜色绘制键为key的 CELL,key在2,3,4,5,6,7,8,9,10,11之间随机 */
void DrawCell(int key,int x,int y,int color)
{
setcolor(color);
rectangle(BoardX+x*CellSize+2, BoardY+y*CellSize+2, BoardX+(x+1)*CellSize-3, BoardY+(y+1)*CellSize-3);
setfillstyle(key, color);
floodfill(BoardX+x*CellSize+3, BoardY+y*CellSize+3,color);
}
/* 擦除CELL */
void EraseCell(int x,int y)
{
setcolor(EraColor);
rectangle(BoardX+x*CellSize+2, BoardY+y*CellSize+2, BoardX+(x+1)*CellSize-3, BoardY+(y+1)*CellSize-3);
setfillstyle(SOLID_FILL, BkGndColor);
floodfill(BoardX+x*CellSize+3, BoardY+y*CellSize+3,EraColor);
setcolor(BkGndColor);
rectangle(BoardX+x*CellSize+2, BoardY+y*CellSize+2, BoardX+(x+1)*CellSize-3, BoardY+(y+1)*CellSize-3);
}
/* 初始化进度条 */
void InitProgressBar()
{
int width=CellSize*BoardWidth;
/* progress bar border rect */
setcolor(BorderColor);
rectangle(BoardX-2,PbY-2,BoardX+width+2,PbY+PbHeight+2);
/* draw a value = 100% progress bar */
setcolor(PbColor);
rectangle(BoardX,PbY,BoardX+width,PbY+PbHeight);
setfillstyle(SOLID_FILL,PbColor);
floodfill(BoardX+1,PbY+1,PbColor);
}
/* 更新进度条，设置为某个百分比 */
void UpdateProgressBar(int percent)
{
int p=percent;
int width;
if(percent<0) p=0;
else if(percent>100) p=100;
width=BoardWidth*percent/100*CellSize;
setfillstyle(SOLID_FILL,BkGndColor);
floodfill(BoardX+1,PbY+1,BorderColor);
if(width<2) return;/* too small value? */
setcolor(PbColor);
rectangle(BoardX,PbY,BoardX+width,PbY+PbHeight);
setfillstyle(SOLID_FILL,PbColor);
floodfill(BoardX+1,PbY+1,PbColor);
}
/* 初始化程序 */
void InitGame(char *bgiPath)
{
int gdriver=DETECT,gmode,i,x,y,key;
struct time sysTime;
/*清空棋盘数据！*/
memset(Board,0,sizeof(Board[0][0][0]*BoardWidth*BoardHeight*2));
/* set new seed! */
gettime(&sysTime);
srand(sysTime.ti_hour*3600+sysTime.ti_min*60+sysTime.ti_sec);
/* enter graphics mode */
initgraph(&gdriver,&gmode,bgiPath);
PairsCount=BoardWidth*BoardHeight/4;
for(i=0; i<PairsCount; i++)
{
key=random(10)+2;
/* fill first cell of pair */
do
{
x=random(BoardWidth);
y=random(BoardHeight);
}
while(Board[x][y][0]!=0);
DrawCell(key,x,y,CellColor);
Board[x][y][0]=1;
Board[x][y][1]=key;
/* fill second cell of pair */
do
{
x=random(BoardWidth);
y=random(BoardHeight);
}
while(Board[x][y][0]!=0);
DrawCell(key,x,y,CellColor);
Board[x][y][0]=1;
Board[x][y][1]=key;
}
setcolor(YELLOW);
outtextxy(BoardX,BoardY+BoardHeight*CellSize+30,"Press ESC to Exit!");
outtextxy(BoardX,BoardY+BoardHeight*CellSize+42,"ArrowKeys to move, Enter to Confirm.");
outtextxy(BoardX,BoardY+BoardHeight*CellSize+54,"--by Hoodlum1980");
PbValue=100;
TotalTime=3*60; /* Total minutes. */
gettime(&sysTime);
StartTime=sysTime.ti_min*60+sysTime.ti_sec;
}
/* 游戏进行 */
void PlayGame()
{
int key,percent;
long curTime;
struct time sysTime;
curCell.x = curCell.y = 0;/*当前所处位置！*/
selCell.x = selCell.y = -1;/*为-1表示当前未选中*/
DrawBorderRect(&curCell, CurColor);
/*用一个循环检测按键！*/
while(key!=K_ESC)
{
/* wait until a key pressed */
while(!(key=GetKeyCode()))
{
gettime(&sysTime);
curTime=sysTime.ti_min*60+sysTime.ti_sec;
percent=(int)((1-(curTime-StartTime)*1.0/TotalTime)*100);
if(percent<=1)
{
DrawGameOver("YOU HAVE LOSE!");
return;
}
else if(percent!=PbValue)
{
UpdateProgressBar(percent);
PbValue=percent;/* update cache PbValue */
}
delay(1000);
}
/* 这时用户按下了某个键 */
/*需要恢复的是此前选中的cell！*/
if(curCell.x==selCell.x && curCell.y==selCell.y)
DrawBorderRect(&curCell, SelColor); /*恢复选中cell的focus痕迹 */
else
DrawBorderRect(&curCell, BkGndColor); /*擦除此前的focus痕迹 */
switch(key)
{
case K_LEFT:
curCell.x--;
if(curCell.x < 0) curCell.x += BoardWidth;
break;
case K_RIGHT:
curCell.x++;
if(curCell.x >= BoardWidth) curCell.x -= BoardWidth;
break;
case K_UP:
curCell.y--;
if(curCell.y < 0) curCell.y += BoardHeight;
break;
case K_DOWN:
curCell.y++;
if(curCell.y >= BoardHeight) curCell.y -= BoardHeight;
break;
/* 对回车键 */
case K_RETURN:
/* 如果此处没有任何cell，不处理！ */
if(Board[curCell.x][curCell.y][0]==0)
break;
/* 与此前选中的位置重合，则不处理 */
if(curCell.x==selCell.x && curCell.y==selCell.y)
break;
/*如果此前没有任何选中，则设置改点为选中位置*/
if(selCell.x<0 || selCell.y<0)
{
selCell.x=curCell.x;
selCell.y=curCell.y;
DrawBorderRect(&selCell,SelColor);
continue;
}
/*如果此前已有选中，则判断是否可以消除！*/
if(FindPath(&selCell,&curCell))
{
/* 消除这两个cell！*/
EraseCell(selCell.x,selCell.y);
EraseCell(curCell.x,curCell.y);
/* 清除棋盘数据 */
Board[selCell.x][selCell.y][0]=0;
Board[selCell.x][selCell.y][1]=0;
Board[curCell.x][curCell.y][0]=0;
Board[curCell.x][curCell.y][1]=0;
/* 清除selCell */
DrawBorderRect(&selCell,BkGndColor);
selCell.x=selCell.y=-1;
/* decrease the pairs count */
PairsCount--;
if(PairsCount==0)
{
DrawGameOver("CONGRATULATIONS!");
return;
}
}
else
{
/* 不能消除这两个cell！*/
/* erase the selCell's focus rect!*/
DrawBorderRect(&selCell,BkGndColor);
selCell.x=selCell.y=-1;
}
break;
case K_ESC:
DrawGameOver("GAME OVER!");
break;
default:
break;
}
/*绘制当前focus位置*/
DrawBorderRect(&curCell, CurColor);
}
}
/* 退出程序 */
void QuitGame()
{
closegraph();
}
/* Entry Point */
int main(int argc,char *argv[])
{
InitGame("");
InitProgressBar();
PlayGame();
getch();
QuitGame();
return 0;
}[[it] 本帖最后由 hoodlum1980 于 2008-4-25 10:14 编辑 [/it]]
连连看TC_hoodlum1980.rar
(56.77 KB)
