说明：本文的代码参考了网络上下载的源代码：《2013.3.25 游戏开发基地——孙广东 消灭小星星》，在此对原作者表示衷心感谢！
这几天在看算法导论里面的BFS和DFS，于是发现消灭小星星这个游戏就用到了BFS算法，就自己试着写了一下消灭小星星游戏的主要代码。现在与大家分享，欢迎批评指正！
#include <stdlib.h>
//小星星的坐标
class point
{
public:
int x;
int y;
point():x(0),y(0){}
};
//存储小星星的链表
class starListNode
{
public:
point p;
starListNode *next;
starListNode()
{
p.x = 0;
p.y = 0;
next = NULL;
}
};
//链表队列
class listQueue
{
public:
starListNode *head;
starListNode *tail;
listQueue():head(NULL),tail(NULL){}
};
listQueue lq;
//初始化队列
bool initListQueue()
{
lq.head = new starListNode();
lq.tail = lq.head;
if(lq.head == NULL)
return false;
lq.head->next == NULL;
return true;
}
//入队
bool enQueue(point tp)
{
starListNode *np = new starListNode();
if(np == NULL)
return false;
np->p.x = tp.x;
np->p.y = tp.y;
np->next = NULL;
lq.tail->next = np;
lq.tail = np;
return true;
}
//出队
bool deQueue(point &tq)
{
if(lq.head == lq.tail)
return false;
starListNode *slnp;
slnp = lq.head->next;
tq.x = slnp->p.x;
tq.y = slnp->p.y;
lq.head->next = slnp->next;
if(slnp == lq.tail)
lq.tail = lq.head;
delete slnp;
return true;
}
//小星星类
class star
{
public:
int x;//横坐标
int y;//纵坐标
int type;//取值为1到5,6表示背景色
int state;//0表示未被选中，1表示被选中
};
star st[10][10];
//初始化所有星星
void initStar()
{
for(int i = 0;i < 10;i++)
for(int j = 0;j < 10;j++)
{
st[i][j].x = j;
st[i][j].y = i;
st[i][j].type = rand()%5 + 1;
st[i][j].state = 0;
}
}
//判断某一个星星的上方是否还有未消去的星星，如果还有未消去的星星则返回true，否则返回false
bool upExistStar(star s)
{
int j = s.x;
int i = s.y;
for(;i > 0;--i)
{
if(st[i-1][j].type != 6)
return true;
}
return false;
}
//处理空格，使星星下落
void dealBlank()
{
int i,j,m;
for(j = 0;j < 10;++j)
{
for(i = 9;i > 0;--i)
{
if(st[i][j].type == 6 && upExistStar(st[i][j]) == true)
{
for(m = i;m > 0;--m)
st[m][j].type = st[m-1][j].type;
st[m][j].type = 6;
}
}
}
}
//判断某一列是否为空白
bool isBlankColumn(int j)
{
for(int i = 0;i < 10;i++)
{
if(st[i][j].type != 6)
return false;
}
return true;
}
//消去出现的空白列
void dealBlankColumn()
{
for(int j = 0;j < 10;j++)
{
if(isBlankColumn(j))
{
for(int m = j;m < 9;m++)
for(int i = 0;i < 10;i++)
st[i][m].type = st[i][m+1].type;
}
}
}
//当选中一颗小星星时，找到与它相邻的所有相同星星
void findAllSameStar(int sx,int sy)
{
if(st[sx][sy].type == 6)
return;
st[sx][sy].state = 1;
int starType = st[sx][sy].type;
point tepo;
tepo.x = st[sx][sy].x;
tepo.y = st[sx][sy].y;
initListQueue();
enQueue(tepo);
point tp;
//用BFS算法，找到与选中的小星星相同的所有相邻小星星
while(deQueue(tp))
{
if(tp.x > 0 && st[tp.x - 1][tp.y].type == starType && st[tp.x - 1][tp.y].state != 1)
{
st[tp.x - 1][tp.y].state = 1;
tepo.x = tp.x - 1;
tepo.y = tp.y;
enQueue(tepo);
}
if(tp.x < 9 && st[tp.x + 1][tp.y].type == starType && st[tp.x + 1][tp.y].state != 1)
{
st[tp.x + 1][tp.y].state = 1;
tepo.x = tp.x + 1;
tepo.y = tp.y;
enQueue(tepo);
}
if(tp.y > 0 && st[tp.x][tp.y - 1].type == starType && st[tp.x][tp.y - 1].state != 1)
{
st[tp.x][tp.y - 1].state = 1;
tepo.x = tp.x;
tepo.y = tp.y - 1;
enQueue(tepo);
}
if(tp.y < 9 && st[tp.x][tp.y + 1].type == starType && st[tp.x][tp.y + 1].state != 1)
{
st[tp.x][tp.y + 1].state = 1;
tepo.x = tp.x;
tepo.y = tp.y + 1;
enQueue(tepo);
}
}
}
int score = 0;
//当鼠标再次点击选中的小星星时，与它相邻的所有相同小星星均消失，并且悬空的小星星下降，空白列被消除
void wipeAllStar()
{
for(int i = 0;i < 10;i++)
{
for(int j = 0;j < 10;j++)
{
if(st[i][j].state == 1 && st[i][j].type != 6)
{
st[i][j].type = 6;
score += 200;//每消去一个星星得200分
st[i][j].state = 0;//消去后状态改为未选中
}
}
}
//处理悬空的小星星，在这里要调用3次dealBlank()是因为如果第一行的一个小星星最大可能向下滑9格，但是在这种情况下调用一次dealBlank()后距离底部的单元格数是4，需要再调用两次dealBlank()才能使小星星坠落到底部
dealBlank();
dealBlank();
dealBlank();
//处理空白列
dealBlankColumn();
}