使用棋盘法的贪吃蛇代码
在我此前发了一篇对其他人的贪吃蛇C代码的分析和注释，在那个代码中的算法主要是用一个线性表存储蛇的所有身体节点的位置。然后随着游戏进行，需要把相应的蛇身节点依次平移一次（把数组里的数据整体平移一次）。对蛇是否撞到自己身体的判断，也需要遍历蛇身一次。因此每一帧实际上都需要O（n）的时间，这里n指的是当前蛇的长度。这个方法假设我们成为线性表法，在其代码中使用了一个int[200][2]的数据去存储每个节点坐标，我想作者是最大的原因应该是这样一次性分配足够的空间，以后的代码就可以书写方便，因为随着游戏进行，蛇肯定是不断增长长度的，所以用链表反倒不如用足够大的数组划算。那么它需要的空间主要是蛇的最大长度*每个坐标占据的空间（大约800bytes）。时间复杂度和空间复杂度都可以看作O（n）。
我这里的代码是另一种方法，称为棋盘法（我记得在这个论坛看过一篇文章说，贪吃蛇不适合棋盘法）。所谓棋盘法就是用一个数组来记录棋盘上每个格子的状态（例如俄罗斯方块的处理逻辑就是典型的棋盘法）。之所以考虑棋盘法，是因为我们主要想把方法1的时间复杂度降为O（1），也就是说我们希望算法和蛇的长度无关。任何玩过贪吃蛇游戏的人都会有这样的一个很直观的认识，就是蛇在移动过程中，其中间身体部分是保持固定姿态不会改变的，而只有蛇头，蛇尾在变化。例如一个很长的蛇，你可以看到蛇身的中间是一动不动的。因此我们就能够想出一个办法，我们只对蛇头和蛇尾进行更新数据和绘制就可以了。不管蛇多长，蛇头蛇尾永远各有1个，因此这样的处理方法就是O（1）。尤其在蛇很长很长以后，这个时间的节省就会更加明显了。而且相比方法1来说，这里我们也不需要关心蛇的长度了（方法1中必须有个变量记录当前的蛇身长度，也就是数组的有效数据长度）。
我们需要记录蛇头和蛇尾的位置，所以我定义了一个记录位置的结构：其实它只是一个坐标。
typedef struct tagCELL{ char x,y; } CELL;
CELL head,tail,food; 分别记录蛇头，蛇尾，食物在棋盘上的位置。
另外，为了让蛇尾能够正确的跟随和复制蛇头的运动轨迹，我们需要在棋盘上记录蛇头的移动方向，这样我们才能准确的使蛇尾跟随蛇头做一个同样的运动轨迹（无论蛇头领先了多少）。见下图所示。下图显示的是棋盘网格，我们对每个网格需要记录两个信息，第一个是这个格子是否是蛇的某个节点。第二个信息是如果这里蛇的节点，蛇头经过此处时的运动方向是什么。（当然，这两个信息可以压缩到一个变量，但是为了可维护性和代码可读性考虑，但强烈建议不要这样做，不要为了一点点好处而得不偿失）。
所以我们的每个格子（cell）需要两个变量，我使用下面的棋盘数据：
char Board[ BoardWidth ][ BoardHeight][2];
对于某个格子(i,j)，它的信息的意义是：
Board[i][j][0]: 这里是否是蛇身节点。
Board[i][j][1]: 运动方向（即图中所标的箭头）。
相应的，我们每一帧需要做的动作如下（不考虑其他逻辑判断）：
（1）擦除当前蛇尾。
（2）根据棋盘记录的方向信息，更新蛇尾到新的位置，并清除此前蛇尾所在位置的棋盘过期数据。
（3）把当前蛇头的信息数据填充到棋盘。
（4）根据当前移动方向，更新蛇头head的位置，并在新的位置绘制蛇头。
空间复杂度，我们最主要的空间就是我们的棋盘，需要BoardWidth*BoardHeight*2个字节，例如我的代码里是20*20*2=800 bytes。使用棋盘法，空间是会比方法1需要的空间稍大一点（这里也可以看出节省时间和节省空间的两个需求的矛盾性，我们总是以实际情况和背景下做最恰当的取舍和权衡的）。但是由于第一种方法的空间利用率并不高效，所以空间复杂度的差别实际上也是不大的。
算法的逻辑上，两者的直观性同样相差不大。所以综合而言，个人感觉棋盘法的综合时空效率还是略好于前者的。
代码行数上，其实核心逻辑部分是差不多的，对方代码是200多行。我的是300多行。消耗时间上，比我上次写的俄罗斯方块要快很多，俄罗斯方块写了2天，这个写+调试大约3~4个小时。我的棋盘法的代码如下，由于我是在ultraedit里面编辑的，所以在代码里我加了比较详细的中文注释：
程序代码：
/*
* 贪吃蛇（棋盘法）
* Author: hoodlum1980
* Date: 2008.3.19
* Email: jinfd@*/
#include <dos.h>
#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>
#define true 1
#define false 0
#define BoardWidth 20
#define BoardHeight 20
/*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
};
/*蛇的前行方向枚举*/
enum DIRECTIONS
{
dr_left=(char)1,
dr_up=(char)2,
dr_right=(char)3,
dr_down=(char)4
};
int CellSize=10;/*单元格尺寸*/
int TotalScore;/*总分*/
/*位置信息*/
int BoardLeft=20;/*像素坐标*/
int BoardTop=20;
int ScoreBoardLeft=250;
int ScoreBoardTop=20;
int InfoLeft=250;
int InfoTop=60;
/*颜色设置*/
int SnakeColor=YELLOW;
int FoodColor=GREEN;
int WallColor=BLUE;/* 墙壁颜色 */
int ScoreColor=CYAN;
int BkGndColor=BLACK;
int InfoColor=LIGHTGRAY;
char Direction; /*当前方向！*/
char TextScore[10];/*用于显示分数的缓冲区*/
char TextInfo[100];/*用于显示信息的缓冲区*/
char TextCache[100];/*用于缓存字符串*/
int FrameTime=600;/*延时时间*/
int FoodEaten;/*食物是否被吃了？*/
/*Board[x][y][0]: 0-none，1-snake body */
/*Board[x][y][1]: history moving direction */
char Board[BoardWidth][BoardHeight][2];/*棋盘*/
typedef struct tagCELL
{
char x;
char y;/*节点网格坐标*/
} CELL;
CELL head,tail,food;/*记录蛇头和蛇尾的位置*/
/*函数列表*/
int GetKeyCode();/*获取键扫描码*/
void NextCell(CELL *cell,char direction); /*根据方向，得到下一个坐标*/
void NextFood(CELL *cell); /*产生下一个随机位置的食物*/
void PutCell(CELL *cell,int color);
void DisplayScore();
void DisplayInfo();
int IsAvailable(CELL *cell); /*是否允许蛇头到达该位置*/
void InitGame(); /*初始化，绘制墙壁，初始蛇，初始事物*/
void PlayGame(); /*游戏循环*/
int PauseGame(); /*暂停游戏*/
void DrawGameOver();/*绘制Game Over。*/
void QuitGame();
/*Get Key Code */
int GetKeyCode()
{
int key=0;
if(bioskey(1))
{
key=bioskey(0);
}
return key;
}
/*判断这个网格位置是否是允许的，如果不是说明游戏结束了*/
int IsAvailable(CELL *cell)
{
char i=cell->x;
char j=cell->y;
if(i<0||i>=BoardWidth||j< 0||j>= BoardHeight||Board[i][j][0])/*看是否越界，看是否已经有蛇身*/
return false;
return true;
}
/*根据方向获取下一个位置*/
void NextCell(CELL *cell,char direction)
{
switch(direction)
{
case dr_left:
cell->x--;
break;
case dr_up:
cell->y--;
break;
case dr_right:
cell->x++;
break;
case dr_down:
cell->y++;
break;
}
}
/*产生下一个食物并且马上绘制出来，在随机位置*/
void NextFood(CELL *cell)
{
int count=0;
do
{
cell->x=random(BoardWidth);
cell->y=random(BoardHeight);
}while(Board[cell->x][cell->y][0] && count++<(BoardWidth*BoardHeight));
PutCell(cell,FoodColor);
}
/*显示分数*/
void DisplayScore()
{
setcolor(BkGndColor);
if(TextScore[0])
outtextxy(ScoreBoardLeft+10,ScoreBoardTop+10,TextScore);
sprintf(TextScore,"Score: %-3d",TotalScore);
setcolor(ScoreColor);
outtextxy(ScoreBoardLeft+10,ScoreBoardTop+10,TextScore);
}
/*显示文字信息*/
void DisplayInfo(char *info)
{
setcolor(BkGndColor);
outtextxy(InfoLeft,InfoTop,TextInfo);
strcpy(TextInfo,info);
setcolor(InfoColor);
outtextxy(InfoLeft,InfoTop,TextInfo);
}
/*我们仅仅绘制一个小矩形就够了！*/
void PutCell(CELL *cell,int color)
{
setcolor(color);
rectangle(BoardLeft+CellSize*cell->x+1,BoardTop+CellSize*cell->y+1,BoardLeft+CellSize*(cell->x+1),BoardLeft+CellSize*(cell->y+1));
}
/*初始化游戏*/
void InitGame()
{
int i,gdriver=DETECT,gmode;
memset(Board,0,sizeof(char)*BoardWidth*BoardHeight*2);
memset(TextScore,0,sizeof(TextScore));
memset(TextInfo,0,sizeof(TextInfo));
memset(TextCache,0,sizeof(TextCache));
initgraph(&gdriver,&gmode,"");
/*绘制墙壁，连续画2个矩形表示墙壁*/
setcolor(WallColor);
setfillstyle(SOLID_FILL,CYAN);
rectangle(BoardLeft-1,BoardTop-1,BoardLeft+CellSize*BoardWidth+1,BoardTop+CellSize*BoardHeight+1);
rectangle(BoardLeft-4,BoardTop-4,BoardLeft+CellSize*BoardWidth+4,BoardTop+CellSize*BoardHeight+4);
floodfill(BoardLeft-2,BoardTop-2,WallColor);
/*初始化蛇头，蛇尾，前行方向，并把数据设置到棋盘！，并且绘制出蛇*/
head.x=2;
head.y=2;
tail.x=head.x-1;
tail.y=head.y;
Direction=dr_right;/*初始运动方向设为向右*/
Board[head.x][head.y][0]=1;/*在棋盘上设置蛇身标志*/
Board[head.x][head.y][1]=Direction;
Board[tail.x][tail.y][0]=1;
Board[tail.x][tail.y][1]=Direction;
PutCell(&head,SnakeColor);
PutCell(&tail,SnakeColor);
/*产生第一个食物,并绘制食物！*/
NextFood(&food);
FoodEaten=false;/*还没被吃掉*/
/*显示分数*/
/*draw score board*/
setcolor(DARKGRAY);
rectangle(ScoreBoardLeft,ScoreBoardTop,ScoreBoardLeft+120,ScoreBoardTop+30);
TotalScore=100;
DisplayScore();
sprintf(TextCache,"SNAKE GAME. --by hoodlum1980");
DisplayInfo(TextCache);
setcolor(DARKGRAY);
outtextxy(InfoLeft,InfoTop+50,"P -- Pause Game;");
outtextxy(InfoLeft,InfoTop+62,"ESC -- Exit Game;");
}
/*游戏循环*/
void PlayGame()
{
int key=0,tick=0;
char headDirection,tailDirection;
while(key!=K_ESC)
{
/* wait until a key pressed */
while(!(key=GetKeyCode()))
{
tick++;
if(tick>=FrameTime)
{
tick=0;/*清空计数！*/
/*如果食物被吃掉了，那么产生新的食物！*/
if(FoodEaten)
{
NextFood(&food);
FoodEaten=false;
}
/*我们应该先擦除蛇尾，再判断蛇头是否可以移动到新的位置*/
/*判断蛇头是否吃到食物，如果吃到食物，不要擦除蛇尾！*/
if(head.x==food.x && head.y == food.y)
{
/*蛇吃到了食物，这里我们只需要加分！*/
TotalScore+=10;
DisplayScore();
FoodEaten=true;
}
else
{
/*擦除当前无效的蛇尾，并且清除（无效）蛇尾的棋盘数据！*/
tailDirection=Board[tail.x][tail.y][1];
PutCell(&tail,BkGndColor);
/*NOTICE: it NOT need clear the direction in Board[x][y][1].~*/
Board[tail.x][tail.y][0]=0;/*蛇身表示清空*/
Board[tail.x][tail.y][1]=0;/*方向也清空了，可能这个并不是很必要。*/
/*仅更新蛇尾的位置！，无需绘制蛇尾也无需填充蛇尾棋盘数据！，因为蛇尾刚才已经有了！*/
NextCell(&tail,tailDirection);
}
/*填充蛇头的棋盘数据*/
Board[head.x][head.y][0]=1;/*该位置成为蛇身*/
Board[head.x][head.y][1]=Direction;/*保存当前的方向*/
headDirection=Direction;
/* 根据当前方向移动蛇身！注意：一定要先记录方向，再移动蛇头，否则蛇尾无法重复蛇头的运动轨迹！ */
NextCell(&head,Direction);/*更新蛇头位置并绘制它*/
if(!IsAvailable(&head))
goto GAMEOVER;
PutCell(&head,SnakeColor);
}
delay(100);
}
/* judge by this value to Avoid fast press keys make it die! */
switch(key)
{
case K_LEFT:
if(headDirection!=dr_right) /*如果用户试图转180时忽略！*/
Direction=dr_left;
break;
case K_UP:
if(headDirection!=dr_down)
Direction=dr_up;
break;
case K_RIGHT:
if(headDirection!=dr_left)
Direction=dr_right;
break;
case K_DOWN:
if(headDirection!=dr_up)
Direction=dr_down;
break;
case K_P:
PauseGame();
break;
}
}
GAMEOVER:
/* Draw the info at the center of Board. */
DrawGameOver();
}
/*暂停游戏*/
int PauseGame()
{
int key=0;
sprintf(TextCache,"Press P to Resume!");
DisplayInfo(TextCache);
while(key!=K_P && key!=K_ESC)
{
while(!(key=GetKeyCode())){}
}
sprintf(TextCache,"SNAKE GAME.--by hoodlum1980");
DisplayInfo(TextCache);
return key;
}
/*绘制Game Over字符串！*/
void DrawGameOver()
{
/*计算棋盘的中心点*/
int cx=BoardLeft+CellSize*BoardWidth/2;
int cy=BoardTop+CellSize*BoardHeight/2;
struct textsettingstype textInfos;
/*获取此前的文字信息*/
gettextsettings(&textInfos);
setcolor(DARKGRAY);
setfillstyle(SOLID_FILL,RED);
/* 连续画两个矩形，红色背景，文字居中 */
rectangle(cx-62,cy-22,cx+62,cy+22);
floodfill(cx,cy,DARKGRAY);
rectangle(cx-60,cy-20,cx+60,cy+20);
settextjustify(CENTER_TEXT,CENTER_TEXT);
setcolor(WHITE);
outtextxy(cx,cy,"GAME OVER!");
/*restore orignal text settings */
settextjustify(textInfos.horiz, textInfos.vert);
}
/*退出游戏，关闭图形模式*/
void QuitGame()
{
closegraph();
}
void main()
{
InitGame();
PlayGame();
getch();
QuitGame();
}
源代码和可执行文件：
[[it] 本帖最后由 hoodlum1980 于 2008-3-26 17:22 编辑 [/it]]
snake_hoodlum1980.rar
