贪吃蛇算法

贪吃蛇算法 贪吃蛇的算法 贪吃蛇是一款非常经典的手机游戏。它有很多算法，这里详细分析一种比较优秀的算法。 首先介绍下主要用到的七个类: l WormMain:最主要的类，控制所有其它类的运行和销毁。 l WormPit:处理键盘输入事件并实例化Worm类和WormFood类的。 l Worm:抽象了贪吃蛇的属性和动作 l WormFood:抽象了食物的属性和动作 l WormScore:用来纪录分数的类 l WormLink:抽象了蛇身上的一段，保存了这段的坐标、方向和所有状态。 l WormException:处理异常类 基本概念介绍 节:一条蛇可以看成有许多正方形的“小格子”拼凑成，我把它称作节。节是蛇身上最小的单位。 段:当许多节连成一条直线，我称它为段。上图的贪吃蛇只有一段，如果它拐弯就变成两段。 链表:用来保存每一段的状态，链表的元素单位是段。且链表的最后一个元素表示蛇的头部段。 坐标系:MIDP中的坐标以左上角那点为(0,0)，向右则x递增，向下则y递增。 Worm类 一条完整的贪吃蛇是由一段一段组成的。链表中保存的第一个元素是蛇的尾巴段，最后一个元素是蛇的头部段。当蛇运动的时候，它头部段增加一节而尾段减少一节。如果它吃到了食物，尾部段就不减少一节。也就是说，蛇是从头部段开始长的。 下面的代码段显示了Worm类保存的各种属性: /* 贪吃蛇可能移动的方向 */ public final static byte DOWN = 2; public final static byte LEFT = 4; public final static byte RIGHT = 6; public final static byte UP = 8; // 贪吃蛇的当前方向 private byte currentDirection; // 保存贪吃蛇每一段的列表 private Vector worm = new Vector(5, 2); // 是否需要更新状态 private boolean needUpdate; // 是否在运动中 private boolean moveOnNextUpdate; // 是否吃到食物 private boolean hasEaten; // 贪吃蛇的初始位置、长度和方向 private final static int INIT_X = 3; private final static int INIT_Y = 8; private final static int INIT_LEN = 8; private final static byte INIT_DIR = RIGHT; #include "snake.h" CSnake::CSnake(int x_pos,int y_pos,int len) { if(len<1) len=1; int i; m_length=len; //蛇的身体体长 //初始化蛇的坐标位置 m_pPos=new SPoint[m_length+2]; m_pPos[0].x=x_pos;m_pPos[0].y=y_pos; for(i=1;i0;i--) { m_newSnake.body[i]=m_newSnake.body[i-1]; } m_newSnake.body[0]=m_newSnake.head; //根据新旧状态特性取正确的状态 m_pStateArray[0]=GetRightState(m_oldSnake.head,m_newSnake.head); for(i=0;i0;i--) m_pPos[i]=m_pPos[i-1]; //蛇头的新位置根据蛇的运动方向判断做相应偏移 switch(m_newSnake.head) { case S_UP: m_pPos[0].y-=SNAKE_MOVE; break; case S_DOWN: m_pPos[0].y+=SNAKE_MOVE; break; case S_LEFT: m_pPos[0].x-=SNAKE_MOVE; break; case S_RIGHT: m_pPos[0].x+=SNAKE_MOVE; break; } } // //蛇的身体增长 // void CSnake::AddBody(int n) { // 分配临时的"save类型"变量，用作保留 // 蛇的各种数据状态 int i; Snake_Struct saveOldSnake,saveNewSnake; BitmapState *savestateArray; SPoint *savePos; //保存蛇的位置信息 // pos savePos=new SPoint[m_length+2]; for(i=0;i