java 贪吃蛇算法分析和代码

贪吃蛇是一款非常经典的手机游戏。它有很多算法，这里详细分析一种比较优秀的算法。首先介绍下主要用到的七个类：WormMain：最主要的类，控制所有其它类的运行和销毁。WormPit：处理键盘输入事件并实例化Worm类和WormFood类的。Worm：抽象了贪吃蛇的属性和动作WormFood：抽象了食物的属性和动作WormScore：用来纪录分数的类WormLink：抽象了蛇身上的一段，保存了这段的坐标、方向和所有状态。WormException：处理异常类基本概念介绍节：一条蛇可以看成有许多正方形的“小格子”拼凑成，我把它称作节。节是蛇身上最小的单位。段：当许多节连成一条直线，我称它为段。上图的贪吃蛇只有一段，如果它拐弯就变成两段。链表：用来保存每一段的状态，链表的元素单位是段。且链表的最后一个元素表示蛇的头部段。坐标系：MIDP中的坐标以左上角那点为(0,0)，向右则x递增，向下则y递增。Worm类一条完整的贪吃蛇是由一段一段组成的。链表中保存的第一个元素是蛇的尾巴段，最后一个元素是蛇的头部段。当蛇运动的时候，它头部段增加一节而尾段减少一节。如果它吃到了食物，尾部段就不减少一节。也就是说，蛇是从头部段开始长的。下面的代码段显示了Worm类保存的各种属性：/*贪吃蛇可能移动的方向*/publicfinalstaticbyteDOWN=2;publicfinalstaticbyteLEFT=4;publicfinalstaticbyteRIGHT=6;publicfinalstaticbyteUP=8;//贪吃蛇的当前方向privatebytecurrentDirection;//保存贪吃蛇每一段的列表privateVectorworm=newVector(5,2);//是否需要更新状态privatebooleanneedUpdate;//是否在运动中privatebooleanmoveOnNextUpdate;//是否吃到食物privatebooleanhasEaten;//贪吃蛇的初始位置、长度和方向privatefinalstaticintINIT_X=3;privatefinalstaticintINIT_Y=8;privatefinalstaticintINIT_LEN=8;privatefinalstaticbyteINIT_DIR=RIGHT;下面重点介绍下Worm类中的几个方法：publicvoidsetDirection(bytedirection)这个方法用来改变贪吃蛇运动的方向，只能90度。看下面的实现代码：if((direction!=currentDirection)&&!needUpdate){//取出列表中的最后一个元素(蛇的头部)WormLinksl=(WormLink)worm.lastElement();intx=sl.getEndX();inty=sl.getEndY();//不同的运动方向坐标的改变也不一样switch(direction){caseUP://当这段向上运动的时候if(currentDirection!=DOWN){y--;needUpdate=true;}break;caseDOWN://当这段向下运动的时候if(currentDirection!=UP){y++;needUpdate=true;}break;caseLEFT://当这段向左运动的时候if(currentDirection!=RIGHT){x--;needUpdate=true;}break;caseRIGHT://当这段向右运动的时候if(currentDirection!=LEFT){x++;needUpdate=true;}break;}//当更改方向后需要更新if(needUpdate==true){worm.addElement(newWormLink(x,y,0,direction));currentDirection=direction;}}publicvoidupdate(Graphicsg)这个函数是更新贪吃蛇状态。每次更新都把头部增加一节，尾部减少一节。如果它吃到食物尾部段就不减少一节。看起来就像整只蛇长了一节。//把贪吃蛇头部增加一格head=(WormLink)worm.lastElement();head.increaseLength();//如果没有吃到食物则尾部减少一格if(!hasEaten){WormLinktail;tail=(WormLink)worm.firstElement();inttailX=tail.getX();inttailY=tail.getY();//如果尾部块长度为0就删除tail.decreaseLength();if(tail.getLength()==0){worm.removeElement(tail);}//尾部减少一格g.setColor(WormPit.ERASE_COLOUR);drawLink(g,tailX,tailY,tailX,tailY,1);}else{//如果吃到食物就不删除尾部hasEaten=false;}needUpdate=false;//确认是否在边界中if(!WormPit.isInBounds(head.getEndX(),head.getEndY())){//如果不在，就死了thrownewWormException(overtheedge);}headX=(byte)head.getEndX();headY=(byte)head.getEndY();//贪吃蛇的头部增加一格g.setColor(WormPit.DRAW_COLOUR);drawLink(g,headX,headY,headX,headY,1);//判断是否吃到自己for(inti=0;iworm.size()-1;i++){sl=(WormLink)worm.elementAt(i);if(sl.contains(headX,headY)){thrownewWormException(youateyourself);}}voiddrawLink(Graphicsg,intx1,inty1,intx2,inty2,intlen)这个函数用来画蛇的一段，一只完整的蛇是一段一段组成的。//把长度转换成像素长度len*=WormPit.CELL_SIZE;//(x1==x2)说明这一段是垂直的if(x1==x2){//把x1转成像素长度x1*=WormPit.CELL_SIZE;//(y2y1)说明是向上运动if(y2y1){//就把头、尾左边交换并转成像素y1=y2*WormPit.CELL_SIZE;}else{//把y1转成像素y1*=WormPit.CELL_SIZE;}g.fillRect(x1,y1,WormPit.CELL_SIZE,len);}else{//这是水平的一段y1*=WormPit.CELL_SIZE;if(x2x1){//就把头、尾左边交换并转成像素x1=x2*WormPit.CELL_SIZE;}else{x1*=WormPit.CELL_SIZE;}g.fillRect(x1,y1,len,WormPit.CELL_SIZE);}publicvoidpaint(Graphicsg)画出一只完整的贪吃蛇WormLinksl;intx1,x2,y1,y2;intlen;for(inti=0;iworm.size();i++){//取出每一段，然后画出这一段，连起来就是一只完整的蛇sl=(WormLink)worm.elementAt(i);x1=sl.getX();x2=sl.getEndX();y1=sl.getY();y2=sl.getEndY();len=sl.getLength();drawLink(g,x1,y1,x2,y2,len);}WormLink类贪吃蛇是由一节一节组成的。因为它经常有一些节连成一条直线形成段，所以这是一种相对有效的方法来保存整个蛇。[X,Y]表示段头部的坐标，然后段的头部开始按照方向向后画若干节。(段的头尾和蛇的头尾不是一个概念)下面代码段是WormLink中的段得属性：//段头部坐标privateintx,y;//段长度privateintlen;//移动方向privatebytedir;下面重点介绍几个重要函数：publicvoiddecreaseLength()这是从段的头部减少一格//首先段的总长度减少1len--;switch(dir){//不同的方向左边的改变也不一样caseWorm.LEFT:x--;break;caseWorm.RIGHT:x++;break;caseWorm.UP:y--;break;caseWorm.DOWN:y++;break;}publicvoidpaint(Graphicsg)画出一只完整的贪吃蛇WormLinksl;intx1,x2,y1,y2;intlen;for(inti=0;iworm.size();i++){//取出每一段，然后画出这一段，连起来就是一只完整的蛇sl=(WormLink)worm.elementAt(i);x1=sl.getX();x2=sl.getEndX();y1=sl.getY();y2=sl.getEndY();len=sl.getLength();drawLink(g,x1,y1,x2,y2,len);}WormLink类贪吃蛇是由一节一节组成的。因为它经常有一些节连成一条直线形成段，所以这是一种相对有效的方法来保存整个蛇。[X,Y]表示段头部的坐标，然后段的头部开始按照方向向后画若干节。(段的头尾和蛇的头尾不是一个概念)下面代码段是WormLink中的段得属性：//段头部坐标privateintx,y;//段长度privateintlen;//移动方向privatebytedir;下面重点介绍几个重要函数：publicvoiddecreaseLength()这是从段的头部减少一格//首先段的总长度减少1len--;switch(dir){//不同的方向左边的改变也不一样caseWorm.LEFT:x--;break;caseWorm.RIGHT:x++;break;caseWorm.UP:y--;break;caseWorm.DOWN:y++;break;}publicbooleancontains(intx,inty)判断所给的坐标[x,y]是否包含在段中switch(dir){//不同的方向判断的方法也不一样caseWorm.LEFT:return((y==this.y)&&((x=this.x)&&(x=getEndX())));caseWorm.RIGHT:return((y==this.y)&&((x=this.x)&&(x=getEndX())));caseWorm.UP:return((x==this.x)&&((y=this.y)&&(y=getEndY())));caseWorm.DOWN:return((x==this.x)&&((y=this.y)&&(y=getEndY())));}publicintgetEndX()得到这一段的尾部x坐标(段方向指向的最后一格的坐标)，当这段是蛇的头部段时，得到的是头部最前面的坐标。//不同的方向判断方法不一样if(dir==Worm.LEFT)returnx-len;if(dir==Worm.RIGHT)returnx+len;returnx;WormPit类WormPit类中包括了Worm和WormFood。贪吃蛇将会在画面中移动寻找食物。如果它吃到食物它将会长一格。如果它碰到边界或者吃到自己将GameOver。下面介绍几个重要的函数：privateintround(intval)求可以被格子宽度(CELL_SIZE)整除的最接近的像素数。intdelta=(